Codeforces Round 829 (Div. 2)

A. Technical Support

题目:

Limit:

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

Describe:

You work in the quality control department of technical support for a large company. Your job is to make sure all client issues have been resolved.
Today you need to check a copy of a dialog between a client and a technical support manager. According to the rules of work, each message of the client must be followed by one or several messages, which are the answer of a support manager. However, sometimes clients ask questions so quickly that some of the manager’s answers to old questions appear after the client has asked some new questions.
Due to the privacy policy, the full text of messages is not available to you, only the order of messages is visible, as well as the type of each message: a customer question or a response from the technical support manager. It is guaranteed that the dialog begins with the question of the client.
You have to determine, if this dialog may correspond to the rules of work described above, or the rules are certainly breached.

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). Description of the test cases follows.
The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the total number of messages in the dialog.
The second line of each test case consists of $n$ characters “Q” and “A”, describing types of messages in the dialog in chronological order. Character “Q” denotes the message with client question, and character “A” — the message with technical support manager answer. It is guaranteed that the first character in the line equals to “Q”.

output:

Input-describe:

Output-describe:

For each test case print “Yes” (without quotes) if dialog may correspond to the rules of work, or “No” (without quotes) otherwise.

Example:

Input:

5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA

Output:

Yes
No
Yes
No
Yes

思路

持续记录Q和A的数量，当出现A时如果存在Q，则将Q的数量减一，当Q为0时记得将A也清零，最后判断是否有剩余的Q即可。

代码

#include<bits/stdc++.h>
using namespace std;

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

    int q = 0;
    int a = 0;
    for(auto c: s){
        if(c == 'Q'){
            q++;
        }
        else{
            a++;
            if(q > 0){
                a--;
                q--;
            }
            if(q == 0){
                a = 0;
            }
        }
    }
    
    if(q){
        cout << "No\n";
    }
    else{
        cout << "Yes\n";
    }
}

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

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

    return 0;
}

B. Kevin and Permutation

题目:

Limit:

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

Describe:

For his birthday, Kevin received the set of pairwise distinct numbers $1, 2, 3, \ldots, n$ as a gift.
He is going to arrange these numbers in a way such that the minimum absolute difference between two consecutive numbers be maximum possible. More formally, if he arranges numbers in order $p_1, p_2, \ldots, p_n$, he wants to maximize the value $$\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,$$ where $|x|$ denotes the absolute value of $x$.
Help Kevin to do that.

Input:

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. Description of the test cases follows.
The only line of each test case contains an integer $n$ ($2 \le n \leq 1,000$) — the size of the set.

output:

Input-describe:

Output-describe:

For each test case print a single line containing $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) describing the arrangement that maximizes the minimum absolute difference of consecutive elements.
Formally, you have to print a permutation $p$ which maximizes the value $\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert$.
If there are multiple optimal solutions, print any of them.

Example:

Input:

2
4
3

Output:

2 4 1 3
1 2 3

思路

没想到优雅的做法，所以把奇偶分开做了。

首先设定步长$step$为$n$的一半，没有详细证明，差不多猜的觉得是对的。

$n$为偶数的时候，从$step$到$1$，输出$i$和$i + step$，当$n$为奇数时，先输出$step$，然后同样迭代从$step$到$1$输出$i + step$和$i$，让$step$与最大值$n$相连，从而得到可能的最大差值。

代码

#include<bits/stdc++.h>
using namespace std;

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

    int step = (n + 1) / 2;
    if(n % 2 == 0){
        for(int i = 1; i <= step; i++){
            cout << i + step << " " << i << " ";
        }
    }
    else{
        cout << step << " ";
        for(int i = step - 1; i >= 1; i--){
            cout << i + step << " " << i << " ";
        }
    }
    
    cout << "\n";
}

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

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

    return 0;
}

C1. Make Nonzero Sum (easy version)

题目:

Limit:

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

Describe:

