个人感受：打了三个小时不到的第一题，然后也就没有多少时间去搞第二题了，特别是第二题还看到了期望这样的东西，这个难以理解，第三题的树分治，myx大佬说50分好拿，但是我觉得也挺难拿的。
单词检索
时间限制: 1 Sec 内存限制: 128 MB
提交: 671 解决:
105
[提交][状态][讨论版]
题目描述
小可可是学校图书馆的管理员，现在他接手了一个十分棘手的任务。
由于学校需要一些材料，校长需要在文章中检索一些信息。校长一共给了小可可N篇文章，每篇文章为一个字符串。现在，校长需要他找到这样的单词，它至少在这N篇文章中的M篇文章里出现过，且单词长度为L。可是，工作量十分庞大，但校长又急需小可可完成这项任务。
现在他向你求助，需要你编写程序完成这项艰巨的任务。
输入
第1行3个正整数N，M，L，表示文章的数目，单词至少出现在M篇文章中和每个单词的长度。
接下来N行，每行一个字符串，表示一篇文章。
输出
仅一行，表示满足检索条件的单词数。
样例输入
3 2 2 noip istudycpp imacppstudent
样例输出
5
对于20%的数据有1≤N,M≤10；
对于100%的数据有1≤N,M≤2000，L≤1000。每篇文章长度不大于1000，均有小写字母组成。
这道题就是一个hash映射，一开始想了trie树和kmp，但是trie树的空间是真的大，指数级别增长还得研究过才行，这里用到了一个
非常重要的结论：一次解决一O（N）的时间求出每段连续子串的hash值，1----j，2----j+1，，3----j+2 ......就是1*k^t%MOD对答案hash的贡献值是确定的，那就直接可以了，在在答案中减去就可以了。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
;
;
long long he;
map<long long,int>flag;
map<long long,int>last;
];
];
int main()
{
scanf("%d%d%d",&n,&m,&l);
he=;
;i<l;i++)
he=(he*)%MOD;
;i<=n;i++)
{
scanf("%s",s);
int len=strlen(s);
;
;j<l-;j++) x=(x*+(s[j]-'a'))%MOD;
;j<len;j++)
{
x=(x*+s[j]-'a')%MOD;
if (!flag[x])
{
a[++a_zhi]=x;
flag[x]++;
last[x]=i;
}
else if (last[x]!=i) flag[x]++,last[x]=i;
x=(x-(s[j-l+]-'a')*he+MOD)%MOD;
}
}
;
;i<=a_zhi;i++)
if (flag[a[i]]>=m) ans++;
printf("%d\n",ans);
}
无聊的游戏
时间限制: 1 Sec 内存限制: 256 MB Special Judge
提交:
213 解决: 42
[提交][状态][讨论版]
题目描述
学校的运动会开始了，体能很菜的小可可没报任何比赛项目，于是和同学们玩一个十分无聊的游戏。
游戏在一个由n*n个方格组成的正方形棋盘上进行，首先在每个方格上均匀随机地填入1到m之间的正整数（每个方格填的数均不同），然后小可可均匀随机地选出k个1到m的数字（可能选的数不在棋盘上），把它们出现在棋盘上的方格涂黑，设有R行被整行涂黑，有C列被整列涂黑，小可可便可以得到2^(R+C)分。
现在小可可想知道他的期望得分是多少，你能帮助他吗？
输入
第一行包含三个正整数n，m，k。
输出
仅一行包含一个实数，为期望得分，如果答案>10^99，就输出10^99，输出被认为正确当且仅当你的输出与标准输出的相对误差不超过10-6。
样例输入
1 2 1
样例输出
2.5
提示
【数据范围】
对于30%的数据，2≤n≤5
对于60%的数据，2≤n≤10，m≤200
对于100% 的数据，2≤n≤300
这道题是非常不错的，我准备再开一篇blog来写这道题，写的是后是0分。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
;
int n,m,k;
double f[N],g[N*N],ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);
]=;i<=n;i++)
f[i]=f[i-]/i*(n-i+);
]=;i<=m;i++)
g[i]=g[i-]/(m-i+)*(k-i+);
;i<=n;i++)
;j<=n;j++)
{
int t=(i+j)*n-i*j;
if(t>k) continue;
ans+=f[i]*f[j]*g[t];
}
ans=ans>1e99?1e99:ans;
printf("%lf",ans);
}