Location>code7788 >text

[Full Title] ACGO Qualifying Tournament #12

Popularity：733 ℃/2024-09-11 03:48:53

ACGO Qualifying Tournament #12 - Topic Explanation

Don't ask why there's no Challenge #11, because Challenge #11 was eaten by the greedy Yuilice (it wasn't).

The difficulty of this challenge has been increased compared to the previous ones.

BREAKING: Little Fish has now joined the R&D department, and the ranking tournament's counting grading system will make a major change in the next few ranking tournaments. After that, there will not be a situation where everyone's level is very low. For students with a good degree, a little bit of playing a couple of ranked matches segment will have a great improvement.

Question 1 - 50% 𝐴𝐼, 50% 𝐻𝑢𝑚𝑎𝑛

Title Link Jump:click to jump

It's great that STL is so great, using its own() method will be able to quickly find the length of a string. See the code for specific ideas, just simulate according to the requirements of the topic.

The AC code for this question is as follows:

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

/*
PS: Confidence Doubling Topic。
Writing this question will make you think this game is particularly easy。But it's not.。
*/

int n, cnt;
string str;

int main(){
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> str;
        if (() > 5) cnt++;
    }
    int ans = ceil(1.0 * cnt / n * 100);
    printf("%d%%AI, %d%%Human\n", ans, 100 - ans);
    return 0;
}

Question 2 - Counting the number of odd and even numbers in an interval

Title Link Jump:click to jump

For this kind of interval problem, you can consider a part of it first. If one asks for an interval from\([1, L]\) What should we do with the numbers in the interval that satisfy the condition? Suppose\(L\) is an even number, then\([1, L]\) The odd and even numbers of the interval should then be\(L / 2\). Similarly, assuming that\(L\) is an odd number, then\([1, L]\) The odd and even numbers of the interval are then respectively\(L / 2 + 1\) cap (a poem)\(L / 2\). Noting that\(L / 2 + 1\) cap (a poem)\(L / 2\) Both formulas can be abbreviated as\((L + 1) / 2\)。

found\(odd(L)\) cap (a poem)\(even(L)\) Respectively, the intervals\([1, L]\) of the number of odd numbers and the number of even numbers. Then it can be concluded that if the requirement\([L, R]\) number of odd numbers in the interval, the answer would be\(odd(R) - odd(L-1)\) cap (a poem)\(even(R) - even(L-1)\)。

The AC code for this question is as follows, the code does not use functions, sorry:

#include <iostream>
using namespace std;

/*
"thinking water problem" (finance)。
Just think a little bit to find a pattern.。
*/

int q, l, r, k;

int main(){
    ios::sync_with_stdio(0);
    (0); (0);
    cin >> q;
    while(q--){
        cin >> k >> l >> r;
        if (k == 1) cout << ((r + 1) >> 1) - ((l) >> 1) << endl;
        else cout << (r >> 1) - ((l - 1) >> 1) << endl;
    }
    return 0;
}

Question 3 - Mars Backpack II

Title Link Jump:click to jump

One Reverse\(0/1\) Template topics for backpacks. Usually.\(0/1\) The goal of the backpack problem is to select a number of items such that the total weight of these items does not exceed the capacity of the backpack and the total value of these items is maximized. While the reverse\(0/1\) The backpack problem works in the opposite direction, where the goal is to select a number of items such that the total weight of these items does not fall below a given minimum value and the total value of these items is minimized.

The main thing is that the definition of state is difficult: set\(dp[j]\) means that the total weight is exactly\(j\) of the minimum cost. Then we can get the following state transfer equation:

\[dp_j = \min(dp_j, dp_{j-w_i} + v_i); \]

Based on the definition of state, we will\(dp\) The arrays are all initialized to positive infinity at the beginning, while the other\(dp_0 = 0\), which means that exactly the weight of\(0\) The minimum cost of the item is\(0\), the positive infinity representation is unanswered for now and will need to be updated in subsequent loops.

After that it's just a matter of running through the normal Knapsack 01 code. When outputting the answer, we need to find an answer that satisfies the condition\((dp[i] \le m)\)The maximum value of the The maximum value is obtained using afor The loop will take care of it.

The AC code for this question is as follows:

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;

/*
opposite direction 01 Backpack Title。
not a big problem，X03 of the students who have done similar topics at the camp（maybe Hangzhou August Issue Only）。
*/

int n, m, sum;
int dp[100005], ans;
int w[1005], v[1005];

