“新智认知”杯第十七届上海大学程序设计春季联赛 C

“新智认知”杯第十七届上海大学程序设计春季联赛 C

题目链接：哆啦A梦传送门

题解：参考网上大佬神犇，这题是要数出字符串不小于m的不同总数。我们按正解的话，估计不好搞。

但题目说了一句话：

除样例外，所有的测试数据的字符串的每个字符均从小写字母 a - z 等概率随机生成。

那么我们可以从这句话得到些端倪。每个字符是等概率 (1/26) 出现的，那么我们可以打个随机数10000的表，发现当长度为8时，重复数已经稳定了，也可以这样想(1/26)^8几乎接近于0了。所以我们就直接在长度10以内，算出重复数。

随机数真好玩，又学到有个操作。

这里是随机数出现的表：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;set<string> S;
int main(){int n,m;string str;cin>>n>>m;
//    string ::iterator it=str.begin();///随机字符for(int i=0;i<n;i++){double t=rand()*100;int item=(int) t;str+=(item%26+'a');
//            it++;}int  len=str.size();LL sum=(LL)(n-m+1)*(n-m+2)/2,ans=0;int t=min(n,15);for(int i=m;i<=t;i++){S.clear();for(int j=0;j+i-1<len;j++){string op=str.substr(j,i);if(S.find(op)!&#d()){ans++;
//                cout<<op<<endl;}else S.insert(op);}///表示前i长度出现的重复数有多少printf("ans=%lldn",ans);}printf("%lldn",sum-ans);return 0;}

标程代码：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;set<string> S;
int main(){int n,m;string str;cin>>n>>m>>str;int len=str.size();///总数，等差数列前n项和LL sum=(LL)(n-m+1)*(n-m+2)/2,ans=0;int t=min(n,8);for(int i=m;i<=t;i++){S.clear();for(int j=0;j+i-1<len;j++){string op=str.substr(j,i);if(S.find(op)!&#d()){ans++;}else S.insert(op);}}printf("%lldn",sum-ans);return 0;}/*
2
dz
zz
28 50
29 24
14 25
oz*/