The third ACM program design competition of Wuhan University of Engineering

The third Wuhan University of Engineering ACM Programming trials

A topic （ Zootopia ）

Topic link ：https://ac.nowcoder.com/acm/contest/19161/A

Title Description

There are four kinds of animals in the animal city A,B,C,D, The food chains of these four animals form an interesting ring .

A eat B,B eat C,C eat D,D eat A.

existing N Animals , With 1∼N Number .

Every animal is A,B,C,D One of the , But we don't know which one it is .

There are three ways to describe this N Describe the food chain of animals ：

The first is 1 X Y, Express X and Y It's the same kind .

The second is 2 X Y, Express X eat Y.

The third is 3 X Y, Express X and Y Not of the same kind , And X Don't eat Y ,Y I don't eat either X.

This man is right N Animals , Use the above three statements , Say... Sentence by sentence K Sentence , this K Some sentences are true , Some are fake .

When a sentence satisfies one of the following three , This is a lie , Otherwise, it's the truth .

The current words conflict with some of the real words in front , It's a lie ;
In the current conversation X or Y Than N Big , It's a lie ;
The current words mean X and X Not of the same kind , It's a lie .
Your task is based on the given N and K Sentence , The total number of output lies .

Topic analysis

Find out the number of statements about the relationship between eating and being eaten in the food chain given in the question

Their thinking

The union search set problem with weights ：
1. First declare an array ： Subscript numbers indicate food , The value placed in the array indicates being eaten .
2. Then declare an array to represent the weight of each relationship .
3. Enter the judged value , Find the root node of two numbers （ The weight of the relationship needs to be updated ）
4. If the two values found are equal and the difference between the weights is 1 And satisfaction is the truth that inquires about the relationship between eating and being eaten , Otherwise, it is false .
5. If the two values found are not equal and meet the query conditions 3, Is the truth , Otherwise, it is false .
6. Count the number of lies .

Code implementation

#include<bits/stdc++.h>
using namespace std;
const int N=10000010;
int n,m,c,t,x,y,a[N],b[N];
int find(int x){
    
    if(b[x]!=x){
    
        int k=find(b[x]);
        a[x]=(a[x]+a[b[x]])%4;
        b[x]=k;
    }
    return b[x];
}
int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)b[i]=i;
    while(m--){
    
        cin>>t>>x>>y;
        if(x>n||y>n||x<1||y<1||t!=1&&x==y) {
    c++;continue;}
        int p1=find(x),p2=find(y),k=t-1;
        if(p1==p2&&((a[x]-a[y])%4+4)%4!=k){
    c++;continue;}
        if(p1!=p2){
    
            b[p1]=p2;
            a[p1]=((k-a[x]+a[y])%4+4)%4;
        }
    }
    cout<<c<<endl;
    return 0;
}

B topic （ room escape ）

Topic link ：https://ac.nowcoder.com/acm/contest/19161/B

Title Description

Xiao Ming didn't play in the school match, but he was asked to set a question . He wants to play school games very much , But now he's trapped in a maze , Now please help Xiao Ming escape from the scene . The maze is composed of n * m A maze of lattices , Some grids are traps , use ’#‘ Express , Xiao Ming will die if he enters the trap ,’.' It means there is no trap . Xiaoming's position is ’S’ Express , The destination uses ’T’ Express .

Xiao Ming can only move up, down, left and right adjacent grids , Each move costs 1 second .

Yes q Two way transmission array , Each transmission array has two ports , It's all in the lattice of the maze , When walking or being transmitted to a lattice with a transmission matrix , Xiao Ming can choose whether to turn on the transmission array . If you turn on the transmission array , Xiao Ming will be transferred to the grid at the other end of the transmission array , This process will cost 3 second ; If you don't turn on the transmission array , Nothing will happen , Xiao Ming can continue to move up, down, left and right .

A grid may have multiple transmission arrays , Xiao Ming can choose any one to start the transmission array . Using a teleport array is very dangerous , Because the other end of some transmission array is in a trap , If Xiao Ming uses such a transmission array , Then he will die . Please tell Xiao Ming the shortest time to escape the scene alive .

Topic analysis

