NOIP提高组模拟赛2
A. 匹配
kmp板子，用A的前缀匹配B的后缀，就是用AB求next数组，答案就是\(next[min(la,lb+1)]\)
注意坑点，kmp匹配是除了本身以外的最大前缀和后缀，需要特判B恰好是A前缀的情况，本题数据诡异，特判有90pts
#include
#include
using namespace std;
const int maxn=1000005;
char a[maxn],b[maxn];
int net[maxn];
void kmp(int la,int lb){
memset(net,0,sizeof(net));
int j=0;
for(int i=2;i<=lb;++i){
while(j&&b[j+1]!=b[i])j=net[j];
if(b[j+1]==b[i])j++;
net[i]=j;
}
printf("%d\n",net[lb]);
}
int main(){
int T;scanf("%d",&T);
for(int ask=1;ask<=T;++ask){
int la,lb;scanf("%d%d",&la,&lb);
scanf("%s",a+1);
for(int i=1;i<=lb;++i)b[i]=a[i];
++lb;scanf("%c",&b[lb]);
while(b[lb]<'a'||b[lb]>'z')scanf("%c",&b[lb]);
if(lb<=la&&b[lb]==a[lb])printf("%d\n",lb);
else kmp(la,lb);
}
return 0;
}
B. 回家
算法一： DFS记录路径 每次删去一个路径上的点，再DFS看是否能到n 得分30pts（考试时候想特判树的情况结果判错了，可恶）
优化：不用每次删去点，dfs寻找路径，如果有一条从i-j（i，j为1-n路径上的点）非1-n路径的路径，那么i-j之间的点就不是必须经过的点，考场上想到了，但是时间（码力）不够,题解说有80-100pts
正解：
考试时候也想到了，但是由于蒟蒻tarjan没学完（没学）无奈打爆力。。
可以想到1-n必须经过的点必定是图的一个割点，但割点并不一定是路径上的点
tarjan割点时记录一下是否在路径上即可，即该点的子树内是否有n
：这个故事告诉我们，不要留坑
代码
留坑
#include
#include
#include
using namespace std;
int read(){
char c;int x=0;
c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){x*=10;x+=c-'0';c=getchar();}
return x;
}
const int maxn=200005;
int n,m;
struct edge{
int to,net;
}e[maxn<<2|1];
int head[maxn],tot;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
int low[maxn],dfn[maxn],tim;
bool flag[maxn];
bool vis[maxn];
bool lv[maxn];
bool tarjan(int x,int fx){
dfn[x]=low[x]=++tim;lv[x]=1;
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;if(v==fx)continue;
if(!dfn[v]){
vis[x]|=tarjan(v,x);
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]&&vis[v])flag[x]=1;
}
else if(lv[v])low[x]=min(low[x],dfn[v]);
}
lv[x]=0;
if(x==n||vis[x])return vis[x]=1;
return 0;
}
int main(){
/// freopen("home.in","r",stdin);
// freopen("home.out","w",stdout);
int T;T=read();
for(int ask=1;ask<=T;++ask){
n=read();m=read();
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
memset(flag,0,sizeof(flag));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
tim=0,tot=0;
for(int i=1;i<=m;++i){
int u,v;u=read();v=read();
add(u,v);add(v,u);
}
tarjan(1,0);
int cnt=0;
for(int i=2;i C. 寿司
题面成功将我误导，以为是考数据结构（还是因为菜），甚至想打线段树（只会这个）
显然是个DP，环形DP，可以想到至少有一盘寿司不用动，否则相当于把环转了一下没有意义。可以断环成链。
考虑R或B其一即可，在环上连续等价于在链的两端或中间，两边比较好考虑。
容易发现一定是靠左的向左边走，靠右的一定向右走，中间一定有一个分界点p，p左边的向左，p右边的向右，而区间右移，即相当于环上顺时针（也可能是逆时针）转了一下，p也一定同方向移动或者不动，就是说p有单调性，这样一来直接\(O(n)\)扫一遍就行了
具体一点
预处理出从i跳到左和右的步数l[i],r[i]，即到左或右有几个与i颜色不同的寿司个数，枚举区间时l[i]减去左界l[],r[i]减去右界r[],就是i向两端走的步数
移动区间，考虑将左边的R还是B移到了右边，对向左走和向右走的有什么影响，在移动p时记录一下几个向左走的几个向右走的
思路比较清晰，代码实现还是很有细节的（还是我太菜），容易算出负数
还有记得开longlong
#include
#include
using namespace std;
const int maxn=2000005;
long long min(long long x,long long y){return x=1;--i){if(c[i]=='B')++p;r[i]=p;}
p=0;long long ans=1e18,sum=0,ls=0,rs=0;
for(int i=1;i<=s;++i)if(c[i]=='R'){sum+=r[i]-r[s+1];rs++;}
for(int i=1;i<=s;++i){
while(p+1<=i+s-1){
if(c[p+1]=='B'){
p++;
}else{
if(l[p+1]-l[i-1]