2021第7届中国大学生程序设计竞赛CCPC桂林站， 签到题5题

补题链接：https://codeforces.com/gym/103409

A.Hero Named Magnus

A Hero Named Magnus
Input file: standard input
Output file: standard output
Time limit: 1 second
Memory limit: 512 megabytes
Dota 2 is a multiplayer online battle arena (MOBA) video game developed and published by Valve. Dota 2
is played in matches between two teams of five players, with each team occupying and defending their own
separate base on the map. Each of the ten players independently controls a powerful character, known as a
‘hero’, who all have unique abilities and differing styles of play. During a match players collect experience
points and items for their heroes to successfully defeat the opposing team’s heroes in player versus player
combat. A team wins by being the first to destroy the other team’s ‘Ancient’, a large structure located
within their base.
The International is an annual esports world championship tournament for the video game Dota 2, hosted
and produced by the game’s developer, Valve. The tournament consists of 18 teams; 12 based on final
results from the Dota Pro Circuit and six more from winning regional playoffs from North America, South
America, Southeast Asia, China, Eastern Europe, and Western Europe regions.
In Year 3021, The International is held in Guilin, China. Once again, just like 1000 years ago, Team LGD
from China will compete against Team Spirit from Russia. But as the championship developing, the rule
is that whoever wins the best of n (n is an odd positive integer) games will win the champion, so a team
should win at least n+1
2
games. (In 2021, n equals to only 5 and Team Spirit won by 3 : 2).
Before the game starts, teams can choose to ban specific heroes from being used by the opponent team.
Among these 1000 years, everyone knows that Team Spirit is very good at using a hero called Magnus,
which once helped them defeat Team LGD in 2021.
Although everyone thinks Team LGD will choose to ban Magnus from the beginning, team LGD thinks
differently. Somehow they think that they are strong enough to beat the opponent’s Magnus and they
will only start to ban Magnus in the x-th game if there is one.
To simplify the problem, if team LGD choose to ban Magnus, they will certainly win the game. Otherwise,
they may have a 50% possibility to win the game.
As one of Team LGD’s fans, JB wants to know what’s the minimum number of n that team LGD can
win the champion in the worst case.
Page 1 of 2
Input
The first line contains an integer T (1 ≤ T ≤ 105
), indicating the number of test cases.
In the next following T lines, each line contains an integer x (1 ≤ x ≤ 2 × 109
), indicating that Team
LGD will start to ban Magnus in the x-th game.
Output
For each test case, please output an integer in one line, indicating the minimum total number of games
to let Team LGD win.
Example
standard input standard output
2
1
3
1
5
Note
Ignoring everyone’s strongest wish, there exists x > 1 in the test data, which means Team LGD won’t
always choose to ban Magnus from the beginning.

题意：

• 战队从第x关开始赢比赛，问赛季总共有多少场比赛，战队才能赢得整个赛季（即赢的场次大于整个赛季场次的一半）。

思路：

• 直接输出x+x-1即可，输了x-1关，需要再赢x关就可以了。
• 不开longlong见祖宗。

