算法练习专栏——Codeforces——CodeforcesRound38-div3

A:Yogurt Sale

“Vosmiorochka”商店的一份酸奶价格为 a burles，但有促销活动，您可以以 b burles 购买两份酸奶。

Maxim 需要购买正好 n 酸奶。购买两杯酸奶时，他可以选择以正价购买，也可以以促销价购买。

Maxim 购买 n 酸奶的最低金额是多少？

输入

第一行包含一个整数 $t$ ( $1 \le t \le {10}^{4}$ ) - 测试用例的数量。

每个测试用例的第一行也是唯一一行包含三个整数 $n$ 、 $a$ 和 $b$ ( $1 \le n \le 100$ 、 $1 \le a, b \le 30$ ) - Maxim 想购买的酸奶数量、一份酸奶的价格以及促销时两杯酸奶的价格。

输出

对于每个测试用例，在单独的行中打印在“Vosmiorochka”购买 $n$ 酸奶的最低成本。

Example

input

output

笔记

在示例的第三个测试用例中，以 15 burles 购买三份酸奶比以 11 购买两份酸奶和以 5 购买一份酸奶更有利。

在该示例的第四个测试用例中，您需要购买四种酸奶，每种酸奶为 5 burles。

代码

#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t -- ){
        int a, b, n;
        cin >> n >> a >> b;
        if (n % 2 == 0) {
            if (b < (2 * a)) cout << b * (n / 2) << '\n';
            else cout << a * n << '\n';
        }
        else{
            if (b < (2 * a)) cout << b * (n / 2) + a << '\n';
            else cout << a * n << '\n';
        }
    }
}

B:Progressive Square

大小为 $n$ 的渐进正方形是一个 $n \times n$ 矩阵。 Maxim 选择三个整数 $a _ {1,1}$ 、 $c$ 和 $d$ ，并根据以下规则构造渐进平方：

$$
a _ {i+1,j} = a _ {i,j} + c
$$

$$
a _ {i,j+1} = a _ {i,j} + d
$$

例如，如果 $n = 3$ 、 $a _ {1,1} = 1$ 、 $c=2$ 和 $d=3$ ，则渐进方块如下所示：

$$
\begin{pmatrix} 1 & 4 & 7 \\ 3 & 6 & 9 \\ 5 & 8 & 11 \end{pmatrix}
$$
上个月，Maxim 构建了一个渐进正方形并记住了 $n$ 、 $c$ 和 $d$ 的值。最近，他发现了 $n^2$ 个整数，并想确保这些确实是那个特定正方形的元素。

可以证明，对于 $n$ 、 $a _ {1,1}$ 、 $c$ 和 $d$ 的任何值，都恰好存在一个满足所有规则的渐进正方形。

输入

第一行包含一个整数 $t$ ( $1 \le t \le {10} ^ 4$ ) - 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$ 、 $c$ 和 $d$ ( $2 \le n \le 500$ 、 $1 \le c, d \le 10^6$ ) - 正方形的大小以及 $c$ 和 $d$ 的值，如所述在声明中。

每个测试用例的第二行包含 $n \cdot n$ 整数 $a _ 1, a _ 2, \dots, a _ {n \cdot n}$ ( $1 \le a _ i \le 10^9$ ) - Maxim 找到的元素。

保证所有测试用例的 $n ^ 2$ 之和不超过 $25 \cdot {10} ^ 4$ 。

输出

对于每个测试用例，如果可以从数组元素 $a$ 构造给定的 $n$ 、 $c$ 和 $d$ 的渐进正方形，则在单独的行中输出“YES”，否则输出“NO”。

您可以以任何大小写(小写或大写)输出每个字母。例如，字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。

Example

input

5
3 2 3
3 9 6 5 7 1 10 4 8
3 2 3
3 9 6 5 7 1 11 4 8
2 100 100
400 300 400 500
3 2 3
3 9 6 6 5 1 11 4 8
4 4 4
15 27 7 19 23 23 11 15 7 3 19 23 11 15 11 15

output

NO
YES
YES
NO
NO

代码

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n, c, d;
        cin >> n >> c >> d;
        vector<int> v(n * n);
        for(auto &x : v) cin >> x;
        sort(v.begin(), v.end());
        vector<vector<int> > a(n, vector<int>(n));
        a[0][0] = v[0];
        vector<int> nv;
        nv.reserve(n * n);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                nv.push_back(a[i][j]);
                if (i + 1 < n){
                    a[i + 1][j] = a[i][j] + d;
                }
                if (j + 1 < n){
                    a[i][j + 1] = a[i][j] + c;
                }
            }
        }
        sort(nv.begin(), nv.end());
        cout << (v == nv ? "YES" : "NO") << '\n';
    }

}

C:Inhabitant of the Deep Sea

https://codeforces.com/contest/1955/problem/C

$n$ 船只出发探索海洋深处。船只编号从 $1$ 到 $n$ ，并按升序排列；第 $i$ 艘船的耐久度为 $a _ i$ 。

海妖按照特定的顺序攻击了船只 $k$ 次。首先，它攻击第一艘船，然后是最后一艘，然后再次攻击第一艘，依此类推。

海妖的每次攻击都会使飞船的耐久度降低 $1$ 。当船的耐久度下降到 $0$ 时，它会沉没并且不再受到攻击(因此船不再是第一艘或最后一艘，海妖只攻击尚未沉没的船)。如果所有船只都沉没了，海妖就没有什么可攻击的了，它就会游走。

例如，如果是 $n=4$ 、 $k=5$ 和 $a=[1, 2, 4, 3]$ ，则会发生以下情况：

1.海妖攻击第一艘船，耐久度为零，现在 $a = [2, 4, 3]$ ；
2.海妖攻击最后一艘船，现在是 $a = [2, 4, 2]$ ；
3.海妖攻击第一艘船，现在是 $a = [1, 4, 2]$ ；
4.海妖攻击了最后一艘船，现在是 $a = [1, 4, 1]$ ；

海妖攻击第一艘船，其耐久度为零，现在为 $a = [4, 1]$ 。

海妖袭击后击沉了多少艘船？

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ( $1 \le n \le 2 \cdot 10^5$ , $1 \le k \le 10^{15}$ ) - 船只数量以及 Kraken 攻击船只的次数。

每个测试用例的第二行包含 $n$ 整数 $a _ 1, a _ 2, \dots, a _ n$ ( $1 \le a _ i \le 10^9$ ) - 船舶的耐用性。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，在单独的行中输出 Kraken 击沉的船只数量。

Example

input

output

代码

#include<iostream>
#include<cstring>
#include<vector>
#include<deque>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n; LL k;
        cin >> n >> k;
        deque<LL> q;
        for(int i = 0; i < n; i++){
            LL x;
            cin >> x;
            q.push_back(x);
        }
        while(k > 1 && !q.empty()){
            if (q.size() == 1){
                if (k >= q[0]){
                    q.pop_back();
                }
                break;
            }
            LL t = k / 2;
            t = min(t, q.front());
            t = min(t, q.back());
            q.front() -= t;
            q.back() -= t;
            k -= 2 * t;
            if (q.front() == 0) q.pop_front();
            if (q.back() == 0) q.pop_back();
        }
        if (k == 1 && !q.empty()){
            q.front() -= 1;
            if (q.front() == 0) q.pop_front();
        }
        cout << n - q.size() << '\n';
    }

}

D:Inaccurate Subsequence Search

Maxim 有一个由 $n$ 个整数组成的数组 $a$ 和一个由 $m$ 个整数组成的数组 $b$ ( $m \le n$ )。

如果数组 $c$ 的元素可以重新排列，使得至少其中的 $k$ 与数组 $b$ 的元素匹配，Maxim 认为长度为 $m$ 的数组 $c$ 是好的。

