Solution to the third game of 2022 Niuke multi school league

The race portal
author ： fn

---

Sign in problem

C topic Concatenation / Connect

The main idea of the topic
Given $n$ A string , Put them together .
The scheme of finding the smallest lexicographic order of the result .$1\le N\le 2\ast 10^6$

Investigation contents
Sort , Complexity optimization

analysis
The solution is not unique .

One $O(nlogn)$ How to do it ： direct sort Sort .

Optional constant optimization ：

1. When defining string Size .
2. Use quick read .

#include<bits/stdc++.h>
using namespace std;
string s[int(2e6+5)];
bool cmp(string &a,string &b){
    
	return a+b<b+a;
}
int main(){
    
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>s[i];
	sort(s,s+n,cmp);
	for(int i=0;i<n;i++)
		cout<<s[i];
	return 0;
} 

---

Basic questions

A topic Ancestor / The ancestors

The main idea of the topic
Give two node numbers $1-n$ The tree of A、B,A、B Each node in the tree has a weight , give $k$ Number of key points $x_1\dots x_n$ .
Ask how many options , Make it possible to remove exactly one key so that the remaining keys are in the tree A On LCA The weight of is greater than that of the tree B On LCA A weight .

Investigation contents
lca,dfs order , simulation

analysis
The template questions .
Known multiple nodes lca Namely dfs Order the first node and the last node lca.
Pretreatment is good dfs order , The first two nodes , The last two nodes , Then enumerate the deleted nodes , Add up the answers .

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+5;
ll n,m,k,a[N],pa[N],b[N],pb[N];
ll x[N];

vector<int> ga[N],gb[N];
int dfs_[200020],len;

void dfsa(int u,int fa){
    
    dfs_[++len]=u;  
    int sz=ga[u].size();
    for(int i=0;i<sz;i++){
    
        if(ga[u][i]!=fa){
    
            dfsa(ga[u][i],u);
        }
    }
}

void dfsb(int u,int fa){
    
    dfs_[++len]=u;  
    int sz=gb[u].size();
    for(int i=0;i<sz;i++){
    
        if(gb[u][i]!=fa){
    
            dfsb(gb[u][i],u);
        }
    }
}

ll xa1=-1,xa2=-1,xa3=-1,lastxa=-1;
ll xb1=-1,xb2=-1,xb3=-1,lastxb=-1;
map<int,bool> mp;

