A – 仓鼠的石子游戏
诶嘿题。画了几张图发现只有\(1\)的情况先手必胜，所以考虑多轮交换先后手即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 200, table[8] = {0, 0, 1, 1, 1, 1, 1, 1};
int T, n, ai[MAX_N];
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]);
bool flag = false;
for (int i = 1; i <= n; i++)
flag ^= (ai[i] == 1);
printf(flag ? "rabbit\n" : "hamster\n");
}
return 0;
}
B – 乃爱与城市拥挤程度
\(\Theta(n^2)\)很好做，就不说了。
考虑进行换根 DP，把父亲的信息换到儿子，然后再恢复回来。但是太特么难写了，所以还是建议各位用 Up & Down 写（而且那样的写法也确实比较好看）。这个是赛时 80 分代码：
// B.cpp
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int MAX_N = 1e5 + 200, MAX_K = 15, mod = 1e9 + 7;
int head[MAX_N], current, n, k, dp[MAX_N][MAX_K], prod[MAX_N][MAX_K];
int ans[MAX_N], ans2[MAX_N], org[MAX_N][MAX_K];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
namespace IO
{
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
inline int rd()
{
int x = 0, f = 1;
char c = gc();
while (!isdigit(c))
{
if (c == '-')
f = -1;
c = gc();
}
while (isdigit(c))
x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
} // namespace IO
int quick_pow(int bas, int tim)
{
int ret = 1;
while (tim)
{
if (tim & 1)
ret = 1LL * ret * bas % mod;
bas = 1LL * bas * bas % mod;
tim >>= 1;
}
return ret;
}
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
void build_prod(int u, int fa)
{
prod[u][0] = dp[u][0] % mod;
for (int i = 1; i <= k; i++)
prod[u][i] = (1LL * prod[u][i - 1] + 1LL * dp[u][i]) % mod;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
for (int j = 1; j <= k; j++)
prod[u][j] = (1LL * prod[u][j] * prod[edges[i].to][j - 1] % mod);
}
void dfs(int u, int fa)
{
dp[u][0] = 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
dfs(edges[i].to, u);
for (int j = 1; j <= k; j++)
dp[u][j] += dp[edges[i].to][j - 1];
}
// get the prod;
build_prod(u, fa);
}
void redfs(int u, int fa)
{
// collecting data;
for (int i = 0; i <= k; i++)
ans[u] += dp[u][i];
build_prod(u, 0);
ans2[u] = prod[u][k];
// to change the root;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa)
{
// make things ready for the subtree;
for (int j = 1; j <= k; j++)
dp[u][j] -= dp[edges[i].to][j - 1];
for (int j = 1; j <= k; j++)
dp[edges[i].to][j] += dp[u][j - 1];
build_prod(u, edges[i].to);
redfs(edges[i].to, u);
for (int j = 1; j <= k; j++)
dp[edges[i].to][j] -= dp[u][j - 1];
for (int j = 1; j <= k; j++)
dp[u][j] += dp[edges[i].to][j - 1];
build_prod(edges[i].to, u);
build_prod(u, 0);
// rec on myself;
for (int j = 1; j <= k; j++)
prod[u][j] = 1LL * prod[u][j] * prod[edges[i].to][j - 1] % mod;
}
}
int main()
{
memset(head, -1, sizeof(head));
n = IO::rd(), k = IO::rd();
for (int i = 1, u, v; i <= n - 1; i++)
u = IO::rd(), v = IO::rd(), addpath(u, v), addpath(v, u);
dfs(1, 0), redfs(1, 0);
for (int i = 1; i <= n; i++)
printf("%d ", ans[i]);
puts("");
for (int i = 1; i <= n; i++)
printf("%d ", ans2[i]);
puts("");
return 0;
}
C – 小w的魔术扑克
看来要好好复习下二分图。
可以考虑建一个二分图，左部为牌面，右部为牌的编号。见图方式见代码：这样建图，利用了一个性质，就是顺子都是一大块极大连通块，所有的顺子都是极大连通块的子集；从右端点做匈牙利可以匹配出最大可以匹配的部分，然后发现如果没法匹配那么上次到的左边必须放弃：因为与上一个可以连通的部分断开了。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 200;
int head[MAX_N], current, n, k, q, vis[MAX_N], pre[MAX_N], lft[MAX_N], ncnt, matching[MAX_N];
struct edge
{
int to, nxt;
} edges[MAX_N << 1];
void addpath(int src, int dst)
{
edges[current].to = dst, edges[current].nxt = head[src];
head[src] = current++;
}
bool hungery(int u, int org)
{
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (vis[edges[i].to] != org)
{
vis[edges[i].to] = org;
if (!matching[edges[i].to] || hungery(matching[edges[i].to], org))
{
matching[edges[i].to] = u, pre[u] = edges[i].to;
return true;
}
}
return false;
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &k);
for (int i = 1, u, v; i <= k; i++)
{
scanf("%d%d", &u, &v);
addpath(u, i + n), addpath(i + n, u);
addpath(v, i + n), addpath(i + n, v);
}
int lcur = 1;
for (int i = 1; i <= n; i++)
{
// fine the leftmost point to pair a conti;
while (!hungery(i, ++ncnt) && lcur <= i)
matching[pre[lcur]] = false, lcur++;
lft[i] = lcur;
}
scanf("%d", &q);
while (q--)
{
int l, r;
scanf("%d%d", &l, &r);
if (lft[r] <= l)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}