[AtCoder] Yahoo Programming Contest 2019

时间:2021-10-28 15:11:20

[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]]);
}