signed main(){
    ios::sync_with_stdio(0);
    (0); (0);
    cin >> n >> m;
    for (int i=1; i<=n; i++){
        cin >> w[i] >> v[i];
        sum += v[i];
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for (int i=1; i<=n; i++){
        for (int j=sum; j>=v[i]; j--){
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    for (int i=1; i<=sum; i++){
        if (dp[i] <= m) ans = i;
    }
    cout << ans << endl;
    return 0;
}

Question 4 - Fracturable Columns

Title Link Jump:click to jump

The question is simple, but it takes a while of careful thinking to get it right. The solution to this question islook for patterns! That's right, it's just a matter of finding the pattern. We just need to focus on how to incorporate this\(4N + 2\) A series of numbers can be divided equally into two elements after removing the\(N\) An isotropic series.

By way of manual simulation, notice that we only need to arrange these numbers vertically to solve the problem. Each of the other columns has four elements, but two of the columns have five elements (representing the\(4N + 2\) (used form a nominal expression)\(+2\) part), with a total of\(N\) Columns. For example, the series\([1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]\). This is what it looks like after arranging it vertically:

1 7 13 19 25
3 9 15 21 27
5 11 17 23

It can be seen that these elements form three isomorphic series and that the lengths of the two isomorphic series are\(5\). Then for a length of\(4\) of the isotropic series we can leave it completely alone and just output it. And for the two series of length\(5\) of the equivariant series, we consider deleting one number from each of these two equivariant series to form a new equivariant series. Taken together, we find that deleting the element\(3\) cap (a poem)\(25\) After that, the new two equal difference series still satisfy the title qualification.

A few more examples are given and it is found that the laws are also similar. Then therefore we can conclude that for any length of\(4N + 2\) of the isotropic series, just delete the first digit of this isotropic series\(2\) Subparagraphs (a) and (b)\(4N + 1\) item, the remaining\(4N\) The elements must be able to form\(N\) A length of\(4\) of the isotropic series.

For more information about this question, you can read Mr. アドル's explanation as a supplement:link jumping。

After finding the rule, the code is very easy to write, the AC code of this question is as follows:

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n, x, d;

signed main(){
    cin >> n >> x >> d;
    if (n == 1){
        cout << -1 << endl;
        return 0;
    }
    cout << 2 << " " << 4 * n + 1 << endl;
    for (int i=0; i<n; i++){
        int t = x + i * d;
        if (i == 1) t += n * d;
        for (int j=0; j<4; j++)
            cout << t + j * n * d << " ";
        cout << endl;
    }
    return 0;
}

Question 5 - Fireworks

Title Link Jump:click to jump

The output of this question is not intentionally difficult for everyone, because the output is too large, beyond the CF limit of 64MB limit, so can only be changed to output the map to output the hash value of the map (for students who have not learned the hash, the output of the answer is also a more difficult thing).

The difficulty of this problem is not really that big, it's an unprivileged shortest-circuit problem with multiple sources and different rights. However, due to the large amount of data, it will time out to use the normal priority queue maintenance (don't ask me how I know, I used priority queue at the beginning and then TLE at test point #13), so we need to consider how to find a workaround to replace the priority queue.

Notice that we only need to use one additionalwhileIf the fireworks happen to be lit, we add the coordinates of the fireworks to the queue.

while(arr[cnt].z <=  && cnt <= k){
    vis[arr[cnt].x][arr[cnt].y] = 1;
    (arr[cnt]); cnt ++;
}

Since each firework only affects one nearby grid per unit of time, it means that the head and tail of the queue have the same weight when the firework is put in, which ensures that the weights of the elements within the queue must be monotonically increasing. This situation converts the problem into a condition for using BFS to find a multisource unweighted shortest circuit.

The AC code for this question is as follows:

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int MOD = 998244353;

int n, m, k, cnt = 2;
struct node{
    int x, y, z;
} arr[1005]; 
queue<node> que;
int dis[5005][5005];
int vis[5005][5005];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

bool cmp(node a, node b){
    return  < ;
}

signed main(){
    ios::sync_with_stdio(0);
    (0); (0);

    cin >> n >> m >> k;
    for (int i=1, x, y, z; i<=k; i++)
        cin >> arr[i].x >> arr[i].y >> arr[i].z;

    sort(arr+1, arr+1+k, cmp);
    (arr[1]);
    vis[arr[1].x][arr[1].y] = 1;

    while(!()){
        node t = ();
        ();
        if (dis[][]) continue;
        dis[][] = ;
        while(arr[cnt].z <=  && cnt <= k){
            vis[arr[cnt].x][arr[cnt].y] = 1;
            (arr[cnt]); cnt ++;
        }
        for (int i=0; i<4; i++){
            int cx = dx[i] + ;
            int cy = dy[i] + ;
            if (cx < 1 || cy < 1 || cx > n || cy > m) continue;
            if (dis[cx][cy]) continue; 
            if (vis[cx][cy]) continue;
            vis[cx][cy] = 1;
            ((node){cx, cy, +1});
        }
    }
    
    long long ans = 0, p = 1;
    for (int i=1; i<=m; i++) 
        p = (p * 233) % MOD;
    for (int i=1; i<=n; i++){
        for (int j=1; j<=m; j++){
            p = (p * 233) % MOD;
            ans = (ans + (dis[i][j] * p) % MOD) % MOD;
        }
    }

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

Question 6 - The Trial of the Sword

Title Link Jump:click to jump

This question is super gross, and I respect from the bottom of my heart those who AC this question during the tournament.

The idea is very well thought out, since all the monsters have to be fought and the time to fight each one is fixed, we can preprocess the time to fight all the monsters at the beginning, and the only thing that needs to be optimized is the time to catch up.

Consider each layer first, for any layer, the key point is to find an optimal path (the shortest path from a certain starting point, passing through all the points before transferring to the next layer) can be. Students who have studied state-compressed dynamic programming can easily think of the template question [Shortest Hamilton path] (Logu link:link jumping）。

For each layer, the specific implementations and functions are as follows:

  1. cover(dist, grid, "#*");

    • commander-in-chief (military)distcap (a poem)gridMarked as"#"maybe"*"of all obstacles to be covered. This step serves to mark all impassable areas and provides the basis for subsequent distance calculation or path planning.

  2. getMinDist(dist, grid, "#");

    • Calculate the distance from the current location to thegridMarked as"#"（The shortest distance to the (obstacle) location. The purpose of this step is to obtain the distance information of the obstacle for the subsequent path planning, so as to facilitate the path selection in the next step.

  3. hamilton(dist, grid);

    • existdistcap (a poem)gridOn performs the computation of Hamiltonian Path with the aim of finding a path that passes through all the goal points. This step serves to find a path that passes through all mandatory points based on the previous distance information.

  4. cover(dist, grid, "#.");

    • treat (sb a certain way)distcap (a poem)gridMarked as"#"(obstacles) and"."(open space) portion of the overlay process. This step is to ensure that subsequent distance calculations exclude marked obstacles and identify passable paths.

  5. getMinDist(dist, grid, "#");

    • Calculate again the distance from the current location togridMarked as"#"of the shortest distance. This step is to update the shortest distance after the path override process to ensure that the latest distance information is obtained.

Other than that it's just a few minor optimizations, see the code comments for details.

The AC code for this question is as follows (this code refers to Mr. Huang's std and modifies it (I am not going to say that I passed myself to death by passing around my array and hated the pointer's day)), if you need a more detailed answer, you canRefer to this article：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

int n, m, k;
string map[30][105];
int dist[105][105];
struct node{
    int x, y, w;
    bool friend operator < (node a, node b){
        return  > ;
    }
};
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

/*
PS：Was going to do it as a pure array with pointers。
Then I wrote myself to death.，nevertheless vector (euphemism) go to the toilet。
Passing around a normal 2D array is killing me.。
::: Although my compiler can't see c++11 exclusionary rule，Every time, you give me the heads up. warning。one's head is swimming。
*/

// conversions，commander-in-chief (military)每一个mythical animal的血量都conversions成对应的数字。
int calc(char c){
    if (c == '.') return 0;
    if (c == 'R') return 1;
    if (c == 'B') return 3;
    if (c == 'D') return 8;
    if (c == 'S') return 24;
    if (c == 'G') return 36;
    return 0x7f7f7f7f;
}

// The most common breadth-first search algorithm：
// Records from sx, sy departures，To the current layer grid The shortest path to each point of the。
// included among these block Represents an unwalkable grid。
vector<vector<int> > bfs(vector<string> &grid, int sx, int sy, string block){
    vector<vector<int> > dist(n, vector<int>(m, 0x7f7f7f7f));
    dist[sx][sy] = 0;
    struct node{
        int x, y;
    }; queue<node> que;
    ((node){sx, sy});
    while(!()){
        node t = ();
        ();
        for (int i=0; i<4; i++){
            int cx =  + dx[i];
            int cy =  + dy[i];
            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
            // string function，Determine if the current grid is an obstacle，Ignore it if it's an obstacle.。
            if ((grid[cx][cy]) != string::npos) continue;
            if (dist[cx][cy] < 0x7f7f7f7f) continue;
            dist[cx][cy] = dist[][] + 1;
            ((node){cx, cy});
        }
    }
    return dist;
}

// commander-in-chief (military) dist The array is based on the grid recover (from illness)。
// If the current position cannot be walked to，则commander-in-chief (military) dist Updated to infinity。
void cover(vector<vector<int> > &dist, vector<string> &grid, string block){
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if ((grid[i][j]) != std::string::npos)
                dist[i][j] = 0x7f7f7f7f;
        }
    }
    return ;
}

// dijkstra shortest-circuit algorithm。
// The main function is to calculate and update the shortest distance from each node to the remaining nodes，and through a breadth-first search（BFS）Algorithms to implement。
// dist[i][j] It is to arrive from the starting point set at the beginning (i, j) Cumulative consideration，The cost of each lattice passed on the path is considered。
void getMinDist(vector<vector<int> > &dist, vector<string> &grid, string block){
    priority_queue<node> que;
    // Get all the starting points in line at the beginning.。
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            ((node){i, j, dist[i][j]});
        }
    }

    while(!()){
        node t = ();
        ();
        if (dist[][] < ) continue;
        for (int i=0; i<4; i++){
            int cx =  + dx[i];
            int cy =  + dy[i];
            if (cx < 0 || cy < 0 || cx >= n || cy >= m) continue;
            if ((grid[cx][cy]) != string::npos) continue;
            // If a better solution already exists，ignore。
            if (dist[cx][cy] <=  + 1) continue;
            dist[cx][cy] =  + 1;
            ((node){cx, cy,  + 1});
        }
    }
}

