垃圾选手练dp
考虑对于一个数，能够把它表示出来也一定可以把它某些1的位变成0变成的数表示出来
那么用大的数更新小的，容易想到每次都把这个大的数的1个1的位变成0
但是这样还是会有重复的情况
比如10010被10110和11010更新，但是这两个数都会被11110更新到
那么DP再加一维，f[i][zt]表示zt这个数当前只受到前i位是1的数的更新，对于前i-1位的更新可以直接加上，第i位的更新在当前的for循环里面处理
这样就不会重复了，同时可以发现这个是一个类似背包的东西，所以i的那维也可以省掉了
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } void write(int d) { if(d<0){putchar(‘-‘);d=-d;} if(d>=10)write(d/10); putchar(d%10+‘0‘); } int f[1100000]; int main() { int n,x,mx=0; n=read(); memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) { x=read(),f[x]++; mx=max(mx,x); } for(int i=22;i>=0;i--) for(int zt=1;zt<=mx;zt++) if(zt&(1<<i))f[zt^(1<<i)]+=f[zt]; f[0]=n; for(int i=0;i<=30;i++) { write(f[i]); puts(""); } return 0; }
原文：https://www.cnblogs.com/AKCqhzdy/p/9768476.html