2022-7-5 personal qualifying 2 competition experience

Game link intranet ：10.7.95.2

Resource access control system

List of topics and number of questions （ This focus IJ Stuck for a long time ）：

B:Why Did the Cow Cross the Road V - Max Cross

Farmer John There are N A pedestrian crossing , The number is 1…N (1≤N≤100,000). In order to let cows pass on these crosswalks ,FJ Electronic cross signal lamp is installed , When cows can pass , The signal light will light up the green cow icon , Otherwise, it will light red . Unfortunately , A big electromagnetic storm damaged some of his signals . List of given damage signals , Please calculate FJ The minimum number of semaphores that need to be repaired , So that there is a length of K Continuous numbered signal lights .

The first line contains N, K, B.

Next B That's ok , Each line is given the number of the damaged signal lamp .

Output the minimum number of semaphores that need to be repaired , So that there is a length of K Continuous numbered signal lights .

Sample Input

10 6 5 2 10 1 5 9

Sample Output

1

Ideas ： Two points

#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],d[N],ds[N];
int n,k,b;
int check(int x){
	x++;
	for (int i=1;i<=b-x+2;i++){
		if (ds[i+x-1]-ds[i-1]+(x-1)>=k){
			return true;
		}
	}
	return false;
}
void work(){
	cin>>n>>k>>b;
	a[0]=0;
	rep(i,1,b){
		cin>>a[i];
	}
	sort(a+1,a+b+1);
	rep(i,1,b){
		d[i]=a[i]-a[i-1]-1;
	}
	d[b+1]=n+1-a[b]-1;
	rep(i,1,b+1){
		ds[i]=ds[i-1]+d[i];
	}
	int l=0,r=b,mid;
	while(l<=r){
		mid=(l+r)/2;
		if (check(mid)==true){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l;
}
signed main(){
	CIO;
	work();
	return 0;
}

M:Angry Cows II

Bessie Designed a new game : Angry Cows. In this game , Players launch cows , When each cow lands, it detonates hay in a certain range . The goal of the game is to use a group of cows to detonate all the hay .N Bales of hay are arranged in different positions on the number axis . The first i The position of hay bale is ci. If a power is R My cow is z Position landing , She will detonate [z-R,x+R] All hay in the range . You can now launch K A cow , The power of every cow is R, Now you need to make sure R The minimum value of , Make use of K A cow can detonate all hay .

The first line has two integers N, K (1<N<5x 104, 1<K<10). Next N That's ok , The first i Line an integer z; (0<ci<109)

Output an integer , namely R  The minimum value of .

Sample Input

7 2 20 25 18 8 10 3 1

Sample Output

5

Ideas ： It's also two points

#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 n,k;
int check(int x){
	int ans=a[1];
	rep(i,1,k){
		ans+=2*x;
		if (ans>=a[n]){
			return true;
		}
		ans=*upper_bound(a+1,a+n+1,ans);
	}
	return false;
}
void work(){
	cin>>n>>k;
	rep(i,1,n){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int l=1,r=N,mid;
	while (l<=r){
		mid=(l+r)/2;
		if (check(mid)==true){
			r=mid-1;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l;
}
signed main(){
	CIO;
	work();
	return 0;
}

I:Subsequences Summing to Sevens

Here you are. n Number , Namely a[1],a[2],...,a[n].

Find the longest interval [x,y], Make the number in the interval (a[x],a[x+1],a[x+2],...,a[y-1],a[y]) And can be 7 to be divisible by .

Output the longest interval length .n (1≤n≤50,000)

If there is no interval that meets the requirements , Output 0.

Sample Input

7 3 5 1 6 2 14 10

Sample Output

5

Ideas ： Use prefix and maintenance to time complexity O(n^2), Then I found three samples , obviously n^2 It was already 1e9 了 .（ I've been thinking about missing the constant card during the exam , I didn't expect to move the essence ） There have been similar problems before .

Encounter interval and related to remainder , The prefix is equal to the value of the array obtained after modulo , It means that the middle segment can be divisible . Then it can be optimized to O（N).

Through two additional arrays , Then sweep both sides to the left and right ends of the longest interval , You can get the answer .

The key is prefix and further optimization .

#include <bits/stdc++.h>
#define CIO std::ios::sync_with_stdio(false)
#define int long long
#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=1e5+5;
int a[N],s[N];
int bgin[N],endd[N]; 
int n;
void work(){
	int ma=-1;
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&a[i]);
		s[i]=(s[i-1]+a[i])%7; 
	}
	rep(i,1,n){
		if (bgin[s[i]]==0)
			bgin[s[i]]=i;
	}
	rep(i,1,n){
		endd[s[i]]=i;
	}
	rep(i,1,n){
		ma=max(ma,endd[i]-bgin[i]);
	}
	cout<<ma;
}
signed main(){
	work();
	return 0;
}

J:There is no "Why Did the Cow Cross the Road I&II&III" here, only Emergency Dispatch

The cow is Farmer John Eat grass on our farm , But because they ate too much mysterious food during the party in the cow pen last night , Now all cows want to spray . Cows are civilized and polite , So every cow wants to find the nearest hut . A known farm can be expressed as a nxm Grid graph of , Each thatched cottage can accommodate unlimited cows at the same time , Every cow can move around every second ( On 、 Next 、 Left 、 Right ) Run a grid in any direction , The same location can accommodate unlimited cows at the same time , But they can't run to the straw pile . The emergency dispatch is very difficult Farmer John, After all, this is a mental job . So please help him , Ask if every cow runs to the nearest hut , How many seconds does it take to get all the cows to the hut ? Of course , Maybe some cows are trapped in straw circles and can't move , So please find out how many cows can only be forced to solve on the spot .

The first line contains two positive integers n,m, It means the length and width of the farm respectively . then n That's ok , Each row m Characters , It means farm , Which character W It means a thatched cottage , character C It means a cow , character , Represents an open space ( You can go through ), character # It means straw pile ( You can't go through ) The data ensure that there is at least one cow on the farm , And at least one thatched cottage , But the total number of thatched cottages will not exceed 100 between .4<n,m < 1000

Output two integers , Space off , The minimum number of seconds required for all cows to reach the nearest thatched cottage and the number of cows to be solved on site . If all cows can't reach any thatched cottage , Seconds output -1.

The question ： Multiple BFS.

Ideas ： Because the number of thatched cottages is small , So start with the thatched cottage , then BFS. But found TL 了 , The positive solution is all thatched cottages together BFS Because I met first vis It must be smaller than the thatched cottage at this point in the back , In fact, in a sense, it is memorization .

#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=1e3+5;
int n,m;
struct maoce{
	int x,y;
}c[200];
char s[N][N];
int vis[N][N];
int cow[N][N];
struct node{
	int x;
	int y;
	int temp;
};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
queue<node> q;
int cnt=0;
void bfs(){
	while(!q.empty()) q.pop();
	rep(i,1,cnt){
		q.push({c[i].x,c[i].y,0});
		vis[c[i].x][c[i].y]=1;
	}
	while (!q.empty()){
		int x=q.front().x;
		int y=q.front().y;
		int t=q.front().temp;
		q.pop();
		for (int i=0;i<4;i++){
			int xx=x+dx[i];
			int yy=y+dy[i];
			if (vis[xx][yy]!=1&&xx>=1&&xx<=n&&yy>=1&&yy<=m){
				if (s[xx][yy]=='.'){
					vis[xx][yy]=1;
					q.push({xx,yy,t+1});
				}
				if (s[xx][yy]=='C'){
					cow[xx][yy]=min(cow[xx][yy],t+1);
					vis[xx][yy]=1;
					q.push({xx,yy,t+1});
				}
			}
		}
	}
}
void work(){
	cin>>n>>m;
	rep(i,1,n){
		rep(j,1,m){
			cow[i][j]=INT_MAX;
		}
	}
	rep(i,1,n){
		rep(j,1,m){
			cin>>s[i][j];
			if (s[i][j]=='W'){
				c[++cnt].x=i;
				c[cnt].y=j;
			}
		}
	}
	int mei=0,ma=-1,zhi;
	bfs();
	rep(i,1,n){
		rep(j,1,m){
			if (s[i][j]=='C'){
				if (cow[i][j]==INT_MAX){
					mei++;
				}
				else{
					ma=max(ma,cow[i][j]);
				}
			}
		}
	}
	cout<<ma<<" "<<mei;
}
signed main(){
	CIO;
	work();
	return 0;
}

C topic ： I am also a search question , Don't take it out .

A topic ： greedy , I took it for granted with a ruler , It's actually n^2（sort Don't get used to writing n+1）