Supplementary questions for the training ground on September 11, 2021

C - Family View

The question ：
Here you are. $n$ Pattern strings , There are only lowercase letters in the pattern string , The sum of the pattern string lengths $len<=1e6$, Then I'll give you a matching string $len<=1e6$, The matching string consists of a full character set . It is required to replace all sub segments in the matching string that match the pattern string with ‘*’ ;
Ideas ：
Optimize AC automata ; ordinary AC Automata will jump violently when matching fail The pointer ; There is also construction fail Tree to count the number of times each matching string appears in the text string . But for this problem, we only need to add a mark where it matches , Record the length , Imagine jumping fail The process of , For each of the automata fail node , We should treat him flag take max, Then mark , So we are building fail Side time , Take... Directly max Just fine , So you don't have to jump fail It's on the edge . So we just have to traverse the automata , If the character of the current text string is not a letter , Then we can go back to the meta node of the automata directly .
Do not assign an initial value to the structure array ！ By default, the full array will be assigned , And then MLE 了 .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=7e5+4;

int t,n;
struct node{
    
	int son[26],fail=0,flag;
}trie[maxn];

int p[maxn];
int tot=1;
queue<int>q;
char s[maxn];
void init(){
    
	tot=0;
	for(int j=0;j<26;j++){
    
		trie[tot].son[j]=0;
	}
	trie[tot].fail=0;
	trie[tot].flag=0;
}
void insert(char *s){
    
	int len=strlen(s),u=0;
	for(int i=0;i<len;i++){
    
		int v=s[i]-'a';
		if(!trie[u].son[v]){
    
			trie[u].son[v]=++tot;
			for(int j=0;j<26;j++){
    
				trie[tot].son[j]=0;
			}
			trie[tot].fail=0;
			trie[tot].flag=0;
		}
		u=trie[u].son[v];
	}
	trie[u].flag=max(trie[u].flag,len);
}
void getfail(){
    
	for(int i=0;i<26;i++)
		if(trie[0].son[i])q.push(trie[0].son[i]);
	while(!q.empty()){
    
		int u=q.front();q.pop();
		trie[u].flag=max(trie[u].flag,trie[trie[u].fail].flag);
		for(int i=0;i<26;i++){
    
			int v=trie[u].son[i];
			int x=trie[u].fail;
			if(!v){
    
				trie[u].son[i]=trie[x].son[i];
			}else{
    
				trie[v].fail=trie[x].son[i];
				q.push(v);
			}
		}
	}
}
void query(char *s){
    
	int u=0,len=strlen(s);
	for(int i=0;i<len;i++)p[i]=0;
	for(int i=0;i<len;i++){
    
		int v=-1;
		if(s[i]>='A'&&s[i]<='Z')v=s[i]-'A';
		if(s[i]>='a'&&s[i]<='z')v=s[i]-'a';
		if(v==-1)u=0;
		else u=trie[u].son[v];
		if(trie[u].flag){
    
			p[i+1]--;
			p[i-trie[u].flag+1]++;
		}
	}
	int res=0;
	for(int i=0;i<len;i++){
    
		res+=p[i];
		if(res==0)putchar(s[i]);
		else putchar('*');
	}
	printf("\n");
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++){
    
			scanf("%s",s);
			insert(s);
		}
		getfail();
		getchar();
		scanf("%[^\n]",s);
		query(s);
	}
	return 0;
}
//D I K L 

D - Tea

The question ：
Lazy to write

Ideas ：
Classification of discussion
You should understand the code

Code ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+4;
int t,n;
ll l,r;
ll ans=0;
int main(){
    
	while(cin>>l>>r){
    
		ans=1e18;
		ll res=r-l;
		if(res<=3)ans=2;
		else ans=(res-3+1)/2+2;
		if(r<=2)ans=1;
		if(r<=1)ans=0;
		if(l==0)ans=min(ans,(r+1)/2);
		cout<<ans<<endl;
	}
	return 0;
}
//D I K L 

I - Tower Defence

