T1 匹配
只不过Kmp的麻烦程度++，因为 Kmp 的优势在这道题中并不是显现得很明显..
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define re register ll
const ll mod1=1e9+7;
const ll mod2=10061;
const ll p=137;
inline void read(ll &ss)
{
ss=0;
ll cit=0;
char ch;
ch=getchar();
while((ch>‘9‘) or (ch<‘0‘))
{
if(ch==‘-‘) cit=1;
ch=getchar();
}
while((ch<=‘9‘) and (ch>=‘0‘))
{
ss=(ss<<3)+(ss<<1)+(ch^48);
ch=getchar();
}
if(cit) ss=-ss;
}
ll n,ts;
ll l1,l2;//A 和 B 分别的长度
char a[200050];
char b[100050];
char ch;
ll pre1[200050];
ll pre2[200050];
ll suf1[100050];
ll suf2[100050];
//这里代指长度..
ll down1[200050];
ll down2[200050];
ll maxn;
inline void Work()
{
for(re i=1;i<=min(l1,l2);++i)
{
if(pre1[i]==suf1[i] and pre2[i]==suf2[i])
{
maxn=max(maxn,(ll)i);
}
}
return ;
}
signed main()
{
read(ts);
down1[0]=1;
down2[0]=1;
for(re i=1;i<=200050;++i)
{
down1[i]=(down1[i-1]*p)%mod1;
down2[i]=(down2[i-1]*p)%mod2;
}
while(ts)
{
--ts;
read(l1); read(l2);
scanf("%s",a+1);
maxn=0;
cin>>ch;
for(re i=1;i<=l2;++i)
{
b[i]=a[i];
}
b[++l2]=ch;
for(re i=1;i<=l1;++i)
{
pre1[i]=((pre1[i-1]*p)%mod1+a[i]-‘a‘+1)%mod1;
pre2[i]=((pre2[i-1]*p)%mod2+a[i]-‘a‘+1)%mod2;
}
for(re i=1;i<=l2;++i)
{
suf1[i]=(suf1[i-1]+(b[l2-i+1]-‘a‘+1)*down1[i-1]%mod1)%mod1;
suf2[i]=(suf2[i-1]+(b[l2-i+1]-‘a‘+1)*down2[i-1]%mod2)%mod2;
}
Work();
printf("%lld\n",maxn);
}
return 0;
}
/*
1
5 3
ababc
d
*/
T2 回家
一个 Tarjan..可是我没有想到..Tarjan 板子全都忘了..
pyt 大佬对于这一道题目有深刻的理解..
采用了非常巧妙的方法..link
#include<bits/stdc++.h> using namespace std; #define ll long long int #define re register ll const ll N=2000050; inline void read(ll &ss) { ss=0; ll cit=0; char ch; ch=getchar(); while((ch>‘9‘) or (ch<‘0‘)) { if(ch==‘-‘) cit=1; ch=getchar(); } while((ch<=‘9‘) and (ch>=‘0‘)) { ss=(ss<<3)+(ss<<1)+(ch^48); ch=getchar(); } if(cit) ss=-ss; } ll n,m; ll ts; ll alls; ll size; ll one,two; ll f[N],vis[N],con[N],son[N],dfn[N],low[N]; bool cut[N]; struct S_1 { ll u; ll v; ll nxt; }a[2000000]; inline void add(ll u,ll v) { a[++ts].u=u; a[ts].v=v; a[ts].nxt=f[u]; f[u]=ts; } inline bool cmp(ll aa,ll bb) { return aa<bb; } inline bool Tarjan(ll root,ll now) { dfn[now]=low[now]=++ts; ll flag=0; for(re i=f[now];i;i=a[i].nxt) { if(!dfn[a[i].v]) { if(Tarjan(root,a[i].v)) son[now]=1; low[now]=min(low[now],low[a[i].v]); if(low[a[i].v]>=dfn[now] and( a[i].v==n or son[a[i].v]==1 )) { flag++; if(now!=root or flag>1) { cut[now]=1; } } } else { low[now]=min(low[now],dfn[a[i].v]); } } if(now==n or son[now]) return 1; return 0; } signed main() { read(alls); while(alls) { --alls; read(n); read(m); memset(f,0,sizeof(f)); memset(a,0,sizeof(a)); memset(con,0,sizeof(con)); memset(son,0,sizeof(son)); memset(vis,0,sizeof(vis)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(cut,0,sizeof(cut)); size=0; for(re i=1;i<=m;++i) { read(one); read(two); if(one==two) continue; add(one,two); add(two,one); } ts=0; for(re i=1;i<=n;++i) { if(!dfn[i]) { Tarjan(i,i); } } for(re i=2;i<=n-1;++i) { if(cut[i] and son[i]) { con[++size]=i; } } sort(con+1,con+1+size,cmp); printf("%lld\n",size); for(re i=1;i<=size;++i) { printf("%lld ",con[i]); } printf("\n"); } return 0; }
T3 寿司
这是一个环..首先明确几点性质：
1. 我们可以把这道题看作在这个序列中随机插入一个分割符号 div ,然后让分割符左边的往右边移动，分割符右边的向右边移动..（也可以看成两边的都向分割符移动）
2. 移动红色符号与蓝色符号的距离是等价的..
3. 某一个符号向边上移动的距离即为 ta 与边上之间相反符号的个数..
eg: BBRBBR | BRRBRRB
如从左往右数第二个 R（即从左往右数第6个符号）..向左边移动的距离即为 4
以上性质都是显然的..
对于这样的一个环..我们将 ta 进行复制..变成一个长度为 2*n 的序列..（这是一个基本的常识操作，对于更多的环形与后效性知识可以参考 李煜东的《算法竞赛进阶指南》）
我们在此对这个长度为 2*n 的序列命名为 T..
我们对 T 截取所有长度为 n 的子序列，即可遍历到所有形态的、长度为 n 的序列情况..
我们命名所有子序列分别为 S1,S2,S3..Sn ;
对所有的子序列分别取中点，然后进行左移和右移..然后分别得到各个 ans，最后取最小值即可得到答案..
接下来我们来证明 ta 的正确性，首先写下这样一个等式：
分别取各个子序列的中点并让各个R向分割符号移动 等价于 以环的形态在每个地方插入一个分割符并让所有 R 字符向分割符移动..
我们可以思考： 在环形序列中插入的任意一个分割符都可以转化为向某一个对应的子序列 Si 的中点插入分割符..
所以等式成立..从而读者应该也可以联想到：取三等分点..四等分点..甚至只向端点移动都可以..(但是不要忘了要让每个点都走更近的路径..)
至此本题思路结束..
个人认为思考量很大..确实需要很深厚的竞赛底子..
这里代码中是计算了向两边移动的距离..因为方便理解一下..有余力的读者可以根据思路进行更多的实现方式..
#include<bits/stdc++.h> using namespace std; #define ll long long int #define re register ll #define le strlen const ll N=1000050; inline void read(ll &ss) { ss=0; ll cit=0; char ch; ch=getchar(); while((ch>‘9‘) or (ch<‘0‘)) { if(ch==‘-‘) cit=1; ch=getchar(); } while((ch<=‘9‘) and (ch>=‘0‘)) { ss=(ss<<3)+(ss<<1)+(ch^48); ch=getchar(); } if(cit) ss=-ss; } ll ts,n; ll f[N*2],lr[N*2],rr[N*2],lb[N*2],rb[N*2]; ll slr[N*2],srr[N*2]; char ss[N]; inline ll Count(ll l,ll r,ll div) { ll temp=0; temp=(slr[div-1]-slr[l-1])+(srr[div]-srr[r+1])-lb[l-1]*(lr[div-1]-lr[l-1])-rb[r+1]*(rr[div]-rr[r+1]); // cout<<"div:"<<div<<" "<<"l:"<<l<<" r:"<<r<<" temp:"<<temp<<endl; // cout<<rb[r+1]<<" "<<(rb[div]-rb[r+1])<<endl; return temp; } signed main() { read(ts); while(ts) { ts--; scanf("%s",ss+1); n=le(ss+1); memset(f,0,sizeof f); slr[0]=0; srr[2*n+1]=0; for(re i=1;i<=n;i++) { if(ss[i]==‘B‘) { f[i]=0; f[i+n]=0; } else { f[i]=1; f[i+n]=1; } } for(re i=1;i<=n*2;i++) { lr[i]=lr[i-1]; lb[i]=lb[i-1]; slr[i]=slr[i-1]; if(f[i]) { lr[i]++; slr[i]+=lb[i]; } else lb[i]++; } for(re i=2*n;i>=1;i--) { rr[i]=rr[i+1]; rb[i]=rb[i+1]; srr[i]=srr[i+1]; if(f[i]) { rr[i]++; srr[i]+=rb[i]; } else rb[i]++; } ll div=1;//分隔符.. ll ans=(ll)1e11; for(re i=1;i<=n;i++) { while(div<i+n-1 and (lb[div]-lb[i-1])<=((lb[i+n-1]-lb[i-1])>>1)) { div++; }//保证分隔符位于区间内，且左边的 B 要等于 B.. ans=min(ans,Count(i,i+n-1,div)); // cout<<Count(i,i+n-1,div)<<endl; //cout<<ans<<endl; } printf("%lld\n",ans); } return 0; }
根据这场考试我们可以发现..难题是真的很难在考场上想出来的..部分题目甚至在考后都需要花上大量时间进行理解..
所以，水题要保准拿分，难题要学会拿部分分，学会取舍，熟练板子，以拿分为目的..