Codeforces Round 575 (Div. 3)

A. Three Piles of Candies

 

想法很简单，三个数相加除2，主要是大数模板。

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

//大数
struct BigInteger
{
	static const int BASE = 100000000; //和WIDTH保持一致
	static const int WIDTH = 8;        //八位一存储,如修改记得修改输出中的%08d
	bool sign;                         //符号, 0表示负数
	size_t length;                     //位数
	vector<int> num;                   //反序存
									   //构造函数
	BigInteger(long long x = 0) { *this = x; }
	BigInteger(const string &x) { *this = x; }
	BigInteger(const BigInteger &x) { *this = x; }
	//剪掉前导0，并且求一下数的位数
	void cutLeadingZero()
	{
		while (num.back() == 0 && num.size() != 1)
		{
			num.pop_back();
		}
		int tmp = num.back();
		if (tmp == 0)
		{
			length = 1;
		}
		else
		{
			length = (num.size() - 1) * WIDTH;
			while (tmp > 0)
			{
				length++;
				tmp /= 10;
			}
		}
	}
	//赋值运算符
	BigInteger &operator=(long long x)
	{
		num.clear();
		if (x >= 0)
		{
			sign = true;
		}
		else
		{
			sign = false;
			x = -x;
		}
		do
		{
			num.push_back(x % BASE);
			x /= BASE;
		} while (x > 0);
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const string &str)
	{
		num.clear();
		sign = (str[0] != '-'); //设置符号
		int x, len = (str.size() - 1 - (!sign)) / WIDTH + 1;
		for (int i = 0; i < len; i++)
		{
			int End = str.size() - i * WIDTH;
			int start = max((int)(!sign), End - WIDTH); //防止越界
			sscanf(str.substr(start, End - start).c_str(), "%d", &x);
			num.push_back(x);
		}
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const BigInteger &tmp)
	{
		num = tmp.num;
		sign = tmp.sign;
		length = tmp.length;
		return *this;
	}
	//绝对值
	BigInteger abs() const
	{
		BigInteger ans(*this);
		ans.sign = true;
		return ans;
	}
	//正号
	const BigInteger &operator+() const { return *this; }
	//负号
	BigInteger operator-() const
	{
		BigInteger ans(*this);
		if (ans != 0)
			ans.sign = !ans.sign;
		return ans;
	}
	// + 运算符
	BigInteger operator+(const BigInteger &b) const
	{
		if (!b.sign)
		{
			return *this - (-b);
		}
		if (!sign)
		{
			return b - (-*this);
		}
		BigInteger ans;
		ans.num.clear();
		for (int i = 0, g = 0;; i++)
		{
			if (g == 0 && i >= num.size() && i >= b.num.size())
				break;
			int x = g;
			if (i < num.size())
				x += num[i];
			if (i < b.num.size())
				x += b.num[i];
			ans.num.push_back(x % BASE);
			g = x / BASE;
		}
		ans.cutLeadingZero();
		return ans;
	}
	// - 运算符
	BigInteger operator-(const BigInteger &b) const
	{
		if (!b.sign)
		{
			return *this + (-b);
		}
		if (!sign)
		{
			return -((-*this) + b);
		}
		if (*this < b)
		{
			return -(b - *this);
		}
		BigInteger ans;
		ans.num.clear();
		for (int i = 0, g = 0;; i++)
		{
			if (g == 0 && i >= num.size() && i >= b.num.size())
				break;
			int x = g;
			g = 0;
			if (i < num.size())
				x += num[i];
			if (i < b.num.size())
				x -= b.num[i];
			if (x < 0)
			{
				x += BASE;
				g = -1;
			}
			ans.num.push_back(x);
		}
		ans.cutLeadingZero();
		return ans;
	}
	// * 运算符
	BigInteger operator*(const BigInteger &b) const
	{
		int lena = num.size(), lenb = b.num.size();
		BigInteger ans;
		for (int i = 0; i < lena + lenb; i++)
			ans.num.push_back(0);
		for (int i = 0, g = 0; i < lena; i++)
		{
			g = 0;
			for (int j = 0; j < lenb; j++)
			{
				long long x = ans.num[i + j];
				x += (long long)num[i] * (long long)b.num[j];
				ans.num[i + j] = x % BASE;
				g = x / BASE;
				ans.num[i + j + 1] += g;
			}
		}
		ans.cutLeadingZero();
		ans.sign = (ans.length == 1 && ans.num[0] == 0) || (sign == b.sign);
		return ans;
	}
	//*10^n 大数除大数中用到
	BigInteger e(size_t n) const
	{
		int tmp = n % WIDTH;
		BigInteger ans;
		ans.length = n + 1;
		n /= WIDTH;
		while (ans.num.size() <= n)
			ans.num.push_back(0);
		ans.num[n] = 1;
		while (tmp--)
			ans.num[n] *= 10;
		return ans * (*this);
	}
	// /运算符 (大数除大数)
	BigInteger operator/(const BigInteger &b) const
	{
		BigInteger aa((*this).abs());
		BigInteger bb(b.abs());
		if (aa < bb)
			return 0;
		char *str = new char[aa.length + 1];
		memset(str, 0, sizeof(char) * (aa.length + 1));
		BigInteger tmp;
		int lena = aa.length, lenb = bb.length;
		for (int i = 0; i <= lena - lenb; i++)
		{
			tmp = bb.e(lena - lenb - i);
			while (aa >= tmp)
			{
				str[i]++;
				aa = aa - tmp;
			}
			str[i] += '0';
		}
		BigInteger ans(str);
		delete[] str;
		ans.sign = (ans == 0 || sign == b.sign);
		return ans;
	}
	// %运算符
	BigInteger operator%(const BigInteger &b) const
	{
		return *this - *this / b * b;
	}
	// ++ 运算符
	BigInteger &operator++()
	{
		*this = *this + 1;
		return *this;
	}
	// -- 运算符
	BigInteger &operator--()
	{
		*this = *this - 1;
		return *this;
	}
	// += 运算符
	BigInteger &operator+=(const BigInteger &b)
	{
		*this = *this + b;
		return *this;
	}
	// -= 运算符
	BigInteger &operator-=(const BigInteger &b)
	{
		*this = *this - b;
		return *this;
	}
	// *=运算符
	BigInteger &operator*=(const BigInteger &b)
	{
		*this = *this * b;
		return *this;
	}
	// /= 运算符
	BigInteger &operator/=(const BigInteger &b)
	{
		*this = *this / b;
		return *this;
	}
	// %=运算符
	BigInteger &operator%=(const BigInteger &b)
	{
		*this = *this % b;
		return *this;
	}
	// < 运算符
	bool operator<(const BigInteger &b) const
	{
		if (sign != b.sign) //正负，负正
		{
			return !sign;
		}
		else if (!sign && !b.sign) //负负
		{
			return -b < -*this;
		}
		//正正
		if (num.size() != b.num.size())
			return num.size() < b.num.size();
		for (int i = num.size() - 1; i >= 0; i--)
			if (num[i] != b.num[i])
				return num[i] < b.num[i];
		return false;
	}
	bool operator>(const BigInteger &b) const { return b < *this; }                     // >  运算符
	bool operator<=(const BigInteger &b) const { return !(b < *this); }                 // <= 运算符
	bool operator>=(const BigInteger &b) const { return !(*this < b); }                 // >= 运算符
	bool operator!=(const BigInteger &b) const { return b < *this || *this < b; }       // != 运算符
	bool operator==(const BigInteger &b) const { return !(b < *this) && !(*this < b); } //==运算符
	// 逻辑运算符
	bool operator||(const BigInteger &b) const { return *this != 0 || b != 0; } // || 运算符
	bool operator&&(const BigInteger &b) const { return *this != 0 && b != 0; } // && 运算符
	bool operator!() { return (bool)(*this == 0); }                             // ！ 运算符

