Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
51581 HSW 最优子序列 C++ 解答错误 0 5 MS 500 KB 2711 2022-07-13 11:53:56

Tests(0/20):


#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int n,m,k,opt,ans1,ans2,cnt; char s[5005]; int a[5005]; int b[5005]; int t[50005]; int tp[55]; int tg[50005]; int lst[20]; int st[50005]; void build(int k,int l,int r) { tg[k]=0; if(l==r) { t[k]=b[l]; return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); t[k]=t[k<<1]+t[k<<1|1]; } void addd(int k,int l,int r) { t[k]=0; tg[k]=1; } void pushdown(int k,int l,int r) { int mid=l+r>>1; if(tg[k]) { addd(k<<1,l,mid); addd(k<<1|1,mid+1,r); tg[k]=0; } } void chg(int k,int l,int r,int x,int y) { if(x<=l&&r<=y) { addd(k,l,r); return; } pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) chg(k<<1,l,mid,x,y); if(y>mid) chg(k<<1|1,mid+1,r,x,y); t[k]=t[k<<1]+t[k<<1|1]; } int qry(int k,int l,int r,int x,int y) { if(x<=l&&r<=y) return t[k]; pushdown(k,l,r); int mid=l+r>>1; int res=0; if(x<=mid) res+=qry(k<<1,l,mid,x,y); if(y>mid) res+=qry(k<<1|1,mid+1,r,x,y); t[k]=t[k<<1]+t[k<<1|1]; return res; } void pls(int k,int l,int r,int x,int y) { if(l==r&&l==x) { t[k]+=y; return; } pushdown(k,l,r); int mid=l+r>>1; if(x<=mid) pls(k<<1,l,mid,x,y); else pls(k<<1|1,mid+1,r,x,y); t[k]=t[k<<1]+t[k<<1|1]; } int ddcx(int k,int l,int r,int x) { if(t[k]==0) return 0; if(l==r&&l==x) return t[k]; int mid=l+r>>1; if(x<=mid) return ddcx(k<<1,l,mid,x); else return ddcx(k<<1|1,mid+1,r,x); } int main() { scanf("%d%d%d",&n,&k,&opt); int i,j,l,r,mk; scanf("%s",s+1); a[1]=int(s[1]-'a'+1); m=1; b[1]=1; for(i=2; i<=n; i++) { if(s[i]==s[i-1]) b[m]++; else a[++m]=int(s[i]-'a'+1),b[m]=1; } l=r=0; for(i=1; i<=k; i++) { j=1; while(a[j]!=i&&j<=m) j++; if(j>m) continue; build(1,1,m); if(j!=1) chg(1,1,m,1,j-1); memset(lst,0,sizeof(lst)); while(j<=m) { l=ddcx(1,1,m,lst[a[j]]); if(!lst[a[j]]||!l) lst[a[j]]=j; else { r=qry(1,1,m,lst[a[j]]+1,j-1); if(r<=b[j]&&r<=l) chg(1,1,m,lst[a[j]]+1,j-1); else if(l<=b[j]&&l<=r) chg(1,1,m,lst[a[j]],lst[a[j]]); else if(b[j]<=l&&b[j]<=r) chg(1,1,m,j,j); } j++; } mk=qry(1,1,m,1,m); if(mk>ans1) { ans1=mk; ans2=i; memset(st,0,sizeof(st)); for(j=1; j<=m; j++) { if(ddcx(1,1,m,j)) st[++cnt]=j; } } } printf("%d\n",ans1); if(opt) { for(i=1; i<=cnt; i++) { for(j=1; j<=b[st[i]]; j++) printf("%c",('a'+a[st[i]]-1)); } } return 0; }


测评信息: