2022-04-02 00:29 已编辑第一拖拉机制造厂拖拉机学院测试开发

关注

Codeforces Round #780 (Div.3)

第一次打cf，有点紧张qwq，还是菜啊

A. Vasya and Coins

题意：

小A有两种硬币，一种面值为1元，另一种面值为2元，给出小A拥有这两种硬币的数量，求小A最小不能拼凑出的最小面额

数据范围：

$0 <= a_i,b_i <= 10^{8}$

思路：

如果小A有 $x$ 个 $1$ 元的硬币， $y$ 个 $2$ 元硬币，那么当 $x > 0$ 时它可以拼凑出 $x + 2 * y$ 元以内的任意金额，故不能凑出的最小金额为 $x + 2 * y + 1$ ，但当 $x = 0$ 时，最小不能凑出的面额为 $1$ 元

代码：

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1000010;
 
int a[N], b[N];
 
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	
	while (n --)
	{
		int x, y;
		cin >> x >> y;
		if (x > 0) cout << (x + 2 * y + 1) << endl;
		else
		{
			cout << 1 << endl;
		}
	}
	
	return 0;
}

B. Vlad and Candies

题意：

小A爱吃糖果，他每次都吃种类最多的一种糖果，如果有多种糖果的种类一样最多，他可以从这些糖果中选择一种吃掉，但小A为了追求口感，他不想连续两次吃同种类的糖果。给出所有糖果的种类数和每个种类的糖果数，求小A是否能在追求口感，即不连续吃两种相同种类的糖果的情况下，吃完所有糖果。

数据范围：

$1 < = n < = 2 * 1 0^{5}$

$1 < = a_{i} < = 1 0^{9}$

思路：

如果所有糖果中一个种类糖果数的最大值减去次大值结果大于 $1$ ，则说明小A不得不连续至少吃两次同一种类的糖果，则无法追求口感。若次大值初始时为 $0$ ，则只有一种糖果时也能如此判断。

代码：

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

const int N = 1000010;

int a[N], b[N];

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

	}
	
	return 0;
}

C. Get an Even String

题意：

给定一个字符串，使其变成长度为偶数，格式为 $a a b b c c d d$ ，即 $a_i = a_{i+1}$ ，此类的字符串，求最少需要删除多少字符

数据范围：

$1 <= \lvert s \rvert <= 2 * 10^5$

思路：

对于字符串 $a e d c a e$ 可以变成 $a a / e e$ 但是长度都为 $2$

对于字符串 $a b c a e b e$ 可以变成 $a a e e$

所以一个贪心的做法就产生了：

我们遍历字符串，如果遇到了相同的字符，就保留这两个相同的字符，中间的全部删除

代码：

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

const int N = 1000010;

int a[N], b[N];
map<char, int> mp;

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n;
	cin >> n;
	
	while (n --)
	{
		string s;
		cin >> s;
		
		int len = 0;
		for (auto c : s)
		{
			if (!mp[c]) mp[c] ++;
			else
			{
				mp.clear();
				len += 2;
			}
		}
		cout << s.size() - len << endl;
		mp.clear();
	}
	
	return 0;
}

D. Maximum Product Strikes Back

题意：

给定一个长度为 $n$ 的数组，数组中每个值的绝对值都小于等于 $2$ ，可以任意删除这个数组的前缀和后缀，使得剩余的子数组的乘积最大，一个空的数组乘积为 $1$ ，求使剩余子数列乘积最大时删除的前缀长度和后缀长度

数据范围：

$1 < = n < = 2 * 1 0^{5}$

$\lvert a_i \rvert <= 2$

思路：

因为空的数组乘积为1，所以最后剩余子数组中一定没有0，所以我们可以通过0来分割数组。

对于一个不含0的数组，我们考虑它所包含的负数的个数，如果负数的个数为偶数，则我们全都保留，整个区间都拿来跟新答案。

如果负数的个数为奇数，我们希望区间内负数的个数为偶数，在此基础上，区间中的数越多越好：

找到第一个负数的位置 $i d$ ，用区间 $[L, i d - 1]$ 和 $[i d + 1, R]$ 来更新答案

找到最后一个负数的位置 $i d$ ，用区间 $[L, i d - 1]$ 和 $[i d + 1, R]$ 来更新答案

因为我们保证了区间中没有 $0$ ，而且负数的个数为偶数个，所以影响最后乘积结果的只有绝对值为2的数的个数

我们用 $c n t$ 来记录 $2$ 的个数的最大值，并用 ans_x 记录删去左边的前缀长度，用 ans_y 记录删去右边的后缀长度，每次有 $2$ 的个数的最大值大于 $c n t$ 时，就更新它们的值

代码：

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

const int N = 1000010;

int a[N], b[N];

int n;
int ans_x, ans_y, cnt;

void upd(int l, int r) // 更新答案的值
{
	if (l > r) return;
	int t = 0;
	for (int i = l;i <= r;i ++)
	{
		if (abs(a[i]) == 2) t ++;
	}
	if (t > cnt)
	{
		cnt = t;
		ans_x = l - 1;
		ans_y = n - r;
	}
}

