Codeforces Global Round 6 题解

Codeforces Global Round 6

Competitive Programmer

$60$ 的倍数要求至少有一个 $0$，至少有两个数字是 $2$ 的倍数，且所有数字加起来是 $3$ 的倍数。

int main() {
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int c0 = 0, c2 = 0, S = 0;
		int l = s.length();
		for (int i = 0; i < l; i++) {
			if (s[i] == '0') c0++;
			if ((s[i] - '0') % 2 == 0) c2++;
			S += s[i] - '0';
		}
		if (c0 && c2 > 1 && S % 3 == 0) cout << "red" << endl;
		else cout << "cyan" << endl;
	}
	return 0;
}

Dice Tower

总和模 $14$ 应该在 $[1,6]$ 之间。注意开 long long，还有 $n>14$。

int main() {
	int T;
	cin >> T;
	while (T--) {
		ll n;
		cin >> n;
		if (n > 14 && n % 14 > 0 && n % 14 < 7) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

Diverse Matrix

随便构造一下就好了，要特判 $n=1$ 和 $m=1$ 的情况。

const int N = 503;
int a[N][N];

int main() {
	int n, m;
	cin >> n >> m;
	if (n == 1 && m == 1) return cout << 0 << endl, 0;
	if (n == 1) {
		for (int i = 1; i <= m; i++) cout << i + 1 << ' ';
		return 0;
	}
	if (m == 1) {
		for (int i = 1; i <= n; i++) cout << i + 1 << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cout << i * (j + n) << " \n"[j==m];
	return 0;
}

Decreasing Debts

最终只关心每个人的净借出/负债，构造时用个堆配对一下即可。

const int N = 1e5 + 7;
int n, m;
ll a[N];
pq< pair< ll, int > > p, q;

int main() {
	rd(n), rd(m);
	for (int i = 1; i <= m; i++) {
		int x, y, z;
		rd(x), rd(y), rd(z);
		a[x] += z, a[y] -= z;
	}
	for (int i = 1; i <= n; i++)
		if (a[i] > 0) p.push(mp(a[i], i));
		else q.push(mp(-a[i], i));
	vector< pair < pi, ll > > ans;
	while (p.size()) {
		int x = p.top().se, y = q.top().se;
		ll s = p.top().fi, t = q.top().fi, z;
		p.pop(), q.pop();
		ans.pb(mp(mp(x, y), z = min(s, t)));
		s -= z, t -= z;
		if (s) p.push(mp(s, x));
		if (t) q.push(mp(t, y));
	}
	cout << ans.size() << endl;
	for (auto i : ans) printf("%d %d %lld\n", i.fi.fi, i.fi.se, i.se);
	return 0;
}

Spaceship Solitaire

有结论：一个位置会超出当且仅当落在这个位置上的奖励超过了需要，且超出的多少等于超过的需要。

那么用个 map 模拟即可。

const int N = 2e5 + 7;
int n, q, a[N], c[N], sz;
map< pi, int > p;
ll s;

inline void del(int x, int y) {
	--sz;
	int z = p[mp(x,y)];
	p.erase(mp(x,y));
	if (c[z] > a[z]) --s;
	c[z]--;
}

inline void add(int x, int y, int z) {
	++sz;
	p[mp(x,y)] = z;
	++c[z];
	if (c[z] > a[z]) ++s;
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), s += a[i];
	rd(q);
	while (q--) {
		int x, y, z;
		rd(x), rd(y), rd(z);
		if (p[mp(x,y)]) del(x, y);
		if (z) add(x, y, z);
		print(s - sz);
	}
	return 0;
}

Almost Same Distance

大力分类讨论即可。

Permutation Concatenation

题目太神仙了，先咕咕咕着。

Red-Blue Graph

题目太神仙了，先咕咕咕着。