The question ：
Here you are. $n$ A tree with edge weights of nodes ($n<=1e5$), Define to delete one edge at a time , The contribution to the answer is the larger value of the diameter of the two separate subtrees . Delete the contribution of each edge to the answer and .
Ideas ：
Let's consider it in two cases ：
If the deleted edge is not the edge on the diameter of the whole tree , Then the contribution to the answer is the diameter of the whole tree .
If the deleted edge is not the diameter of the whole tree , We take a larger value for the diameter of the subtrees on both sides .
We can easily prove that , After deleting an edge , The diameter of the subtree must start from the endpoint of the original diameter .（ If it's not the longest chain from the end , Then he will replace the chain at the end point , Add the original diameter ）.
Then we can preprocess to delete an edge on the diameter , The maximum diameter of the subtree , That is, for each point , Ask him how far he can stretch without passing through the diameter , Then do it left and right DP,$dp[i]=max(len,now+cnt)$, Finally, run again and add the larger diameter to the answer .
Code ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll n,t;
struct node{
    
	ll to,w;
};
vector<node>v[100040];
ll dep[100040];
bool vis[100040];
int root,root2;
ll sum=0;
ll ans=0;
ll res=0;
ll dp1[100040];
ll dp2[100040];
void dfs1(int x,int pre){
    
	if(dep[x]>dep[root])root=x;
	for(int i=0;i<v[x].size();i++){
    
		if(v[x][i].to==pre)continue;
		dep[v[x][i].to]=dep[x]+v[x][i].w;
		dfs1(v[x][i].to,x);
	}
}
void dfs2(int x){
    
	vis[x]=1;res++;
	for(int i=0;i<v[x].size();i++){
    
		if(dep[x]==dep[v[x][i].to]+v[x][i].w){
    
			dfs2(v[x][i].to);
		}
	}
}
ll cnt=0;
ll now=0;
ll lenn=0; 
void dfs4(int x,int pre,ll d){
    
	cnt=max(cnt,d);
	for(int i=0;i<v[x].size();i++){
    
		if(v[x][i].to==pre||vis[v[x][i].to])continue;
		dfs4(v[x][i].to,x,d+v[x][i].w);
	}
}
int f=0;
void dfs3(int x,int pre){
    
	cnt=0;
	if(f==0&&x!=root2){
    
		dfs4(x,0,0);
		dp1[x]=max(lenn,now+cnt);
		lenn=max(lenn,now+cnt);
	}
	if(f==1&&x!=root){
    
		dfs4(x,0,0);
		dp2[x]=max(lenn,now+cnt);
		lenn=max(lenn,now+cnt);
	}
	for(int i=0;i<v[x].size();i++){
    
		if(v[x][i].to==pre||vis[v[x][i].to]==0)continue;
		now+=v[x][i].w;
		dfs3(v[x][i].to,x);
	}
}
void dfs5(int x,int pre){
    
	if(x!=root2){
    
		ans+=max(dp1[pre],dp2[x]);
	}
	for(int i=0;i<v[x].size();i++){
    
		if(v[x][i].to==pre||vis[v[x][i].to]==0)continue;
		dfs5(v[x][i].to,x);
	}
}
int main(){
    
	scanf("%lld",&t);
	while(t--){
    
		scanf("%lld",&n);
		for(int i=1;i<n;i++){
    
			ll a,b,c;
			scanf("%lld%lld%lld",&a,&b,&c);
			v[a].push_back({
    b,c});
			v[b].push_back({
    a,c});
		}
		for(int i=1;i<=n;i++)vis[i]=0,dp1[i]=0,dp2[i]=0;
		root=0;
		dep[0]=0;
		dep[1]=0;
		dfs1(1,0);
		root2=root;
		dep[root]=0;
		dfs1(root,0);
		sum=dep[root];
		ans=0;res=0;
		dfs2(root);
		ans=1LL*sum*(n-res);
		now=0;lenn=0;
		f=0;
		dfs3(root2,0);
		f=1;
		now=0;lenn=0;
		dfs3(root,0);
		dfs5(root2,0);
		printf("%lld\n",ans);
		for(int i=1;i<=n;i++)v[i].clear();
	}
	return 0;
}
//K L 

K - Barricade

The question ：
Here you are. $n$ A little bit $m$ A graph of bars and edges , You need to stop from 1 To $n$ All the shortest circuits , Blocking each side has a price . Find the minimum cost of blocking the shortest circuit .
Ideas ：
At the time of the game , I thought of something that I didn't have DP Transfer , It turns out that it's not right .
Then it's actually a network flow naked question , As a Streaming Player , I didn't see it was wrong , You need to reflect on yourself .
Just buckle out the shortest circuit first , To block these roads is to stop them 1 Sum point $n$, In two parts , Typical minimum cut .
Code ：

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int t,n,m;
struct node{
    
