文章目錄

• 前言
• 考場
• 題目解析
• • T1
  • T2
  • T3
• 總結
• 代碼
• • T1
  • T2
  • T3

前言

50pts
30+0+20
rnk19
…
把1000ms看成10s我也真是個人才。
T3自然溢出50帶模數T成20有點離譜。
但倒沒有因為WA失分。
就是菜罷了

考場

這次時間管理還是比較合理的。
乍看三題覺得T1似乎是個傘兵題
這離線下來可持久化數組二分一下不隨便做？

…
能有甚么奇怪的原因，你就是不想讓我得分。

T2乍一看又感覺可做了。
然后發現需要求權值的平方和。
先暴力枚舉情況上輪廓線的話 $n=3$ 都感覺要T…
直接棄療，本次滿分200分。

T3想到了類似題解的那個定義。
然后這個問法肯定往SA上想啊。
但是它變來變去似乎直接求SA會出大問題。
然后就不會勒。
（補題的時候這個問題也沒有解決qwq）
我會哈希！
服了 1040004000 1.5s跑不過去。

但是還是不是特別想寫暴力。
還是對T1比較有想法。
瞅T1瞅到九點想法越來越少
然后就去敲 T3 暴力樂。
很好寫半個小時寫完了。
30min 50pts遠超lb預期
怕鍋還上了個雙哈希。
不過那個題只要不自然溢出單雙哈希都是會T的。
愛咋咋地吧。

此時還有2.5h
我就剩個暴力巨好寫的T1了。
瞬間悠閑起來。
（既然暴力好寫，這題其實還是應該先打個暴力，雖然這次沒吃虧，但對拍還是寫了個暴力，不如提前寫了。）
一開始覺得可能是平衡樹，但越想越覺得平衡樹不可做。
開始lxl化想是否可以根號分治之類的神奇科技。
一開始按照常規根號分治思路，肯定要想修改集合大于根號如何小于根號如何。
發現修改集合大于根號根本沒法如何。
然后靈光一閃覺得可以利用神奇的均攤對修改分塊，忽略掉一些很垃圾的修改。
仔細想想還是挺可行的。
想想實現似乎是 $O(mf(B)\log m+\frac{m}{B}m\log m)$
每次貢獻復雜度都會是觀察者的變化量至少減少 $\frac{1}{B}$ （上取整），$f(B)$ 就是這個貢獻次數。
打表發現卡成最差也就是 $8B?9B$ 左右。而且除非對著我的算法和塊長卡，否則根本卡不滿。

在一看時間 10秒？，那不過了？（大伏筆）

然后就愉快的開始敲。
后來由于感覺這個做法不是正解且出數據的人恐怕并不會想著卡，把 $B$ 調成了 $300$ 左右，復雜度往前傾斜一點，讓后面穩定的重構復雜度低一些。

算是被 std::set 玩明白了，來回debug其實就一直在這件事上。
出考場：

啊焯

題目解析

T1

每次把變化量平均分成 k 份，有一份超了就重構，這樣復雜度是 $O(m{\log }_{1.5}t)$ 的。
你說它難吧看題解一點不難，你說它不難還就是想不到。
還是類似于利用 set 忽略修改，復雜度均攤的思路，但這個均攤靠譜多了。

T2

技巧題。
《變形》：$f^2(x)=f(x)?f(x)$
把問題轉化為在同一種填數方案下（關鍵！）任務兩種連邊方案的方案數。
然后直接插頭dp即可。
（補題發現這種輕插頭dp其實挺好寫的）

T3

蜜汁題目
正準備敲“現在也沒明白”然后突然就想明白了并且去補完了本題
其實本題真是離正解很近了，唯一的障礙是我學了SA
關鍵是要靈活。
本題由于特殊元素在不同的后綴中值不一樣，用SA常規的倍增加基排是不可行的，因為基排的原理是基于值域的。
就給你兩個后綴，讓你比較字典序，怎么做？
哈希加二分啊！
我暑假的時候還用這個做法切過一個題，現在反而不會了（悲）
所以我們可以使用基于比較的快速排序，寫一個復雜度 $\log$ 的cmp揉進去。
加上 std::sort 的 $\log$ ，預處理總復雜度 $n{\log }^{2}n$。
有了SA后面就簡單了，直接二分找到SA數組里的左右端點中間的后綴均為答案。
注意一些超出結尾的細節。

總結

還是比較慘的一次考試
最近就沒有不慘過
但是T1,3對題目的直覺與大方向都是對的。
題目雖然整體偏難，但也不是沒有切題的機會（尤其T3）
明天加油吧！awa

代碼

