2022-7-4 personal qualifying 1 competition experience

Game link intranet ：10.7.95.2

Resource access control system

F topic （ original ）：

It is said that a god of death once gave an oracle on this demon guiding continent , If anyone can solve the problem left behind , It can protect its eternal life !. Given a length of n String S, Try selecting a continuous substring S[L~r], Satisfy 2<l<r<n And S[l~r] Is string S The prefix of , namely S[L~r] And S[1~r-1+1] Same meter . Ask what is the longest length of the continuous substring that can be selected to meet the conditions ？ Oh, yes. , Forgot to say , This continent is now the territory of the undead .

Input     Only a string consisting of lowercase letters S.1<|S|< 500000.

Output     An integer , Indicates the longest length .

The sample input

ababa

abcde

Sample output

3

0

The question ： Find the largest prefix of the string , This prefix has the same paragraph after the main string .

Experience ： At the beginning of this problem, I read it wrong , Directly mistaken for finding the maximum prefix next The board question of , But in fact, it is right to think about it carefully .（ That is to say, no matter where the same paragraph is ,next Can traverse ） It's a blind cat that meets a dead mouse （ Cry ）.

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e6+5;
char s[N];
int nxt[N];
int ma=-1;
void next(){
	int i=0,j=-1;
	nxt[0]=-1;
	while (i<strlen(s)){
		if (j==-1||s[i]==s[j]){
			i++;j++;
			nxt[i]=j;
			ma=max(j,ma);
		}
		else{
			j=nxt[j];
		}
	}
}
void work(){
	cin>>s;
	next();
	cout<<ma;
}
signed main(){
	CIO;
	work();
	return 0;
}

PS： The senior said that he could also use string hashing + Two points , Or suffix array .（ Neither of these has been learned ）

E topic ：blocks

Luogu P8185

In order to improve her vocabulary , cow Bessie I brought a set of four building blocks , Each building block is a cube , There is a letter written on each side . She is arranging the blocks in a row , Make the letters on the top of the building blocks spell words , To learn spelling . Given Bessie The letters on the four building blocks , And a list of words she wants to spell , Please judge which words in the list she can successfully spell with building blocks .

Input The first line contains N（1≤N≤10）, by Bessie The number of words you want to spell . The following four lines , Each line contains a string containing six uppercase letters , Express Bessie The letters on the six sides of a building block . following N Line inclusion Bessie Want to spell N Word . Each is composed of 1 To 4 A capital letter .

Output ："YES" or "NO"

The sample input

6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM

Sample output

YES
NO
YES
YES
NO
NO

The question ： Four six sided dice have a letter on each side ,q Time to ask , Can you spell the corresponding word

Experience ： I've been simulating it for a long time , Another bucket , And remember , Finally, I used pure violence , The code is very long , The positive solution should be search , You don't master your own search well .

Own code

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e6+5;
struct ss{
	char c[10];
}s[15];
int tong[10];
int t[10][10];
char w[10];
void work(){
	int n;cin>>n;
	rep(i,1,4){
		rep(j,1,6){
			cin>>s[i].c[j];
		}
	}
	rep(i,1,n){
		cin>>w;
		int len=strlen(w);
		memset(t,0,sizeof t); 
		rep(j,0,len-1){
			rep(k,1,4){
				rep(l,1,6){
					if (s[k].c[l]==w[j]){
						t[k][j+1]=1;
						break;
					}
				}
			}
		}
		int f=0;
		rep(a,1,len){
			rep(b,1,len){
				rep(c,1,len){
					rep(d,1,len){
						int ans=0;
						memset(tong,0,sizeof tong);
						tong[a]=1;tong[b]=1;tong[c]=1;tong[d]=1;
						rep(j,1,len){
							ans+=tong[j];
						}
						if (ans<len){
							continue;
						}
						if (t[1][a]+t[2][b]+t[3][c]+t[4][d]>=len&&f==0){
							cout<<"YES"<<endl;
							f=1;
						}
					}
				}
			}
		}
		if (f==0){
			cout<<"NO"<<endl;
		}
	}
}
signed main(){
	CIO;
	work();
	return 0;
}

