Codeforces Round 1005 (Div. 2) 补题

思路：首先比较好想到的思路是，如果我们要保证数组的分数最大，那么我们删除的连续子数组里一定不能有2个及以上的相同的元素，否则删除后一定会让分数比初始时刻小（初始时刻的分数就是最大分数，后续操作也就是保证数组的分数和初始时刻一样），所以我们一开始要将某个元素出现次数 >= 2的位置标记位false,保证后续不会选到，最后用双指针扫一遍即可，注意 j == n的时候要break,否则会TLE，因为最坏

一笙589

939人浏览 · 2025-03-16 23:35:41

一笙589 · 2025-03-16 23:35:41 发布

A：Brogramming Contest

Problem - A - Codeforces

题意：初始时给定一个长度为n的01字符串s, 和一个空字符串t,每次操作可以从两个字符串中将任意长度的后缀移动到另一个字符串的后面，问：让s字符串全为0，t字符串全为1所需要的最小操作次数

思路：对于一个字符串比如10011101,我们可以将其化简为10101(就是合并所有相邻的0，1字符),这样操作肯定是让操作次数最小化的，然后我是通过手玩了几组样例，最后猜了个结论: 如果合并后的字符串 tmp 是0开头，那么答案就是tmp.size() - 1, 1开头就是tmp.size();

#include <iostream>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		string tmp;
		for(int i = 0; i < n; i ++)
		{
			for(int j = i; j <= n; j ++)
			{
				if(s[j] == s[i]) continue;
				else
				{
					tmp += s[i];
					i = j - 1;
					break;
				}
			}
		}
	//	cout << tmp << '\n';
		cout << tmp.size() - 1 + (tmp[0] == '1') << '\n';
	}
}

B:Variety is Discouraged

Problem - B - Codeforces

题意：给定一个长度为n的数组，定义这个数组的分数为：数组的长度 - 不同的元素数量；我们可以最多执行一次操作：删除连续的非空子数组；问我们再保证最大分数的前提下，最小化数组的长度，输出要删除位置的起点位和终点位，不删则输出0。

#include <iostream>
#include <vector>
#include <map>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n;
		cin >> n;
		vector<bool> b(n + 1, true);
		vector<int> a(n + 1, 0);
		vector<int> c(n + 1, 0);
		for(int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			c[a[i]] ++;
		}
		for(int i = 1; i <= n; i ++)
		{
			if(c[a[i]] >= 2) b[i] = false;
		}
		
		int l = 0, r = 0;
		int len = 0;
		for(int i = 1; i <= n; i ++)
		{
			if(b[i])
			{
				for(int j = i; j <= n; j ++)
				{
					if(b[j])
					{
						if(j - i + 1 > len)
						{
							len = j - i + 1;
							l = i;
							r = j;
						}
						if(j == n)
						{
							i = j;
							break;
						}
					}
					else
					{
						i = j;
						break;
					}
				}
			}
		}
		if(len == 0) cout << 0 << '\n';
		else cout << l << ' ' << r << '\n';
	}
}

C： Remove the Ends

Problem - C - Codeforces

题意：给定一个长度为n的数组，每次可以选择获得数组中的一个元素的绝对值，如果选择的元素是负数则删除从该位置开始数组的后缀，正数则删除前缀；问：可以获得的最大值是多少

思路：比较明显的贪心思路是，一定是从开头或者结尾开始选，因为选了正数就要删除前缀，所以我们用一个前缀数组pre[i]记录前i个正数的和，用一个后缀数组suf[j]记录后j个负数的abs和,最后有点dp的思想：如果a[i] > 0 我们选这个元素及其前缀是否更优，如果a[i] < 0 我们选这个元素及其后缀是否更优，如果a[i] > 0 && a[i + 1] < 0 那么我们可以同时选择这两个元素，保证不冲突

#include <iostream>
#include <vector>
#include <map>
#define int long long
using namespace std;

const int mod = 1e9 + 7;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n;
		cin >> n;
		vector<int> a(n + 2, 0);
		for(int i = 1; i <= n; i ++) cin >> a[i];
		
		vector<int> pre(n + 1, 0);
		vector<int> suf(n + 2, 0);
		
		for(int i = 1; i <= n; i ++)
		{
			pre[i] = pre[i - 1];
			if(a[i] > 0)
			{
				pre[i] += a[i];
			}
		}
		
		for(int i = n; i >= 1; i --)
		{
			suf[i] = suf[i + 1];
			if(a[i] < 0)
			{
				suf[i] += abs(a[i]);
			}
		}
		
		int ans = 0;
		for(int i = 1; i <= n; i ++)
		{
			if(a[i] > 0) ans = max(ans, pre[i]);
			if(a[i] < 0) ans = max(ans, suf[i]);
			ans = max(ans, max(pre[i], suf[i]));
			if(a[i] > 0 && a[i + 1] < 0)
			{
				ans = max(ans, pre[i] + suf[i + 1]);
			}
		}
		cout << ans << '\n';
	}
}

D:Eating

Problem - D - Codeforces

看了别的大佬思路才勉强写出来的题

题意：给定一个长度为n的数组，和q个查询，每次查询会给定一个x，一开始将x放在n + 1的位置，如果x大于此时左边的元素，x就可以吃掉它，并向左前进一格，之后x的值就会变成x异或被吃掉的元素的值，问：x可以吃掉多少元素（每次查询是独立的）

思路：这题对于位运算的理解要求比较高，对于目前x的最高位 j ，如果左边元素的最高位都没有到达 j, 那么x是一定可以吃掉的，并且不影响此时x的最高位，如果x碰见了一个数此时的最高位和x一样，那么就要判断x此时能否吃掉它,如果不能就break，所以我们从最高位来遍历x，为了简化代码直接从30位判断就好

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#define int long long
using namespace std;

const int N = 1e6 + 5;
typedef pair<int,int> PII;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int t;
	cin >> t;
	while(t --)
	{
		int n, q;
		cin >> n >> q;
		vector<int> a(n + 2, 0);
		vector<vector<int>> pre(n + 2, vector<int>(31, 0));
		vector<int> s(n + 2, 0);
		
		for(int i = 1; i <= n; i ++) cin >> a[i];
		for(int i = 1; i <= n; i ++) s[i] = s[i - 1] ^ a[i];
		for(int i = 1; i <= n; i ++)
		{
			for(int j = 0; j <= __lg(a[i]); j ++) pre[i][j] = i;
			for(int j = __lg(a[i]) + 1; j <= 30; j ++) pre[i][j] = pre[i - 1][j];
		}
		
		
		while(q --)
		{
			int x;
			cin >> x;
			int now = n;
			for(int j = 30; j >= 0; j --)
			{
				if(x < (1 << j)) continue;
				else
				{
					int nxt = pre[now][j];
					x = x ^ (s[now] ^ s[nxt]);
					now = nxt;
					if(!now || a[now] > x) break;
					x ^= a[now];
					now --;
				}
			}
			cout << n - now << ' ';
		}
		cout << '\n';
	}
	return 0;
}