“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 C CSL 的密码

“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛 C CSL 的密码

题目链接：牛客第三题

来源牛客

唉，前两题签到签的太顺，到这题啥都不想，直接把所有字串扔到set里面，返回set大小.......显然，tle了

据说出题人为了让不会后缀数组和自动机的同学能过，特地改成了除样例意外随机生成字符串

此题整合网上资料，主要有两种解法。

方法一：

源自：

题目说了一句话：

除样例外，所有的测试数据的字符串的每个字符均从小写字母 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;}

本题AC代码：

/*#include <iostream>
#include <cstring>
#include <string>
#include <stack>*/
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
set <string> S;
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int n,m;string str;cin>>n>>m>>str;//srand(time(0))；//随机字符/*for(int i=0;i<n;i++){double t=rand()*100;int item=(int) t;str+=(item%26+'a');}*/int len=str.length();//不去重时的字串总数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);}}//cout<<"ans="<<ans<<endl;}cout<<sum-ans<<endl;
}

方法二：哈希+set

源自：=40462314

源码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{ios::sync_with_stdio(false);int n, m;cin >> n >> m;string s;cin >> s;set <ull> se;ull p = 131;ll ans = 0;for(int len = m; len <= n; len ++){if(len > 10)ans += n - len + 1;else{se.clear();for(int i = 0; s[i]; i ++){if(i + len > s.length())continue;ull z = 0;for(int j = i; j < i + len; j ++)z= z * p + (s[j] - 'a' + 3);//哈希se.insert(z);}ans += se.size();}}cout << ans << endl;
}