int h[N],e[N*2],ne[N*2],idx;
int f[N][21];
int d[N];
void add(int a,int b) //  Save edge 
{
     
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void bfs(int u)  //  Preprocessing 
{
    
    queue<int> q; q.push(u),d[u] = 1;
    while(!q.empty()){
    
        int x = q.front(); q.pop();
        for(int i=h[x]; ~i; i = ne[i]){
    
            int y = e[i];
            if(d[y]) continue;          //  Updated points   No need to update 
            d[y] = d[x]+1;
            f[y][0] = x; 
            for(int j = 1; j<=20; j++)  //  I'm lazy here   Didn't write log Determine the highest height of the tree 
                f[y][j] = f[f[y][j-1]][j-1];
            q.push(y);                  //  Put the current point into   In line 
        }
    }
}

int lca(int a,int b){
     //  seek a,b Of lca 
    if(d[a]<d[b]) swap(a,b);
    for(int i=20; i>=0; i--)
        if(d[f[a][i]]>=d[b])  //  Find and b Nodes of the same height 
            a = f[a][i];
    if(a==b) return a;
    for(int i=20; i>=0; i--)
        if(f[a][i]!=f[b][i]) a= f[a][i],b = f[b][i]; //  Look up for places with common roots 
    
    return f[a][0];
}

ll ansa[N]; 
ll ansb[N];

int main(){
    
	memset(h, -1, sizeof h);  //  Initializing the header node 
	
	cin>>n>>k; //  Every tree n Nodes ,k Two key nodes  
	for(int i=1;i<=k;i++){
    
		cin>>x[i]; //  Given k Two key nodes 
		mp[x[i]]=1; 
	}
	
	//  Enter two trees  
	for(int i=1;i<=n;i++){
    
		cin>>a[i];
	}	
	for(int i=1;i<=n-1;i++){
    
		cin>>pa[i];
	}	
	for(int i=1;i<=n;i++){
    
		cin>>b[i];
	}	
	for(int i=1;i<=n-1;i++){
    
		cin>>pb[i];
	}
	
	
	len=0;
    for(int i=1;i<=n-1;i++){
    
        int from,to;
        from=i+1; to=pa[i];
        
        ga[from].push_back(to);
        ga[to].push_back(from);
        
        add(from,to); add(to,from); //  Two way side 
    }
    
    bfs(1); //  Yes a The tree goes on lca Preprocessing , Root is 1 
        
	dfsa(1,0);
    
    for(int i=1;i<=len;i++){
    
        if(mp[dfs_[i]]){
    
        	if(xa1==-1){
    
        		xa1=dfs_[i]; //  Record a Of dfs The first in the preface x 
        	}
        	else if(xa2==-1){
    
				xa2=dfs_[i]; //  Record a Of dfs Second in the preface 2 individual x 
				break;
			}
        }
    }
    for(int i=len;i>=1;i--){
    
        if(mp[dfs_[i]]){
    
        	if(lastxa==-1){
    
        		lastxa=dfs_[i]; //  Record a Of dfs The last one in the preface x 
        	}
        	else if(xa3==-1){
    
				xa3=dfs_[i]; //  Record a Of dfs The penultimate in the sequence 2 individual x 
				break;
			}
        }
    }
	
	ll t1=a[lca(xa1,lastxa)]; //  On both sides lca Weight of nodes 
	for(int i=1;i<=k;i++){
     //  Enumerate and delete each node  
		if(x[i]==xa1){
    
			ansa[i]=a[lca(xa2,lastxa)];
		}
		else if(x[i]==lastxa){
    
			ansa[i]=a[lca(xa1,xa3)];
		}
		else{
     //  Delete an intermediate node ,lca The value is on both sides lca Weight of nodes  
			ansa[i]=t1;
		}
	}
	
	//  initialization  
	memset(h, -1, sizeof h);  //  Initializing the header node 
	memset(e,0,sizeof e);
	memset(ne,0,sizeof ne);
	idx=0;
	memset(f,0,sizeof f);
	memset(d,0,sizeof d);
    
	len=0;
    for(int i=1;i<=n-1;i++){
    
        int from,to;
        from=i+1; to=pb[i];
        
        gb[from].push_back(to);
        gb[to].push_back(from); //  Two way side  
        
        add(from,to); add(to,from); //  Two way side 
    }
    bfs(1); //  Yes b The tree goes on lca Preprocessing , Root is 1 
    
	dfsb(1,0);
	
    for(int i=1;i<=len;i++){
    
        if(mp[dfs_[i]]){
    
        	if(xb1==-1){
    
        		xb1=dfs_[i]; //  Record b Of dfs The first in the preface x 
        	}
        	else if(xb2==-1){
    
				xb2=dfs_[i]; //  Record b Of dfs Second in the preface 2 individual x 
				break;
			}
        }
    }
    for(int i=len;i>=1;i--){
    
        if(mp[dfs_[i]]){
    
        	if(lastxb==-1){
    
        		lastxb=dfs_[i]; //  Record b Of dfs The last one in the preface x 
        	}
        	else if(xb3==-1){
    
				xb3=dfs_[i]; //  Record b Of dfs The penultimate in the sequence 2 individual x 
				break;
			}
        }
    }
    
	t1=b[lca(xb1,lastxb)]; //  On both sides lca Weight of nodes 
	for(int i=1;i<=k;i++){
     //  Enumerate and delete each node  
		if(x[i]==xb1){
    
			ansb[i]=b[lca(xb2,lastxb)];
		}
		else if(x[i]==lastxb){
    
			ansb[i]=b[lca(xb1,xb3)];
		}
		else{
     //  Delete an intermediate node ,lca The value is on both sides lca Weight of nodes  
			ansb[i]=t1;
		}
	}
	
	//  There are many points on the tree LCA, Namely DFS The sum of the smallest order DFS The two points with the largest order LCA.
	ll ans=0; //  The answer is to delete a number of solutions 
	
	for(int i=1;i<=k;i++){
     //  Enumerate and delete each node  
		if(ansa[i]>ansb[i]){
    
			ans++;
		}
	}
	
	cout<<ans<<endl;
}
/* 5 3 5 4 3 6 6 3 4 6 1 2 2 4 7 4 5 7 7 1 1 3 2 */ 

---

Advanced questions

J topic Journey / travel

The main idea of the topic
Given several intersections , You don't need to wait for the red light to turn right , Go straight 、 Both left turn and U-turn need to wait for a red light .
Please wait for the red light at least several times from the beginning to the end .

Investigation contents
Shortest path ,dijkstra Algorithm , deque bfs

analysis
Method 1 （ More intuitive ）：
Think of every road as a point , At the intersection , Form an edge weight of 0/1 The directed graph of . then dijkstra Algorithm for the shortest path .

Method one code ：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tup;
const int N = 1000005;
int n, m, cross[N][4], dis[N][4];
bool vis[N][4];
unordered_map<int, int> id[N];
int st1, st2, en1, en2;
int main() {
    
    ios::sync_with_stdio(false), cin.tie(0);
    //  Read in the data  
    cin >> n;
    for (int i = 1; i <= n; i++) {
    
        for (int j = 0; j < 4; j++) {
    
            cin >> cross[i][j];
            if (cross[i][j]) id[i][cross[i][j]] = j;
        }
    }
    cin >> st1 >> st2 >> en1 >> en2;
    
    memset(dis, 0x3f, sizeof(dis));
    int idx = id[st2][st1];
    dis[st2][idx] = 0;
    priority_queue<tup, vector<tup>, greater<tup>> PQ;
    
    tup t0(0, st2, idx);
    PQ.push(t0);
// PQ.push({0, st2, idx});
    
	while (!PQ.empty()) {
    
     	tup t1=PQ.top();
		int d=get<0>(t1), u=get<1>(t1), x=get<2>(t1);
	// auto [d, u, x] = PQ.top();
        
        PQ.pop();
        if (vis[u][x]) continue;
        vis[u][x] = true;
        for (int i = 0; i < 4; i++) {
    
            int delta = (i != (x + 1) % 4);
            int v = cross[u][i];
            if (!v) continue;
            int j = id[v][u];
            if (d + delta < dis[v][j]) {
    
                dis[v][j] = d + delta;
                
				tup t2(dis[v][j], v, j);
				PQ.push(t2);
			// PQ.push({dis[v][j], v, j});
            }
        }
    }
    int ans = dis[en2][id[en2][en1]];
    if (ans > n * 4) {
    
        ans = -1;
    }
    cout << ans; 
}

Method 2 （ faster ）：
No mapping , Use a double ended queue directly on the given data BFS solve , Use one deque Maintenance queue .

Method 2 code ：

#include<bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int maxn=5e5+7;
struct node{
    int x,y,step;};
int n,sx,sy,tx,ty,ans,p[5];
int v[maxn][4],mp[maxn][4];

int main(){
    
	//  Read in the data  
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=0;j<4;j++){
    
			cin>>v[i][j];
			mp[i][j]=maxn;
		}
	cin>>sx>>sy>>tx>>ty;
	
	deque<node> q; //  deque  
	q.push_front({
    sx,sy,0});
	while(q.size()){
    
		node n1=q.front();
		int x=n1.x, y=n1.y, step=n1.step;
		
		q.pop_front();
		if(y==0)
			continue;
		int j;
		for(int i=0;i<4;i++){
    
			if(v[x][i]!=y)
				continue;
			j=i;
		}
		if(mp[x][j]<=step)
			continue;
		else
			mp[x][j]=step;
		for(int i=0;i<4;i++){
    
			if(v[y][i]!=x)
				continue;
			j=(i+1)%4; //  Turn right  
		}
		for(int i=0;i<4;i++){
    
			if(i==j)
				q.push_front({
    y,v[y][i],step}); //  Turn right and put it in front of the queue  
			else
				q.push_back({
    y,v[y][i],step+1}); //  Steps in other directions +1, And put it behind the queue  
		}
	}
	
	for(int i=0;i<4;i++)
		if(v[tx][i]==ty)
			ans=mp[tx][i];
			
	if(ans==maxn)
		ans=-1;
	cout<<ans<<"\n";
	return 0;
}