	//重载<<使得可以直接输出大数
	friend ostream &operator<<(ostream &out, const BigInteger &x)
	{
		if (!x.sign)
			out << '-';
		out << x.num.back();
		for (int i = x.num.size() - 2; i >= 0; i--)
		{
			char buf[10];
			//如WIDTH和BASR有变化,此处要修改为%0(WIDTH)d
			sprintf(buf, "%08d", x.num[i]);
			for (int j = 0; j < strlen(buf); j++)
				out << buf[j];
		}
		return out;
	}
	//重载>>使得可以直接输入大数
	friend istream &operator>>(istream &in, BigInteger &x)
	{
		string str;
		in >> str;
		size_t len = str.size();
		int start = 0;
		if (str[0] == '-')
			start = 1;
		if (str[start] == '\0')
			return in;
		for (int i = start; i < len; i++)
		{
			if (str[i] < '0' || str[i] > '9')
				return in;
		}
		x.sign = !start;
		x = str.c_str();
		return in;
	}
};
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		BigInteger a, b,c;
		cin >> a >> b >> c;
		BigInteger ans;
		ans = (a + b + c) / 2;
		cout << ans << endl;
	}
	return 0;
}

 

B. Odd Sum Segments

 

前缀和，记元素和，若区间中元素和为正，则记下来。

