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

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

题目链接：

解题思路：

数据随机生成，当子串大于长度一定值默认认为不相同。

小于这个默认值的，要么扔进set，要么hash

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#define ull unsigned long long
#define ll long longusing namespace std;const int N = 1e5+5;set<ull>cnt;
char s[N];int main()
{ll n,m;while (~scanf("%lld %lld",&n,&m)){scanf("%s",s);//ll ans = (n-m+1)*(n-m+2)/2;ull Hash=0;ll ans_lower_15=0,ans=0;for (int i=m;i<=min(15LL,n);i++){///子串长度cnt.clear();for (int j=0;j<=n-i;j++){///子串起点ull Hash = 0;for (int k=j;k<(j+i);k++)///求出对应子串哈希值Hash = Hash*27+(s[k]-'a'+1);cnt.insert(Hash);}ans_lower_15 += cnt.size();}ans += ans_lower_15;if (n>15 && m<=15) ans += (n-16+1)*(n-16+2)/2;if (n>15 && m>15) ans = (n-m+1)*(n-m+2)/2;printf("%lldn",ans);}return 0;
}

标准AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
set<string>s;
int main()
{ll n, m,count=0;string a;cin >> n >> m >> a;ll sum = (n - m + 1)*(n - m + 2) / 2;for (int i = m; i <= min(n,15LL); i++){for (int j = 0; i + j - 1 < n; j++){string temp = a.substr(j, i);if (s.find(temp) != s.end())count++;elses.insert(temp);}}cout << sum - count << endl;return 0;
}

第二份代码怎么说呢，提交C++11一会儿让过，一会儿不让过。不过尽量别像这份代码里一样用count做变量，毕竟count绿的，提交的编译器也不知道会整出什么幺蛾子。

总的来说，第二份交把人疯了。C++14可以过。

不能白被题目坑，就写几点自己的问题。

①进行int数据进行longlong运算会爆掉，当出现需要得到n*n之类的时候要注意。

②substr可以很方便的取到子串，塞入map，set什么的

③使用min函数比较int和longlong型数据会报错，把int转化为longlong就OK了