过了这么久才来写……
BC的后两道题好难……（第二道题也不怎么简单……）
1001 Fxx and string
正着倒着枚举一次就ok
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 10005
char a[N];
int main() {
int T,len,ans;
scanf("%d",&T);
while(T--) {
scanf("%s",a+);
len = strlen(a+);
ans = ;
for(int i = ;i <= len;i++){
if(a[i] != 'y') continue;
for(int k = ;true;k++){
if(i*k*k > len) break;
if(a[i*k]=='r' && a[i*k*k]=='x') ans++;
}
}
for(int i = ;i <= len;i++){
if(a[i] != 'x') continue;
for(int k = ;true;k++){
if(i*k*k > len) break;
if(a[i*k]=='r' && a[i*k*k]=='y') ans++;
}
}
printf("%d\n",ans);
}
return ;
}
这个题更新数据以后，爆搜肯定挂，比如（1000000,1,100000）
所以要用dp，dp[x] = min(dp[x-i],dp[x/k]) ,1<=i<=t，容易想明白，但是暴力转移肯定挂，至于线段树，我帮你们写了，也挂……
所以只能维护单调队列来优化这个dp
维护[x-t,x-1]之间的单调队列，使其从队头到队尾是递增的，然后正常转移，更新单调队列就可以（单调队列在dp里的用处真的很大）
单调队列代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
const int INF = 1e9;
const int N = 1e6+;
int dp[N],n,k,t;
deque<int> dq; ///维护一个从队尾到队头 递减的队列
int main() {
int T,x;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&k,&t);
dp[]=;
while(!dq.empty()) dq.pop_back();
dq.push_back();
for(int i=; i<=n; i++) {
dp[i]=INF;
if(i%k==) dp[i]=min(dp[i],dp[i/k]+);
while(!dq.empty()) {
x=dq.front();
if(x<i-t||x>i-) dq.pop_front();
else break;
}
if(!dq.empty()) dp[i]=min(dp[i],dp[x]+);
while(!dq.empty()) {
x=dq.back();
if(dp[x]>=dp[i]) {
dq.pop_back();
} else break;
}
dq.push_back(i);
}
printf("%d\n",dp[n]);
}
return ;
}
挂了的线段树代码（笑哭）
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6+;
#define lc 2*node
#define rc 2*node+1
#define MAX 1e9
int seg[N*+],dp[N];
void Build(int node,int l,int r){
if(l == r) seg[node] = MAX;
else {
int mid = (l+r)>>;
Build(lc,l,mid);
Build(rc,mid+,r);
seg[node] = min(seg[lc],seg[rc]);
}
}
void Update(int node,int l,int r,int k,int num){
if(l==r) {
seg[node] = num;
return;
}
int mid = (l+r)>>;
if(k <= mid) Update(lc,l,mid,k,num);
else Update(rc,mid+,r,k,num);
seg[node] = min(seg[lc],seg[rc]);
}
int query(int node,int l,int r,int ql,int qr){
int p1,p2;
if(ql > r || qr < l) return MAX;
if(l >= ql && r <= qr) return seg[node];
int mid = (l+r)>>;
p1 = query(lc,l,mid,ql,qr);
p2 = query(rc,mid+,r,ql,qr);
return min(p1,p2);
}
int main()
{
int T,x,k,t;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&x,&k,&t);
Build(,,x);
dp[] = ;
Update(,,x,,dp[]);
for(int i = ;i <= x;i++){
int q = query(,,x,i-t,i-);
dp[i] = q+;
if(i % k == ) dp[i] = min(dp[i],dp[i/k]+);
Update(,,x,i,dp[i]);
}
printf("%d\n",dp[x]);
}
return ;
}