【记录CF】Codeforces Round #780 (Div. 3) A~F1 题解

最新推荐文章于 2024-04-29 11:56:38 发布

辞树c

最新推荐文章于 2024-04-29 11:56:38 发布

阅读量533

点赞数

分类专栏： Codeforces 文章标签： c++ 算法 acm竞赛蓝桥杯

本文链接：https://blog.csdn.net/qq_58207591/article/details/123917177

版权

Codeforces 专栏收录该内容

7 篇文章 1 订阅

订阅专栏

A. Vasya and Coins

B. Vlad and Candies

C. Get an Even String

D. Maximum Product Strikes Back

E. Matrix and Shifts

F1. Promising String (easy version)

A. Vasya and Coins

题目链接：Problem - A - Codeforces

题目大意：Vasya 有 a 个 1-burle coin，有 b 个 2-burle coin，问他不能通过不找钱支付的价格的最小值。

解题思路：如果 a 不为 0，从 1 ~ a + b * 2 中的所有价格都可以经过组合进行支付，因此最小不能支付的价格为 a + b * 2 + 1；如果 a 为 0，不论 2-burle coin 有几个，都无法表示 1 这个价格，因此最小不能支付的价格为 1。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        if(a == 0) cout << 1 << endl;
        else cout << a + b * 2 + 1 << endl;
    }
    return 0;
}

B. Vlad and Candies

题目链接：Problem - B - Codeforces

题目大意：给定一个序列，第 i 个位置代表第 i 种糖果的数量，每次吃糖果只能吃当前数量最多的糖果，并且每次相邻两次只能吃不同种类的糖果，问是否能够吃完所有糖果。

解题思路：考虑数量最多的糖果，第一次选择这种糖果，第二次就需要选择其它糖果，因此如果数量最多的这种糖果的数量比数量第二多的糖果的数量 + 1 还多，那么第二次只能吃数量最多的这种糖果，但又不能两次吃相同的糖果，因此一定吃不完所有糖果。反之一定能通过这两种糖果控制其它糖果的数量，从而吃掉所有糖果。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
int a[N];

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        if(a[n] > a[n - 1] + 1) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}

C. Get an Even String

题目链接：Problem - C - Codeforces

题目大意：定义偶字符串满足 1.长度为偶数；2.对于字符串中每个奇数位置 $i$ ， $a_i = a_{i + 1}$ 。（空字符串也是偶字符串），求给定字符串最少去掉几个字符能得到偶字符串。

解题思路：考虑贪心，找每次第一对出现的相同字符，然后将之间的所有字符抛弃，可以发现这样处理之后，后面剩下的字符中才更有机会找到相同字符。如 aefebfaf，从前往后扫，最先匹配到的是 e，然后抛掉 f 和开头的 a，剩下 bfaf 再匹配到 f，抛掉 a 和开头的 b，因此最终删除的是 4 个字符。再看看先匹配 a 的情况，就需要删除 6 个字符，先匹配 f 的情况也是删除 6 个字符。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        map<char, int> mp;
        int len = s.size(), ans = 0;
        for(int i = 0; i < len; i++){
            if(mp[s[i]]){
                ans++;
                mp.clear();
            }
            else mp[s[i]] = 1;
        }
        cout << len - ans * 2 << endl;
    }
    return 0;
}

D. Maximum Product Strikes Back

题目链接：Problem - D - Codeforces

题目大意：给定一个序列 a（其中 $-2\leqslant a_i\leqslant 2$ ），定义序列的乘积为序列中每个数相乘的值（空序列的乘积定义为 1），每次可以从最左端或最右端删除元素，问从左、右各删除几个元素能够使得序列乘积最大。

