源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

image-20220407144258400

(头一次知道全A是绿色的

A. Vasya and Coins

题目大意:

image-20220407144403406

思路:

思考如果没有1硬币,则只能支付2的倍数的金额,1无法支付

若有一个1硬币和无限2硬币,则任意金额都可支付

$1 = 1$

$2 = 2$

$3 = 2 + 1$

$4 = 2 + 2$

$5 = 2 + 2 + 1$

因此,最大金额能支付的金额为a+2*b

最大不能支付的金额为$a+2*b+1$

代码:

void solution()
{
	long long a, b;
	cin >> a >> b;
	if (a == 0)
		cout << 1 << endl;
	else
		cout << a + 2 * b + 1 << endl;
}

B. Vlad and Candies

题目大意:

image-20220407145008255

思路:

该题都难点在于读题

题目中说会优先选择“the most frequent”的蛋糕,这里的意思是取最大的蛋糕

之后,我们再来想一下什么情况下是NO

如果当前最大的蛋糕只有一个,大小为maxn,如果第二大的蛋糕大小为maxn-1,那么这两个蛋糕可以来回吃,但如果更小的话,则必须连续吃2口

因此判断蛋糕中大小为maxn和maxn-1的数量,若大于等于2个,则可以,否则不行

代码:

void solution()
{
	int n;
	cin >> n;
	map<int, int> vis;
	int tmp;
	int maxn;
	maxn = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> tmp;
		maxn = max(maxn, tmp);
		vis[tmp]++;
	}
	if (vis[maxn] + vis[maxn - 1] >= 2 || maxn == 1)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

C. Get an Even String

题目大意:

image-20220407153422054

思路:

我们使用类似dp的方法,用M[it]表示最长的一个以it结尾的非偶数串

用ans表示当前能达到的最大的偶数串

之后遍历字符串,若M[it] > ans,则更新ans为M[it]

否则,更新M[it] = ans + 2

最后得到的ans,即为最长偶数串

代码:

void solution()
{
	string oriS;
	cin >> oriS;
	int ans = 0;
	map<char, int> M;
	for (char it: oriS)
	{
		if (M[it] > ans)
		{
			ans = max(ans,M[it]);
			M[it] = 0;
		}else
		{
			M[it] = ans+2;
		}
	}
	cout << oriS.size()-ans << endl;
}

D. Maximum Product Strikes Back

题目大意:

image-20220407153422054

思路:

首先我们知道0一定不能取,因此需要按0分割区间

思考一下如果没有0该怎么解决这个问题?

怎么在一个区间内找价值最大的一个子区间,很容易想到一个滑动窗口的问题,但是这个问题并不是简单的加减,因此我们不能随意舍弃任何一个有贡献的数,由此,我们使用双指针,按照类似单调队列的方式不断去最大值

值得注意的是,由于数据过大,我们不能真的去算具体结果,只能存乘2的数量

代码:

void solution()
{
	int n;
	cin >> n;
	vector<int> nums(n);
	int tmp = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
		if (nums[i] == 0)
			tmp++;
	}
	if (tmp == n)
	{
		cout << n << " 0" << endl;
		return;
	}
	int maxn = 0;
	int l = n;
	int r = 0;
	int nowf = true;
	int nowAns = 0;
	deque<pair<int, int>> Q;
	for (int i = 0; i < n; i++)
	{
		if (nums[i] == 0)
		{
			while (!Q.empty())
			{
				if (Q.front().first < 0)
					nowf = !nowf;
				if (abs(Q.front().first) == 2)
					nowAns--;
				if (nowf && nowAns > maxn)
				{
					maxn = nowAns;
					l = Q.front().second+1;
					r = n - Q.back().second - 1;
				}
				Q.pop_front();
			}
			nowAns = 0;
		}
		else
		{
			if (Q.empty())
			{
				if (nums[i] < 0)
					nowf = false;
				else
					nowf = true;
				if (abs(nums[i]) == 2)
					nowAns = 1;
				else
					nowAns = 0;
			}
			else
			{
				if (nums[i] < 0)
					nowf = !nowf;
				if (abs(nums[i]) == 2)
					nowAns++;
			}
			Q.push_back({ nums[i], i });
			if (nowf && nowAns > maxn)
			{
				maxn = nowAns;
				l = Q.front().second;
				r = n - Q.back().second - 1;
			}
		}
	}
	while (!Q.empty())
	{
		if (Q.front().first < 0)
			nowf = !nowf;
		if (abs(Q.front().first) == 2)
			nowAns--;
		if (nowf && nowAns > maxn)
		{
			maxn = nowAns;
			l = Q.front().second+1;
			r = n - Q.back().second - 1;
		}
		Q.pop_front();
	}
	cout << l << " " << r << endl;
}