This is the easy version of the problem. The difference is that in this version the array can not contain zeros. You can make hacks only if both versions of the problem are solved.
You are given an array $[a_1, a_2, \ldots a_n]$ consisting of integers $-1$ and $1$. You have to build a partition of this array into the set of segments $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ with the following property:
Denote the alternating sum of all elements of the $i$-th segment as $s_i$: $s_i$ = $a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$. For example, the alternating sum of elements of segment $[2, 4]$ in array $[1, 0, -1, 1, 1]$ equals to $0 - (-1) + 1 = 2$. The sum of $s_i$ over all segments of partition should be equal to zero.
Note that each $s_i$ does not have to be equal to zero, this property is about sum of $s_i$ over all segments of partition.
The set of segments $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ is called a partition of the array $a$ of length $n$ if $1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$ and $r_i + 1 = l_{i+1}$ for all $i = 1, 2, \ldots k-1$. In other words, each element of the array must belong to exactly one segment.
You have to build a partition of the given array with properties described above or determine that such partition does not exist.
Note that it is not required to minimize the number of segments in the partition.

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10,000$). Description of the test cases follows.
The first line of each test case contains an integer $n$ ($1 \le n \le 200,000$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $-1$ or $1$) — the elements of the given array.
It’s guaranteed that the sum of $n$ over all test cases does not exceed $200,000$.

output:

Input-describe:

Output-describe:

For each test case, if required partition does not exist, print $-1$. Otherwise, print an integer $k$ — the number of segments in the partition.
Then in the $i$-th of the following $k$ lines print two integers $l_i$ and $r_i$ — description of the $i$-th segment. The following conditions should be satisfied:
$l_i \le r_i$ for each $i$ from $1$ to $k$. $l_{i + 1} = r_i + 1$ for each $i$ from $1$ to $(k - 1)$. $l_1 = 1, r_k = n$.
If there are multiple correct partitions of the array, print any of them.

Example:

Input:

4
4
1 1 1 1
6
-1 1 1 1 1 1
3
1 -1 1
1
1

Output:

1
1 4
2
1 3
4 6
-1
-1

思路

以为是easy version的做法，结果连hard version也一起做了。

WA了三发，因为加了一个特判……但是特判判错了……

把特判去掉之后过了

观察可以得到，需要知道是正一多还是负一多，以正一多的情况为例，需要找到某些位置，把正一转换为负一。可以知道，选择某个连续区间，区间的奇数下标位置的元素会被转换正负，所以若要转换正负，最小的区间长度为2，而容易知道，一段较长的区间的转换结果，可以由若干个长度为2和长度为1的子区间替换，而不影响转换结果，同时转换之后拥有更灵活的组合方式，同时题目不要求最小化区间数量，所以应该使用灵活的区间组合代替长的区间。同时可以知道，长度为1的区间不对结果产生任何影响，长度为2的区间则会转换第二个位置的正负。

所以问题就转换为，该如何选择若干个长度为2的区间，转换这些区间第二个位置的正负，从而让正负数量相等（剩余的区间可以用长度为1的子区间补满）？对于这个问题，可以贪心来做。只要枚举需要转换且合法的位置，把它们加入答案即可。

代码

#include<bits/stdc++.h>
using namespace std;

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

    int posi = 0, negt = 0;
    for(auto x: a){
        if(x > 0){
            posi++;
        }
        else{
            negt++;
        }
    }
    
    int tar = 1;
    int num = posi - negt;
    if(negt > posi){
        tar = -1;
        num = negt - posi;
    }

    vector<array<int,2>> ans;
    for(int i = 1; i < n && num > 0; i++){
        if(a[i] == tar){
            if(ans.size() == 0){
                for(int j = 0; j < i - 1; j++){
                    ans.push_back({j, j});
                }
                ans.push_back({i - 1, i});
                num -= 2;
            }
            else{
                int pre = ans.back()[1];
                if(i - pre <= 1){
                    continue;
                }
                for(int j = pre + 1; j < i - 1; j++){
                    ans.push_back({j, j});
                }
                ans.push_back({i - 1, i});
                num -= 2;
            }
        }
    }

    if(num != 0){
        cout << "-1\n";
    }
    else{
        int pre = ans.size() == 0? -1: ans.back()[1];
        if(pre != n - 1){
            for(int i = pre + 1; i < n; i++){
                ans.push_back({i, i});
            }
        }
        cout << ans.size() << "\n";
        for(auto [l, r]: ans){
            cout << l + 1 << " " << r + 1 << "\n";
        }
    }
}

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

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

    return 0;
}

