I went to the hospital in the afternoon. I could only finish the sign in question of the competition over there. It's really uncomfortable that I can't do two questions without making up and solving them now

codeforce 1551 B2 title link: Click here to transfer

Meaning: give n elements and their numbers, as well as the types and numbers of pigments. Ask you to color them as much as possible
1. Elements with the same number cannot be painted with the same color
2. The quantity of each color must be the same (not counting those not colored)
The number of colors given cannot exceed 3

Idea:
Construct a structure and record their color, number and type (self-defined)
First, count the number of each category. For those less than or equal to K, their category is the color number, and for those greater than k, their category is 0, that is, they are not colored. Then sort according to the original number of the whole array.
After that, set the element color of n%k, that is, the part that cannot be divided by K, to 0. Next, dye the elements every k time. Since the previous operation has ensured that there will be no duplicate color and residual, the final structure must be legal.
Finally, sort according to the original number and output their colors

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
int t,n,k;
struct node{
    int id;//number
    int val;//type
    int color;//colour
}a[MAXN];
bool cmp1(node a,node b){return a.val<b.val;}
bool cmp2(node a,node b){return a.id<b.id;}//reset
int color[MAXN];
map <int ,int >mp;
//Construct a structure to store the color, starting order and type of each box.
//First, count the number of each kind, change the number of more than k blocks into 0, and then sort the whole array according to the number of blocks
//Then change the number of the remaining squares that cannot be divided into whole numbers to 0, traverse the array, and do not color the squares with number 0 (= 0)
//After that, the blocks are colored every k time, and finally reordered and output according to the initial order of the blocks.

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
       memset(a,0,sizeof(a));
       mp.clear();
       cin>>n>>k;//Type of color
       int N=n;int temp=0;
       for(int i=1;i<=n;i++)
       {
           cin>>a[i].val;
           a[i].id=i;
           mp[a[i].val]++;
           if(mp[a[i].val]>k) //There are too many of the same kind. You must not color it
           {
               a[i].val=0;
               N--;
           }
       }
        temp=N%k;//The actual amount of coloring should be% less k
        sort(a+1,a+1+n,cmp1);
        int cnt=1;
        for(int i=1;i<=n;i++)
        {
            if(a[i].val==0) a[i].color=0;//Previously marked non colored squares
            else if(temp>0)//What's the remainder
            {
                a[i].color=0;
                temp--;
            }
            else //Every k time a cycle of coloring, because too many kinds of cases have been handled before, it can certainly ensure the legitimacy
            {
                a[i].color=cnt;
                cnt++;
                if(cnt>k) cnt=1;
            }
        }

        sort(a+1,a+1+n,cmp2);
        for(int i=1;i<=n;i++) cout<<a[i].color<<" ";
        cout<<endl;
    }

    return 0;
}

Question K of red wine competition

Meaning:
Give n and a string of strings. This string is an incremental arrangement from 1 to N, but one number is missing. You are required to find the less number.
Idea:
There are many ways to write illegal cases in the middle of the way. You can find them directly, or cut sub strings and compare them with the table typed in advance. However, if n is less, it means that the string is legal (at least the program thinks so), and no number will be output. This special judgment was written at that time. Unexpectedly, it was stuck for three times. It's a pity.

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int a[105];
string ans[105];
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int cnt = 1;
	int step = 1;
	int pos = 1;
	cin >> n;
	cin >> s;
	for (int i = 1; i <= 100; i++)
	{
		ans[i] = to_string(i);
	}
	for (int i = 0; i < s.length(); i += pos)
	{
		string temp = s.substr(i, step);
		if (temp != ans[cnt])
		{
			cout << cnt;
			return 0;
		}
		cnt++;
		if (cnt == 10) step = 2;
		if (cnt == 11) pos = 2;
		if (cnt == 100) step = 3;
		if (cnt == 101) pos = 3;
	}
	cout << n;
	return 0;
}

Question M of red wine competition

Meaning:
There are n judges in total. They can give a maximum of 3 points and a minimum of - 3 points. The results of m judges have been given, so you can ask for the highest and lowest possible points at this stage
Idea:
Too lazy to force

#include<bits/stdc++.h>
using namespace std;
double n, m;
double a[105];