scanf("%s",s+1） It can make s String from 1 Start reading .

H topic :Sleeping in Class

Luogu P8183

The question ： Give you an array , You can replace two adjacent numbers in this array with their sum , Let this be 1 operations , After how many operations , All numbers in the array are equal .

Input  

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

Output  

3
2
0

Experience ： Two points , There are many dichotomous questions used in this way , The core of the idea is to think of using dichotomy （doge）, The essence is to determine the answer based on dichotomy , Verify the answer again .

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e5+5;
int a[N];
int sum;
int n;
int check(int x){
	if (sum%x!=0)
		return false;
	int av=sum/x;
	int ans=0,i=0;
	while (i<=n){
		ans=0;
		while (ans<av&&i<=n){
			i++;
			ans+=a[i];
		}
		if (ans>av){
			return false;
		}
	}
	return true;
}
void work(){
	cin>>n;
	sum=0;
	rep(i,1,n){
		cin>>a[i];
		sum+=a[i];
	}
	if (sum==0){
		cout<<0<<endl;
		return;
	}
	nep(i,n,1){
		if (check(i)==true){
			cout<<n-i<<endl;
			break;
		}
	}
}
signed main(){
	CIO;
	int _;cin>>_;
	while (_--){
		work();
	}
	return 0;
}

J topic :Photoshoot 2

Luogu P8184

Title Description

In a familiar scene , Farmer John Is putting his N A cow (1<N<105) In a row ( Press them for convenience 1…N Number ), For taking pictures . first , Cows follow from left to right a1, a2,...,aN The order of .Farmer John Our goal is to follow b1,,bN Arrange the cows from left to right . So , He can make a series of changes to the order . Each time, select a cow and move it to the left . Please calculate the minimum number of modifications required for Farmer John to arrange the cows in the required order .

Input format

The first line of input contains N, The second line contains a1, a2,….,aN, The third line contains b1, b2,,bN

Output format

The output produces Farmer John The minimum number of modifications required for the required sequence .

Input  

5
5 1 3 2 4
4 5 2 1 3

Output  

2

The question ： Give two arrays , Array 1 The element of can be moved to the left by any lattice , Least mobile behavior , Make the two arrays equal .

Experience ： It is the first time to combine differential array in actual combat , I can't believe it when I pass , It's just that it's suddenly over .

Because after moving the grid , The element originally on the left moves to the right , It is equivalent to an interval plus one . Interval modification , Single point query , Then I thought of differential array .

#include <bits/stdc++.h>
#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
const int N=2e5+5;
int a[N],b[N],af[N];
int d[N];
int n;
int lowbit(int x){
	return x&(-x);
}
void add(int x,int b){
	while (x<=n){
		d[x]+=b;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while (x){
		ans+=d[x];
		x-=lowbit(x);
	}
	return ans;
}
void work(){
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
		af[a[i]]=i;
	}
	rep(i,1,n)
		cin>>b[i];
	int cnt=0;
	rep(i,1,n){
		if (af[b[i]]+query(af[b[i]])!=i){
			add(1,1);
			add(af[b[i]],-1);
			cnt++;
		}
	}
	cout<<cnt;
}
signed main(){
	CIO;
	work();
	return 0;
}

Above are the four questions made in the exam .

Supplementary questions can be filled ：

K:Reincarnated MOO An original question , Thinking and F The same way , String hash + Two points

I:Photoshoot Thinking questions , Even numbers become 01 Array

L:Visits It is related to whether the graph has a ring

A:Subset Equality String puzzle .（ I didn't understand the idea ）

B:Redistributing Gifts Clever solutions can become Floyd The illustration .（ The example is given to 500 Can be associated n^3 Complexity ）