NOIP2017提高组 模拟赛15（总结）
第一题 讨厌整除的小明
【题目描述】
小明作为一个数学迷，总会出于数字的一些性质喜欢上某个数字，然而当他喜欢数字k的时候，却十分讨厌那些能够整除k而比k小的数，认为那些数会分解数字k从而破坏掉k的美感……
有一天，他想：如果所有人都和自己一样，那么是不是喜欢两个含有倍数关系的不同数字的人就不能做朋友了？于是他想，至少用多少个集合，才能包括1到n的所有n个整数，使得所有存在倍数关系的两个不同数字在不同的集合里面？
小明脑子不好使，于是把问题交给了你。
【输入格式】
第一行一个数字q，表示询问次数
接下来q行，每一行一个数字n，表示问题中的n。
【输出格式】
共q行，每行一个数字，表示数字n对应的问题的答案。
【输出样例】
2
7
10
【输出样例】
3
4
【解题思路】
其实就是求\(2^T≤n\)中最大的T值，答案即为T+1。
为什么？
列个次方表：
|次方|0|1|2|3|4|5|
|-|-|-|-|-|-|
|2|1|2|4|8|16|32|
|3|1|3|9|27|81|243|
|5|1|5|25|125|625|3125|
如此图排列，那么质数\(pi^k\)已经处理好，那合数呢？
设合数\(X=p1^{k1}*p2^{k2}*p3^{k3}*……*pn^{kn}\)
X可以放在第（k1+k2+k3+……+kn）列里，则一定不会有倍数关系。
因为自然数X分解成质因数只会有一种方案。
假设Y=KX（K>1），且X,Y在同一列。
那么∑p(Y)=∑p(K)+∑p(X)，K>1所以∑p(K)>0。
所以X,Y不可能在同一列。
又可以知道∑q≤T。（最大的次方数不超过T）
求出T即可。时间复杂度O(q log n)
【代码】
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int T;
ll n;
int main()
{
freopen("2057.in","r",stdin);
freopen("2057.out","w",stdout);
scanf("%d",&T);
while(T--)
{
scanf("%lld",&n); int s=0;
while(n) { n>>=1; s++; }
printf("%d\n",s);
}
return 0;
}
第二题 山高 （原题 bzoj3193 地形生成）
【题目描述】
有n座山，每座山有一个高度和关键数字。
现将这n座山排成一排，要求对于每座山排在其前面且比它高的山的数量小于它的关键数字。
询问不同的标号序列和等高线序列的数量是多少。
标号序列就是按顺序写下每座山的标号，等高线序列就是按顺序写下它们的高度。
【输入格式】
第一行一个整数n。
接下来n行每行两个整数表示每座山的高度和关键数字。
【输出格式】
两个整数表示不同的标号序列的数量和不同的等高线序列的数量。
答案对2011取模。
【输出样例】
2
2 2
2 2
【输出样例】
2 1
【数据规模】
1 <= n <= 1000，所有数字不大于 1000000000,
对于30%的数据, 1 <= n <= 100
【解题思路】
假如没有相同高度的山就好做了……
题目的si是小于，si--，化成小于等于。
先从大到小排序，高度hi相等的关键字si小的在前。
先把同一高度的提取出来。
对于一段高度相同的山，第1个为i，最后一个为t。
先考虑第一个答案：
那么第j（i≤j≤t）座山可选取的范围就是min(i,sj+1)+j-i，所有的山的范围乘起来就是答案。
1 2 3 4 5…i…j…t，j可以放在i之前的山（它们都高过j）的后面，一共有i种（第0座山到第i-1座山的后面，还要和sj+1取min），还可以放在相等的山的后面，也就是j-i。所以山j的范围是min(i,sj+1)+j-i。
考虑第二个答案：
因为相同的山即使标号不同也只记做一种方案。
所以，相同的山一定是从前往后放的。也就是相同的山i,i+1，i一定放在i+1之前。
列出dp方程：dp[i][j]表示第i个相同的山，放在第j个山（之前的山，不与当前山等高）的后面的方案数。
\(dp[i][j]=\sum_{k=0}^{j}dp[i-1][k]\)
j是有序的，也就是si。
可以用前缀和优化，dp[i][j]=dp[i][j-1]+dp[i-1][j];
f[j]=dp[1~i][j]，表示当前山放在第j座山后面的方案数。
f[j]=f[j]+f[j-1];
【代码】
#include<cstdio>
#include<algorithm>
#define imin(a,b) ((a<b)?(a):(b))
using namespace std;
typedef long long ll;
const int N=1200;
const int mods=2011;
int n,ans1,ans2,f[N];
struct data { int h,s; } d[N];
bool cmp(data A,data B) { return (A.h>B.h || (A.h==B.h && A.s<B.s)); }
int main()
{
freopen("2239.in","r",stdin);
freopen("2239.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&d[i].h,&d[i].s),d[i].s--;
sort(d+1,d+1+n,cmp); ans1=ans2=1;
for(int i=1;i<=n;)
{
int t=i,mk;
while(d[t+1].h==d[t].h && t<n) t++;
for(int j=1;j<=n;j++) f[j]=0;
f[0]=1;
for(int j=i;j<=t;j++)
{
ans1=ans1*((imin(i,d[j].s+1)+j-i)%mods)%mods;
mk=imin(i-1,d[j].s);
for(int k=1;k<=mk;k++) f[k]=(f[k]+f[k-1])%mods;
}
int tmp=0; mk=imin(i-1,d[t].s);
for(int j=0;j<=mk;j++) tmp=(tmp+f[j])%mods;
ans2=ans2*tmp%mods;
i=t+1;
}
printf("%d %d\n",ans1,ans2);
return 0;
}
第三题 ABA字符串 （原题 bzoj3620 似乎在梦中见过的样子）
【题目描述】
给出一个长度为n的字符串（均为小写字母），以及一个整数k。
问该字符串的所有子串中，能被切分为A+B+A的形式且 len(A) >= k, len(B) >= 1 的子串数量有多少。
【输入格式】
第一行一个字符串
第二行一个整数k
【输出格式】
一个整数表示答案。
【输出样例】
abcabcabc
2
【输出样例】
8
【解题思路】
暴力O(n²)的KMP，没什么好说的……（其实是懒得写了）
【代码】
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=10010;
char sd[N],*st;
int n,m,ans;
int ne[N],mi[N];
int main()
{
freopen("2240.in","r",stdin);
freopen("2240.out","w",stdout);
scanf("%s",sd);
scanf("%d",&m);
n=strlen(sd); st=sd;
int nt=n;
for(int w=1;w<nt;w++)
{
ne[0]=ne[1]=mi[0]=mi[1]=0; int k=0;
for(int i=2;i<=n;i++)
{
while(k>0 && st[i-1]!=st[k]) k=ne[k];
if(st[i-1]==st[k]) k++;
ne[i]=k; mi[i]=k;
if(mi[ne[i]]>=m) mi[i]=mi[ne[i]];
if(mi[i]>=m && (mi[i]<<1)<i) ans++;
}
st=st+1; n--;
}
printf("%d\n",ans);
return 0;
}