首页 > 其他分享 >CodeForces 1839E Decreasing Game

CodeForces 1839E Decreasing Game

时间:2023-06-13 22:12:51浏览次数:60  
标签:typedef 重集 int CodeForces long Game maxn Decreasing define

洛谷传送门

CF 传送门

不会,不知道该如何评价。确实是自己的问题。

这种题肯定考虑先 / 后手必胜的充要条件。

直接给出结论:若 \(a\) 能被分成两个和相等的可重集,后手必胜,否则先手必胜

感性理解一下,如果 \(a\) 能被分成两个和相等的可重集,先手选一个数,后手选另一个可重集中的数。因为两个可重集的和相等,所以一定不会出现后手没法选的情况。

如果不能,先手随便选即可。因为后手无法操作也无法使接下来的 \(a\) 能被分成两个和相等的可重集。

然后随便 \(O(n \sum\limits_{i = 1}^n a_i)\) dp 一下找到分组方案即可。

code
// Problem: E. Decreasing Game
// Contest: Codeforces - Codeforces Round 876 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1839/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 310;

int n, a[maxn], f[maxn][maxn * maxn], g[maxn][maxn * maxn], b[maxn];

void solve() {
	scanf("%d", &n);
	int s = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		s += a[i];
	}
	f[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= s; ++j) {
			if (j >= a[i] && f[i - 1][j - a[i]]) {
				f[i][j] = 1;
				g[i][j] = 1;
			}
			if (f[i - 1][j]) {
				f[i][j] = 1;
				g[i][j] = 2;
			}
		}
	}
	if ((s & 1) || !f[n][s / 2]) {
		puts("First");
		fflush(stdout);
		while (1) {
			int x = -1, y = -1;
			for (int i = 1; i <= n; ++i) {
				if (a[i]) {
					x = i;
					break;
				}
			}
			printf("%d\n", x);
			fflush(stdout);
			scanf("%d", &y);
			if (y <= 0) {
				break;
			}
			int mn = min(a[x], a[y]);
			a[x] -= mn;
			a[y] -= mn;
		}
	} else {
		puts("Second");
		fflush(stdout);
		for (int i = n, j = s / 2; i; --i) {
			if (g[i][j] == 1) {
				b[i] = 1;
				j -= a[i];
			} else {
				b[i] = 2;
			}
		}
		while (1) {
			int x, y = -1;
			scanf("%d", &x);
			if (x <= 0) {
				break;
			}
			for (int i = 1; i <= n; ++i) {
				if (a[i] && b[i] != b[x]) {
					y = i;
					break;
				}
			}
			printf("%d\n", y);
			fflush(stdout);
			int mn = min(a[x], a[y]);
			a[x] -= mn;
			a[y] -= mn;
		}
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:typedef,重集,int,CodeForces,long,Game,maxn,Decreasing,define
From: https://www.cnblogs.com/zltzlt-blog/p/17478825.html

相关文章

  • Educational Codeforces Round 150 (Rated for Div. 2) 题解
    https://codeforces.com/contest/1841https://codeforces.com/contest/1841/problemsD.PairsofSegmentshttps://codeforces.com/contest/1841/problem/D因为\(n\)只有\(2000\),所以考虑枚举每一对\((i,j)\)满足区间有交集并且\(i\neqj\)。如果有交集,就合并。然后......
  • Unity3D:Pick and select GameObjects
    推荐:将NSDT场景编辑器加入你的3D工具链3D工具集:NSDT简石数字孪生PickandselectGameObjects可以在Scene视图中或从Hierarchy窗口中选择一个游戏对象。也可以一次选择多个游戏对象。Unity会在Scene视图中突出显示选择的游戏对象及其子项。默认情况下,选择轮廓颜色为橙......
  • Codeforces Round 877 (Div.2) 题解 A - D
    A.BlackboardList题目大意起初黑板上有两个数,现在不断选取两个数作出他们俩差的绝对值并写在黑板上,如此往复直到黑板上有\(n\)个数。现在给定这\(n\)个数,问起初两数的其中一个数是多少。解题思路我们分两种可能:要么这两个数有负数,要么没有。有负数的情况,因为每次写下......
  • Educational Codeforces Round 9-C. The Smallest String Concatenation(字符串排序)
    原题链接C.TheSmallestStringConcatenationtimelimitpertestmemorylimitpertestinputoutputn strings a1, a2, ..., an.You'dliketoconcatenatethemtogetherinsomeordersuchthattheresultings......
  • Codeforces Round #143 (Div. 2)-D. Magic Box
    原题链接D.MagicBoxtimelimitpertestmemorylimitpertestinputoutputOnedayVasyawasgoinghomewhenhesawaboxlyingontheroad.Theboxcanberepresentedasa......
  • Codeforces Round #320 (Div. 2) - D. "Or" Game
    原题链接D."Or"GametimelimitpertestmemorylimitpertestinputoutputYouaregiven n numbers a1, a2, ..., an.Youcanperformatmost k operations.For......
  • Codeforces Round #416 (Div. 2)-C. Vladik and Memorable Trip
    原题链接C.VladikandMemorableTriptimelimitpertestmemorylimitpertestinputoutputVladikoftentravelsbytrains.HerememberedsomeofhistripsespeciallywellandIwouldliketotellyouaboutone......
  • Codeforces Round #415 (Div. 2)-C. Do you want a date?
    原题链接C.Doyouwantadate?timelimitpertestmemorylimitpertestinputoutputn1 to n.Sothe i-thhackedcomputerislocatedatthepoint xi.Moreoverthecoordinatesofallcomputersaredistinct.L......
  • Codeforces Round #221 (Div. 2)-D. Maximum Submatrix 2
    原题链接D.MaximumSubmatrix2timelimitpertestmemorylimitpertestinputoutputYouaregivenamatrixconsistingofdigitszeroandone,itssizeis n × m.Youare......
  • Educational Codeforces Round 20-C. Maximal GCD
    原题链接C.MaximalGCDtimelimitpertestmemorylimitpertestinputoutputn.Youshouldcreatesuch strictlyincreasing sequenceof k positivenumbers a1, a2, ..., ak,thattheirsumisequalto nGr......