解题思路：由于 $-2 \leqslant a_i \leqslant 2$ ，空序列值为 1，那么可以把 0 作为分隔符，将每一段的负数个数控制成偶数个（如果是奇数个就比较删除到最左边的一个负数和删除到最右边的一个负数，剩下的序列值的大小，保留较大的一种情况），然后比较每一段的乘积值，由于只有 2 和 -2 对乘积值有贡献，只要计算每段中 abs() = 2 的数个数，最多的即为答案序列，再通过答案序列左右端点可以得到左右删除的元素个数。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
int a[N], prefs[N], pretwo[N];

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            prefs[i] = prefs[i - 1] + (a[i] < 0);    // 负数个数前缀和
            pretwo[i] = pretwo[i - 1] + (abs(a[i]) == 2);    // 2和-2的个数前缀和
        }
        a[n + 1] = 0;
        
        vector<PII> v;
        
        int pos = 0;
        for(int i = 1; i <= n + 1; i++){
            if(a[i] == 0){
                v.push_back({pos + 1, i - 1});    // 存储按0分隔的每一段
                pos = i;
            }
        }
        int ma = 0, ansl = 0, ansr = 0;
        for(auto i : v){
            int l = i.first, r = i.second;
            if((prefs[r] - prefs[l - 1]) % 2 == 0){    // 负数个数为偶数直接判断序列值
                if(ma <= pretwo[r] - pretwo[l - 1]){
                    ma = pretwo[r] - pretwo[l - 1];
                    ansl = l - 1;
                    ansr = n - r;
                }
            }
            else{
                for(int i = l; i <= r; i++){    // 判断每一段从左删除到第一个负数后的值是否比当前最大值大
                    if(a[i] < 0){
                        if(ma <= pretwo[r] - pretwo[i]){
                            ma = pretwo[r] - pretwo[i];
                            ansl = i;
                            ansr = n - r;
                        }
                        break;
                    }
                }
                for(int i = r; i >= l; i--){    // 判断每一段从右删除到第一个负数后的值是否比当前最大值大
                    if(a[i] < 0){
                        if(ma <= pretwo[i - 1] - pretwo[l - 1]){
                            ma = pretwo[i - 1] - pretwo[l - 1];
                            ansl = l - 1;
                            ansr = n - i + 1;
                        }
                        break;
                    }
                }
            }
        }
        cout << ansl << ' ' << ansr << endl;
    }
    return 0;
}

E. Matrix and Shifts

题目链接：Problem - E - Codeforces

题目大意：给出一个 n * n 的 01 矩阵（矩阵元素只有 0 或 1），可以进行任意次的任意平移操作（每行向上平移、每行向下平移、每列向左平移、每列向右平移），这个操作无消耗；还可以进行单点修改操作，即将 0 改为 1 或将 1 改为 0，每次消耗 1 burl，求将矩阵变为单位矩阵的最小消耗为多少。

解题思路：由于平移不影响相对位置，因此只需要找与主对角线平行的斜线中 1 最多的个数即可。剩下的操作就是修改 1 和 0 了，斜线中差几个 1 就需要将几个 0 改为 1，其它位置多几个 1 就需要将这些 1 全部改为 0。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 2005;
char s[N][N];

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int sum1 = 0;
        for(int i = 0; i < n; i++){
            cin >> s[i];
            for(int j = 0; j < n; j++){
                if(s[i][j] == '1') sum1++;
            }
        }
        int ma = 0;
        for(int i = 0; i < n; i++){
            int cnt = 0;
            for(int j = 0; j < n; j++){
                if(s[(i + j) % n][j] == '1') cnt++;
            }
            ma = max(ma, cnt);
        }
        cout << n - ma + sum1 - ma << endl;
    }
    return 0;
}

F1. Promising String (easy version)

题目链接：Problem - F1 - Codeforces

题目大意：给定一个仅包含 '+' 和 '-' 的字符串，可以进行下面这样的操作，将相邻的两个 '-' 变为一个 '+' 。定义一个字符串是平衡的当且仅当 '+' 和 '-' 数量相等，定义一个字符串是有希望的当且仅当可以进行任意次操作之后使得字符串是平衡的。求给定字符串中有多少子串是有希望的。

解题思路：由于本体是 easy 版本，数据范围很小，可以直接暴力枚举，定义一个记录平衡性的变量 cnt，出现 '+' 时 cnt++，出现 '-' 时 cnt--。

如果 cnt = 0，即子串中正负符号已经相等了，答案 +1；

如果子串中 '-' 个数多于 '+'，且多出 3 的倍数，每多出 3 个 '-'，就说明一定至少有两个 '-' 相邻，可以将用这两个转换成一个 '+'，这样就一定可以使子串平衡，即子串就是有希望的，因此答案 +1；

其他情况下子串就不是有希望的，继续枚举即可。

AC代码：

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define mid (l + r >> 1)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const int INF = 0x3f3f3f3f;
const ll LLF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1000000007;
const int N = 200005;
int a[N];

int main(){
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        int n, ans = 0;
        cin >> n;
        string s;
        cin >> s;
        for(int i = 0; i < n; i++){
            int cnt = 0;
            for(int j = i; j < n; j++){
                if(s[j] == '+') cnt++;
                else cnt--;
                if(cnt == 0 || cnt < 0 && cnt % 3 == 0) ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}