// Compute the Hamiltonian path
// 即从起点departures走完所有的点最后再回来的路径最短路。
void hamilton(vector<vector<int> > &dist, vector<string> &grid){
    struct node{
        int x, y;
    }; vector<node> vec;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (grid[i][j] == '*')
                vec.push_back((node){i, j});
        }
    }

    int k = ();
    vector<vector<int> > f(k);
    // f Arrays are used to calculate each key node（mythical animal）The shortest circuit between。
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        auto toOther = bfs(grid, sx, sy, "#");
        for (int j=0; j<k; j++){
            f[i].push_back(toOther[vec[j].x][vec[j].y]);
        }
    }

    // insofar as Hamilton lost，Go directly to the search for Logu template questions to have a look first。
    // X04-01 of the students should have learned（After all, I'm the one who picked the topic.）。
    vector<vector<int> > dp(1 << k, vector<int>(k, 0x7f7f7f7f));
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        dp[1 << i][i] = dist[sx][sy];
    }
    for (int i=0; i<(1<<k); i++){
        for (int j=0; j<k; j++){
            if (~i >> j & 1) continue;
            for (int l=0; l<k; l++){
                if (~(i ^ 1 << j) >> l & 1) continue;
                dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][l] + f[l][j]);
            }
        }
    }
    for (int i=0; i<k; i++){
        int sx = vec[i].x;
        int sy = vec[i].y;
        dist[sx][sy] = dp[(1 << k) - 1][i];
    }
}

