【GDOI2021PJ Day2T1】杂音密码(noise)
2021/4/17 10:25:50
本文主要是介绍【GDOI2021PJ Day2T1】杂音密码(noise),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【GDOI2021PJ Day2T1】杂音密码(noise)
Description
Input
Output
Sample Input
样例输入1:
7 3
0 2 1 1 7
2 2 7 3 5 0 1
2 1 2
样例输入2:
7 3
0 2 1 1 7
0 1 6 0 1 0 1
1 2 3
Sample Output
8
题解
考场不会KMP的痛
把混合序列和杂音序列一减(注意处理一下模数),就是一道KMP模板题了,直接拿密码序列去匹配即可
But我考场不会KMP+没处理模数痛失80
CODE
#include<cstdio> #include<string> #define max(a,b) (((a)>(b))?(a):(b)) #define min(a,b) (((a)<(b))?(a):(b)) #define R register int #define N 100005 #define ll long long #define mo 256 using namespace std; inline void read(int &x) { x=0;int f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f; } int t,m,mi[N],hun[N<<1],n[N<<1],next[N<<1],a,b,c,d,e,s[N<<1],ans,ans1[N<<1]; int main() { freopen("noise.in","r",stdin); freopen("noise.out","w",stdout); read(t);read(m);read(a);read(b);read(c);read(d);read(e); for (R i=1;i<=t;++i) { if (i==1) n[i]=a; else n[i]=(((n[i-1]<<b)+(n[i-1]>>c))%mo+d)%mo%e; } for (R i=1;i<=t;++i) read(hun[i]); for (R i=1;i<=t;++i) s[i]=(hun[i]-n[i]+mo)%mo; for (R i=1;i<=m;++i) read(mi[i]); for (R i=2,j=0;i<=m;++i) { while (j && mi[j+1]!=mi[i]) j=next[j]; if (mi[j+1]==s[i]) ++j;next[i]=j; } for (R i=1,j=0;i<=t;++i) { while (j && mi[j+1]!=s[i]) j=next[j]; if (mi[j+1]==s[i]) ++j; if (j==m) ans1[++ans]=i-m+1,j=next[j]; } if (!ans) printf("wrong\n"); else { printf("%d\n",ans); for (R i=1;i<=ans;++i) printf("%d ",ans1[i]); printf("\n"); } return 0; }
这篇关于【GDOI2021PJ Day2T1】杂音密码(noise)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!