[AtCoder] Yahoo Programming Contest 2019

[AtCoder] Yahoo Programming Contest 2019

  很遗憾错过了一场 AtCoder 。听说这场是涨分场呢，于是特意来补一下题。

---

A - Anti-Adjacency

  显然 \(K \leq \frac{N + 1}2\)

int n, k;

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	read(n), read(k);
	if (k <= (n + 1 >> 1)) puts("YES");
	else puts("NO");
}

---

B - Path

  欧拉路。

const int N = 7;
int n = 4, x, y, deg[N], jcnt;

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	for (int i = 1; i < n; ++i) read(x), read(y), ++deg[x], ++deg[y];
	for (int i = 1; i <= n; ++i) if(deg[i] & 1) ++jcnt;
	if (jcnt == 0 ||jcnt == 2) puts("YES");
	else puts("NO");
}

---

C - When I hit my pocket...

  如果 \(B-A\leq 2\)的话，那么直接拍饼干肯定不比做交易差。

  否则，就先把饼干数拍到 \(A\) ，然后就卖一次买一次，最后如果还有单独的一次操作机会就拍一下就可以了。

int k, a, b;

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	read(k), read(a), read(b);
	if (b - a <= 2) return printf("%d\n", k + 1), 0;
	if (k <= a - 1) return printf("%d\n", k + 1), 0;
	else{
		ll ans = 1;
		ans += a - 1; k -= a - 1;
		ans += (ll)(k >> 1) * (b - a);
		if (k & 1) ++ans;
		printf("%lld\n", ans);
	}
}

---

D - Ears

  D题就开始比 A, B, C 有思维啦。

  我们发现在走路的过程中可以一直重复来回走一个格子，这样可以不改变格子的值得奇偶性的情况下，任意改变上面的数。于是，我们联想到奇偶性以后，可以发现，如果我们将走偶数次视为没有走的话，可以发现，这个轨迹最后就是一条直线。也就是说，整个轨迹应该是 偶——奇——偶。

  然后我就很天真地开始写——但是这样例死活过不去。好吧，因为如果想要某个格子走0次的话，就不满足上面的规律了——因为0次需要严格地不走。所以整个轨迹应该是 0——（偶）——（奇）——（偶）——0。其中括号里面的任何一项都可以不存在。

  然后记录一下处在那一段，直接dp就可以了。

const int N = 2e5 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, a[N];
ll dp[N][5], ans = INF;

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	read(n);
	for (int i = 1; i <= n; ++i) read(a[i]);
	dp[0][1] = dp[0][2] = dp[0][3] = dp[0][4] = INF;
	for (int i = 1; i <= n; ++i) {
		dp[i][0] = dp[i - 1][0] + a[i];
		dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]) + (a[i] ? (a[i] & 1) : 2);
		dp[i][2] = std::min(std::min(dp[i - 1][1], dp[i - 1][2]), dp[i - 1][0]) + (a[i] & 1 ^ 1);
		dp[i][3] = std::min(dp[i - 1][2], dp[i - 1][3]) + (a[i] ? (a[i] & 1) : 2);
		dp[i][4] = std::min(std::min(dp[i - 1][1], dp[i - 1][2]), std::min(dp[i - 1][3], dp[i - 1][4])) + a[i];
	}
	for (int i = 0; i < 5; ++i) SMIN(ans, dp[n][i]);
	printf("%lld\n", ans);
}

---

E - Odd Subrectangles

  我个人感觉这道题是这一场里面最难的，比F还要难。我一开始想dp，但是发现好像不太行。然后想了半天想不出来，只能看了一眼题解的前几句话。直接把那两句话复制过来吧。

  ”如果选的行数确定了，那么选某一列的奇偶性也会确定。“主要get到假设选的行先确定的思路。

  然后继续推，那么想要让选的列加起来的奇偶性为偶数，那么只能选奇数个和是奇数列，和是偶数的随便选多少。

  那么我们假设有 \(a\) 个偶数列， \(b\) 个奇数列。那么就是选的列的方案数就是 \(且是奇数2^a \cdot \sum \limits_{i\leq b\text{且}i是奇数}{C_b^{i}} = 2^a \cdot 2^{b-1} = 2^{m-1}\)。所以不管怎么选行，对应的列的方案数总是 \(2^{m-1}\) ——但是，\(b\) 如果是 \(0\) 的话，那么没办法选奇数个奇数列了！那么也就是说，如果我们把一行看做一个数，那么我们选的这些行的异或和不应该为 \(0\)！

​ 那么异或和不为 \(0\) 的方案数就是线性基的套路了。证明可以自己百度，也很简单，这里给出结论：如果线性基的大小是\(r\) ，原序列的长度为 \(n\)，那么异或和不为 \(0\) 的方案数为 \(2^n - 2^{n-r}\)。

const int N = 300 + 7;
const int P = 998244353;

int n, m, a[N][N], b[N][N], r;

inline int fpow(int x, int y) {
	int ans = 1;
	for (; y; y >>= 1, x = (ll)x * x % P) if (y & 1) ans = (ll)ans * x % P;
	return ans;
}

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	read(n), read(m);
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) read(a[i][j]);
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j)
			if (a[i][j])
				if (!b[j][j]) {
					for (int k = 1; k <= m; ++k) b[j][k] = a[i][k];
					++r;
					break;
				} else for (int k = 1; k <= m; ++k) a[i][k] ^= b[j][k];
	}
	printf("%lld\n", (ll)fpow(2, m - 1) * (fpow(2, n) + P - fpow(2, n - r)) % P);
}

---

F - Pass

  对于问序列的方案数的题目的套路，一般是考虑直接构造序列，考虑这个序列需要满足的特征。

  发现对于序列的前 \(i\) 项（\(1 \leq i \leq n\) 也就是说不包括后 \(n\) 项），他能拿到的球一定只能来自前 \(i\) 个人。这样的话，红球和蓝球的数量都有了上限，也同时因为对方的上限也有了下限。

  这样的话就是 dp 的裸题了。设 \(dp[i][j]\) 表示前 \(i\) 步，拿了 \(j\) 个蓝球的方案数，讨论这一部拿红球还是蓝球转移一下就好了。

const int N = 2000 + 7;
const int P = 998244353;

int n, cntb[N << 1], dp[N << 1][N << 1];
char s[N];

inline void Inc(int &x, int y) {x += y; x >= P ? x -= P : 0;}

int main() {
	#ifdef hzhkk
	freopen("hkk.in", "r", stdin);
	#endif
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) cntb[i] = cntb[i - 1] + s[i] - '0';
	for (int i = n + 1; i <= (n << 1); ++i) cntb[i] = cntb[i - 1];
	dp[0][0] = 1;
	for (int i = 1; i <= (n << 1); ++i) {
		for (int j = std::max(cntb[i] - i, 0); j <= std::min(cntb[i], i); ++j) {
			if (j) dp[i][j] = dp[i - 1][j - 1];
			if (i > j) Inc(dp[i][j], dp[i - 1][j]);
			//  dbg("dp[%d][%d] = %d\n", i, j, dp[i][j]);
		}
	}
	printf("%d\n", dp[n << 1][cntb[n]]);
}