2、总结：4个题，只能做A、B，全都靠hack上分。。
01 HDU 5944 水
1、题意：一个字符串，求有多少组字符y,r,x的下标能组成等比数列。
2、总结：有个坑，y,r,x顺序组公比q>1，也可反着来x,r,y顺序组。
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<map>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=,MAX=; int main()
{
int t,a[N];
char str[N];
scanf("%d",&t);
while(t--){
scanf("%s",str+); //才知道可以这样输
int len=strlen(str+),sum=; //str+1
for(int i=;i<=len;i++) {
if(str[i]=='y') {
for(int j=;i*j*j<=len;j++) {
if(str[i*j]=='r'&&str[i*j*j]=='x') {
sum++;
}
}
}
}
for(int i=;i<=len;i++) {
if(str[i]=='x') { //x,r,y反顺序扫一遍
for(int j=;i*j*j<=len;j++) {
if(str[i*j]=='r'&&str[i*j*j]=='y') {
sum++;
}
}
}
}
cout<<sum<<endl;
} return ;
}
02 HDU 5945 好题，单调队列优化的dp
1、题意：给出x,k,t三个数，目的是将x变到1。有两种操作，1.X=X−i(0<=i<=t). 2.if k|X,X=X/k.
2、总结：还不太懂单调队列，看了一个黄名爷的代码。只是这题本来也好坑，hack之后就没几个过了的。
3、思路：设f[i]表示将i变到1所需的最小步骤。如果k|i , f[i]=min( f[j] , f[i/k] ); 否则f[i]=min( f[j] )，其中i-t<=j<=i-1。这里要快速求出min( f[j] )，用单调队列维护一下即可，时间复杂度为O(n)。
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=; //一开始把这两个数组放main()里面直接就溢出了
int f[N],q[N]; //f[i]表示将i变到1的操作次数q[i]，q[N]存储i-t<=j<=i-1范围的位置，并且单调递增
int main()
{
int T,x,k,t;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&x,&k,&t);
int head=,tail=;
q[++tail]=;
mes(f,INF); f[]=;
for(int i=;i<=x;i++) {
if(i%k==) f[i]=f[i/k]+;
while(i-t>q[head]&&head<=tail) head++; //不符合的弹出
if(head<=tail) f[i]=min(f[i],f[q[head]]+); //f[i]=min( f[j] )
q[++tail]=i; //位置压入队列
while(head<tail&&f[q[tail]]<f[q[tail-]]) q[tail-]=q[tail],tail--; //要使f[q[head]]=min( f[j] )，所以q中不符合单调递增的就去掉; 注意head<tail，如果==就说明q中只存了一个位置，也就没必要进行这一步
}
printf("%d\n",f[x]);
} return ;
}