---

H topic Hacker / hackers

The main idea of the topic
Given length is $n$ Lowercase string of $A$ and $k$ A length of $m$ Lowercase string of $B_1\dots B_k$ ,$B$ Each position of has a unified weight $v_1\dots v_m$ .

For each $B_i$ Find the maximum interval sum , The string formed by this interval is $A$ The string of . Empty interval method .

Investigation contents
string matching , Postfix automaton , The maximum interval and

analysis
We can transform the problem , It's equivalent to $B_i$ Find it as the end position in $A$ The longest substring length in , Then find the maximum sub segment sum in this interval , The maximum value of all positions is the answer .
For the longest substring of each position , It can be done to $A$ Build a suffix automaton , then $B_i$ From left to right in $A$ The suffix of automata is transferred , If the current node cannot be transferred, skip to the parent node , Finally, if it cannot be transferred, the length is 0, If the transfer is successful, it is the maximum length of the node before the transfer +1.

Suffix automata gate

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=1e6+5,maxm=1e6+5;
struct ad{
    
	int ch[26],len,fa;
}node[maxn];
int n,m,k,lst=1,tot=1,b[maxn];
char s[maxn],a[maxm];
inline int read(){
    
	int d=0,f=0,c=getchar();
	for(;c<48||c>57;c=getchar()) f|=c=='-';
	for(;c>47&&c<58;c=getchar()) d=(d<<1)+(d<<3)+(c^48);
	return f?-d:d;
}
void add(int x){
    
	int p=lst,np=lst=++tot,q,nq;
	node[np].len=node[p].len+1;
	for (;p&&!node[p].ch[x];p=node[p].fa) node[p].ch[x]=np;
	if (!p) node[np].fa=1;
	else{
    
		q=node[p].ch[x];
		if (node[q].len==node[p].len+1) node[np].fa=q;
		else{
    
			nq=++tot;node[nq]=node[q];node[nq].len=node[p].len+1;
			for (;p&&node[p].ch[x]==q;p=node[p].fa) node[p].ch[x]=nq;
			node[q].fa=node[np].fa=nq;
		}
	}
}
int main(){
    
	//  Read in the data  
	n=read();m=read();k=read();
	scanf("%s",s+1);
	for (int i=1;i<=n;++i) add(s[i]-'a');
	for (int i=1;i<=m;++i) b[i]=read();
	
	while (k--){
    
		scanf("%s",a+1);
		ll ans=0,sum=0,p=1;
		for (int i=1;i<=m;++i){
    
			if (sum+b[i]>=0&&node[p].ch[a[i]-'a']){
    
				p=node[p].ch[a[i]-'a'];
				sum+=b[i];
			} 
			else{
    
				p=1;
				sum=0;
			} 
			ans=max(ans,sum);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

---