int main()
{
	//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	double max_val = n * 3-0.0;
	double min_val = n * (-3)-0.0;
	for (int i = 1; i <= m; i++)
	{
		double temp;
		cin >> temp;
		temp /= 1.0;
		max_val = max_val - (3 - temp);
		min_val = min_val + (temp + 3);
	}
	printf("%lf %lf", min_val / n + 0.0, max_val / n + 0.0);
	return 0;
}

Question P of the red wine competition

This question is still very interesting. During the game, I saw that the range of n was nodding for a while. Later, I saw that the range of buying data suddenly turned around and found a map container.
Meaning:
A group has n members, and one day these members will send m messages. These team members are lazy dogs who don't read messages. They only empty unread messages (including their own messages) when they send messages. Enter line m, the content is the number of the group member sending the message, and output line m, which requires you to calculate the number of unread messages of all people in the whole group after a group member sends the message.
Idea:
Define a map container. The content stored in it is the number of rounds of the last operation of the member with this number. This will clear his unread messages before he sends them. The specific operation is sum - = cnt MP [i]. After he sends the message, sum is accumulating n-1.

#include<bits/stdc++.h>
using namespace std;
int n, m;
long long sum = 0;
map <int, int> mp;//What round is the last emptying operation of a number
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int cnt = 0;
	while (m--)
	{
		int pos;
		cin >> pos;
		sum = sum - (cnt - mp[pos]);
		cnt++;
		mp[pos] = cnt;
		sum = sum + n-1;
		cout << sum<<endl;
	}
	

	return 0;
}

Question J of red wine brother

Meaning:
Give you a string. You can choose to exchange two arbitrary characters or not. This is called an operation. Now, according to the given string, if a person makes an operation behind your back, can you detect it
Idea:
Determine whether there are duplicate characters in the string

#include<bits/stdc++.h>
using namespace std;
string s;
set <char> ss;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> s;
	
	for (int i = 0; i < s.length(); i++)
	{
		ss.insert(s[i]);
	}
	if (ss.size() == s.length()) cout << 1;
	else cout << 0;

	return 0;
}

Codeforces 1551A Title Link

Meaning:
Arbitrarily select an interval, define that f(l,r) is the result of multiplying the maximum value in the interval by the minimum value in the interval, and output the maximum value of this result.
Idea:
First, the conclusion is the maximum value of a[i] multiplied by a[i-1] after a round of traversal.
Suppose we choose a pair of adjacent numbers first. If we add a nearby number to change the value of f(i,j), then in fact, this value is the value of f(i-1,i) or f(j,j+1). That is, it seems that the previous value of f(i,j) will be updated, but it is actually just another pair of adjacent (i,j) values.

#include<bits/stdc++.h>
using namespace std;
int t, n;
#define MAXN 100005
long long a[MAXN];
long long ans;
int pos;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		ans = 0;
		cin >> n;
		memset(a, 0, sizeof(a));
		long long max_n=-1;
		long long min_n=-1;
		long long ans = 0;
		pos = 1;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
			if (i > 1) ans = max(a[i] * a[i - 1],ans);
		}
		

		cout << ans<< endl;
	}
	return 0;
}

Codeworks 1554b title link: Click here to transfer

Meaning:
Select any logarithm and define that f(i,j) is i × \times ×j-k × \times × (a[i]|a[j]), find the maximum value of f(i,j)
Idea:
According to the binary bit operation, k can be obtained × \times × The maximum value of (a[i]|a[j]) is nothing more than 2 × \times ×max(a[i],a[j]) × \times × k. And the front i × \times × The size took off long ago, and the two derivatives are not in the same order of magnitude at all. So it becomes a greedy idea to make i and j as large as possible, and then find the maximum value in the two-layer loop traversal.

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
long long t, n,k;
long long a[MAXN];

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> n>>k;
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= n; i++) cin >> a[i];		
		long long ans = -9999999999999;
		if (n > 400)
		{
			for (long long i = n-400; i < n; i++)
			{
				for (long long j = i + 1; j <= n; j++)
				{
					ans = max(ans, i * j - k * (a[i] | a[j]));
				}
			}
		}
		else
		{
			for (int i = 1 ; i < n; i++)
			{
				for (int j = i + 1; j <= n; j++)
				{
					ans = max(ans, i * j - k * (a[i] | a[j]));
				}
			}
		}
		

		cout << ans<<endl;
	}

	return 0;
}