1. 首頁 > 生活百科 > >

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

生活百科

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();}
E - Keep Being Substring如果X中有一些位置，它們一直沒有被刪除，并保留到了Y中 ， 那么這些位置一定形成一個連續段 。有這種位置的情況，操作次數一定比沒有的少，因為沒有這種位置的情況，X中所有元素都要被刪除 ， Y中所有元素都是手動加上的 。
先看能不能在X中有位置不被刪除的情況下完成目標，枚舉X中被保留的子段的開頭位置i，把X和Y放到一起跑后綴數組+算出LCP數組 。我們的目標是找到j ， 滿足X中以i開頭的后綴，與Y中以j開頭的后綴的LCP最長 。通過在LCP數組上two-pointers可以輕松找到這樣的j 。
然后就是X中全被刪光的情況了 。題目要求修改過程中時刻是A的子串，所以我們應該先把X刪得只剩下一個字符，然后"跑"到A中某一個Y出現的地方 ， 因為只有一個字符好跑路，多出來的都是累贅，最后肯定都是要刪掉的，這些多出來的字符可能導致不是A的子串 。用哈希找出Y在A中出現的所有位置，把這些位置的值\(A_i\)標記為目標值，只要我們達到了其中一個目標值就可以還原出整個Y 。把X中的所有值\(X_i\)標記為起始值，從這些起始值開始跑bfs ， 兩個值之間有邊當且僅當它們在A中的某個地方相鄰 。這樣就通過bfs找到了從"X的一個字符"到"Y的一個字符"的最少操作次數 。
時間復雜度\(O(nlogn)\) 。
點擊查看代碼#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 ull unsigned 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 n;vector <int> s;namespace SA{ int sa[500010],lcp[500010],rk[1000010],cnt[500010],tmp[500010],add,cur; void rsort() {cur=0;for(int i=s.size()-1;i>=s.size()-add;--i) tmp[cur++]=i;rep(i,s.size()) if(sa[i]-add>=0) tmp[cur++]=sa[i]-add;int bd=max(n+3,(int)s.size()+3);rep(i,bd+3) cnt[i]=0;rep(i,s.size()) ++cnt[rk[i]];repn(i,bd+3) cnt[i]+=cnt[i-1];cur=0;for(int i=s.size()-1;i>=0;--i) sa[--cnt[rk[tmp[i]]]]=tmp[i]; } int cmp(int x,int y){return (int)(rk[x]!=rk[y]||rk[x+add]!=rk[y+add]);} void getSA() {rep(i,s.size()+s.size()+3) rk[i]=0;rep(i,s.size()) rk[i]=s[i],sa[i]=i;int m=0;for(int msk=0;m<s.size();++msk){add=(msk==0 ? 0:(1<<(msk-1)));rsort();tmp[sa[0]]=1;repn(i,s.size()-1) tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);m=tmp[sa[s.size()-1]];rep(i,s.size()) rk[i]=tmp[i];} } void getLCP() {rep(i,s.size()) --rk[i];lcp[0]=0;rep(i,s.size()){if(rk[i]==0) continue;int lst=(i==0 ? 0:max(0,lcp[rk[i-1]]-1));while(i+lst<s.size()&&sa[rk[i]-1]+lst<s.size()&&s[i+lst]==s[sa[rk[i]-1]+lst]) ++lst;lcp[rk[i]]=lst;} }}int a[200010],xnn,ynn,x[200010],y[200010],ans=1e9,sum[200010],isTarg[200010],dist[200010];ull h[200010],H=11451419,HH,pw[200010];multiset <int> st;vector <int> g[200010];queue <int> q;ull getHash(int lb,int ub){return h[ub+1]-h[lb]*pw[ub-lb+1];}int main(){fileio();cin>>n;rep(i,n) scanf("%d",&a[i]);cin>>xnn;rep(i,xnn) scanf("%d",&x[i]);cin>>ynn;rep(i,ynn) scanf("%d",&y[i]);rep(i,ynn) s.pb(y[i]);s.pb(n+2);rep(i,xnn) s.pb(x[i]);SA::getSA();SA::getLCP();bool hvy=false;int mxc=0;rep(i,s.size()-1){if(SA::sa[i]<ynn)//是y{hvy=true;st.clear();}else{st.insert(SA::lcp[i]);if(hvy) mxc=max(mxc,*st.begin());}}st.clear();hvy=false;for(int i=s.size()-2;i>=0;--i) if(SA::sa[i]!=ynn){if(SA::sa[i]<ynn){hvy=true;st.clear();st.insert(SA::lcp[i]);}else{if(hvy) mxc=max(mxc,*st.begin());st.insert(SA::lcp[i]);}}if(mxc>0) ans=(xnn-mxc)+(ynn-mxc);rep(i,ynn) HH=HH*H+y[i];rep(i,n) h[i+1]=h[i]*H+a[i];pw[0]=1;repn(i,n+3) pw[i]=pw[i-1]*H;rep(i,n-ynn+1){ull hv=getHash(i,i+ynn-1);if(hv==HH) ++sum[i],--sum[i+ynn];}rep(i,n){sum[i+1]+=sum[i];if(sum[i]>0) isTarg[a[i]]=1;}rep(i,n-1) g[a[i]].pb(a[i+1]),g[a[i+1]].pb(a[i]);rep(i,n+3) dist[i]=1e8;rep(i,xnn) if(dist[x[i]]==1e8){dist[x[i]]=0;q.push(x[i]);}while(!q.empty()){int f=q.front();q.pop();rep(i,g[f].size()) if(dist[g[f][i]]==1e8){dist[g[f][i]]=dist[f]+1;q.push(g[f][i]);}}int add=xnn-1+ynn-1;repn(i,n) if(isTarg[i]) ans=min(ans,dist[i]*2+add);cout<<ans<<endl;termin();}

推薦閱讀