C

Title:

Given an integer, it is required to find a 0~(n - 1) permutation, so that each number Ai+i of the permutation is equal to the square number and output the sequence found. If the output - 1 is not found

Solution idea: one eye structure problem~~

We can get an idea: if Ak+k is a square number, and Ak>k, we can also construct the index k~Ak, which is a square number. For example, the sixth place 10, the seventh place 9, the eighth place 8, until the tenth place 6
In this way, we construct an interval matching condition.
After thinking about how to realize all perfectly, we can think that the distance between a number and its nearest square must be less than itself. When we enumerate from the back to the front, the index is fixed. As long as we find the difference of the smallest square that is larger than the current index as the number placed at the current position, the problem of the interval from the current number to the current index will be solved, The number to be selected at the beginning of each interval must be smaller than the index, and the number to be selected at the end must be used. All previous intervals cannot use all the numbers used in the current interval, and all this construction is valid.

code implementation

There are multiple groups of test data in this question. We need to find the smallest square number larger than a certain number. You can use preprocessing+dichotomy to subtract the enumeration time. Here, we use the set container in STL, which contains dichotomy search. It is very convenient.

Pretreatment

for (int i = 0; i <= 1000 ; i ++)
	{
		if (i * i > 200010)
			break;

		num.insert (i * i);
	}

Specific structure

int a[N];
void solve()
{
	int n;
	cin >> n;
	n = n - 1;

	for (int i = n; i >= 0; i --)
	{
		int x = *num.lower_bound (i);// Find the smallest square by dichotomy
		a[i] = x - i;
		int p = x - i;

		while (p != i and i >= 0)// Cycle forward until it reaches the left end of the interval
		{
			i --;
			a[i] = x - i;
		}
	}

	for (int i = 0; i <= n ; i ++)
		cout << a[i] << ' ';

	cout << '\n';
}

D

Title:

Given 2n contestants, each two contestants will play the knockout game, and the winner will be promoted. This is an interactive question, allowing you to ask any two marked people about the victory comparison. For example, a vs b a will output 1 if they win more games, 2 if they win more games, and 0 if they are flat
The number of queries is limited to 2 n + 2 3 \frac{2^n +2}{3} 32n+2​

Solution ideas

According to the recursive idea, the first idea is to select some players who won the first time according to the inquiry, and then ask the current players who have not been eliminated first
According to this idea, it can be found that the winner of the four contestants can be asked only twice
Then the total number of queries for this idea is 2n * (1 - 1/4n)/(1 - 1/4) - sum of simple proportional sequence

Let's talk about how to ask the winner of four contestants twice

See the winners of 1, 2, 3, 4 as shown in the figure
It can be known that the winning games of the four people are 0 0 1 2
2 1 must be one match short, 3 4 must be one match short
Then we can discuss the score of 1 and 3 first
1, 1 win in 3
Then 1 will win at least one game, that is, 1 won the match between 1 and 2. You can know the winner by comparing 1 with 4 directly instead of comparing with 2
2, 3 wins in 1 3
In the same way, just ask again who wins more games in 2 and 3
3, 1 3 draw
Note: 1 3 are all 0. Just ask 2 4 again, and the winner is the real winner
So we have A for this question

code implementation

#include<bits/stdc++.h>
using namespace std;
int Ask (int x, int y)
{
	printf ("? %d %d\n", x, y);
	fflush (stdout);
	int q;
	scanf ("%d", &q);
	return q;
}
int n;
vector<int> a;
void solve()
{
	a.clear();
	scanf ("%d", &n);
	
	for (int i = 1 ; i <= (1 << n) ; i ++)
		a.push_back (i);
	
	while (a.size() > 1)
	{
		if (a.size() == 2)
		{
			int q = Ask (a[0], a[1]);
			a = {q == 1 ? a[0] : a[1]};
			break;
		}
		
		vector<int> b;
		//The number of array a is divided by 4 in each round, and we need to decide that the number is 2
		for (int i = 0; i < a.size(); i += 4)
		{
			int per1 = a[i], per2 = a[i + 1], per3 = a[i + 2], per4 = a[i + 3];
			int q = Ask (per1, per3);
			
			if (q == 1) // a wins
			{
				int p = Ask (per1, per4);
				
				if (p == 1)
					b.push_back (per1);
				else b.push_back (per4);
			}
			else if (q == 2) // b Win
			{
				int p = Ask (per2, per3);
				
				if (p == 1)
					b.push_back (per2);
				else b.push_back (per3);
			}
			else if (!q)// it ends in a draw
			{
				int p = Ask (per2, per4);
				
				if (p == 1)
					b.push_back (per2);
				else b.push_back (per4);
			}
		}
		
		a = b;
	}

	printf ("! %d\n", a[0]);
	fflush (stdout);
}
int main()
{
	int t = 1;
	scanf ("%d", &t);
	
	while (t--)
		solve();
	
	return 0;
}