C
模拟
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define ll long long const int MAXN=100+5; const int inf=1e9+7; int main() { int T; char a[MAXN]; int cas=1; char b[10]="nanodesu"; scanf("%d",&T); while(T--) { scanf("%s",a+1); int len=strlen(a+1); printf("Case #%d: ",cas++); if(len<=3) { for(int i=1;i<=len;i++) printf("%c",a[i]); for(int i=0;i<8;i++) printf("%c",b[i]); printf(" "); continue; } int ok=0; if(a[len]=='u'&&a[len-1]=='s'&&a[len-2]=='e'&&a[len-3]=='d') ok=1; if(!ok) { for(int i=1;i<=len;i++) printf("%c",a[i]); for(int i=0;i<8;i++) printf("%c",b[i]); printf(" "); } else { for(int i=1;i<=len-4;i++) printf("%c",a[i]); for(int i=0;i<8;i++) printf("%c",b[i]); printf(" "); } } return 0; }
D
找规律
#include <iostream> #include<string.h> #include<stdio.h> using namespace std ; #define ll long long char s[20][15]={"","a","ab","aab","aabb","aaaba","aaabab","aaababb","aaababbb","aaaababba","aaaababbaa"}; int main() { int t,ca; scanf("%d",&t); ca=1; while(t--) { int n,m; scanf("%d%d",&n,&m); printf("Case #%d: ",ca++); if(n==1) { for(int i=1;i<=m;i++) printf("a"); printf(" "); } else if(n==2) { if(m<=10) printf("%s ",s[m]); else { printf("aaaa"); m=m-4; int a=m/6; for(int i=1;i<=a;i++) printf("babbaa"); int b=m%6; if(b==1) printf("a"); else if(b==2) printf("aa"); else if(b==3) printf("bab"); else if(b==4) printf("babb"); else if(b==5) printf("babba"); printf(" "); } } else { for(int i=1;i<=m;i++) { if(i%3==1) printf("a"); else if(i%3==2) printf("b"); else printf("c"); } printf(" "); } } return 0; }
J
求有多少段 | 起来<=m
记录二进制 每一位的前缀和
枚举开始位子 二分结束的位子
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 1000010 #define inf 1e9+7 #define ll long long #define MAXN 100010 ll z[MAXN]; int sum[MAXN][33]; int m; bool chick(int a,int b) { //printf("%d %d ",a,b); ll ans=0; for(int i=0;i<32;i++) { int c=sum[a][i]-sum[b-1][i]; if(c>0) ans=ans+(1<<i); } //printf("%lld ",ans); return ans<m; } int main() { int t,ca; scanf("%d",&t); ca=1; while(t--) { int n; scanf("%d%d",&n,&m); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { scanf("%lld",&z[i]); for(int j=0;j<=31;j++) { if(z[i]&(1<<j)) sum[i][j]++; sum[i][j]+=sum[i-1][j]; } } ll ans=0; for(int i=1;i<=n;i++) { int l,r; l=i; r=n; int ans1=i-1; while(l<=r) { int mid=(l+r)>>1; if(chick(mid,i)) { ans1=max(ans1,mid); l=mid+1; } else r=mid-1; } // printf("%d ",ans1); ans=ans+ans1-i+1; } printf("Case #%d: %lld ",ca++,ans); } return 0; }
G数位DP
dp[i][j]第i位<=j有多少个
#include <iostream> #include<string.h> #include<stdio.h> using namespace std ; #define ll long long int dig[12]; int jud; int z[12]; int dp[12][30000]; void calc(int a) //dp[i][j] 第i位 小于j多少个 { int cnt=0; jud=0; while(a) { dig[cnt++]=a%10; a=a/10; jud=jud+dig[cnt-1]*z[cnt-1]; } } int dfs(int len,int sum,int e) { if(len<0) return sum>=0; if(sum<0) return 0; if(!e&&dp[len][sum]!=-1) return dp[len][sum]; int u=e?dig[len]:9; int ans=0; for(int i=0;i<=u;i++) ans+=dfs(len-1,sum-i*z[len],e&&(i==u)); if(!e) dp[len][sum]=ans; return ans; } int calc1(int n) { int cnt=0; while(n) { dig[cnt++]=n%10; n=n/10; } return dfs(cnt-1,jud,1); } int main() { int t,ca; scanf("%d",&t); z[0]=1; for(int i=1;i<=11;i++) z[i]=z[i-1]*2; ca=1; memset(dp,-1,sizeof(dp)); while(t--) { int a,b; scanf("%d%d",&a,&b); calc(a); printf("Case #%d: %d ",ca++,calc1(b)); } return 0; }