int main(){
    ios::sync_with_stdio(0);
    (0); (0);
    cin >> n >> m >> k;
    vector<vector<string> > grids(k, vector<string>(n));
    for (auto &grid : grids){
        for (auto &row : grid){
            cin >>  row;
        }
    }
    int cost = k - 1;
    for (auto &grid : grids){
        for (auto &row : grid){
            for (auto &c : row){
                if (c != '#' && c != '.'){
                    cost += calc(c);
                    c = '*';
                }
            }
        }
    }

    vector<vector<int> > dist = bfs(grids[0], 0, 0, "#*");
    
    /*
        Remove certain obstacles and key points first，to calculate the initial shortest path。
        peri-urban areas hamilton function to handle path planning between critical points，Get the optimal path for all critical points。
        Final further elimination of blank areas and obstacles，重新计算网格中各点The shortest circuit between径，Getting to the end result。
    */
    for (auto &grid : grids){
        cover(dist, grid, "#*");
        getMinDist(dist, grid, "#");
        hamilton(dist, grid);
        cover(dist, grid, "#.");
        getMinDist(dist, grid, "#");
    }

    // Calculate the answer。
    int ans = 0x7f7f7f7f;
    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            ans = min(ans, dist[i][j]);
        }
    }

    cout << ans + cost << endl;
    return 0;
}
<Previous