A topic today

source ：2022 The fifth Guangxi University Student Program Design Competition A topic Arrangement

Investigate ： Structure ordering ( This week's test site )

difficulty ： Orange question

This topic examines the use of structural ordering , In the previous weekly survey, there have been many . In the subject , It is necessary to prioritize the comprehensive difficulty , Consider some other cases of equality . The title is very template , The only pit may not be open long long May be wa, The data range is 1e6*1e6=1e12 Explosive int Type of .

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
using namespace std;
struct ss {
	int id;
	ll x, y;
	ll sum;
}a[2020];
bool cmp(ss h1, ss h2) {
	if (h1.sum == h2.sum) {
		if (h1.x == h2.x) {
			return h1.id < h2.id;
		}
		else {
			return h1.x < h2.x;
		}
	}
	else {
		return h1.sum < h2.sum;
	}
}
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].y;
		a[i].id = i;
		a[i].sum = a[i].x * a[i].y;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		cout << (char)(a[i].id + 'A' - 1) << " ";
	}
	return 0;
}

B topic God

source ：[yLOI2019] Qingyuan cherry

Investigate ： Combinatorial mathematics

difficulty ： Yellow title

First, assume that all power rails are the same , that Number of schemes for placing power rail * m!

hold Spaces are regarded as objects , At this time m Power rails are equivalent to diaphragms , Altogether Insert the clapboard at three positions .

Available Number of schemes for placing power rail =

According to the formula of combination number

Available

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
using namespace std;
int main() {
	ll n, m, p;
	cin >> n >> m >> p;
	ll ans = 1;
	for (ll i = n - m * 2 + 2; i <= n - m + 1; i++) {
		ans = ans * i % p;
	}
	cout << ans;
	return 0;
}

C topic you

source ：NYOJ-1058 Parts and problems

Investigate ： violence /dfs Naked topic ( This week's test site )

difficulty ： Orange question

The title is dfs The basic use of , Because the data range is small , You can do it by deep search ,dfs You can choose or not , Students who have made it can add a little difficulty to themselves , Try again. If you can figure it out k, Then the selected numbers are output . The data range of this question is relatively small , Violence can also be used to solve , The time complexity is O(2^n) about 1,048,576, Don't worry about overtime at all .

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
using namespace std;
ll a[30];
ll n, m;
int f = 0;
void dfs(ll x, ll y) {
	if (y == m) { // If it happens to be m, Then mark .
		f = 1;
		return;
	}
	if (x == n + 1) {
		return;
	}
	dfs(x + 1, y + a[x]); // Choose the top number 
	dfs(x + 1, y); // Do not select the current number 
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	dfs(1, 0); // Search deeply from the first number 
	if (f) {
		cout << "Successful trade";
	}
	else {
		cout << "Transaction failed";
	}
	return 0;
}

D topic Add

source ：2021 Niuke winter vacation algorithm basic training camp 6 I Greedy snake

Investigate ：bfs Naked topic ( This week's test site )

difficulty ： Orange question

Is also a naked bfs topic , In fact, the afterimage does not affect , Because according to bfs In principle , You will not repeatedly add the points you have passed to the queue , In fact, the afterimage is just a cover , In fact, it is still the shortest distance from the starting point to the end point , Finally, don't forget to take 100 Conversion unit .

#include<bits/stdc++.h>
#define endl '\n'
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 100 + 10;
using namespace std;
int n, m, sx, sy, ex, ey;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
char mg[maxn][maxn];
bool vis[maxn][maxn];
struct node
{
    int x, y;
    int step;
};
void bfs()
{
    node p;
    p.x = sx; p.y = sy;
    p.step = 0;
    queue<node> q;
    q.push(p);
    vis[sx][sy] = 1;
    while (!q.empty())
    {
        node tmp = q.front();
        q.pop();
        if (tmp.x == ex && tmp.y == ey)
        {
            cout << tmp.step * 100 << endl;
            return;
        }
        for (int i = 0; i < 4; i++)
        {
            int xx = tmp.x + dx[i];
            int yy = tmp.y + dy[i];
            if (mg[xx][yy] != '#' && xx > 0 && yy > 0 && xx <= n && yy <= m && !vis[xx][yy])
            {
                node tp;
                tp.x = xx;
                tp.y = yy;
                tp.step = tmp.step + 1;
                vis[xx][yy] = 1;
                q.push(tp);
            }
        }
    }
    cout << "-1" << endl;
}

int main()
{
    while (cin >> n >> m)
    {
        memset(vis, 0, sizeof(vis));
        cin >> sx >> sy;
        cin >> ex >> ey;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                cin >> mg[i][j];
            }
        }
        bfs();
    }
}

E topic training

source ：[NOI1999] Birthday cake

