2022牛客多校第3场

contest传送门

战况

standing

整体来看没有前几次的好，今天的字符串题目 $H$ 我也没有写出来。

补题

H-Hacker

题意

给出长度为 $n$ 的小写字符串 $A$ 和 $k$ 个长度为 $m$ 的小写字符串 $B_1 … B_k$ ， $B$ 的每个位置拥有统一的权值 $v_1 … v_m$ ，对于每个 $B_i$ 求最大和区间满足该区间构成的字符串是 $A$ 的子串（空区间合法）。

思路

首先用给字符串 $A$ 建立一个后缀自动机

之后对于每个字符串 $B_i$ ，通过在后缀自动机上匹配的方法进行对 $B_i$ 的匹配，对于 $B_i$ 的每个位置 $j$ ，求以 $B_{ij}$ 为结尾的在 $A$ 中出现过的最长后缀的最大区间和，每一次取 $max$ 值，遍历完一个串之后就是这个串的 $ans$ 。

代码

#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<string>
#include<set>
#include<unordered_map>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=500005;
const int MAXN=100005;

int n,m,k;
LL a[MAXN];
char s[MAXN];

struct SamNode{
	int ch[26];
	int len,fa;
	SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<1];
SamNode temp[MAXX];
int las=1,sam_cnt=1;

void add(int c){
	int p=las;int np=las=++sam_cnt;
	sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
	if(!p) sam[np].fa=1;
	else{
		int q=sam[p].ch[c];
		if(sam[q].len==sam[p].len+1) sam[np].fa=q;
		else{
			int nq=++sam_cnt;sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
		}
	}
}

inline void solve(){
	scanf("%d%d%d",&n,&m,&k);
	getchar();scanf("%s",s+1);
	for(int i=1;i<=m;++i)
		scanf("%lld",&a[i]);
	
	int len=strlen(s+1);
	for(int i=1;i<=len;++i)
		add(s[i]-'a');
	for(int i=1;i<=k;++i){
		getchar();scanf("%s",s+1);
		len=strlen(s+1);
		LL ans=0LL,anss=0LL;
		int now=1;
		for(int j=1;j<=len;++j){
			if(anss>0&&sam[now].ch[s[j]-'a']){
				anss+=a[j];
				now=sam[now].ch[s[j]-'a'];
			}
			else if(sam[1].ch[s[j]-'a']){
				anss=a[j];
				now=sam[1].ch[s[j]-'a'];
			}
			else{
				anss=0LL;
				now=1;
			}
			ans=max(ans,anss);
		}
		printf("%lld\n",ans);
	}
	
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}

总结

在 $SAM$ 中不一定非要把每个字符串都加到 $SAM$ 中才能进行子串匹配

在这道题中就是只对原串 $A$ 建立了 $SAM$ ，然后对于每一个新串，通过 $trie树$ 的匹配方式进行匹配即可。

J-Journey

题意

给定一个城市有若干十字路口，右转不需要等红灯，而直行、左转、掉头都需要等红灯，求从起点的路到终点的路最少等多少次红灯。

思路

把城市中的每条路当成一个节点，把每个十字路口进行的四种操作当成边，建图，直接 $dijkstra$ 即可解决。

或者也可以不建图，可以直接在 $dijkstra$ 进行顶点转移的操作，最后达到的效果是一样的。

还有一种做法， $bfs$ ，具体原理和上面类似，不再赘述。

代码

#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<string>
#include<set>
#include<unordered_map>
#define Inf 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
typedef pair<int,P> PP;
const int MAXX=500005;

struct hashfunc{
    template<typename T, typename U>
    size_t operator() (const pair<T, U> &i) const {
        return (LL)(i.first)*1000000LL+(LL)(i.second);
    }
};

int n,stx,sty,enx,eny;
unordered_map<P,int,hashfunc> dij;
int c[MAXX][4];

void dijs(){
	priority_queue<PP,vector<PP>,greater<PP> > pq;
	pq.emplace(0,P(stx,sty));
	dij[P(stx,sty)]=0;
	
	while(!pq.empty()){
		PP now=pq.top();pq.pop();
		P mid=now.second;
		if(dij[mid]!=now.first) continue;
		
		int jk=now.second.second;
		for(int i=0;i<4;++i){
			if(!c[jk][i]) continue;
			int too=c[jk][i],lenn=1;
			if(c[jk][(i+3)%4]==now.second.first)
				lenn=0;
			if(!dij.count(P(jk,too))||dij[P(jk,too)]>dij[mid]+lenn){
				dij[P(jk,too)]=dij[mid]+lenn;
				pq.emplace(dij[P(jk,too)],P(jk,too));
			}
		}
	}
}

inline void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		for(int j=0;j<4;++j)
			scanf("%d",&c[i][j]);
	}
	
	scanf("%d%d%d%d",&stx,&sty,&enx,&eny);
	dijs();
	
	if(!dij.count(P(enx,eny)))
		printf("-1\n");
	else
		printf("%d\n",dij[P(enx,eny)]);
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}