T1

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=2e6+100; const int M=2e4+100;int n,m,tot;struct node{ll w;int id;bool operator < (const node oth)const{if(w!=oth.w)return w<oth.w;else return id<oth.id;}bool operator > (const node oth)const{if(w!=oth.w)return w>oth.w;else return id>oth.id;}bool operator == (const node oth)const{return w==oth.w&&id==oth.id;} };multiset<node>s[N]; ll val[N],sum[N]; int p[N][5],k[N]; ll giv[N][5]; int lst; int mem[N],num,ans[N]; void solve(int now,int op){ll lft=sum[now];for(int i=1;i<=k[now];i++) lft-=val[p[now][i]];if(op){for(int i=1;i<=k[now];i++){if(s[p[now][i]].find((node){giv[now][i],now})==s[p[now][i]].end()){debug("!\n");exit(0);}s[p[now][i]].erase(s[p[now][i]].find((node){giv[now][i],now}));}}if(lft<=0){ans[++lst]=now;}else{int w=lft/k[now];for(int i=1;i<=k[now];i++){int add=w;lft-=add;giv[now][i]=val[p[now][i]]+add;s[p[now][i]].insert((node){giv[now][i],now});}}return; }int tag[N]; signed main(){//#ifndef ONLINE_JUDGEfreopen("obs.in","r",stdin);freopen("obs.out","w",stdout);//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);//#endifn=read();m=read();for(int clo=1;clo<=m;clo++){int op=read();if(op==1){int now=++tot,t=read()^lst;k[now]=read();assert(k[now]<=3);for(int i=1;i<=k[now];i++){p[now][i]=read()^lst;sum[now]+=val[p[now][i]];}sum[now]+=t;solve(now,0);}else{int x=read()^lst,v=read()^lst;lst=0;num=0;val[x]+=v;for(node o:s[x]){if(o.w>val[x]) break;if(tag[o.id]!=clo) mem[++num]=o.id;//assert(tag[o.id]!=clo);tag[o.id]=clo;}for(int i=1;i<=num;i++){solve(mem[i],1);}sort(ans+1,ans+1+lst);printf("%d ",lst);sort(ans+1,ans+1+lst);for(int i=1;i<=lst;i++) printf("%d ",ans[i]);puts("");}//lst=0;}return 0; } /* 5 10 1 9 3 3 4 5 2 4 1 1 4 2 1 4 1 4 3 1 2 3 2 2 4 2 1 4 1 6 2 1 5 2 1 2 1 4 1 3 1 2 2 3 5 */

T2

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=2e6+100; const int M=2e4+100; const int mod=998244353;int n,m,tot; int mp[75][8],mi[10]; ll f[2][150][150]; int num[3],st[3][10];void init(){ mi[0]=1;for(int i=1;i<=8;i++){mi[i]=mi[i-1]<<1;//printf("i=%d mi=%d\n",i,mi[i]);}num[0]=1;num[1]=2;num[2]=1;st[0][1]=0;st[1][1]=1;st[1][2]=2;st[2][1]=3; }void work(){n=read();m=read();int S=mi[m+1]-1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]);}memset(f,0,sizeof(f));int now=1,nxt=0;f[nxt][0][0]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){swap(now,nxt);memset(f[nxt],0,sizeof(f[nxt]));for(int p=0;p<mi[m+1];p++){for(int q=0;q<mi[m+1];q++){if(!f[now][p][q]) continue;int n1=((p&mi[j-1])?1:0)+((p&mi[j])?1:0);int n2=((q&mi[j-1])?1:0)+((q&mi[j])?1:0);//printf(" p=%d q=%d n1=%d+%d n2=%d+%d\n",p,q,//(p&mi[j]),(p&mi[j+1]),((q&mi[j])?1:0),((q&mi[j+1])?1:0));//printf(" ?? %d&%d=%d\n",p,mi[j],p&mi[j]);for(int k=0;k<=4;k++){if(mp[i][j]!=-1&&mp[i][j]!=k) continue;int a=k-n1,b=k-n2;//printf(" k=%d a=%d b=%d\n",k,a,b);if(a<0||b<0) continue;for(int s=1;s<=num[a];s++){int np=(p&(S^(mi[j-1]|mi[j])))|(st[a][s]<<(j-1));for(int t=1;t<=num[b];t++){int nq=(q&(S^(mi[j-1]|mi[j])))|(st[b][t]<<(j-1));if(j==m){if((np&mi[m])||(nq&mi[m])) continue;np=(np<<1)&S;nq=(nq<<1)&S;}(f[nxt][np][nq]+=f[now][p][q])%=mod;}}}}}//for(int p=0;p<mi[m+1];p++){// for(int q=0;q<mi[m+1];q++){// if(f[nxt][p][q]){// printf("(%d %d) p=%d q=%d f=%lld\n",i,j,p,q,f[nxt][p][q]);// }// }//}//puts("");}}printf("%lld\n",f[nxt][0][0]); }signed main(){freopen("grid.in","r",stdin);freopen("grid.out","w",stdout);init();int T=read();while(T--) work();return 0; } /* 1 1 2 1 1 */

T3

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) #define ok debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=2e6+100; const int M=2e4+100;int n,m,tot;ull h[N],Mi[N],key=100003; int s[N],ss[N],nxt[N][10],pre[10]; void init_Hash(){Mi[0]=1;for(int i=1;i<=n;i++) Mi[i]=Mi[i-1]*key;for(int i=1;i<=n;i++) h[i]=h[i-1]*key+(s[i]+1);return; } inline ull Hash(int l,int r){return h[r]-h[l-1]*Mi[r-l+1]; } int a[12],b[12],na,nb; inline int Lcp(int x,int y){int st=0,ed=n-max(x,y)+1;while(st<ed){int mid=(st+ed+1)>>1;if(Hash(x,x+mid-1)==Hash(y,y+mid-1)) st=mid;else ed=mid-1;}return st; } inline int lcp(int x,int y){na=0;nb=0;for(int i=0;i<=9;i++){if(nxt[x][i]) a[++na]=nxt[x][i];if(nxt[y][i]) b[++nb]=nxt[y][i];}a[++na]=n+1;b[++nb]=n+1;sort(a+1,a+1+na);sort(b+1,b+1+nb);int res(0),pa=x-1,pb=y-1;for(int i=1;;i++){//printf("res=%d a=%d b=%d (%d %d) (%d %d)\n",res,a[i],b[i],pa+1,a[i]-1,pb+1,b[i]-1);if(max(a[i],b[i])==n+1||Hash(pa+1,a[i]-1)!=Hash(pb+1,b[i]-1)){//printf(" dif Lcp=%d\n",Lcp(pa+1,pb+1));return res+Lcp(pa+1,pb+1);}else{//printf(" ok\n");res+=a[i]-pa;pa=a[i];pb=b[i];}} } bool cmp(int x,int y){int o=lcp(x,y);//printf("cmp: (%d %d) o=%d %d %d\n",x,y,o,s[x+o],s[y+o]);if(x+o>n||y+o>n) return x>y;int u=x+o-s[x+o]>=x?s[x+o]:-1,v=y+o-s[y+o]>=y?s[y+o]:-1;//if(u==v){// printf("(%d %d) o=%d u=%d v=%d\n",x,y,o,u,v);//}assert(u!=v);return u<v; } int sa[N],rk[N],height[N]; int mn[N][20],lg[N],mi[20]; void SA(){for(int i=1;i<=n;i++) sa[i]=i;sort(sa+1,sa+1+n,cmp);for(int i=1;i<=n;i++) rk[sa[i]]=i;for(int i=2;i<=n;i++) height[i]=lcp(sa[i-1],sa[i]); } void init_ST(){lg[0]=-1;for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;mi[0]=1;for(int i=1;i<=lg[n];i++) mi[i]=mi[i-1]<<1;for(int i=1;i<=n;i++) mn[i][0]=height[i];for(int k=1;k<=lg[n];k++){for(int i=1;i+mi[k]-1<=n;i++) mn[i][k]=min(mn[i][k-1],mn[i+mi[k-1]][k-1]);}return; } inline int Min(int l,int r){int k=lg[r-l+1];return min(mn[l][k],mn[r-mi[k]+1][k]); } inline int Suf(int x,int len){int st=x,ed=n;while(st<ed){int mid=(st+ed+1)>>1;//printf(" (%d %d) mid=%d %d>=%d?\n",st,ed,mid,Min(x,mid),);if(Min(x+1,mid)>=len) st=mid;else ed=mid-1;}return st; } inline int Pre(int x,int len){if(height[x]<len) return x;int st=2,ed=x;while(st<ed){int mid=(st+ed)>>1;if(Min(mid,x)>=len) ed=mid;else st=mid+1;}return st-1; }signed main(){ freopen("similar.in","r",stdin);freopen("similar.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++){scanf("%1d",&ss[i]);int x=ss[i];s[i]=i-pre[x];for(int j=pre[x]+1;j<=i;j++) nxt[j][x]=i;pre[x]=i;}s[n+1]=-1;init_Hash();//for(int i=1;i<=n;i++) printf("%d",s[i]);//puts("");//for(int i=1;i<=n;i++){// for(int j=i+1;j<=n;j++) printf("(%d %d) lcp=%d %d<%d?:%d\n",i,j,lcp(i,j),i,j,cmp(i,j));//}//printf("%d\n",cmp(6,7));exit(0);SA();//for(int i=1;i<=n;i++){//printf("i=%d sa=%d h=%d ",i,sa[i],height[i]);//for(int j=sa[i];j<=n;j++) printf("%d",j-s[j]>=sa[i]?s[j]:0);//puts("");//}init_ST();int lst(0);for(int i=1;i<=m;i++){int l=read()^lst,r=read()^lst,len=r-l+1;int pos=rk[l];lst=Suf(pos,len)-Pre(pos,len)+1;//printf(" (%d %d) pos=%d (%d %d)\n",l,r,pos,Pre(pos,len),Suf(pos,len));printf("%d\n",lst);//lst=0;}return 0; } /* 1 1 2 1 1 */

總結

以上是生活随笔為你收集整理的2.5：模拟总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。