Portal


Main idea of the title:
There are t groups of samples,
Each group has n numbers. You can add any positive integer of unlimited size after n numbers. So that the average of all numbers is 1.

Idea:
For classified discussion, when the sum of N numbers is n, there is no need to add any numbers.
When the sum of N numbers is less than N, an integer can be added so that the sum of n+1 numbers is n+1, so the answer is 1
When the sum of N numbers is greater than N, add 0 at the end until the meaning of the question is met, so the answer is n-ans

code:

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

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 1,x;i <= n;++i) {
        cin >> x;
        ans += x;
    }
    if(ans < n) cout << 1 << endl;
    else if(ans == n) cout << 0 << endl;
    else cout << ans-n << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Topic summary:
Thinking water problem

Portal

Main idea of the title:
There are t groups of samples, with four numbers in each group, n,m,x,y;
The matrix representing n*m has a person in the position of x and y.
Place 2 balls in the matrix and ask where the two balls should be placed in order to get the largest number of steps for the person to pick up the two balloons and return to the original position. This man can only walk up, down, left and right.

Idea:
If a balloon is placed first, it will be placed farthest from the current person's position.
When a person reaches that position, the farthest position from that position is the position of another balloon.
So enumerating four endpoints can get the result.

code:

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

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

void solve()
{
    int n,m,x,y;
	cin >> n >> m >> x >> y;
	int ans1 = fabs(n-x)+fabs(m-y);
	int ans2 = fabs(1-x)+fabs(m-y);
	int ans3 = fabs(n-x)+fabs(1-y);
	int ans4 = fabs(1-x)+fabs(1-y);
	int ma = max(ans1,max(ans2,max(ans3,ans4)));
	if(ma == ans1 || ma == ans4) {
		cout << n << ' ' << m << ' ' << 1 << ' ' << 1 << endl;
 	}
	else {
		cout << 1 << ' ' << m << ' ' << n << ' ' << 1 << endl;
	} 
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Topic summary:
Thinking water problem

Portal

Main idea of the title:
There are t groups of samples,
Each group of examples gives n values. If there is (1 < = I < n) such that hi < hi + 1, record it as a lucky point and ask the order of the most lucky points when the difference between the first number and the last number is the smallest.

Idea:
First, sort all the values, so we can find and confirm the first and last numbers. Then start from the position of the first number and output to the last, and then output from a[1] to the position of the last number. We can prove that in general, we will get two ascending sub segments and one largest fault, which is the case where we can get the most lucky points.

code:

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

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

const int maxn = 2e5+10;
int a[maxn];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;++i) {
        cin >> a[i];
    }
    sort(a+1,a+1+n);
    int mi = 0x3f3f3f3f,cn = 0;
    for(int i = 2;i <= n;++i) {
        if(a[i]-a[i-1] < mi) {
            mi = a[i]-a[i-1];
            cn = i;
        }
    }
    cout << a[cn-1] << ' ';
    for(int i = cn+1;i <= n;++i) {
        cout << a[i] << ' '; 
    }
    for(int i = 1;i < cn-1;++i) {
        cout << a[i] << ' ';
    }
    cout << a[cn] << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Topic summary:
Thinking water problem

Portal


Main idea of the title:
There are t groups of samples, each with an integer n
Two people take turns to subtract the divisor of the current number (excluding 1 and themselves)
Both men are smart enough to ask who will win given a number

Idea:
Game problem, two people will have a unified split number standard.
First of all, for the analysis of numbers, it is not difficult to find that if the numbers are divided into even numbers multiplied by a prime number, they will be divided into odd numbers multiplied by the current prime number, which guarantees that the current person will win the game. We find that the results of odd prime and even prime multiplication are deterministic.
Secondly, we need to analyze the special prime number 2. If it is not to the nth power of 2, the multiplied prime number must not be 2 and can not be judged. For the n-th power of 2, we find that to the odd power of 2, the first person loses and to the even power, the first person wins.
Draw a conclusion.

code:

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

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

void solve()
{
    int n;
    cin >> n;
    bool si = true;
    for(int i = 2;i <= sqrt(n);++i) {
        if(n%i == 0) {
            si = false;
            break;
        }
    }
    if(si) {
        cout << "Bob" << endl;
        return ;
    }
    int m = n,cnt = 0;
    while(m%2 == 0) m/=2,cnt++;
    if(m == 1) {
        if(cnt%2 == 1) cout << "Bob" << endl;
        else cout << "Alice" << endl;
        return ;
    } 
    if(n%2 == 1) {
        cout << "Bob" << endl;
    }
    else 
        cout << "Alice" << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Topic summary:
Game problems are representative ones.
The analysis of numbers should be sensitive.

Portal


Main idea of the title:
Given a string s with a length of n, two operations can be performed on S:
s.pop_back(),s= s+s;
Ask the string with the smallest dictionary order and the length of k

Idea:
Traverse from front to back. If the current position is the same as the first position, we think it is copied from one position for the time being, and then traverse backward. If the current position is greater than the character of the corresponding position, we get the minimum s of s=s+s, which can be output to the k-th position circularly. If it is less than the corresponding position, we will match the first position from the current position again. It can be proved that the string obtained by the minimum update substring is the smallest string.

code:

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

#define LL long long
map<int,int> mp;
int main()
{
    int n,k;
    cin >> n >> k;
    int index = 0;
    string s;
    cin >> s;
    string ans = "";
    ans += s[0];
    for(int i = 1;i < s.length();++i) {
        if(s[i] > ans[index])
            break;
        ans += s[i];
        if(s[i] == ans[index]) 
            index++;
        else 
            index = 0;
    }
    while(index != 0) {
        ans.pop_back();
        index--;
    }
    for(int i = 0;i < k;++i) 
        cout << ans[i%ans.length()];
    cout << endl;
}

Topic summary:
The data range of E1 and E2 is different, and the idea of problem solving is the same. For small data, we can match by intercepting strings. Matching one by one is an optimization of complexity.