NOIP 2015模拟赛[nodgd题]题解&总结

第一题一辈子过不了系列

这次考试又学到了许多新东西，受益匪浅

但是成绩依旧不够理想，第一题又炸了，明明好好的一道打表题都打错了，身败名裂

以后还是继续巩固一下这些零零散散的知识，否则考试犯了错找不出来要浪费好多时间

好数
【问题描述】
nodgd认为，如果一个数的三进制表示里数字1的个数和数字2的个数一样多，那就是好数。现在nodgd想知道不小于n的最小的m个好数，你快告诉他。
【输入格式】
输入文件A.in。
第一行包含有一个整数T，表示nodgd提问的次数。
接下来T行，每行两个十进制表示的整数n,m，表示nodgd的一次提问。
【输出格式】
输出文件A.out。
对每次提问输出一行，包含m个由小到大排列的十进制表示的整数，两个数之间用空格隔开（注意，行末也应该有一个空格，不然可能会出现一些莫名其妙的错误），表示nodgd的这次提问的答案。
【样例输入】
4
1 5
100 5
10000 5
1000000 5
【样例输出】
5 7 11 15 19
104 106 116 128 132
10016 10019 10023 10034 10035
1000003 1000009 1000011 1000026 1000031
【样例解释】
第一次提问中，5的三进制表示是12，7的三进制表示是21，11的三进制表示是102，15的三进制表示是120，19的三进制表示是201。
【数据范围】
对于50%的数据，1≤n≤100,m≤10；
对于100%的数据，1≤n≤10^6,m≤100,T≤100

这题看起来很复杂，但是认真分析就会发现，n的范围并不大，并且由于求的数字具有特殊性，所以打表是一个很现实的做法，实际上打表是真的能过的，虽然时间效率相对较低但是比较平均，最后打出来的表也就10w左右

最后注意缩小一下常数，因为打表几乎是卡着时间过的，常数大一点就爆了

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int t,n,m,s[155000],tot,f[20];
int main(){
int i,cnt=0,j;
f[0]=1;
for(i=1;i<=20;i++)f[i]=f[i-1]*3;
for(i=1;i<=1e6+650;i++){
int cnt1=0,cnt2=0,x=i;
int k=ceil(log(x)/log(3));
for(j=k;j>=0&&x;j--){
int cur=f[j];
int temp=x/cur;
if(temp==2)cnt2++;
if(temp==1)cnt1++;
x-=temp*f[j];
}
if(cnt1==cnt2)s[++tot]=i;
}
cin>>t;
while(t--){
scanf("%d%d",&n,&m);
int pos=lower_bound(s+1,s+1+tot,n)-s;
for(i=1;i<=m;i++)printf("%d ",s[pos+i-1]);
putchar(10);
}
}

好文章
【问题描述】
nodgd写了一篇文章，自认为这是一篇好文章。nodgd的文章由n个小写英文字母组成。文章的一个子串指的是文章中的一段连续的字母，子串的长度就是这一段的字母个数。nodgd在文章中用了排比、对偶、前后照应之类的手法，所以就有很多个子串是相同或者相近的。为了向大家证明这是一篇好文章，nodgd决定给自己的文章进行评分。nodgd首先确定了一个整数m，然后统计出文章中有多少个不相同的长度为m的子串，这个数量就是文章的评分。
然而，nodgd懒得老老实实计算这个评分了，就把任务丢给了你。
【输入格式】
输入文件B.in。
第一行包含两个整数n,m，表示文章的长度和需要统计的子串长度。
第二行包含一个长度为n的只包含小写字母的字符串。
【输出格式】
输出文件B.out。
输出一行一个整数，表示文章的评分。
【样例输入1】
5 3
aaaab
【样例输出1】
2
【样例解释1】
长度为3的子串有3个，分别是aaa,aaa,aab，其中不同的只有2个。
【样例输入2】
9 3
abcabacba
【样例输出2】
7
【样例解释2】
共有7个长度为3的子串，每个长度为3的子串都不同。
【数据范围】
对于30%的数据，1≤m≤n≤200；
对于50%的数据，1≤m≤n≤2000；
对于另外20%的数据，1≤m≤50≤n≤200000；
对于100%的数据，1≤m≤n≤200000

这是一道非常有价值的题，不在于题目本身是多么的难，多么的经典，而是其中蕴含的算法的优化和改进是平常做题中没有涉及到的，但却是非常重要的

首先可以想到用set,map加上substr来搞，能过50分

然后我们发现这些东西都是非常费时的，最费时的就是一个一个枚举子串

因此我们想到用字符串hash,既能在O(N)时间内推算出每一个子串的hash值，又能够直接判断答案

但是单纯的字符串hash只能过70分，原因很简单，数据里出现了卡hash的数据

我们知道，选择hash的种子时一般都会选择1e9+7这样的质数，但是问题就在于其自然溢出

如果选择了一个种子为b,我们很容易知道字符串的编号就在[0,b-1]区间中，但是出题人如果比较厉害并且很无聊，就会出数据卡这种种子，因为某些特殊的字符串会使得每一个子串不聚集的概率为%0.06左右

所以我们明白，选择的种子过小了，实际上如果保证正确率在%99以上，需要选择的种子必须大于1e15，但这显然是不现实的

所以这里我们可以选择开两个hash表，然后给同一个字符串附上两个hash值，在判断两个字符串是否相同时，必须两个hash值都相同才行

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e5+5,mod1=1e9+7,mod2=1e9+9;
int n,m;
char s[maxn];
struct Hash{
int p,P,hash1[maxn],hash2[maxn];
void init(int p1,int P1){
p=p1,P=P1;
hash2[0]=1;
for(int i=1;i<=n;i++){
hash1[i]=(1LL*hash1[i-1]*p+(s[i]-'a'+1))%P;//这里和下面的取模都不能乱搞
hash2[i]=1LL*hash2[i-1]*p%P;//只有背代码了……有点难理解
}
}
int getha(int L,int R){
return (hash1[R]-1LL*hash1[L-1]*hash2[R-L+1]%P+P)%P;
}
}Ha,Hb;
struct Charactor{
int h1,h2;
bool operator<(const Charactor& h)const{
return h1==h.h1?h2<h.h2:h1<h.h1;
}
}H[maxn];
int main(){
int i,j,ans=1;
scanf("%d%d",&n,&m);
scanf("%s",s+1);
Ha.init(67,mod1);
Hb.init(89,mod2);
for(i=1;i+m-1<=n;i++){
H[i].h1=Ha.getha(i,i+m-1);
H[i].h2=Hb.getha(i,i+m-1);
}
sort(H+1,H+1+n-m+1);
for(i=2;i+m-1<=n;i++)
ans+=(H[i].h1!=H[i-1].h1||H[i].h2!=H[i-1].h2);
cout<<ans;
}