1.角谷猜想
#include<iostream> #include<cstdio> #include<cstring> #define maxn 10010 using namespace std; char ch[maxn],st[maxn]; int t,top; int main(){ //freopen("Cola.txt","r",stdin); freopen("kakutani.in","r",stdin);freopen("kakutani.out","w",stdout); scanf("%d",&t); while(t--){ scanf("%s",ch+1); int len=strlen(ch+1); top=0; for(int i=1;i<=len;i++){ if(top>0&&st[top]=='1'&&ch[i]=='3'){//出现13 top=top-1; } else if(ch[i]!='7'&&ch[i]!='4'){ top=top+1; st[top]=ch[i]; } } if(top==0){ printf("0 "); continue; } for(int i=1;i<=top;i++){ printf("%c",st[i]); } printf(" "); } fclose(stdin);fclose(stdout); return 0; }
2.刀塔（二分答案）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1000010 using namespace std; int x,y,Asd,jk,A,B,k,ans,t,q,n,Max,nm,a[N],f[N][20],Min[N]; void init(){ Min[0]=-1; for(int i=1;i<=n;i++){ Min[i]=((i&(i-1))==0)?Min[i-1]+1:Min[i-1]; f[i][0]=a[i]; } for(int j=1;j<=Min[n];j++) for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } int find(int L,int R){ int k=Min[R-L+1]; return min(f[L][k],f[R-(1<<k)+1][k]); } int main(){ freopen("dota.in","r",stdin);freopen("dota.out","w",stdout); scanf("%d%d%d%d",&n,&A,&B,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); init(); for(int i=1;i<=n-B-k+1;i++){ Max=B-A; for(int j=A;j<=Max;j++){ nm=B-j; Asd=find(i,i+j-1); jk=find(i+j+k,i+j+k+nm-1); ans=max(ans,min(Asd,jk)); } } cout<<ans; }
/* 题目可以简化为选择一段长为B+K的区间，中间去掉k个数，且去掉k个数后两侧的数都多于a 二分答案，对于每个答案，check的方法就是枚举中间区间的位置，枚举两侧区间最大满足答案的长度判断是否满足上面的条件即可 */ #include<cstdio> #include<algorithm> #define maxn 2000010 using namespace std; int x[maxn],l[maxn],r[maxn]; int n,a,b,k,ans; bool check(int c){ for(int i=1;i<=n;i++){ if(x[i]>=c)l[i]=l[i-1]+1; else l[i]=0; } for(int i=n;i>=1;i--){ if(x[i]>=c)r[i]=r[i+1]+1; else r[i]=0; } for(int i=1;i<=n;i++){ if(l[i-1]>=a&&r[i+k]>=a&&l[i-1]+r[i+k]>=b)return 1; } return 0; } int main(){ freopen("dota.in","r",stdin);freopen("dota.out","w",stdout); //freopen("dota10.in","r",stdin); int left,right,mid; scanf("%d%d%d%d",&n,&a,&b,&k); for(int i=1;i<=n;i++){ scanf("%d",&x[i]); if(x[i]>right)right=x[i]; } left=1,right=right+1; while(left<=right){ int mid=(left+right)>>1; if(check(mid))ans=mid,left=mid+1; else right=mid-1; } printf("%d",ans); }
3.反击数（kmp+数位dp）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char p[32]; int m,f[32],a[32]; long long dp[20][2000][2]; long long l,r,k; void KMP(){ f[0]=0;f[1]=0; for(int i=1;i<m;i++){ int j=f[i]; while(j&&p[i]!=p[j])j=f[j]; f[i+1]=p[i]==p[j]?j+1:0; } } long long dfs(int k,int w,bool limit,bool get){ if(!k)return get; else if (!limit&&dp[k][w][get]!=-1)return dp[k][w][get]; else { long long ans=0; for(int i=0,j=limit?a[k]:9;i<=j;i++){ int t=w; while(t&&p[t]-'0'!=i)t=f[t]; if(p[t]-'0'==i)t++; ans+=dfs(k-1,t,limit&&(i==a[k]),get||(t==m)); } return limit?ans:dp[k][w][get]=ans; } } long long query(long long x){ int cnt=0; while(x){ a[++cnt]=x%10; x/=10; } memset(dp,-1,sizeof(dp)); return dfs(cnt,0,1,0); } int main(){ freopen("spenum.in","r",stdin);freopen("spenum.out","w",stdout); //freopen("Cola.txt","r",stdin); cin>>l>>r;scanf("%s",p);cin>>k; m=strlen(p); KMP(); k+=query(l-1); if(query(r-1)<k){ printf("Hey,wake up!"); return 0; } long long tmp=1,ans=l-1; while(tmp<r-l+1)tmp=tmp*2; while(tmp){ if(query(ans+tmp)<k)ans+=tmp; tmp=tmp/2; } cout<<ans+1; return 0; }