题面：https://www.cnblogs.com/Juve/articles/11487699.html
队长快跑：
权值线段树与dp
yy的不错
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1e5+5;
int n,a[MAXN],b[MAXN],ans=0,lsh[MAXN<<1],cnt,tot=0;
struct node{
int l,r,laz,mx;
}tr[MAXN<<4];
void build(int k,int l,int r){
tr[k].l=l,tr[k].r=r;
if(l==r){
tr[k].mx=0;
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void down(int k){
tr[k<<1].laz+=tr[k].laz;
tr[k<<1|1].laz+=tr[k].laz;
tr[k<<1].mx+=tr[k].laz;
tr[k<<1|1].mx+=tr[k].laz;
tr[k].laz=0;
}
void pushup(int k){
tr[k].mx=max(tr[k<<1].mx,tr[k<<1|1].mx);
}
int query_max(int k,int opl,int opr){
int l=tr[k].l,r=tr[k].r;
if(opl<=l&&r<=opr) return tr[k].mx;
if(tr[k].laz) down(k);
int mid=(l+r)>>1,res=0;
if(opl<=mid) res=max(res,query_max(k<<1,opl,opr));
if(opr>mid) res=max(res,query_max(k<<1|1,opl,opr));
return res;
}
void update(int k,int opt,int val){
int l=tr[k].l,r=tr[k].r;
if(l==r){
tr[k].mx=max(tr[k].mx,val);
return ;
}
if(tr[k].laz) down(k);
int mid=(l+r)>>1;
if(opt<=mid) update(k<<1,opt,val);
else update(k<<1|1,opt,val);
pushup(k);
}
void change(int k,int opl,int opr){
int l=tr[k].l,r=tr[k].r;
if(opl<=l&&r<=opr){
++tr[k].mx;
++tr[k].laz;
return ;
}
if(tr[k].laz) down(k);
int mid=(l+r)>>1;
if(opl<=mid) change(k<<1,opl,opr);
if(opr>mid) change(k<<1|1,opl,opr);
pushup(k);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&a[i],&b[i]);
lsh[++tot]=a[i],lsh[++tot]=b[i];
}
sort(lsh+1,lsh+tot+1);
cnt=unique(lsh+1,lsh+tot+1)-lsh;
for(int i=1;i<=n;++i){
a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;
b[i]=lower_bound(lsh+1,lsh+cnt+1,b[i])-lsh;
}
build(1,1,cnt);
for(int i=n;i>=1;--i){
if(a[i]>b[i]){
int p=query_max(1,1,b[i]-1)+1;
update(1,b[i],p);
change(1,b[i]+1,a[i]);
}else{
int p=query_max(1,1,a[i]-1)+1;
update(1,b[i]+1,p);
}
}
printf("%d
",tr[1].mx);
return 0;
}
影魔：
主席树，每个深度建树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e5+5;
int n,m,c[MAXN],fa[MAXN],ans,tot=0;
int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0;
void add(int u,int v){
++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt;
}
int root1[MAXN],root2[MAXN];
struct node{
int ls,rs,val;
}tr[MAXN<<7];
void build(int &k,int l,int r,int pos,int val){
k=++tot;
if(l==r){
tr[k].val=val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) build(tr[k].ls,l,mid,pos,val);
else build(tr[k].rs,mid+1,r,pos,val);
}
void update(int &k,int l,int r,int pos,int val){
++tot;
tr[tot]=tr[k];
k=tot;
tr[k].val+=val;
if(l==r) return ;
int mid=(l+r)>>1;
if(pos<=mid) update(tr[k].ls,l,mid,pos,val);
else update(tr[k].rs,mid+1,r,pos,val);
}
int merge1(int x,int y,int l,int r,int p){
if(!x||!y) return x+y;
int k=++tot;
if(l==r){
tr[k].val=min(tr[x].val,tr[y].val);
update(root2[p],1,n,max(tr[x].val,tr[y].val),-1);
return k;
}
int mid=(l+r)>>1;
tr[k].ls=merge1(tr[x].ls,tr[y].ls,l,mid,p);
tr[k].rs=merge1(tr[x].rs,tr[y].rs,mid+1,r,p);
return k;
}
int merge2(int x,int y,int l,int r){
if(!x||!y) return x+y;
int k=++tot;
tr[k].val=tr[x].val+tr[y].val;
int mid=(l+r)>>1;
tr[k].ls=merge2(tr[x].ls,tr[y].ls,l,mid);
tr[k].rs=merge2(tr[x].rs,tr[y].rs,mid+1,r);
return k;
}
int query(int k,int l,int r,int opl,int opr){
if(opl<=l&&r<=opr) return tr[k].val;
int res=0,mid=(l+r)>>1;
if(opl<=mid) res+=query(tr[k].ls,l,mid,opl,opr);
if(opr>mid) res+=query(tr[k].rs,mid+1,r,opl,opr);
return res;
}
int deep[MAXN];
void dfs(int x,int fa){
build(root1[x],1,n,c[x],deep[x]);
update(root2[x],1,n,deep[x],1);
for(int i=pre[x];i;i=nxt[i]){
int y=to[i];
if(y==fa) continue;
deep[y]=deep[x]+1;
dfs(y,x);
root1[x]=merge1(root1[x],root1[y],1,n,x);
root2[x]=merge2(root2[x],root2[y],1,n);
}
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
}
for(int i=2;i<=n;++i){
scanf("%d",&fa[i]);
add(fa[i],i);
}
deep[1]=1;
dfs(1,0);
for(int i=1,k,dis;i<=m;++i){
scanf("%d%d",&k,&dis);
ans=query(root2[k],1,n,deep[k],deep[k]+dis);
printf("%d
",ans);
}
return 0;
}
抛硬币：
乱搞dp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=3005;
const int mod=998244353;
int l,len,f[MAXN][MAXN],s[MAXN];
char ch[MAXN];
signed main(){
scanf("%s",ch+1);
scanf("%d",&l);
len=strlen(ch+1);
//cout<<len<<endl;
for(int i=1;i<=len;++i){
f[i][0]=1;
for(int j=i-1;j>=1;--j){
if(ch[j]==ch[i]){
s[i]=j;
break;
}
}
}
//for(int i=1;i<=len;++i) cout<<s[i]<<endl;
f[0][0]=1;
for(int i=1;i<=len;++i){
for(int j=1;j<=l;++j){
if(s[i]!=0) f[i][j]=((f[i-1][j]+f[i-1][j-1]-f[s[i]-1][j-1])%mod+mod)%mod;
else f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
}
}
printf("%d
",f[len][l]);
return 0;
}