例如，如果 $b = [1, 2, 3, 4]$ 和 $k = 3$ ，则数组 $[4, 1, 2, 3]$ 和 $[2, 3, 4, 5]$ 很好(它们可以按如下方式重新排序： $[1, 2, 3, 4]$ 和 $[5, 2, 3, 4]$ )，而数组 $[3, 4, 5, 6]$ 和 $[3, 4, 3, 4]$ 不好。

Maxim 希望选择长度为 $m$ 的数组 $a$ 的每个子段作为数组 $c$ 的元素。帮助 Maxim 计算有多少个选定的阵列是好的。

换句话说，找到使元素 $a _ l, a _ {l+1}, \dots, a _ {l + m - 1}$ 形成良好数组的位置数 $1 \le l \le n - m + 1$ 。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$ 、 $m$ 和 $k$ ( $1 \le k \le m \le n \le 2 \cdot 10^5$ ) - 数组中的元素数量 $a$ 和 $b$ ，即所需的匹配元素数量。

每个测试用例的第二行包含 $n$ 整数 $a _ 1, a _ 2, \dots, a _ n$ ( $1 \le a _ i \le 10^6$ ) - 数组 $a$ 的元素。

每个测试用例的第三行包含 $m$ 整数 $b _ 1, b _ 2, \dots, b _ m$ ( $1 \le b _ i \le 10^6$ ) - 数组 $b$ 的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$ 。同样，保证所有测试用例的 $m$ 之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，在单独的行上输出数组 $a$ 的良好子段的数量。

思路

使用滑动窗口的思路

代码

#include <iostream>
#include <algorithm>
#include <map>

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)

using namespace std;
typedef long long ll;

void solve() {
    int N, M, K; cin >> N >> M >> K;
    map<int, int> cntA, cntB;
    ll A[N];
    int cnt = 0;
    F0R(i, N) cin >> A[i];
    F0R(i, M) {
        int X; cin >> X; cntB[X]++;
    }
 
    F0R(i, M-1) {
        cntA[A[i]]++;
        if (cntA[A[i]] <= cntB[A[i]]) cnt++;
    }
    int ans = 0;
    FOR(i, M-1, N) {
        cntA[A[i]]++;
        if (cntA[A[i]] <= cntB[A[i]]) cnt++;
        if (cnt >= K) ans++;
        cntA[A[i-M+1]]--;
        if (cntA[A[i-M+1]] < cntB[A[i-M+1]]) cnt--;
    }
    cout << ans << endl;
 
}
 
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
 
    int T = 1;
    cin >> T;
    while(T--) {
        solve();
    }
 
	return 0;
}

E:Long Inversions

https://codeforces.com/contest/1955/problem/E

给出了长度为 $n$ 的二进制字符串 $s$ 。二进制字符串是仅由字符“1”和“0”组成的字符串。

您可以选择一个整数 $k$ ( $1 \le k \le n$ )，然后多次应用以下操作：选择字符串中的 $k$ 个连续字符并将它们反转，即将所有“0”替换为“1”，反之亦然反之亦然。

使用这些操作，您需要使字符串中的所有字符等于“1”。

例如，如果 $n=5$ 、 $s=00100$ ，您可以选择 $k=3$ 并按以下步骤操作：

选择从 $1$ -st到 $3$ -rd字符的子串，得到 $s=\color{blue}{110}00$ ；
选择从第 $3$ -rd到第 $5$ -th字符的子串，得到 $s=11\color{blue}{111}$ ；

使用所描述的操作查找可以使字符串中的所有字符等于“1”的 $k$ 的最大值。请注意，实现此目的所需的操作数量并不重要。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 5000$ ) - 字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$ ，由字符“1”和“0”组成。

保证测试中所有测试用例的值 $n^2$ 之和不超过 $25 \cdot 10^6$ 。