int calNeg(int l, int r) // 计算区间内有多少负数
{
	int t = 0;
	for (int i = l;i <= r;i ++) if (a[i] < 0) t ++;
	return t;
}

void cal(int l, int r) // 计算这个区间
{
	int t = calNeg(l, r);
    
    // 如果区间内负数个数为偶数，则这个区间应全部保留
	if (t % 2 == 0) upd(l, r); 
	else
	{
		int id = l;
		while(a[id] > 0) id ++; // 计算第一个负数的下标
		upd(l, id - 1); // 取这个负数的前一段
		upd(id + 1, r); // 和后一段分别计算
		id = r; 
		while(a[id] > 0) id --; // 计算最后一个负数的下标
		upd(l, id - 1); // 取这个负数的前一段
		upd(id + 1, r); // 和后一段分别计算
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int m;
	cin >> m;
	
	while (m --)
	{
		cin >> n;
		for (int i = 1;i <= n;i ++) cin >> a[i];
		
		a[n + 1] = 0; // 特别设置 n+1 的位置为 0
		ans_x = n; // 删除前缀的长度
		ans_y = 0; // 删除后缀的长度
		cnt = 0;
		
		for (int i = 1, j = 1;i <= n + 1;i ++)
		{
			if (a[i] == 0) // 以 0 分隔每一段
			{
				if (i - 1 >= j) cal(j, i - 1); // 只要不是连续的 0，就计算
				j = i + 1; // j为下一段的左端点
			}
		}
		
		cout << ans_x << ' ' << ans_y << endl;
	}
	
	return 0;
}

E. Matrix and Shifts

题意：

给定一个 $n * n$ 的01矩阵，你可以执行以下4个操作

将第一行放到最后一行下面

将最后一行放到第一行上面

将第一列放到最后一列后面

将最后一列放到第一列前面

其实就是上下左右移动

求经过多次操作后，和一个单位矩阵（主对角线的元素都是1）比，最少可以有多少个不同的地方

数据范围：

$1 < = n < = 2000$

思路：

因为单位矩阵上只有对角线上有元素 $1$ ，所以我们考虑，多次操作后，矩阵的主对角线的元素上有 $a n s$ 个 $1$

矩阵一共有 $s u m$ 个 $1$

那么和单位矩阵比，对角线上一共有 $n - a n s$ 个不同的地方，除了对角线，有 $s u m - a n s$ 个不同的地方（因为单位矩阵除了对角线都是0）

也就是说，我们希望多次操作后，对角线上的1的个数尽可能的多

所以我们可以枚举第一行，假设这个点就是最后答案中的对角线里面的点，然后我们向右下方向前进，寻找路线上 $1$ 最多的一种情况

最后结果为 $n - a n s + s u m - a n s$ ，即为对角线上的不同处加上对角线以外的不同处

代码：

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

const int N = 2010;

char a[N][N];

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int m;
	cin >> m;
	
	while (m --)
	{
	    int n;
		cin >> n;
		
		int sum = 0;
		for (int i = 0;i < n;i ++) 
		{
		    for (int j = 0;j < n;j ++)
		    {
		        cin >> a[i][j];
		        if (a[i][j] == '1') sum ++;
		    }
		}
		
		int ans = 0;
		for (int j = 0;j < n;j ++)
		{
		    int res = 0;
		    for (int i = 0;i < n;i ++)
		    {
		        if (a[i][(i + j) % n] == '1') res ++;
		    }
		    ans = max(ans, res);
		}
		
		cout << n + sum - 2 * ans << endl;
	}
	
	return 0;
}

F1. Promising String (easy version)

题意：

给定一个长度为 $n$ 的只包含 $+$ 和 $-$ 的字符串，经一次操作可以将连续的两个 $-$ 变成 $+$ ，求这个字符串有多少子串满足操作后（可以为 $0$ 次）字串内 $+$ 的个数等于 $-$ 的个数

数据范围：

$1 < = t < = 500$

$1 < = n < = 3000$

思路：

首先我们假设有 $a$ 个负号， $b$ 个正号，经 $k$ 次操作后，负号数等于正号数，则有：

$a - 2 * k = b + k$
$a - b = 3 * k$
$(a - b) \% 3 = 0$

所以相当于我们求每个子串所包含的 $+$ 和 $-$ 的数量，如果 $-$ 的数量减去 $+$ 的数量模 $3$ 等于 $0$ 且 $-$ 的数量大于等于 $+$ 的数量，则说明这个子串满足要求

代码：

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

const int N = 2010;

char a[N];

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int m;
	cin >> m;
	
	while (m --)
	{
	    int n;
		cin >> n;
		
		string s;
		cin >> s;
		
		int res = 0;
		for (int i = 0;i < s.size();i ++)
		{
		    int add = 0, sub = 0;
		    if (s[i] == '+') add ++;
		    else sub ++;
		    for (int j = i + 1;j < s.size();j ++)
		    {
		        if (s[j] == '+') add ++;
		        else sub ++;
		        if (sub >= add && (sub - add) % 3 == 0) res ++;
		    }
		}
		
		cout << res << endl;
	}
	
	return 0;
}