#include
using namespace std;
typedef long long LL;
int main(){
    int T;  cin>>T;
    while(T--){
        LL n;  cin>>n;
        if(n==1)cout<<"1\n";
        else {
            cout<<(n+n-1)<<"\n";
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

I. PTSD

I. PTSD
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
There are n soldiers in JB kingdom, numbered as 1,2,⋯,n. The i-th soldier has a power value of i.

There is a tournament in the kingdom now. The soldiers need to be divided into several groups where each soldier belongs to exactly one group. Note that it’s allowed for a group to contain only one single soldier. For some unknown reason, some soldiers have a disease called PTSD (post-traumatic stress disorder). The soldiers with PTSD don’t like being the second strongest soldier in their groups. Formally speaking, a soldier with PTSD will be upset if there is exactly one other soldier with a larger power value than him in his group.

JB, the king of JB kingdom, wants to maximize the sum of the power values of the soldiers who feel upset because of PTSD. You are asked to help him divide the soldiers.

Input
There are multiple test cases. The first line of the input contains a positive integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤106), indicating the number of soldiers.

The second line contains a string s of length n. It’s guaranteed that s only contains ‘0’ and ‘1’. The i-th character describes the i-th soldier: If si= ‘1’, the i-th soldier has PTSD. Otherwise, the i-th soldier doesn’t have PTSD.

It’s guaranteed that the sum of n of all test cases doesn’t exceed 106.

Output
For each test case, output one line containing an integer, indicating the maximum sum of power values of the upset soldiers.

Example
inputCopy
4
5
10101
8
11111111
4
1100
4
0110
outputCopy
4
16
3
3
Note
For the first test case, a valid division is [1, 2], [3, 4], [5], which makes the 1-st soldier and the 3-rd soldier upset. [1, 2], [3, 5], [4] is also valid.

For the second test case, a valid division is [1, 2], [3, 4], [5, 6], [7, 8].

For the third test case, a valid division is [1, 3], [2, 4].

For the fourth test case, a valid division is [1, 2, 3, 4].

题意：

• 给出一个长为n的01序列，表示第i个士兵是否患有PTSD。
• 已知第i个士兵的力量为i， 现在给士兵分组（每组>=1人），如果组内有力量大于它的人，且他是PTSD，那他就会悲伤+i。
• 现在要求最大化所有士兵的悲伤和。（自由分组）

思路：

• 首先只要PTSD的士兵会悲伤，力量比他大的人都排在他后面。
• 所以倒序扫一遍，维护当前没有PTSD的或者没有力量比他大的人的数量，然后遇到一个PTSD就让他俩组合一下，答案累加即可。
• 不开longlong见祖宗。

#include
using namespace std;
typedef long long LL;
int main(){
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        string s;  cin>>s;
        LL t = 0, ans = 0;
        for(int i = n-1; i >= 0; i--){
            if(s[i]=='0')t++;
            else{
                if(t>0){
                    t--;  ans += i+1;
                }else{
                    t++;
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

G. Occupy the Cities

G. Occupy the Cities
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
JB is playing a game. There are n cities in the game, numbered as 1,2,⋯,n. The i-th city and the j-th city are adjacent if and only if i=j−1 or i=j+1. Initially, some of the cities are occupied by JB.

The game runs in rounds. At the beginning of a round, each occupied city can mark at most one adjacent unoccupied city as the target of attack. At the end of the round, all the attack targets marked become occupied. The game ends when all the cities are occupied.

JB wants to occupy all the cities in minimum rounds. Can you help him?

Input
There are multiple test cases. The first line of the test case contains a positive integer T, indicating the number of test cases. For each test case:

The first line contains an integer n (1≤n≤106), indicating the number of cities.

The next line contains a string s of length n. It’s guaranteed s only contains ‘0’ and ‘1’. The i-th character describes the initial state of the i-th city: if si= ‘1’, the i-th city is occupied by JB initially. Otherwise, the i-th city is not occupied initially.

It’s guaranteed that the sum of n over all the test cases doesn’t exceed 106. It’s also guaranteed that there is at least one ‘1’ in s.

Output
For each test case, output one line, containing the minimum number of rounds to occupy all the cities.

Example
inputCopy
5
3
010
4
0100
7
0001000
5
11111
6
010101
outputCopy
2
2
4
0
1
Note
For the second test case, the best way is 0100→0110→1111.

题意：

• 给出一个长为n的01序列，每个1每回合可以向相邻中的某一个0拓展，让那个0变成1。
• 求最少多少轮数组全部变成1。

思路：

• 反正无穷轮一定可以拓展到，且时间为相邻两个1之间0的数量的最大值差不多。考虑每个0左右最近的1，如果1先过来了，那么答案就是距离x，如果1先去别的方向了，那就是x+1。
• 二分最终的轮数mid，每次check每个0左右最近的1距离是否都<=x（1先往这边拓展），或者=x+1也可以被拓展到（1先往别的方向了）
• 左右最近的1可以O(n)预处理出来，复杂度O(nlogn)

//题意：长为n的01序列，每个1每次可以向相邻中的某一个0拓展，最少多少轮全部变成1.
//思路：二分轮数mid，每次check每个0左右最近的1距离是否都<=x-1，或者=x也可以被拓展到（1先往这边拓展）
#include
using namespace std;
typedef long long LL;
const int maxn = 2e6+10;
int n;  string s;
int pre[maxn], lst[maxn]; //预处理左右两边最近的1的位置
int vis[maxn];  //维护每个1是否选了拓展方向
int check(int x){
    for(int i = 0; i < n; i++)vis[i] = 0; //初始没有选
    for(int i = 0; i < n; i++){
        if(s[i]=='1')continue;
        int mi = min(i-pre[i], lst[i]-i)+1;
        if(mi <= x)continue;  //满足条件
        if(pre[i]>=0 && !vis[pre[i]] && mi<=x+1){ vis[pre[i]] = 1;  continue; }//左边有1且没用过，那么往这里拓展
        if(lst[i]<n && !vis[lst[i]] && mi<=x+1){ vis[lst[i]] = 1;  continue; }//右边有1且没用过，那么往这里拓展
        return 0;
    }
    return 1;
}
int main(){
    int T;  cin>>T;
    while(T--){
        cin>>n>>s;
        int x = -1e9;
        for(int i = 0; i < n; i++){
            pre[i] = x;  if(s[i]=='1')x = i;
        }
        x = 1e9;
        for(int i = n-1; i >= 0; i--){
            lst[i] = x;  if(s[i]=='1')x = i;
        }
        int l = 0, r = n;
        while(l < r){
            int mid = l+r>>1;
            if(check(mid))r = mid;
            else l = mid+1;
        }
        cout<<l<<"\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

E. Buy and Delete

E. Buy and Delete
time limit per test1.5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Alice and Bob are playing a game on a directed graph G. There are n vertices in G, labeled by 1,2,…,n. Initially, there are no edges in G. Alice will first buy some direct edges from the shop and then add them into G. After that, Bob needs to delete edges until there are no edges in G. In a deletion round, Bob can delete a subset of edges S from G, such that when only keeping edges in S, the graph is acyclic. Note that Alice can buy nothing, and in such a case the number of deletion rounds is 0.

There are m edges in the shop. Alice has c dollars, so the total price of edges she will buy should not exceed c. Alice wants to maximize the number of deletion rounds while Bob wants to minimize it. Both Alice and Bob will play optimally. Please write a program to predict the number of deletion rounds.

Input
The input contains only a single case.

The first line of the input contains three integers n,m and c (2≤n≤2000, 1≤m≤5000, 1≤c≤109), denoting the number of vertices in G, the number of edges in the shop, and how many dollars Alice has.

In the next m lines, the i-th line (1≤i≤m) contains three integers ui,vi and pi (1≤ui,vi≤n, ui≠vi, 1≤pi≤100000), denoting a directed edge in the shop. Alice can pay pi dollars to buy it, and add an edge from vertex ui to vertex vi in G.

Output
Print a single line containing an integer, denoting the number of deletion rounds.

Examples
inputCopy
3 2 4
1 2 5
2 3 6
outputCopy
0
inputCopy
3 3 3
1 2 1
2 3 1
1 3 1
outputCopy
1

题意：

• n个点的有向图，初始只有点没有边，然后A有c元可以在商店买边（u->v的边价值w元）
• B每次可以删边集（此集合独立于图时是无环的）
• A希望最大化删除次数，B希望最小化，都采用最优策略，求要几轮删完。

思路：

• 从B的角度看完全图，次数只有可能为{0无边,1无环,2环}。因为每次可以删掉一整个环嘛。
• 所以A加边时需要尽可能构成环。所以只需判断图中最小有向环权值是否<=c即可（A是否能买得起环）
• 判环的方式直接dfs会TLE，可以跑n边Dijkstra，每次从1点出发再回到这点，即st==ed的情况下，dist[ed]的值就是最小环。 因为初始值要赋0，所以加个if判断一下y==st时候更新dist[x] + w的值即可，最后判断一下是否能买得起。

//题意：n个点的有向图，A有c元买边，B每次删边集（此集合独立于图时是无环的），A希望最大化次数，都最优策略，要几轮删完。
//思路：从B的角度看完全图，次数只有可能为{0无边,1无环,2环}。所以A加边时需要尽可能构成环。所以只需判断图中最小有向环权值是否<=c即可。
//有向图最小环：对于每条边，判断从一点出发是否能够不通过这条边再回到起点即可，以其中一点为起点跑dijkstra，权值即为该点最小环。跑n遍即可。
#include
using namespace std;
typedef long long LL;
const LL maxn = 5e4+10;
#define PII pair<LL,LL>
#define fi first
#define se second

LL n, m, c;
struct node{ LL x, y, w; }e[maxn];
vector<PII>G[maxn];

LL dist[maxn], vis[maxn], res = 1e18;
void dijkstra(LL st, LL ed){
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0,st});
    for(LL i = 1; i <= n; i++)dist[i]=1e9+10, vis[i] = 0;
    dist[st] = 0;
    while(q.size()){
        LL x = q.top().se;  q.pop();
        if(vis[x])continue;
        vis[x] = 1;
        for(auto it : G[x]){
            LL y = it.fi, w = it.se;
            if(y == st) res = min(res, dist[x] + w);
            if(dist[y] > dist[x]+w){
                dist[y] = dist[x]+w;
                q.push({dist[y],y});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>c;
    LL ok = 0;
    for(LL i = 1; i <= m; i++){
        LL x, y, z;  cin>>x>>y>>z;
        G[x].push_back({y,z});
        e[i] = {x,y,z};
        if(z<=c){ ok = 1; }
    }
    if(ok==0){ cout<<"0\n"; return 0; } //1个都买不起, 不用删
    for(int i = 1; i <= n; i++){
        dijkstra(i,i);
    }
    if(res<=c)cout<<"2\n"; //买得起环, 要删2次
    else cout<<"1\n";      //买不起环，1次删完
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

D.Assumption is All You Need

D. Assumption is All You Need
time limit per test1.5 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
JB holds the belief that assumption is all you need to solve a problem. In order to prove that, JB has given you two permutations of numbers from 1 to n: A and B, and JB wants you to output a sequence of element swapping operation (xi,yi) on A, so that:

every pair of swapped element forms an inversion pair (i.e. xiAyi when the i-th operation is being performed)
A will become B at the end of the swapping sequence.
or determine it is impossible. Help prove JB’s belief by solving this problem!
Input
There are multiple test cases. The first line of the input contains one integer T indicating the number of test cases. For each test case:

The first line contains one integer n (1≤n≤2021), indicating the number elements in A and B.

The second line contains n distinct integers A1,A2,…,An (1≤Ai≤n), indicating the array A.

The third line contains n distinct integers B1,B2,…,Bn (1≤Bi≤n), indicating the array B.

It is guaranteed that the sum of n in all test cases will not exceed 2021.

Output
For each test case, if there doesn’t exist a sequence, output the one line containing one integer “-1”.

Otherwise, in the first line output one integer k (0≤k≤n(n−1)2), indicating the length of the swapping sequence. Then, output k line each containing two integers xi and yi (1≤xi

Example
inputCopy
3
2
1 2
2 1
4
4 1 2 3
1 3 2 4
8
8 7 6 5 4 3 2 1
1 8 7 6 5 4 3 2
outputCopy
-1
2
1 2
2 4
7
7 8
6 7
5 6
4 5
3 4
2 3
1 2

题意：

• 两个长为n的排列A和B，每次可以交换A中的逆序对，问A能否通过操作得到B，打印操作。

思路：

• 因为逆序对（只能前面大的和后面小的换），所以贪心较大的数应该尽可能的放在前边。
• 然后从大到小枚举每个数构造。如果当前下标比目标下标大，因为再往前已经没有更大的数了，所以肯定构造不出来了。
• 因为对于已经安排好位置的更大的i不能再去交换它，所以在当前id和目标id之间找最大的数不停交换直到不能交换为止即可。
• 最后判断一下A数组是否等于B数组，然后输出。

//题意：两个长为n的排列A和B，每次可以交换A中的逆序对，问A能否通过操作得到B，打印操作。
//思路：因为逆序对（只能前面大的和后面小的换），贪心较大的数应该尽可能的放在前边。然后从大到小枚举每个数，构造即可。
#include
using namespace std;
const int maxn = 5e4+10;
int a[maxn], b[maxn], ida[maxn], idb[maxn];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n;  cin>>n;
        for(int i = 1; i <= n; i++){
            cin>>a[i];  ida[a[i]] = i;
        }
        for(int i = 1; i <= n; i++){
            cin>>b[i];  idb[b[i]] = i;
        }
        int ok = 1;
        vector<pair<int,int> >res;
        for(int i = n; i >= 1; i--){ //从大到小枚举数n到1
            if(ida[i]==idb[i])continue;
            if(ida[i]>idb[i]){ ok = 0;  break;} //如果i的当前id比目标id大，那么永远也不可能交换到目标位置（前面没有更大的数了）
            int now = ida[i], goal = idb[i];    //当前位置, 目标位置
            for(int j = i-1; j >= 1; j--){      //对于已经安排好位置的更大的i不能再去交换它
                if(ida[j]>now && ida[j]<=goal){ //在当前id和目标id之间找最大的数不停交换直到不能交换为止
                    ida[i] = ida[j];
                    swap(a[now], a[ida[j]]);
                    swap(now, ida[j]);
                    res.push_back({now, ida[j]});
                }
            }
        }
        for(int i = 1; i <= n; i++){
            if(a[i]!=b[i])ok = 0;
        }
        if(ok==0)cout<<"-1\n";
        else{
            cout<<res.size()<<"\n";
            for(auto& x : res){
                if(x.first>x.second)swap(x.first,x.second);
                cout<<x.first<<" "<<x.second<<"\n";
            }
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47