期望得分：100+30+100=230
实际得分：100+30+70=200
T3 数组开小了 。。。。。
记录 1的前缀和，0的后缀和
枚举第一个1的出现位置
#include<cstdio> #include<cstring> #include<algorithm> #define N 100002 using namespace std; char s[N]; int num[N]; int suf0[N],pre1[N]; int main() { freopen("reverse.in","r",stdin); freopen("reverse.out","w",stdout); scanf("%s",s+1); int len=strlen(s+1); for(int i=1;i<=len;i++) num[i]=s[i]-'0'; for(int i=1;i<=len;i++) pre1[i]=pre1[i-1]+num[i]; for(int i=len;i;i--) suf0[i]=suf0[i+1]+(!num[i]); int ans=len; for(int i=1;i<=len;i++) ans=min(ans,pre1[i-1]+suf0[i]); ans=min(ans,pre1[len]); printf("%d",ans); }
从1——n枚举一遍
二进制表示它有哪些数出现过了，相当于哈希
然后Σ C（i，2）
#include<cstdio> using namespace std; int f[1026]; void count(int x) { int s=0; while(x) { s|=1<<x%10; x/=10; } f[s]++; } int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); int n; scanf("%d",&n); for(int i=1;i<=n;i++) count(i); long long ans=0; for(int i=1;i<=1023;i++) ans+=1ll*f[i]*(f[i]-1)/2; printf("%I64d",ans); }
考场思路：
种类只有2^9种可能
所以枚举每一种可能
那问题转化为了 有x种数，用它来组成<=n的数的方案数
开始想裸的数位DP，但它不能保证所有的x种数都用上
然后又改的状压DP，dp[i][j] 表示填了i位，使用数的状态为j，
虽然能保证所有的x种数都用上，但数位DP的作用难以体现：
若枚举这一位填哪个数，因为不知道前面填了什么，所以也不能确定这一位填什么
脑补的改进方法是 数位DP加一维表示状态，状压DP加一维表示上一位填了什么
可行性未知
考场错误的状压DP
#include<cstdio> #include<cstring> using namespace std; int tmp[10],num[10]; int use[10],dp[10][1024]; int a[10],b[10]; int main() { int n,len=0; scanf("%d",&n); if(n<10) { printf("0"); return 0; } while(n) { tmp[++len]=n%10; n/=10;} for(int i=len,len=0;i;i--) num[++len]=tmp[i]; int tot,sum,T; long long ans=0; num[0]=10; for(int s=2;s<1023;s++) { if(s==2) { int sad=4; } memset(use,false,sizeof(use)); tot=0; memset(b,0,sizeof(b)); memset(dp,0,sizeof(dp)); for(int i=0;i<10;i++) if(s&(1<<i)) tot++,use[i]=true,b[i]=tot; T=1<<tot; for(int i=1;i<=tot;i++) dp[1][1<<i-1]=1; for(int i=1;i<len;i++) for(int t=T-1;t;t=t&(t-1)) for(int j=0;j<=num[i+1];j++) if(use[j]) dp[i+1][t|1<<b[j]-1]+=dp[i][t]; tot=0; for(int i=1;i<=len;i++) tot+=dp[i][T-1]; ans+=1ll*tot*(tot-1)/2; if(tot) printf("%d %d ",s,tot); } printf("%I64d ",ans); }
考场错误的数位DP
#include<cstdio> #include<cstring> using namespace std; int tmp[10],num[10]; int dp[10][10][10][2]; bool use[10]; int main() { int n,len=0; scanf("%d",&n); if(n<10) { printf("0"); return 0; } while(n) { tmp[++len]=n%10; n/=10;} for(int i=len,len=0;i;i--) num[++len]=i; int S=1<<10; long long tot,ans=0; for(int s=S-1;s;s=s&(s-1)) { memset(use,false,sizeof(use)); memset(dp,0,sizeof(dp)); for(int i=0;i<10;i++) if(s&(1<<i)) use[i]=true; for(int i=1;i<10;i++) dp[1][i][0]=1; for(int i=1;i<len;i++) for(int j=0;j<10;j++) for(int k=0;k<2;k++) if(k) for(int l=0;l<=num[i];l++) dp[i+1][l][1]+=dp[i][j][1]; else for(int l=0;l<10;l++) if(l==num[i]) dp[i+1][l][1]+=dp[i][j][0]; else dp[i+1][l][0]+=dp[i][j][0]; tot=0; for(int i=1;i<=len;i++) for(int j=0;j<10;j++) { tot+=dp[i][j][0]+dp[i][j][1]; printf("%d %d ",dp[i][j][0],dp[i][j][1]); } ans+=tot*(tot+1)/2; } printf("%I64d ",ans); }
30暴力
#include<cstdio> #include<cstring> bool visx[10]; bool visy[10]; using namespace std; int main() { freopen("number.in","r",stdin); freopen("number.out","w",stdout); int n; scanf("%d",&n); int X,Y,sx,sy,ans=0; bool ok; for(int x=1;x<n;x++) { X=x; while(X) { if(!visx[X%10]) visx[X%10]=true; X/=10; } for(int y=x+1;y<=n;y++) { Y=y; while(Y) { if(!visy[Y%10]) visy[Y%10]=true; Y/=10; } ok=true; for(int i=0;i<10 && ok;i++) if(visx[i]!=visy[i]) ok=false; ans+=ok; memset(visy,0,sizeof(visy)); } memset(visx,0,sizeof(visx)); } printf("%d",ans); }
贪心
肯定是上升的时候，越大越好
下降的时候，越小越好
所以有了初步思路：
每次找连续下降的最后一个，然后找连续上升的最后一个，循环往复
看似很正确
但请看下图：
假设k=2，如果按上面的思路，那么后面会选上9
接下来要找连续下降 9后面那个点和8都不满足k=2的差值
所以我们得到的答案=4
但最优解是不要9，选后面的12和8
因为9后面的那个点不能下降，所以到了12仍然是处于上升，所以12比9更优
所以，我们不能找连续的序列，而是
只要现在处于上升阶段，就找最大的
只要现在处于下降阶段，就找最小的
幸亏打了暴力，对拍拍出了这个bug
#include<algorithm> #include<cstdio> #include<iostream> #define N 1000001 using namespace std; int e[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { freopen("wave.in","r",stdin); freopen("wave.out","w",stdout); int n,k; read(n); read(k); for(int i=1;i<=n;i++) read(e[i]); bool up=true; int now,len=1; for(now=1;now<=n && e[now+1]<=e[now];now++); int last=e[now++]; while(now<=n) { if(!up) { while(now<=n) { if(last-e[now]>=k) { last=e[now]; len++; up^=1; break; } else if(e[now]>=last ) last=e[now]; now++; } } else { while(now<=n) { if(e[now]-last>=k) { last=e[now]; len++; up^=1; break; } else if(e[now]<=last) last=e[now]; now++; } } now++; } printf("%d",len); }
对拍代码（n^2）
#include<cstdio> #include<iostream> #include<algorithm> #define N 1000001 using namespace std; int f[N][2],a[N]; void read(int &x) { x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } } int main() { freopen("data.in","r",stdin); freopen("std.out","w",stdout); int n,k; read(n); read(k); for(int i=1;i<=n;++i) read(a[i]); int mx,ans=0; for(int i=1;i<=n;i++) { mx=0; for(int j=i-1;j;j--) if(a[j]-a[i]>=k) mx=max(mx,f[j][1]); f[i][0]=mx+1; ans=max(ans,f[i][0]); mx=0; for(int j=i-1;j;j--) if(a[i]-a[j]>=k) mx=max(mx,f[j][0]); if(mx) { f[i][1]=mx+1; ans=max(ans,f[i][1]); } } printf("%d",ans); }