当前位置: 首页 > news >正文

先辈题解

首先我们先观察到 $ 114514 $ 中只有三种数,$ 1 \(,\) 4 \(,\) 5 $,这给了我们一个思路,直接枚举这三个数代表的字母是什么,字母共有 $ 26 $ 种,所以我们的复杂度是 $ O(26^3n) $的。

code:

void dfs(int s1,int s2,int s3){int len1=0,len2=0,len3=0,len4=0,len5=0,len6=0;for(int i=1;i<=n;i++){if(a[i]==s1) len5=(len5+len4)%mod,len2=(len2+len1)%mod,len1=(len1+1)%mod;if(a[i]==s2) len6=(len6+len5)%mod,len3=(len3+len2)%mod;if(a[i]==s3) len4=(len4+len3)%mod;}ans=(ans+len6)%mod;return;
}
for(int i=1;i<=26;i++)
{for(int j=1;j<=26;j++){if(j==i) continue;for(int k=1;k<=26;k++){if(k==j||k==i) continue;dfs(i,j,k);}}
}

注:dfs中要倒着加

这样我们就拿到了 $ 60 $ 分,考虑怎么优化。

我们观察到在dfs中我们转移时只用上了 $ s1,s2,s3 $ ,所以我们可以开个vector来记录每一个字母的出现位置,然后直接跳三个字母的离当前最近的那个。

code:

void dfs(int s1,int s2,int s3){int len1=0,len2=0,len3=0,len4=0,len5=0,len6=0;int id1=0,id2=0,id3=0;for(int i=min({q[s1][id1],q[s2][id2],q[s3][id3]});i<=n;i=min({q[s1][id1],q[s2][id2],q[s3][id3]})){if(a[i]==s1) len5=(len5+len4)%mod,len2=(len2+len1)%mod,len1=(len1+1)%mod,id1++;if(a[i]==s2) len6=(len6+len5)%mod,len3=(len3+len2)%mod,id2++;if(a[i]==s3) len4=(len4+len3)%mod,id3++;}ans=(ans+len6)%mod;return;
}
for(int i=1;i<=n;i++)
{a[i]=s[i]-'a'+1,up=max(up,a[i]);q[a[i]].push_back(i);
}
for(int i=1;i<=26;i++) q[i].push_back(n+1);
for(int i=1;i<=up;i++)
{for(int j=1;j<=up;j++){if(j==i) continue;for(int k=1;k<=up;k++){if(k==j||k==i) continue;dfs(i,j,k);}}
}

这样我们还是 $ 60 $ 分,这个已经没什么好方法优化了,我们接着从 $ 114514 $ 上下手。

观察到 $ 1 $ 出现了 $ 3 $ 次, $ 4 $ 出现了 $ 2 $ 次,而 $ 5 $ 只出现了 $ 1 $ 次。

我们尝试少枚举一个字母,容易发现,我们一定要枚举 $ 1 $ 代表的字符,因为它出现 $ 3 $ 次,若不枚举它不好搞,$ 4 $ 也同理,但是 $ 5 $ 只出现了一次,我们不用考虑它和前边的某个数相同,只要它和另两个不同就行,其他的都没有影响。这样,我们把这个方法优化到了 $ O(26^2n) $,看起来很可过了。

code:

constepxr int mod=114514; 
#define add(x,y) x=(x+y)%mod
void dfs(int s1,int s2){int len1=0,len2=0,len3=0,len4=0,len5=0,len6=0;for(int i=1;i<=n;i++){if(a[i]==s1) add(len5,len4),add(len2,len1),add(len1,1);else if(a[i]==s2) add(len6,len5),add(len3,len2);else add(len4,len3);}add(ans,len6);
}
for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1,up=max(up,a[i]);
for(int i=1;i<=up;i++)
{for(int j=1;j<=up;j++){if(j==i) continue;dfs(i,j);}
}

等我们交上去一看,很不幸T了,为什么呢?因为取模太慢了。只要把

#define add(x,y) x=(x+y)%mod

改成

#define add(x,y) x+=y,x=x>=mod?x-mod:x

就好了。

完整代码 :

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+10,mod=114514;
char s[N];
int a[N],ans,n,up,siz[27];
inline int in(){int k=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9') k=(k<<3)+(k<<1)+c-'0',c=getchar();  return k*f;
}
#define add(x,y) x+=y,x=x>=mod?x-mod:x
void dfs(int s1,int s2){int len1=0,len2=0,len3=0,len4=0,len5=0,len6=0;for(int i=1;i<=n;i++){if(a[i]==s1) add(len5,len4),add(len2,len1),add(len1,1);else if(a[i]==s2) add(len6,len5),add(len3,len2);else add(len4,len3);}add(ans,len6);
}
signed main(){// freopen("ex_anc3.in","r",stdin);freopen("1.out","w",stdout);// freopen("1.in","r",stdin);freopen("1.out","w",stdout);freopen("anc.in","r",stdin);freopen("anc.out","w",stdout);scanf("%s",(s+1));n=strlen(s+1);for(int i=1;i<=n;i++) a[i]=s[i]-'a'+1,up=max(up,a[i]);for(int i=1;i<=up;i++){for(int j=1;j<=up;j++){if(j==i) continue;dfs(i,j);}}printf("%d\n",ans);return 0;
}
///////////////////////////////////////////////////
//                      ♪♪♪                      //
///////////////////////////////////////////////////
//つ ◕_◕ つ
//༼ つ ◕_◕ ༽つ
http://www.hskmm.com/?act=detail&tid=31112

相关文章:

  • U-Boot启动探秘:从汇编到命令行的奇幻之旅 - 指南
  • 双指针的初步了解
  • 倍增并查集学习笔记
  • 两数相加-leetcode
  • CF2147E
  • 线程共享区域
  • ZR 2025 NOIP 二十连测 #1
  • 运行时数据区
  • work1
  • 2025 年液压机厂家推荐榜:伺服/小型/大型/数控/液压机厂家口碑推荐,品质可靠 聚焦智能适配,助力企业高效生产
  • 快速上手!山海鲸 4 种高频数据接入方式
  • AI赋能,重塑未来招聘:深度解析易路AI人岗匹配解决方案
  • 2025高级语言程序设计第一次作业lcr
  • luogu 个人主页
  • D230809E. 勇敢的阿乐
  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭
  • object类
  • Day 10
  • 2025 年生态格宾网厂家推荐榜:格宾网石笼/格宾网护坡/格宾网挡墙/格宾网网箱厂家推荐,聚焦工程安全与生态保护,助力基建项目高效落地
  • 时序博弈算法荣获时间检验奖
  • 背叛 仇恨 消极 如刀子刺穿了铁心 嘲笑 嗤之以鼻 漠然后只剩下孤寂
  • STM32主控芯片硬件设计总结