一直忙着复习，所以好久好久没写题解了。
暑假集训开始了，开始写题解吧，顺便有自己的一个计划，会在博客中体现的：
cf #240 div2 D
D. Mashmokh and ACM
Mashmokh’s boss, Bimokh, didn’t like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh’s team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn’t able to solve them. That’s why he asked you to help him with these tasks. One of these tasks is the following.
A sequence of l integers b1, b2, …, bl (1 ≤ b1 ≤ b2 ≤ … ≤ bl ≤ n) is called good if each number divides (without a remainder) by the next number in the sequence. More formally for all i (1 ≤ i ≤ l - 1).
Given n and k find the number of good sequences of length k. As the answer can be rather large print it modulo 1000000007 (109 + 7).
Input
The first line of input contains two space-separated integers n, k (1 ≤ n, k ≤ 2000).
Output
Output a single integer — the number of good sequences of length k modulo 1000000007 (109 + 7).
input
3 2
output
5
题意： 就是说输入n,k； 问你在1-n中 长度为k的有效序列有多少个， 有效序列的定义 就是 非递减序列，1<=ai<=n 且ai+1 % ai ==0， 也就是每一个序列中的数都是前一个的整数倍。
分析： 这种题目需要我们慢慢推理： 不能急也不能慌，感觉上是肯定能做的。
首先 这个序列 自然是与n息息相关， 自然和长度k 也有关系。
而且 n 和n-1 的序列必然也是 有关系的， 由此我们细想一会儿不难想到是状态的转移，既然想到这方面必然就得思考怎么创建dp与转移方程。
不妨设 dp[i ][ j ]代表 以i为结尾的 长度为j的最大值； 那么想想若是i,j+1 呢？ 我们可以在原来的长度为j的后面加一个i即可， 说明 dp[i][j+1] >=dp[i][j]。 那么i 的整数倍 也是如此：dp[i*k][j+1]>dp[i][j];
不难得到结果；
int main()
{
//freopen("1.txt","r",stdin);
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++) //所有长度为1，以i结尾的都一种
dp[i][1]=1;
for(int j=1;j<k;j++){
for(int i=1;i<=n;i++){
if(dp[i][j])
for(int len=i;len<=n;len+=i){
//长度为j+1，以 i的倍数 结尾的必然包含长度为j 以i结尾的种数
// 因为在后面加上一个i的倍数 即可
dp[len][j+1]+=dp[i][j],dp[len][j+1]%=MOD;
}
}
}
int ans=0;
for(int i=1;i<=n;i++){ //所有长度为k的，以1-n结尾的
ans+=dp[i][k],ans%=MOD;
}
printf("%d\n",ans);
return 0;
} 一场GYM 试试手而已，最后还是没有AK
2016 Al-Baath University Training Camp Contest-1 I. March Rain
题意：
由一串序列1-n来表示屋顶，在这个屋顶上会给你洞，然后你最多使用k块板子， 每一块板子的长度都可以自由更改，可以不同，然后问板子中 最长的板子 最小值是多少？
最小化最大值，咋一想觉得是贪心，但是最后20+分钟想了一会儿贪心觉得想不出来， 往正解上想到了，但是并没有时间敲and debug了。 其实二分也可以看成一种贪心， 我们只需要二分板子的长度（1-1e9），然后判断在这个长度下，板子够不够用即可
using namespace std;
int pos[1000005];
int p[1000005];
int work(int n,int len){
int cnt=0;
int ans=0;
for(int i=1;i<=n;i++){
if(pos[i]>cnt){
// printf("dong =%d ",pos[i]);
ans++;
cnt=pos[i]+len-1;
// printf("%d %d\n",cnt,pos[i]);
}
}
return ans;
}
int main(){
int t;
//freopen("1.txt","r",stdin);
scanf("%d",&t);
while(t--){
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&pos[i]);
int l=1;
int r=pos[n];
while(l<r){
int mid=(l+r)/2; //现在长度为mid
// printf("%d %d %d\n",l,r,work(n,mid));
if(work(n,mid)> k){ //长度不够，需要>cnt块
l=mid+1;
}
else
r=mid;
}
printf("%d\n",l);
}
return 0;
} J X and Beasts
这个题就是一个最大递增子序列问题，不是最长而是最大，由于n*n可以过，就随便写了写
using namespace std;
int f[1000005];
int x[105],y[105];
void work(){
mem(f);
for(int i=2;i<=1000000;i*=2){
for(int j=1;j*i<=1000000;j++){
f[i*j]++;
}
}
// for(int i=1;i<=100;i++){
// printf("%d %d\n",i,f[i]);
// }
}
int dp[105];
int main(){
//freopen("1.txt","r",stdin);
work();
int t;
scanf("%d",&t);
while(t--){
int n;
int sum=0;
scanf("%d",&n);
int pre=0;
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
//x[i]=f[x[i]];
}
for(int i=1;i<=n;i++){
int maxn=0;
for(int j=i-1;j>=1;j--){
if(x[i]>x[j]){
maxn=max(maxn,dp[j]);
}
}
dp[i]=f[x[i]]+maxn;
}
for(int i=1;i<=n;i++)
sum=max(sum,dp[i]);
printf("%d\n",sum);
}
return 0;
}