本打算退役,不再搞acm了,果然大脑变sb了很多!一个水题竟然看这么长时间,开始竟然把 或 当做是 与 ,脑残
思路: 每一个数,扫描前面的数,最多把20位更新为1,所以最多更新20位
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <algorithm> using namespace std; set<int> st; const int maxn=100010; int a[maxn],bit[22]; struct BIT { int id,pos; bool operator<(BIT a)const { return pos > a.pos; } }b[22]; int main() { int n; while(scanf("%d",&n)==1) { for(int i=1;i<=n;i++) scanf("%d",&a[i]); st.clear(); memset(bit,-1,sizeof(bit)); for(int i=1;i<=n;i++) { st.insert(a[i]); for(int j=0;j<20;j++) if(a[i]&(1<<j)) bit[j]=i; int cnt=0; for(int j=0;j<20;j++) if(bit[j]!=-1) b[cnt].id=j,b[cnt++].pos=bit[j]; sort(b,b+cnt); int tmp=0,pre=-1; for(int j=0;j<cnt;j++) { tmp|=(1<<b[j].id); if(j+1<cnt&&b[j].pos==b[j+1].pos) continue; st.insert(tmp); } } printf("%d\n",st.size()); } return 0; }