Investigate ：dfs, Pruning optimization ( This week's test site )

difficulty ： Green topic

Search for + prune

use mins[i] It means the first one i The smallest surface area of the layer minv[i] It means the first one i Minimum volume of layer , Set the bottom layer as n layer , Enumerate the height and radius of each layer .

But the complexity is so complicated

So we need to add optimization （ prune ）

Let's first look at some details in the topic ：

When i<M when , requirement And

This sentence tells us one thing , When we When enumerating radius and height, the upper and lower bounds can be determined Of , This is pruning one

The second detail ：

  Look at this picture and you will find out whether the bottom area of the lowest layer is the sum of the upper surface areas ( That is, the blackened place in the figure below )

So we just need to enumerate to the lowest level to record There is no need to consider the blackened part , Simplify the procedure

Look at other pruning :

1. If the minimum surface area currently searched is greater than the known minimum surface area, exit directly

2. If the current search volume has exceeded the subject limit , The exit

3. If the current surface area deduced from the volume is not good, exit directly

summary ：

1. When enumerating radius and height, the upper and lower bounds can be determined

2. If the minimum surface area currently searched is greater than the known minimum surface area, exit directly

3. If the volume of the current search has exceeded the subject limit, exit

4. If the current surface area deduced from the volume is not good, exit directly

#include<iostream>
#include<cmath>
using namespace std;

const int N = 24, INF = 1e9;

int n, m;
int minv[N], mins[N];
int res = INF;

// Record the radius and height of each layer , Because it will use the height of the upper floor 
int R[N], H[N];

//u Current level ,v The current volume and ,s The current processing area and 
void dfs(int u, int v, int s)
{
    if(v + minv[u] > n) return;
    if(s + mins[u] >= res) return;
    if (s + 2 * (n - v) / R[u + 1] >= res) return;

    if(!u)
    {
        if(v == n) res = s;
        return;
    }

    // Search order , First R after H, From big to small 
    for(int r = min(R[u + 1] - 1,(int)sqrt((n - v - minv[u - 1]) / u)); r >= u; r--)
        for(int h = min(H[u + 1] - 1, (n - v - minv[u - 1]) / r / r); h >= u; h--)
        {
            H[u] = h, R[u] = r;

            // At the bottom, you need to add r*r
            int t = u == m ? r * r : 0;

            dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
        }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + 2 * i * i;
    }

    //m+1 Layer does not exist , As sentinel , Reduce the judgment of boundary conditions 
    R[m + 1] = H[m + 1] = INF;

    dfs(m, 0, 0);

    if(res == INF) res = 0;
    cout << res << endl;


    return 0;
}

F topic 了

source ：2021 Niuke winter vacation algorithm basic training camp 3 J Add and multiply

Investigate ： game ( Other questions )

difficulty ： Yellow title

n=1 Special judgment required （ Very important ）

If n It's not equal to 1, You can find , If the last operation is done by backhand , Then the second hand will win .（ Odd number + Odd number = even numbers , Multiplying an even number by any number equals an even number ）.

Otherwise, if the initial state has at most one even number , The first hand always has a way to turn the situation into all odd numbers and then hand it to the second hand , At most, the backhand produces an even number , Therefore, the situation remains the same when you give it first . In the end, there is only one even number at most , So the first hand must win .

conversely , If the initial state has at least two even numbers , No matter what you do first , There must be at least two even numbers when the second hand returns to the first hand , So the situation we face first and finally is two even numbers , The second is the winner .

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int k;
    int x = 0,y = 0;
    for(int i = 1;i <= n;i++){
        cin >> k;
        if(k % 2){
            x++;
        }else{
            y++;
        }
    }
    if(n == 1&&k % 2){
        cout << "kk caiji";
    }else if(y > 1 || n % 2){
        cout << "mz nb";
    }else{
        cout << "kk caiji";
    }
    return 0;
}

G topic Do you

source ： Cattle guest Lao Tzu's full arrangement

Investigate ：dfs, to flash back ( This week's test site )

difficulty ： Orange question

Ideas ： Find the current state for each position , All numbers that can be placed in the current position . When all positions are numbered, release the number used one by one . namely dfs The idea of backtracking . You can also use STL Of next_permutation Function makes complete permutation , But I suggest you use dfs Write it down .

#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
//  Calculation u->n The path of path
void dfs(int u)
{
    if(u==n)// The boundary conditions 
    {
        for(int i=0;i<n;i++) // Here is i It's from 0 Start ,i It's an array subscript 
                printf("%d ",path[i]);
        printf("\n");
        return ;
    }
    else{
        for(int i=1;i<=n;i++)// Note that there i It's from 1 Start , Because this is arranged 1~n
        {
            if(!st[i]){
                path[u]=i;
                st[i]=true;
                dfs(u+1);// After going back , Restore the scene 
                path[u]=0;
                st[i]=false;
            }
        }
    }
}
int main()
{
    cin >> n;
    dfs(0);
    return 0;
}