最终分段数可能小于k，或大于k。若小于k则NO，大于k则到k-1后直接输出n。

#include<iostream>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 2e5 + 5;
ll a[maxn];
ll sum[maxn];
int main() {
	cin.sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--) {
		vector<int>ans;
		bool ok = 0;
		int n, k;
		cin >> n >> k;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			sum[i] = sum[i - 1] + a[i];
			if (sum[i] % 2 == 1)ok = 1;
		}
		if ((k % 2 == 0 && sum[n] % 2 == 1) || (k % 2 == 1 && sum[n] % 2 == 0)) {
			cout << "NO" << endl;
			continue;
		}
		int st = 0;
		for (int i = 1; i <= n; i++) {
			if ((sum[i] - sum[st]) % 2 == 1) {
				ans.push_back(i);
				st = i;
			}
		}
		if (ans.size() < k)cout << "NO" << endl;
		else {
			cout << "YES" << endl;
			for (int i = 0; i < k - 1; i++) {
				cout << ans[i] << ' ';
			}
			cout << n << endl;
		}
	}
}

 

C. Robot Breakout

 

每一个询问独立，不需处理。对于每个机器人，记录它能走到的x轴，y轴范围，分两个区间记录，读入一个机器人的默认位置时用该点xy坐标更新区间，若能向左，则x轴左区间扩到最负，其它类似。

如果读入一个机器人时，该机器人能到的区间与目前记录的之前所有机器人能到的区间无交集，则无答案。若有交集，则总区间更新为该交集。

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
const int N=1e5;
int q;
bool is_cross(int x1, int y1, int x2, int y2) {
	if (x2 > y1 || x1 > y2)
		return false;
	return true;
}
int main() {
	cin.sync_with_stdio(false);
	cin >> q;
	int stX, edX, stY, edY;
	while (q--) {
		int n;
		cin >> n;
		stX = -N, edX = N;
		stY = -N, edY = N;
		bool flg = true;
		for (int i = 0; i < n; i++) {
			int x, y;
			int f1, f2, f3, f4;
			cin >> x >> y >> f1 >> f2 >> f3 >> f4;
			int stx = x, edx = x;
			int sty = y, edy = y;
			if (f1) {
				stx = -N;
			}
			if (f2) {
				edy = N;
			}
			if (f3) {
				edx = N;
			}
			if (f4) {
				sty = -N;
			}
			if (!is_cross(stX, edX, stx, edx) || !is_cross(stY, edY, sty, edy)) {
				flg = false;
			}
			else {
				stX = max(stX, stx);
				edX = min(edX, edx);
				stY = max(stY, sty);
				edY = min(edY, edy);
			}
		}
		if (!flg)cout << 0 << endl;
		else {
			cout << 1 << ' ' << stX << ' ' << stY << endl;
		}
	}
	return 0;
}

 

D1. RGB Substring (easy version)

 

给的数据很小，所以自然想到暴力搜，对每一个字符，检查它后面k个字符，记录错误个数，但是刚开始没想到这个字符可能是能变的，例如"GGBRGB"，若直接查，错5个，但把第一个G改为R，就只需要改一个。因此对每一个位置，要尝试3种字符，对每一种都检查后面。

后来也想过dp，但dp只能记录连续的，例如"RBBRGB"，dp要改2个，实际只要改1个。所以dp应该是不能用的。

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int q, k, n;
string s;
string t = "RGB";
int dp[2010];
int main() {
	cin.sync_with_stdio(false);
	cin >> q;
	while (q--) {
		cin >> n >> k;
		cin >> s;
		int ans = 2000;
		for (int i = 0; i <= n - k; i++) {
			for (int b = 0; b < 3; b++) {
				int tp = 0;
				for (int j = 0; j < k ; j++) {
					if (s[i + j] != t[(b + j)%3]) {
						tp++;
					}
				}
				ans = min(ans, tp);
			}
		}
		cout << ans << endl;
	}
	return 0;
}