#include<cstdio> #include<cstdlib> #include<algorithm> #include<ctime> using namespace std; typedef long long ll; int Case,n,i,j;ll ans,sum,A,B,a[100],x,v[111111],pool[100]; const int N=20; ll cal(){ ll ans=sum; for(int S=0;S<1<<n;S++){ ll A=sum,B=0; for(i=0;i<n;i++)if(S>>i&1)A^=v[i],B^=v[i]; A-=B; if(A<0)A=-A; if(A<ans)ans=A; } return ans; } void print(ll x){ for(int i=11;~i;i--)printf("%lld",x>>i&1); puts(""); } ll myabs(ll x){return x>0?x:-x;} ll solve1(int x){ ll cur=a[x]; for(int i=x-1;~i;i--)if(sum>>i&1){ cur^=a[i]; } return myabs(cur-(sum^cur)); } ll solve2(int x){ ll cur=0; for(int i=x-1;~i;i--){ cur=max(cur,cur^a[i]); } return myabs(cur-(sum^cur)); } int main(){ //srand(time(NULL)); scanf("%d",&Case); while(Case--){ scanf("%d",&n); //n=rand()%10+1; sum=0; for(i=0;i<61;i++)a[i]=0; for(i=0;i<n;i++){ scanf("%lld",&x); //x=rand()%1000; v[i]=x; sum^=x; for(j=60;~j;j--)if(x>>j&1){ if(a[j])x^=a[j]; else {a[j]=x;break;} } } //ll vio=cal(); for(i=0;i<61;i++)for(j=i+1;j<61;j++)if(a[j]>>i&1)a[j]^=a[i]; for(i=60;~i;i--)if(sum>>i&1)break; int lim=i; if(lim>=0){ for(i=0;i<61;i++)pool[i]=a[i]&sum,a[i]=0; for(i=0;i<61;i++){ x=pool[i]; for(j=60;~j;j--)if(x>>j&1){ if(a[j])x^=a[j]; else {a[j]=x;break;} } } for(i=0;i<61;i++)for(j=i+1;j<61;j++)if(a[j]>>i&1)a[j]^=a[i]; ans=min(sum,min(solve1(lim),solve2(lim))); }else{ ans=0; } /*A=sum,B=0;*/ //print(sum); //for(i=60;~i;i--)if(a[i])print(a[i]); /*ans=sum; for(i=60;~i;i--)if((A^a[i])>=(B^a[i])&&(A^a[i])-(B^a[i])<ans){ A^=a[i]; B^=a[i]; ans=A-B; }*/ /*if(ans==vio)puts("OK");else{ printf("vio=%lld ans=%lld\n",vio,ans); printf("%d\n",n); for(i=0;i<n;i++)printf("%lld ",v[i]); puts(""); while(1); }*/ printf("%lld\n",ans); } }
B. Tribute
按题意模拟即可。
#include<bits/stdc++.h> using namespace std; int casenum, casei; typedef unsigned int UI; int n; vector<UI>vt, wt; multiset<UI>sot; multiset<UI>ans; bool solve() { for(int i = 1; i <= n; ++i) { int x = *sot.begin(); ans.insert(x); // printf("x = %d\n", x); // for(auto y : vt)printf("%d ", y); puts(""); wt.clear(); for(auto y : vt) { int z = x + y; // printf("%d\n", z); if(sot.find(z) == sot.end())return 0; sot.erase(sot.find(z)); wt.push_back(z); } for(auto y : wt)vt.push_back(y); } return 1; } int main() { scanf("%d", &casenum); for(casei = 1; casei <= casenum; casei ++) { scanf("%d", &n); int m = (1 << n) - 1; vt.clear(); vt.push_back(0); sot.clear(); ans.clear(); for(int i = 1; i <= m; ++i) { int x; scanf("%d", &x); sot.insert(x); } if(!solve())puts("NO"); else { int id = 0; for(auto it : ans)printf("%d%c", it, ++id == n ? ‘\n‘ : ‘ ‘); } } }
C. Boardroom Meeting
CDQ分治+扫描线树状数组，时间庞大度$O(n\log^2n)$。
#include<cstdio> #include<algorithm> using namespace std; const int N=200010; int Case,n,i,a[N],b[N],c[N],ans,f[N],qa[N],qb[N],bit[N],vis[N],T; inline void up(int&a,int b){a<b?(a=b):0;} inline void ins(int x,int p){for(;x<=n;x+=x&-x)if(vis[x]<T)vis[x]=T,bit[x]=p;else up(bit[x],p);} inline void ask(int x,int&p){for(;x;x-=x&-x)if(vis[x]==T)up(p,bit[x]);} inline bool cmp(int x,int y){return a[x]<a[y];} void solve(int l,int r){ if(l==r){ up(ans,++f[l]); return; } int mid=(l+r)>>1,i,j,ca=0,cb=0; solve(l,mid); for(i=l;i<=mid;i++)qa[++ca]=i; for(;i<=r;i++)qb[++cb]=i; sort(qa+1,qa+ca+1,cmp); sort(qb+1,qb+cb+1,cmp); T++; for(i=j=1;i<=cb;i++){ while(j<=ca&&a[qa[j]]<a[qb[i]]){ ins(b[qa[j]],f[qa[j]]); j++; } ask(b[qb[i]]-1,f[qb[i]]); } solve(mid+1,r); } int main(){ scanf("%d",&Case); while(Case--){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=n;i++)scanf("%d",&b[i]),c[i]=b[i]; sort(c+1,c+n+1); for(i=1;i<=n;i++)b[i]=lower_bound(c+1,c+n+1,b[i])-c; for(i=1;i<=n;i++)f[i]=0; ans=0; solve(1,n); printf("%d\n",ans); } } /* 1 6 1 2 6 3 4 6 4 1 3 5 7 7 */
D. Secret Santa
第二类斯特林数容斥，时间庞大度$O(a\log n)$。
#include<cstdio> const int N=2010,P=1000000007; int n,a,i,j,Case,fac[N],S[N][N]; int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;} int T(int m,int n){ int ans=0; for(int k=0;k<m;k++){ int t=fac[k]; if((k+m)%2)t=(P-t)%P; t=1LL*t*po(k+1,n)%P; t=1LL*t*S[m][k+2]%P; ans=(ans+t)%P; } return ans; } int main(){ for(i=0;i<N;i++)for(j=0;j<N;j++){ if(i>=1&&j==0){S[i][j]=0;continue;} if(i==j){S[i][j]=1;continue;} if(j>=1&&j<i)S[i][j]=(1LL*S[i-1][j]*j+S[i-1][j-1])%P; } for(fac[0]=i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%P; scanf("%d",&Case); while(Case--){ scanf("%d%d",&n,&a);a++;n-=a-2; printf("%d\n",T(a,n)); } }
E. Guessing Game