Codeforces Round 939 (Div. 2)

A. Nene’s Game

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

Nene invented a new game based on an increasing sequence of integers $a_1, a_2, \ldots, a_k$.
In this game, initially $n$ players are lined up in a row. In each of the rounds of this game, the following happens:
Nene finds the $a_1$-th, $a_2$-th, $\ldots$, $a_k$-th players in a row. They are kicked out of the game simultaneously. If the $i$-th player in a row should be kicked out, but there are fewer than $i$ players in a row, they are skipped.
Once no one is kicked out of the game in some round, all the players that are still in the game are declared as winners.
For example, consider the game with $a=[3, 5]$ and $n=5$ players. Let the players be named player A, player B, $\ldots$, player E in the order they are lined up initially. Then,
Before the first round, players are lined up as ABCDE. Nene finds the $3$-rd and the $5$-th players in a row. These are players C and E. They are kicked out in the first round. Now players are lined up as ABD. Nene finds the $3$-rd and the $5$-th players in a row. The $3$-rd player is player D and there is no $5$-th player in a row. Thus, only player D is kicked out in the second round. In the third round, no one is kicked out of the game, so the game ends after this round. Players A and B are declared as the winners.
Nene has not yet decided how many people would join the game initially. Nene gave you $q$ integers $n_1, n_2, \ldots, n_q$ and you should answer the following question for each $1 \le i \le q$ independently:
How many people would be declared as winners if there are $n_i$ players in the game initially?

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 250$). The description of test cases follows.
The first line case contains two integers $k$ and $q$ ($1 \le k, q \le 100$) — the length of the sequence $a$ and the number of values $n_i$ you should solve this problem for.
The second line contains $k$ integers $a_1,a_2,\ldots,a_k$ ($1\leq a_1<a_2<\ldots<a_k\leq 100$) — the sequence $a$.
The third line contains $q$ integers $n_1,n_2,\ldots,n_q$ ($1\leq n_i \leq 100$).

output:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 250$). The description of test cases follows.
The first line case contains two integers $k$ and $q$ ($1 \le k, q \le 100$) — the length of the sequence $a$ and the number of values $n_i$ you should solve this problem for.
The second line contains $k$ integers $a_1,a_2,\ldots,a_k$ ($1\leq a_1<a_2<\ldots<a_k\leq 100$) — the sequence $a$.
The third line contains $q$ integers $n_1,n_2,\ldots,n_q$ ($1\leq n_i \leq 100$).

Input-describe:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 250$). The description of test cases follows.
The first line case contains two integers $k$ and $q$ ($1 \le k, q \le 100$) — the length of the sequence $a$ and the number of values $n_i$ you should solve this problem for.
The second line contains $k$ integers $a_1,a_2,\ldots,a_k$ ($1\leq a_1<a_2<\ldots<a_k\leq 100$) — the sequence $a$.
The third line contains $q$ integers $n_1,n_2,\ldots,n_q$ ($1\leq n_i \leq 100$).

Output-describe:

For each test case, output $q$ integers: the $i$-th ($1\le i \le q$) of them should be the number of players declared as winners if initially $n_i$ players join the game.

Example:

Input:

6
2 1
3 5
5
5 3
2 4 6 7 9
1 3 5
5 4
3 4 5 6 7
1 2 3 4
2 3
69 96
1 10 100
1 1
100
50
3 3
10 20 30
1 10 100

Output:

2
1 1 1
1 2 2 2
1 10 68
50
1 9 9

思路

二分一下

代码

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
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    int k, q;
    cin >> k >> q;
    vector<int> a(k);
    for(auto &x: a){
        cin >> x;
    }

    while(q--){
        int n;
        cin >> n;
        
        int idx = upper_bound(a.begin(), a.end(), n) - a.begin();

        while(idx != 0 && n > 0){
            n -= idx;
            idx = upper_bound(a.begin(), a.end(), n) - a.begin();
        }
        
        cout << n << " ";
    }
    
    cout << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

B. Nene and the Card Game

题目:

Limit:

time limit per test: 1 second
memory limit per test: 256 megabytes

Describe:

You and Nene are playing a card game. The deck with $2n$ cards is used to play this game. Each card has an integer from $1$ to $n$ on it, and each of integers $1$ through $n$ appears exactly on $2$ cards. Additionally, there is a table where cards are placed during the game (initially, the table is empty).
In the beginning of the game, these $2n$ cards are distributed between you and Nene so that each player receives $n$ cards.
After it, you and Nene alternatively take $2n$ turns, i.e. each person takes $n$ turns, starting with you. On each turn:
The player whose turn is it selects one of the cards in his hand. Let $x$ be the number on it. The player whose turn is it receives $1$ point if there is already a card with the integer $x$ on the table (otherwise, he receives no points). After it, he places the selected card with the integer $x$ on the table.
Note that turns are made publicly: each player can see all the cards on the table at each moment.
Nene is very smart so she always selects cards optimally in order to maximize her score in the end of the game (after $2n$ rounds). If she has several optimal moves, she selects the move that minimizes your score in the end of the game.
More formally, Nene always takes turns optimally in order to maximize her score in the end of the game in the first place and to minimize your score in the end of the game in the second place.
Assuming that the cards are already distributed and cards in your hand have integers $a_1, a_2, \ldots, a_n$ written on them, what is the maximum number of points you can get by taking your turns optimally?

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.
The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards you and Nene receive in the beginning of the game.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the integers on the cards in your hand. It is guaranteed that each integer from $1$ through $n$ appears in the sequence $a_1, a_2, \ldots, a_n$ at most $2$ times.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

output:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.
The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards you and Nene receive in the beginning of the game.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the integers on the cards in your hand. It is guaranteed that each integer from $1$ through $n$ appears in the sequence $a_1, a_2, \ldots, a_n$ at most $2$ times.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Input-describe:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.
The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards you and Nene receive in the beginning of the game.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the integers on the cards in your hand. It is guaranteed that each integer from $1$ through $n$ appears in the sequence $a_1, a_2, \ldots, a_n$ at most $2$ times.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output-describe:

For each test case, output one integer: the maximum number of points you can get.

Example:

Input:

5
4
1 1 2 3
8
7 4 1 2 8 8 5 5
8
7 1 4 5 3 4 2 6
3
1 2 3
1
1

Output:

1
2
1
0
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
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    int n;
    cin >> n;
    set<int> st;
    int ans = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(st.count(x)){
            ans++;
        }
        st.insert(x);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

C. Nene’s Magical Matrix

题目:

Limit:

time limit per test: 2 seconds
memory limit per test: 256 megabytes

Describe:

The magical girl Nene has an $n\times n$ matrix $a$ filled with zeroes. The $j$-th element of the $i$-th row of matrix $a$ is denoted as $a_{i, j}$.
She can perform operations of the following two types with this matrix:
Type $1$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{i, j}:=p_j$ for all $1 \le j \le n$ simultaneously. Type $2$ operation: choose an integer $i$ between $1$ and $n$ and a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$. Assign $a_{j, i}:=p_j$ for all $1 \le j \le n$ simultaneously.
Nene wants to maximize the sum of all the numbers in the matrix $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}a_{i,j}$. She asks you to find the way to perform the operations so that this sum is maximized. As she doesn’t want to make too many operations, you should provide a solution with no more than $2n$ operations.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of test cases follows.
The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.

output:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of test cases follows.
The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.

Input-describe:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of test cases follows.
The only line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the size of the matrix $a$.
It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5 \cdot 10^5$.

Output-describe:

For each test case, in the first line output two integers $s$ and $m$ ($0\leq m\leq 2n$) — the maximum sum of the numbers in the matrix and the number of operations in your solution.
In the $k$-th of the next $m$ lines output the description of the $k$-th operation:
an integer $c$ ($c \in {1, 2}$) — the type of the $k$-th operation; an integer $i$ ($1 \le i \le n$) — the row or the column the $k$-th operation is applied to; a permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$ — the permutation used in the $k$-th operation.
Note that you don’t need to minimize the number of operations used, you only should use no more than $2n$ operations. It can be shown that the maximum possible sum can always be obtained in no more than $2n$ operations.

Example:

Input:

2
1
2

Output:

1 1
1 1 1
7 3
1 1 1 2
1 2 1 2
2 1 1 2

思路

构造，想不出来是真的想不出来

代码

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
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    int n;
    cin >> n;

    int s = 0;
    for(int i = 1; i <= n; i++){
        s += i * (2 * i - 1);
    }

    cout << s << ' ';

    int m = 2 * n;

    cout << m << "\n";

    for(int i = n; i >= 1; i--){
        cout << 1 << " " << i << " ";

        for(int j = 1; j <= n; j++){
            cout << j << " ";
        }

        cout << "\n";

        cout << 2 << " " << i << " ";

        for(int j = 1; j <= n; j++){
            cout << j << " ";
        }

        cout << "\n";
   }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}