The shortest path problem from one point to another （ Conveyor belt ）.

Their thinking

1. Set up a vector The container stores the address information of the conveyor , Find the beginning and the end .
2. Set a priority queue to store the shortest path of each step , Array dis Update the shortest path , Array vis Mark the way you've walked .
3. First the dis The values in the array are set to the maximum value for future updates . When starting first, push the starting point into the queue first , Then take out the step size and coordinates , Judge whether it is equal to the end coordinate , If yes, the current step size is returned , If not, find the next shortest step update and save it in the priority queue , It is also necessary to determine whether there is a portal at this point. If there is a portal and the step size passing through the portal is less than the current step size, continue to update and store it in the priority queue . Cycle back and forth in turn, and finally find the end point and return to the step size , If not, return -1.

Code implementation

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 310;
const int dx[4] = {
    -1, 1, 0, 0}, dy[4] = {
    0, 0, -1, 1};
int n, m, q;
int stx, sty, edx, edy;
char mp[N][N];
vector<PII> edges[N][N];
int dis[N][N];
bool vis[N][N];

int Dijkstra()
{
    
    memset(dis, 0x3f, sizeof dis);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({
    0, {
    stx, sty}});
    dis[stx][sty] = 0;
    while (!heap.empty()) {
    
        int distance = heap.top().first;
        int a = heap.top().second.first, b = heap.top().second.second;
        heap.pop();
        if (vis[a][b])
            continue;
        vis[a][b] = true;
        if (a == edx && b == edy) return distance;
        for (int i = 0; i < 4; i++) {
    
            int x = a + dx[i], y = b + dy[i];
            if (!(x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#' && dis[x][y] > distance + 1))
                continue;
            dis[x][y] = distance + 1;
            heap.push({
    dis[x][y], {
    x, y}});
        }
        for (auto t : edges[a][b]) {
    
            int x = t.first, y = t.second;
            if (!(mp[x][y] != '#' && dis[x][y] > distance + 3))
                continue;
            dis[x][y] = distance + 3;
            heap.push({
    dis[x][y], {
    x, y}});
        }
    }
    return -1;
}
int main()
{
    
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
    
        cin >> mp[i] + 1;
        for (int j = 1; j <= m; j++)
            if (mp[i][j] == 'S') stx = i, sty = j;
            else if (mp[i][j] == 'T') edx = i, edy = j;
    }
    while (q--) {
    
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a++, b++, c++, d++;
        edges[a][b].push_back({
    c, d});
        edges[c][d].push_back({
    a, b});
    }
    cout << Dijkstra() << endl;
    return 0;
}

C topic （ Camping ？ Food ！）

Topic link ：https://ac.nowcoder.com/acm/contest/19161/C

Title Description

$StarrySky$ Pikachu of likes camping very much , Because camping means playing , It also means $StarrySky$ Make food for it . and $StarrySky$ Also know this , therefore , This time camping ,$StarrySky$ All at once $n$ Different dishes , He's going to $n$ The dishes are arranged in a row , The serial numbers are $\text{1},\text{2},...,n$, To finish these ,$StarrySky$ A whim , Want to ask a question about Picchu .

$StarrySky$ Set a value for each cake , Use them separately $w_{\text{1}},w_{\text{2}},...,w_n$ Express , The value may be negative , He will ask Picchu questions $m$ Time , Each query gives a value $k$, And Pikachu needs to give an answer $p(\text{0}\le p\le n)$, bring $k-\sum _{i=\text{0}}^p{w}_i$ non-negative , But the result is the smallest , special , If there are multiple minimum results , that , Pikachu wants to give the biggest $p$, And if the $p=\text{0}$, Then the value of this expression is $k$.$w_0$ The value of is constant 0. Pikachu broke his fingers , How it wants to electrocute itself with 100000 volts $StarrySky$, But it can't , Because then it won't be able to eat food in the future , Nor can we fight together , therefore , Pikachu asked you for help , I hope you can help it .

Topic analysis

Given n Number and weight of each number , Give a number k, Find the largest p bring $k-\sum _{i=\text{0}}^p{w}_i$ It's a non negative number .

Their thinking

First, create a structure to store k Values and p value , Array sum The prefix and of statistical weights . Every change p The value of the implementation expression is non negative , And then we do a sort . Take out the biggest q.

Code implementation

# include <iostream>
# include <cstdio>
# include <algorithm>
typedef long long ll;
const int N = 1e5 + 5;
int n;
struct Sum {
    
    ll ans;
    int id;
    const bool operator < (const Sum& rhs) const {
    
        return ans < rhs.ans || (ans == rhs.ans && id < rhs.id);
    }
};
ll w[N];
Sum sum[N];
int main() {
    
    int m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    
        scanf("%lld", &w[i]);
    }
    for (int i = 1; i <= n; i++) {
    
        sum[i].ans = sum[i-1].ans + w[i];
        sum[i].id = i;
    }
    sum[n + 1].ans = 0;
    sum[n + 1].id = 0;
    std::sort(sum + 1, sum + 2 + n);
    while (m--) {
    
        int k;
        scanf("%d", &k);
        Sum t;
        t.ans = k;
        t.id = 0x3f3f3f3f;
        auto it = std::upper_bound(sum + 1, sum + 2 + n, t) - 1;

        if (it == sum) {
    
            puts("-1");
            continue;
        }

        printf("%d\n", it->id);
    }
    return 0;
}