	int to,w;
};
vector<node>v[1004];
int dis1[1004],dis2[1004];
queue<int>q;
struct edge{
    
	int to,cap,rev;
}; 
vector<edge>mp[1004];
int level[1004];// Distance label from vertex to source  
int iter[1004]; // Current arc , The edge before it is useless  
void add(int from,int to,int cap){
    
	mp[from].push_back({
    to,cap,mp[to].size()});
	mp[to].push_back({
    from,0,mp[from].size()-1});
}
void bfs(int s){
    
	memset(level,-1,sizeof(level));
	queue<int>q;
	level[s]=0;
	q.push(s);
	while(!q.empty()){
    
		int v=q.front();q.pop();
		for(int i=0;i<mp[v].size();i++){
    
			edge &e=mp[v][i];
			if(e.cap>0&&level[e.to]<0){
    
				level[e.to]=level[v]+1;
				q.push(e.to);
			}
		}
	}
	
}
int dfs(int v,int t,int f){
    
	if(v==t)return f;
	for(int &i=iter[v];i<mp[v].size();i++){
    
		edge &e=mp[v][i];
		if(e.cap>0&&level[v]<level[e.to]){
    
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
    
				e.cap-=d;
				mp[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
    
	int flow=0;
	while(1){
    
		bfs(s);
		if(level[t]<0)return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f=dfs(s,t,1e9))>0)flow+=f;
	}
    return flow;
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
    
			int a,b,c;scanf("%d%d%d",&a,&b,&c);
			if(a==b)continue;
			v[a].push_back({
    b,c});
			v[b].push_back({
    a,c});			
		}
		for(int i=1;i<=n;i++){
    
			dis1[i]=dis2[i]=1e9;
		}
		dis1[1]=0;
		while(!q.empty())q.pop();
		q.push(1);
		while(!q.empty()){
    
			int x=q.front();q.pop();
			for(int i=0;i<v[x].size();i++){
    
				if(dis1[v[x][i].to]>dis1[x]+1){
    
					dis1[v[x][i].to]=dis1[x]+1;
					q.push(v[x][i].to);
				}
			}
		}
		dis2[n]=0;
		q.push(n);
		while(!q.empty()){
    
			int x=q.front();q.pop();
			for(int i=0;i<v[x].size();i++){
    
				if(dis2[v[x][i].to]>dis2[x]+1){
    
					dis2[v[x][i].to]=dis2[x]+1;
					q.push(v[x][i].to);
				}
			}
		}
		for(int i=1;i<=n;i++){
    
			for(int j=0;j<v[i].size();j++){
    
				if(dis1[i]+dis2[v[i][j].to]+1==dis1[n]){
    
					add(i,v[i][j].to,v[i][j].w);
				}
			}
		}
		printf("%d\n",max_flow(1,n));
		for(int i=1;i<=n;i++)v[i].clear(),mp[i].clear();
	} 
	return 0;
} 
//K L 

L - Eighty seven

The question ：
Here you are. $n$ Number ($n<=50$), Each time, it is guaranteed not to take less than or equal to 3 On the premise of number , Ask if you can take ten numbers so that the sum of these ten numbers is 87;

Ideas ：
Violent backpack +bitset Optimize

Code ：

#include<bits/stdc++.h>
using namespace std;
bitset<90>s[11];
int a[51],f[51][51][51];
int n;
int solve(int x,int y,int z){
    
	for(int i=0;i<=10;i++)s[i].reset();
	s[0][0]=1;
	for(int i=1;i<=n;i++){
    
		if(i==x||i==y||i==z||a[i]>87)continue;
		for(int j=10;j>0;j--){
    
			s[j]|=s[j-1]<<a[i];
		}
	}
	return s[10][87];
}
int main(){
    
	int t;
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
		for(int i=1;i<=n;i++){
    
			for(int j=i;j<=n;j++){
    
				for(int k=j;k<=n;k++){
    
					f[i][j][k]=solve(i,j,k);
				}
			}
		}
		int m;
		scanf("%d",&m);
		while(m--){
    
			int b[3];
			scanf("%d%d%d",&b[0],&b[1],&b[2]);
			sort(b,b+3);
			if(f[b[0]][b[1]][b[2]])printf("Yes\n");
			else printf("No\n");
		}
	}
}