C2. Make Nonzero Sum (hard version)

题目:

Limit:

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

Describe:

This is the hard version of the problem. The difference is that in this version the array contains zeros. You can make hacks only if both versions of the problem are solved.
You are given an array $[a_1, a_2, \ldots a_n]$ consisting of integers $-1$, $0$ and $1$. You have to build a partition of this array into the set of segments $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ with the following property:
Denote the alternating sum of all elements of the $i$-th segment as $s_i$: $s_i$ = $a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}$. For example, the alternating sum of elements of segment $[2, 4]$ in array $[1, 0, -1, 1, 1]$ equals to $0 - (-1) + 1 = 2$. The sum of $s_i$ over all segments of partition should be equal to zero.
Note that each $s_i$ does not have to be equal to zero, this property is about sum of $s_i$ over all segments of partition.
The set of segments $[l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]$ is called a partition of the array $a$ of length $n$ if $1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n$ and $r_i + 1 = l_{i+1}$ for all $i = 1, 2, \ldots k-1$. In other words, each element of the array must belong to exactly one segment.
You have to build a partition of the given array with properties described above or determine that such partition does not exist.
Note that it is not required to minimize the number of segments in the partition.

Input:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10,000$). Description of the test cases follows.
The first line of each test case contains an integer $n$ ($1 \le n \le 200,000$) — the length of array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $-1$, $0$, or $1$) — the elements of the given array.
It’s guaranteed that the sum of $n$ over all test cases does not exceed $200,000$.

output:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10,000$). Description of the test cases follows.
The first line of each test case contains an integer $n$ ($1 \le n \le 200,000$) — the length of array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $-1$, $0$, or $1$) — the elements of the given array.
It’s guaranteed that the sum of $n$ over all test cases does not exceed $200,000$.

Input-describe:

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10,000$). Description of the test cases follows.
The first line of each test case contains an integer $n$ ($1 \le n \le 200,000$) — the length of array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i$ is $-1$, $0$, or $1$) — the elements of the given array.
It’s guaranteed that the sum of $n$ over all test cases does not exceed $200,000$.

Output-describe:

For each test case print an integer $k$ — the number of segments in the partition. If required partition does not exist, print $-1$.
If partition exists, in the $i$-th of the following $k$ lines print two integers $l_i$ and $r_i$ — description of the $i$-th segment. The following conditions should be satisfied:
$l_i \le r_i$ for each $i$ from $1$ to $k$. $l_{i + 1} = r_i + 1$ for each $i$ from $1$ to $(k - 1)$. $l_1 = 1, r_k = n$.
If there are multiple correct partitions of the array, print any of them.

Example:

Input:

5
4
0 0 0 0
7
-1 1 0 1 0 1 0
5
0 -1 1 0 1
3
1 0 1
1
1

Output:

4
1 1
2 2
3 3
4 4
4
1 1
2 2
3 5
6 7
-1
2
1 1
2 3
-1

思路

加入$0$并不影响C1的思路，算法同样成立。

代码

