经验总结

  1. 首页 > 生活 > >

[题解] Atcoder Regular Contest ARC 151 A B C D E 题解( 二 )

生活百科

  • \(di:0\ 0\ 0\ 0\ 0\ \cdots\)
  • \(si:0\ 1\ 2\ 3\ 4\ \cdots\)
  • \(no:0\ 1\ 0\ 1\ 0\ 1\ \cdots\)
    • 规律很明显了吧 。
    时间复杂度\(O(m)\) 。
    点击查看代码#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <int,int>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;int sa[100010],di[100010],si[100010],no[100010];int dfsdi(int i);int dfssi(int i);int dfssa(int i){if(sa[i]>-1) return sa[i];if(i==0) return sa[i]=0;map <int,int> mp;repn(j,i-2) mp[dfssa(j)^dfssa(i-1-j)]=1;rep(j,i) mp[dfsdi(j)^dfsdi(i-1-j)]=1;rep(j,500) if(mp.find(j)==mp.end()) return sa[i]=j;return sa[i]=0;}int dfsdi(int i){if(di[i]>-1) return di[i];if(i==0) return di[i]=0;map <int,int> mp;rep(j,i-1) mp[dfsdi(j)^dfssa(i-j-1)]=1;rep(j,500) if(mp.find(j)==mp.end()) return di[i]=j;return di[i]=0;}int dfssi(int i){if(si[i]>-1) return si[i];if(i==0) return si[i]=0;map <int,int> mp;rep(j,i){mp[dfssi(j)^dfsdi(i-j-1)]=1;if(i-j-1>0) mp[dfssi(j)^dfssa(i-j-1)]=1;}rep(j,500) if(mp.find(j)==mp.end()) return si[i]=j;return si[i]=0;}int dfsno(int i){if(no[i]>-1) return no[i];if(i==0) return no[i]=0;map <int,int> mp;rep(j,i){mp[dfssi(j)^dfssi(i-j-1)]=1;}rep(j,500) if(mp.find(j)==mp.end()) return no[i]=j;return no[i]=0;}LL n,m,x[200010],y[200010];int main(){fileio();/*rep(i,100005) sa[i]=di[i]=si[i]=no[i]=-1;rep(i,100) dfssa(i),dfsdi(i),dfssi(i),dfsno(i);rep(i,20) cout<<sa[i]<<' ';cout<<endl;rep(i,20) cout<<di[i]<<' ';cout<<endl;rep(i,20) cout<<si[i]<<' ';cout<<endl;rep(i,20) cout<<no[i]<<' ';*/cin>>n>>m;rep(i,m) scanf("%lld%lld",&x[i],&y[i]);if(m==0){puts(n%2==0 ? "Aoki":"Takahashi");termin();}LL ans=0;rep(i,m-1) if(y[i]==y[i+1]) ans^=1;ans^=(x[0]-1);ans^=(n-x[m-1]);puts(ans ? "Takahashi":"Aoki");termin();}
    D - Binary Representations and Queries将输入的数组称为\(a\)，输出的数组称为\(b\) 。显然b是a的一个线性组合，也就是每个\(b_i\)都\(=\sum_{j=0}^{n-1}coef_j\cdot a_j\)，其中coef是系数 。\(a_j\to b_i\)的系数取决于什么呢？其实系数等于输入的q个操作存在多少个子集，满足对j依次进行子集中的操作后，j变成了i 。操作指的是对某一位的翻转，比如输入\(16 \ 0\)就表示如果一个数的第16位是0，就把他变成1 。观察发现，对每一位的操作都是独立的、互不影响的，所以可以先把对第\(n-1\)位的操作都做完，再做第\(n-2,n-3\)位的操作…… 但是注意对于同一位的操作，顺序是不能换的 。这样这题都好做了，我们可以在trie树上从上往下，依次进行每一位的所有操作 。每一层的系数可以统一计算 。
    时间复杂度\(O(nlogn+q)\) 。
    点击查看代码#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;++i)#define repn(i,n) for(int i=1;i<=n;++i)#define LL long long#define pii pair <LL,LL>#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){#ifdef LGSfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endif}void termin(){#ifdef LGSstd::cout<<"\n\nPROGRAM TERMINATED";#endifexit(0);}using namespace std;const LL MOD=998244353;LL n,q,a[1000010];vector <LL> op[20];int main(){fileio();cin>>n>>q;rep(i,1<<n) scanf("%lld",&a[i]);LL x,y;rep(i,q){scanf("%lld%lld",&x,&y);op[x].pb(y);}for(int i=n-1;i>=0;--i){pii vx=mpr(1,0),vy=mpr(0,1);rep(j,op[i].size()){if(op[i][j]==0) (vy.fi+=vx.fi)%=MOD,(vy.se+=vx.se)%=MOD;else (vx.fi+=vy.fi)%=MOD,(vx.se+=vy.se)%=MOD;}int full=1<<(i+1);for(int st=0;st<(1<<n);st+=full){int mid=st+(full>>1);rep(j,full>>1){LL vl=a[st+j],vr=a[mid+j];a[st+j]=(vx.fi*vl+vx.se*vr)%MOD;a[mid+j]=(vy.fi*vl+vy.se*vr)%MOD;}}}rep(i,1<<n) cout<<a[i]<<' ';termin();}

    经验总结扩展阅读


    上一篇：表白总是失败却越挫越勇的星座

    下一篇：值得选的电视有哪些 创维夏普长虹怎么选