E. Matrix and Shifts

题目大意:

image-20220407165834905

思路:

(感觉这个比D题简单

写过八皇后的人应该都知道,不论怎么平移,对应的对角线不会变化

因此枚举n条对角线中1的数量,取最大的一条对角线即可

答案为对角线上0的数量和非对角线上1的数量

代码:

void solution()
{
	int n;
	cin >> n;
	vector<string> bd(n+1);
	for (int i = 1; i <= n; i++)
	{
		cin >> bd[i];
		bd[i] = "-" + bd[i];
	}
	int tot1 = 0;
	vector<int> nums(n+1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (bd[i][j] == '1')
			{
				tot1++;
				if (i-j >= 0)
					nums[i-j]++;
				else
					nums[n-(j-i)]++;
			}
	int maxn = 0;
	for (int i = 0; i <= n; i++)
		maxn = max(maxn,nums[i]);
//	cout << maxn << endl;
	cout << n-maxn+(tot1-maxn) << endl;
}

F2. Promising String (hard version)

题目大意:

image-20220407162032449

思路:

F1F2一起写了这里

思考一下那些字符串符合要求

  • 字符串中+数量和-数量相等的
  • 字符串中-的数量比+的数量大3*k的

如何快速得知前缀当中有多少个符合条件的字符串呢?

可以先求一遍前缀和,之后可以看某个位置之前有多少个数等于当前位置的前缀和,有多少个数,就有多少个子串,但此时,还没有考虑-较多的情况

我们可以直接令前缀和%3,看之前有多少个%3之后和他相等的数,但同时,另一个前缀和相等的位置的前缀和应当小于后一个前缀和,因为我们只要-较多的情况,不要+较多的情况

对于这个问题,我们可以使用树状数组来实现,类似求逆序对

代码:

template<typename T>
class Fenwick
{
public:
	Fenwick()
	{
	}

	Fenwick(int _n) : n(_n)
	{
		fenw.resize(n + 1);
	}

	void resize(int _n)
	{
		n = _n;
		fenw.clear();
		fenw.resize(_n + 1);
	}

	void modifty(int x, T val)
	{
		while (x <= n)
		{
			fenw[x] += val;
			x |= (x + 1);
		}
	}

	T get(int x)
	{
		T cnt{};
		while (x >= 0)
		{
			cnt += fenw[x];
			x = (x & (x + 1)) - 1;
		}
		return cnt;
	}

private:
	vector<T> fenw;
	int n;
};

void solution()
{
	int n;
	string s;
	cin >> n >> s;
	vector<int> preAns(n + 1);
	int minn = 0;
	for (int i = 0; i < n; i++)
	{
		preAns[i + 1] = preAns[i] + (s[i] == '-' ? 1 : -1);
		minn = min(preAns[i + 1], minn);
	}
	minn = minn * -1;
	Fenwick<int> fen[3];
	for (int i = 0; i < 3; i++)
		fen[i].resize(n + minn + 1);
	int ans = 0;
	for (int i = 0; i <= n; i++)
	{
		int tmp = abs((preAns[i] + minn) % 3);
		ans += fen[tmp].get(preAns[i] + minn);
		fen[tmp].modifty(preAns[i] + minn, 1);
	}
	cout << ans << endl;
}