E topic （ Looking for a regular ）

Topic link ：https://ac.nowcoder.com/acm/contest/19161/E

Title Description

Arrange positive integers according to the following rules ：

set up n In the i Xing di j Column , Please export i and j The least common multiple of .

Topic analysis

find n The subscript represented i,j. seek i and j The least common multiple of .

Their thinking

First observe , Odd lines are all odd ; Even lines are all even . And the odd number is the order of odd numbers （1,3,5,7···）; On the even line is the order of even numbers （2,4,6,8···）. So first we should find n Is the odd or even number on the line , Then find the corresponding number of columns by the number of rows . Then find the least common multiple .

Code implementation

#include<bits/stdc++.h>
using namespace std;
int n,m,i,j;
int main(){
    
    cin>>n;
    m=(n+1)/2;// Find the corresponding number of rows 
	if(n%2) i=1;else i=2;// Judge n Is it an odd row or an even row 
    while(m>i){
    m-=i;i+=2;} j=m;// Find the corresponding number of columns 
    cout<<i*j/__gcd(i,j)<<endl;
    return 0;
}

I topic （ We are champions ）

Topic link ：https://ac.nowcoder.com/acm/contest/19161/I

Title Description

Xiao Zhi and Pikachu once again stood on the stage of baokemeng battle , The competition system has changed this time , It adopts the top four double defeat competition system , In other words ： Before the top four , Fight in pairs , The loser will be eliminated directly , Once in the top four , If you lose a match , Enter the loser Group , If you win all the way in the loser Group , You can still reach the finals , Fight for the championship .

More intuitive , The competition process after the top four is shown in the figure below ：

If you know there are $n$ Wei baokemeng trainer participated , that , Xiao Zhi and Pikachu want to win the championship , At least a few games are needed , How many games are needed at most , And what is the difference between the maximum number of sessions and the minimum number of sessions ？

Topic analysis

Adopt the top four double defeat competition system to calculate the minimum and maximum games used by the champion and calculate the difference .

Their thinking

First of all, if you win all the way, there is no doubt that it takes the least number of games to win the championship , If you lose a game, you can win the championship only if you win all the winners in the loser Group . Therefore, the most winning games are won when entering the top four , After being promoted to the top four, I lost the first game , Then you need to win all the losers . The minimum and maximum number of games used before entering the top four are the same , The only difference is that after entering the top four, he won one more game in the loser Group . So the difference between winning the championship in the most games and winning the championship in the least games is the same , It's the extra game after the top four .

Code implementation

#include<bits/stdc++.h>
using namespace std;
long long n,m,c;
int main(){
    
    scanf("%lld",&n);
    for(int i=0;i<n;i++){
    
        scanf("%lld",&m);
        c=0;
        while(m>4){
    c++;m/=2;}// Several rounds were played before the top four 
        printf("%lld %lld 1\n",c+3,c+4);// How many rounds have you played in total 
    }
    return 0;
}