输出

对于每个测试用例，输出可以使用所描述的操作获得仅由字符“1”组成的字符串 $s$ 的最大整数 $k$ }( $1 \le k \le n$ )。

Example

input

5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

output

笔记

在第一个示例中，所有子段都很好。

在第二个示例中，好的子分段从位置 $1$ 、 $2$ 和 $3$ 开始。

在第三个示例中，好的子分段从位置 $1$ 和 $2$ 开始。

思路

只需要枚举所有的然后模拟操作即可.

操作需要贪心的操作,即从前往后如果当前位置为0就操作,否则不操作,直接暴力修改是(N3)的.

但是修改实际上是一个区间异或操作,可以用差分实现,复杂度为(N2).

代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            char c;
            cin >> c;
            a[i] = c - '0';
        }
        for(int i = n; i >= 1; i--){
            auto b = a;
            for(int j = n; j >= 1; j--){
                b[j] ^= b[j - 1];
            }
            bool ok = true;
            for(int j = 1; j <= n; j++){
                if ((b[j] ^ b[j - 1]) == 0 && j + i - 1 <= n){
                    b[j] ^= 1;
                    if (j + i <= n) b[j + i] ^= 1;
                }
                b[j] ^= b[j - 1];
                if (b[j] == 0){
                    ok = false;
                    break;
                }
            }
            if (ok){
                cout << i << '\n';
                break;
            }
        }
    }

}

F:Unfair Game

https://codeforces.com/contest/1955/problem/F

晚上Alice和Bob聚集在一起，对一个 $n$ 整数序列进行了一场激动人心的游戏，序列中的每个整数**不超过 $4$ **。游戏规则太复杂，无法描述，所以我们只描述获胜条件 - 如果序列中所有数字的按位异或不为零，则爱丽丝获胜；否则，鲍勃获胜。

他们邀请伊芙担任评委。最初，Alice 和 Bob 玩的是 $n$ 号码。一场游戏结束后，Eve 从序列中删除一个数字，然后 Alice 和 Bob 玩 $n-1$ 数字。 Eve 再次删除一个数字，之后 Alice 和 Bob 玩 $n - 2$ 数字。这一直持续到数字序列为空为止。

Eve 似乎认为在这样的游戏中，Alice 几乎总是获胜，所以她希望 Bob 获胜的次数尽可能多。如果夏娃以最佳方式删除数字，则确定鲍勃可以战胜爱丽丝的最大次数。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例的数量。

每个测试用例的第一行也是唯一一行包含四个整数 $p_i$ ( $0 \le p_i \le 200$ ) - 游戏开始时序列中的一、二、三和四的数量。

输出

对于每个测试用例，如果 Eve 以最佳方式删除数字，则在单独的行中打印 Bob 获胜的最大次数。

Example

input

output

思路

显然4只要是奇数个肯定是Alice获胜,所以第一步是要把4变成偶数个.

然后可以发现必须要1,2,3奇偶性相同才可以,我们可以枚举是让1,2,3数量同时为奇数还是同时为偶数,取较大的即可.

代码

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int c[4];
        for(int i = 0; i < 4; i++) cin >> c[i];
        if (c[3] % 2 == 1) c[3] -= 1;
        int ans = 0;
        for(int i = 0; i < 2; i++){
            int t[4];
            memcpy(t, c, sizeof t);
            int sum = t[3] / 2 + (i == 1);
            for(int j = 0; j < 3; j++){
                if (t[j] % 2 != i) t[j] -= 1;
                if (t[j] < 0) sum = -1e9;
                else sum += t[j] / 2;
            }
            ans = max(ans, sum);
        }
        cout << ans << '\n';
    }

}

算法练习专栏——Codeforces——Codeforces Round 943 (Div. 3) 上一篇

算法练习专栏——Codeforces——Codeforces Round 942 (Div. 2) 下一篇