T1 匹配
水题。
KMP裸题。
hash完美AC。
我WA 0。
内心十分激动。
明显的KMP，但是板子没背会，于是yy：
while (j<=la+lb+1)
{
if (!i) nx[j++]=i++;
else
{
while (sa[i+1]!=sa[j] and i) i=nx[i];
nx[j++]=i++;
if (i>la) i=nx[i];
}
}
狗屎。
唯一的好处是让我复习了一遍Hash和KMP。
处理最后一位b时注意去除回车和空格。（WA 9 根源）
小弟不才。
T2 回家
水题。
不过我不会 WA 10。
没打过点双，自己yy了一个无向图缩点，最后把点，缩成了一坨。
神奇的是这种超级超级超级错解竟然能够70 ，而我之加了一句话。
然后发现没法改了，开始撸正解。
学到了点双，收获不错。
点双+Dfs，AC，记得数组要往大里开，要把起点和终点除掉。
小弟不才。
1 #include<cstdio> 2 #include<vector> 3 #include<cmath> 4 #include<cstring> 5 #include<iostream> 6 #include<algorithm> 7 #define mm(a) memset(a,0,sizeof(a)) 8 #define HZOI using namespace std 9 HZOI; 10 const int MAXN=2e6+3; 11 struct node{ 12 int v,next; 13 }edge[MAXN<<2]; 14 int T,n,m; 15 int tt,et,efirst[MAXN],first[MAXN],vv[MAXN<<2],nx[MAXN<<2]; 16 int cnt,tot,tail,dfn[MAXN],low[MAXN],be[MAXN],vis[MAXN],stack[MAXN]; 17 int iscut[MAXN],idcut[MAXN],oldid[MAXN]; 18 int ans[MAXN],nu; 19 vector<int > vec[MAXN]; 20 inline int read(); 21 inline void Add(int ,int ); 22 inline void NewAdd(int ,int ); 23 void Tarjan(int ,int ); 24 bool Dfs(int ); 25 inline void Clear(); 26 int main() 27 { 28 T=read(); 29 while (T--) 30 { 31 Clear(); 32 n=read(); m=read(); 33 for (int i=1,x,y; i<=m; ++i) 34 { 35 x=read(); y=read(); 36 Add(x,y); Add(y,x); 37 } 38 Tarjan(1,1); 39 if (!dfn[n]) {printf("0 ");continue;} 40 int num=cnt; 41 for (int i=1; i<=n; ++i) 42 if (iscut[i]) 43 idcut[i]=++num,oldid[num]=i; 44 for (int i=1; i<=cnt; ++i) 45 for (int j=0; j<vec[i].size(); ++j) 46 { 47 int x=vec[i][j]; 48 if (iscut[x]) 49 { 50 NewAdd(i,idcut[x]); 51 NewAdd(idcut[x],i); 52 be[x]=idcut[x]; 53 } 54 else be[x]=i; 55 } 56 memset(vis,0,sizeof(vis)); 57 if (be[1]==be[n]) {printf("0 ");continue;} 58 Dfs(be[1]); 59 sort(ans+1,ans+nu+1); 60 printf("%d ",nu); 61 for (int i=1; i<=nu; ++i) 62 printf("%d ",ans[i]); 63 puts(""); 64 } 65 return 0; 66 } 67 bool Dfs(int k) 68 { 69 if (be[n]==k) return 1; 70 if (iscut[oldid[k]] and oldid[k]!=1) ans[++nu]=oldid[k]; 71 vis[k]=1; 72 for (int i=efirst[k]; i; i=edge[i].next) 73 { 74 if (vis[edge[i].v]) continue; 75 if (Dfs(edge[i].v)) return 1; 76 } 77 if (iscut[oldid[k]] and oldid[k]!=1) --nu; 78 return 0; 79 } 80 void Tarjan(int k,int root) 81 { 82 dfn[k]=low[k]=++tot; 83 stack[++tail]=k; 84 if (k==root and !first[k]) {vec[++cnt].push_back(k); return ;} 85 int flag=0; 86 for (int i=first[k]; i; i=nx[i]) 87 { 88 int ver=vv[i]; 89 if (!dfn[ver]) 90 { 91 Tarjan(ver,root); 92 low[k]=min(low[k],low[ver]); 93 if (low[ver]>=dfn[k]) 94 { 95 ++flag; 96 if (k!=root or flag>1) iscut[k]=1; 97 ++cnt; 98 int to; 99 do 100 { 101 to=stack[tail--]; 102 vec[cnt].push_back(to); 103 }while (to!=ver); 104 vec[cnt].push_back(k); 105 } 106 } 107 else low[k]=min(low[k],dfn[ver]); 108 } 109 } 110 inline void Add(int u,int v) 111 { 112 vv[++tt]=v; nx[tt]=first[u]; first[u]=tt; 113 } 114 inline void NewAdd(int u,int v) 115 { 116 edge[++et].v=v; edge[et].next=efirst[u]; efirst[u]=et; 117 } 118 inline int read() 119 { 120 int cc=0; char ch=getchar(); 121 while (ch<'0' or ch>'9') ch=getchar(); 122 while (ch>='0' and ch<='9') cc=(cc<<3)+(cc<<1)+(ch^48),ch=getchar(); 123 return cc; 124 } 125 inline void Clear() 126 { 127 mm(efirst); mm(first); 128 mm(dfn); mm(be); 129 mm(iscut); mm(idcut); mm(oldid); 130 for (int i=1; i<=cnt; ++i) vec[i].clear(); 131 cnt=tot=tail=tt=nu=et=0; 132 return ; 133 }
T3 寿司
神仙题。
把环搞成一段序列，首尾相接，使他长度变为2n（环题的惯用套路）。
接下来就不是好想的了，我怎么可能看出来这玩意儿有***单调性？！
只要我们稍微思考一下，会发现一个很显然的性质：序列中存在一个断点，使它左边的点全移向左边，右边的全移向右边。
那么就接着会有一个更显然的性质：断点左边的0/1一定等于右边的0/1。
O（n2）：枚举断点暴力计算。
O（nlogn）（我的极限）：二分搜索断点，然后O（1）计算。
O（n）：说过这道题有一个神奇的单调性，我们把序列看成一个0/1串，我们使0移向序列两侧，只要我们的mid（断点）一直向右移动，左边的1的手机数量会越来越少，而右边的1越来越多，这说明0向左走的步数越来越少，于是断点会不断向右移动，这是我们便找到了这个单调性，线性平行O（n）复杂度。
这里给出一些巨佬的题解，留做借鉴：mikufun ，DeepInC 。
小弟不才。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define int long long 5 #define mm(a) memset(a,0,sizeof(a)) 6 #define HZOI using namespace std 7 HZOI; 8 const int MAXLEN=3e6+3; 9 int T; 10 int ch[MAXLEN]; 11 int lb[MAXLEN],rb[MAXLEN],lr[MAXLEN],rr[MAXLEN],sl[MAXLEN],sr[MAXLEN]; 12 int l,r,mid; 13 inline int min(int a,int b) {return a<b?a:b;} 14 inline int Cal(int ,int ,int ); 15 signed main() 16 { 17 scanf("%lld",&T); 18 while (T--) 19 { 20 mm(lb); mm(rb); mm(lr); mm(rr); mm(sl); mm(sr); 21 int t=1; 22 ch[t]=getchar(); 23 while (ch[t]!='B' and ch[t]!='R') ch[t]=getchar(); 24 while (ch[t]=='B' or ch[t]=='R') ch[++t]=getchar(); 25 --t; 26 for (int i=t+1; i<=t*2; ++i) ch[i]=ch[i-t]; 27 t<<=1; 28 lb[0]=lr[0]=sl[0]=0; 29 for (int i=1; i<=t; ++i) 30 { 31 lb[i]=lb[i-1]; lr[i]=lr[i-1]; sl[i]=sl[i-1]; 32 if (ch[i]=='R') ++lr[i]; 33 else ++lb[i],sl[i]+=lr[i]; 34 } 35 rb[t|1]=rr[t|1]=sr[t|1]=0; 36 for (int i=t; i>=1; --i) 37 { 38 rb[i]=rb[i+1]; rr[i]=rr[i+1]; sr[i]=sr[i+1]; 39 if (ch[i]=='R') ++rr[i]; 40 else ++rb[i],sr[i]+=rr[i]; 41 } 42 t>>=1; mid=1; 43 int ans=0x7fffffffffffffff; 44 for (int i=1; i<=t; ++i) 45 { 46 l=i,r=i+t-1; 47 while(mid<i+t-1&&lb[mid]-lb[i-1]<=(lb[i+t-1]-lb[i-1])/2) mid++; 48 // cout<<mid<<endl; 49 ans=min(ans,Cal(l,mid,r)); 50 // cout<<"ans="<<ans<<endl; 51 } 52 printf("%lld ",ans); 53 } 54 return 0; 55 } 56 inline int Cal(int l,int mid,int r) 57 { 58 return sl[mid-1]-sl[l-1]-(lb[mid-1]-lb[l-1])*lr[l-1]+sr[mid]-sr[r+1]-(rb[mid]-rb[r+1])*rr[r+1]; 59 }
永不放弃。