本文共 1863 字，大约阅读时间需要 6 分钟。
题目链接：。
题意是求可以变换位置以后相同的子串有多少个，那么做法是只要每个数字的平方和，立方和以及四次方和都相同就可以了。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 typedef pair PII; 8 const int N = 5e4 + 5; 9 const int M = 1e5 + 5;10 const int DX = 3;11 int n, m;12 LL s[N], pre2[N], pre3[N], pre4[N];13 int vism[M];14 int mp[M];15 LL mm2[M], mm3[M], mm4[M];16 int len[M];17 LL nn[655][N]; 18 int tot;19 int main(){20 scanf("%d", &n);21 for(int i = 1; i <= n; ++ i){22 scanf("%lld", &s[i]);23 pre2[i] = pre2[i-1] + s[i]*s[i];24 pre3[i] = pre3[i-1] + s[i]*s[i]*s[i];25 pre4[i] = pre4[i-1] + s[i]*s[i]*s[i]*s[i];26 }27 scanf("%d", &m);28 LL t;29 for(int i = 1; i <= m; ++ i){30 scanf("%d", &len[i]);31 vism[len[i]] = 1;32 for(int j = 0; j < len[i]; ++ j){33 scanf("%lld", &t);34 mm2[i] += t*t;35 mm3[i] += t*t*t;36 mm4[i] += t*t*t*t;37 }38 }39 for(int i = 1; i < M; ++ i){40 if(vism[i]){41 for(int j = i; j <= n; ++ j){42 nn[tot][j-i] = (((pre4[j] - pre4[j-i]) << DX) << DX) + ((pre3[j] - pre3[j-i]) << DX) + (pre2[j] - pre2[j-i]);43 }44 sort(nn[tot], nn[tot] + n-i+1);45 mp[i] = tot ++;46 }47 }48 LL tmp, p;49 for(int i = 1; i <= m; ++ i){50 tmp = ((mm4[i] << DX) << DX) + (mm3[i] << DX) + mm2[i];51 p = mp[len[i]];52 printf("%d\n", upper_bound(nn[p], nn[p]+n-len[i]+1, tmp) - lower_bound(nn[p], nn[p]+n-len[i]+1, tmp));53 }54 }
需要注意的是，所有串的长度不超过2e5，那么tot的个数不会太多，因为不同长度种类的个数从1开始，那么到不了几百，他们的累和就会超过2e5，因此，以上算法在时间和空间上都能够承受。同时需要注意的是，仓鼠说这题卡map，因此用sort过。
转载于:https://www.cnblogs.com/zzyDS/p/6941897.html