#include<bits/stdc++.h>
using namespace std;

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

    int posi = 0, negt = 0;
    for(auto x: a){
        if(x > 0){
            posi++;
        }
        else if(x < 0){
            negt++;
        }
    }
    
    int tar = 1;
    int num = posi - negt;
    if(negt > posi){
        tar = -1;
        num = negt - posi;
    }

    vector<array<int,2>> ans;
    for(int i = 1; i < n && num > 0; i++){
        if(a[i] == tar){
            if(ans.size() == 0){
                for(int j = 0; j < i - 1; j++){
                    ans.push_back({j, j});
                }
                ans.push_back({i - 1, i});
                num -= 2;
            }
            else{
                int pre = ans.back()[1];
                if(i - pre <= 1){
                    continue;
                }
                for(int j = pre + 1; j < i - 1; j++){
                    ans.push_back({j, j});
                }
                ans.push_back({i - 1, i});
                num -= 2;
            }
        }
    }

    if(num != 0){
        cout << "-1\n";
    }
    else{
        int pre = ans.size() == 0? -1: ans.back()[1];
        if(pre != n - 1){
            for(int i = pre + 1; i < n; i++){
                ans.push_back({i, i});
            }
        }
        cout << ans.size() << "\n";
        for(auto [l, r]: ans){
            cout << l + 1 << " " << r + 1 << "\n";
        }
    }
}

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

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

    return 0;
}

D. Factorial Divisibility

题目:

Limit:

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

Describe:

You are given an integer $x$ and an array of integers $a_1, a_2, \ldots, a_n$. You have to determine if the number $a_1! + a_2! + \ldots + a_n!$ is divisible by $x!$.
Here $k!$ is a factorial of $k$ — the product of all positive integers less than or equal to $k$. For example, $3! = 1 \cdot 2 \cdot 3 = 6$, and $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$.

Input:

The first line contains two integers $n$ and $x$ ($1 \le n \le 500,000$, $1 \le x \le 500,000$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le x$) — elements of given array.

output:

Input-describe:

Output-describe:

In the only line print “Yes” (without quotes) if $a_1! + a_2! + \ldots + a_n!$ is divisible by $x!$, and “No” (without quotes) otherwise.

Example:

Input:

6 4
3 2 2 2 3 3

Output:

Yes

思路

首先可以知道，可以预处理计算出$1!$到$x!$，同时因为$a_i <= x$，所以也能计算出任意$a_i!$。至于无法存储这么大阶乘，可以考虑使用哈希来表示这个数，保险起见，我用了三哈希来确保哈希值能在该题目下唯一的表示一个数。同时，在模定义下，加法和乘法是仍然成立的，所以也可以按照题目的要求，计算$\sum (a_i!)$，同时可以知道，$\sum (a_i!) <= n * (x!)$，所以在知道了$(x!)$和$\sum (a_i!)$的情况下，枚举$k$从$1$到$n$，判断在模域下，是否有$k * (x!) == \sum(a_i!)$即可。

代码

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve(){
    i64 n, x;
    cin >> n >> x;
    vector<i64> a(n);
    for(auto &e: a){
        cin >> e;
    }

    i64 mods[3];
    mods[0] = (i64)1e9 + 7;
    mods[1] = (i64)1e9 + 9;
    mods[2] = (i64)1e9 + 21;

    auto mul = [&](array<i64,3> arr, i64 num){
        array<i64,3> res;
        for(int i = 0; i < 3; i++){
            res[i] = ((arr[i] * num) % mods[i] + mods[i]) % mods[i];
        }
        return res;
    };
    auto add = [&](array<i64,3> arr1, array<i64,3> arr2){
        array<i64,3> res;
        for(int i = 0; i < 3; i++){
            res[i] = ((arr1[i] + arr2[i]) % mods[i] + mods[i]) % mods[i];
        }
        return res;
    };

    vector<array<i64,3>> calc(x + 1, {0, 0, 0});
    calc[1] = {1, 1, 1};
    for(i64 i = 2; i <= x; i++){
        calc[i] = mul(calc[i - 1], i);
    }

    array<i64,3> tar = {0, 0, 0};
    for(auto e: a){
        tar = add(tar, calc[e]);
   }

    for(i64 i = 1; i <= n; i++){
        if (tar == mul(calc[x], i)){
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

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

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

    return 0;
}