AGC 017
A
DP 即可。
const int N = 55;
int n, p, a[N];
ll dp[N][2];
int main () {
IN (n), IN (p);
lep (i, 1, n) IN (a[i]), a[i] &= 1;
dp[0][0] = 1;
lep (i, 1, n) lep (j, 0, 1) dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ a[i]];
printf ("%lld\n", dp[n][p]);
return 0;
}
B
考虑第二个格子，相当于将第一个格子的权值加上 $k,k\in[C,D]\cup [-D,-C]\cup \mathrm{Z}$ ，找到经过中间这些格子后，能够表示出来的权值区间，判断 $A-B$ 在不在区间内即可。
注意操作次数不是 $n-2$ 而是 $n-1$，因为关于 $B$ 的绝对值限制也算一次操作。
int n, A, B, C, D;
int main () {
IN (n), IN (A), IN (B), IN (C), IN (D);
bool flag = false;
lep (i, 0, n - 1) {
ll L = 1ll * C * (n - i - 1) - 1ll * D * i;
ll R = 1ll * D * (n - i - 1) - 1ll * C * i;
flag |= (L <= B - A && B - A <= R);
}
puts (flag ? "YES" : "NO");
return 0;
}
C
经典套路，如果数字 $x$ 出现了 $c$ 次，则视为有一个区间 $[x-c+1, x]$ ，答案即为 $[1,n]$ 上没有被覆盖的整点位置个数。
用桶维护每个位置的覆盖次数，修改可以直接修改。
const int N = 2e5 + 5;
int n, m, ans, a[N], sta[N], seq[N];
int main () {
IN (n), IN (m);
lep (i, 1, n) {
IN (a[i]), ++ sta[a[i]];
if (a[i] - sta[a[i]] + 1 > 0) ++ seq[a[i] - sta[a[i]] + 1];
}
lep (i, 1, n) ans += ! seq[i];
int x, y;
while (m -- ) {
IN (x), IN (y);
if (a[x] - sta[a[x]] + 1 > 0) -- seq[a[x] - sta[a[x]] + 1], ans += ! seq[a[x] - sta[a[x]] + 1];
-- sta[a[x]], a[x] = y, ++ sta[a[x]];
if (a[x] - sta[a[x]] + 1 > 0) ans -= ! seq[a[x] - sta[a[x]] + 1], ++ seq[a[x] - sta[a[x]] + 1];
printf ("%d\n", ans);
}
return 0;
}
D
好像是惊天套路。
考虑 $1$ 的每个儿子节点，不难发现对于整个游戏而言，每个儿子的子树都是一个子游戏。略有不同的是，子游戏包含了儿子到父亲的边。因为无论何时都可以直接切掉父亲到这个儿子的边从而使得儿子的游戏结束。
注意到因为儿子到父亲的边的存在，这个游戏的 SG 值就需要加上这条边的贡献。发现这条边的实质作用是使所有游戏状态都多了一个 SG 值为 $0$ 的后继状态（也就是切掉儿子到父亲的边）。
接下来讨论一下这个边带来的变化。注意到对于原来 SG 值为 $0$ 的状态，因为多了这么个后继状态，其 SG 值变成了 $1$ 。同样考虑原来 SG 值为 $1$ 的状态，其原来的后继状态中本来有 $0$，而这些 $0$ 都变成了 $1$，同时又多了这么个 SG 值为 $0$ 的后继状态，所以其 SG 值变成了 $2$ 。
通过同样的手法，不难证明原来 SG 值为 $n$ 的状态，多出这个后继状态后 SG 值就变成了 $n + 1$ 。
所以父亲的 SG 值就等于儿子的 SG 值加一后的异或和。
const int N = 1e5 + 5;
int n;
vector <int> to[N];
int sg (int u, int pre) {
int now = 0;
for (int v : to[u]) if (v != pre) now ^= sg (v, u) + 1;
return now;
}
int u, v;
int main () {
IN (n);
lep (i, 2, n) IN (u), IN (v), to[u].pb (v), to[v].pb (u);
puts (sg (1, 0) ? "Alice" : "Bob");
return 0;
}
E
好牛逼的题。
首先可以对插口连边，然后新建起点终点，找地的对应连，找路径即可。可惜这样出来复杂度是 $O(n^2)$ 。
将积木变成边。左右部分看成点：如果 $C_i=0$ 那么就是一个编号为 $A_i$ 的点，否则是一个编号为 $-C_i$ 的点。右边如果 $D_i=0$ 那么就是一个编号为 $-B_i$ 的点，否则是一个编号为 $D_i$ 的点。
惊天发现，这样子的话如果两个积木能对上，当且仅当左边右边的点的编号相同。此时将积木看成边，因为每个积木都需要用，于是这个问题就变成了：找若干个个起点编号为正，终点编号为负的路径，使得其经过了所有的边（用上了所有的积木）。
剩下的就是判合法性，需要注意的就是一个联通块中不能出现环，不然起点终点的正负相同。剩下的记录入度和出度后判一下就好了。
const int N = 1e5 + 5;
const int H = 4e2 + 5;
const int _ = 2e2;
bool able[H];
int n, h, a, b, c, d, in[H], ot[H], fa[H];
int find (int x) { return x == fa[x] ? x : fa[x] = find (fa[x]); }
int u, v;
int main () {
IN (n), IN (h);
lep (i, 0, _ << 1) fa[i] = i;
lep (i, 1, n) {
IN (a), IN (b), IN (c), IN (d);
c == 0 ? ++ ot[u = _ + a] : ++ ot[u = _ - c];
d == 0 ? ++ in[v = _ - b] : ++ in[v = _ + d];
if (find (u) != find (v)) fa[find (u)] = find (v);
}
int s = 0, t = 0;
Lep (i, 0, _) if (in[i] < ot[i]) return puts ("NO"), 0;
lep (i, _ + 1, _ << 1) if (in[i] > ot[i]) return puts ("NO"), 0;
lep (i, 0, _ << 1) if (in[i] != ot[i]) able[find (i)] = true;
lep (i, 0, _ << 1) if (in[i] + ot[i]) if (! able[find (i)]) return puts ("NO"), 0;
puts (s == t ? "YES" : "NO");
return 0;
}
F
不想强搞，咕掉了。
0 条评论