Up & Down 的 \(\Theta(n)\) DP
我们发现，这道题其实就是要判断把子树中，最大不超过\(\frac{n}{2}\)的子树接到根部上，子树是否仍能保持\(> \frac{n}{2}\)。
我们按照第一遍的做法做一次 DP，记录当前子树最大和次大值。
然后考虑得出 Up 的 DP 值：首先从父亲转移，然后再用最大值和次小值（不能在同一子树内，这就是次小值存在的意义）来更新当前的 Up 的 DP 值。
我们发现，这道题其实就是要判断把子树中，最大不超过\(\frac{n}{2}\)的子树接到根部上，子树是否仍能保持\(> \frac{n}{2}\)。
我们按照第一遍的做法做一次 DP，记录当前子树最大和次大值。
然后考虑得出 Up 的 DP 值：首先从父亲转移，然后再用最大值和次小值（不能在同一子树内，这就是次小值存在的意义）来更新当前的 Up 的 DP 值。
诶嘿题。画了几张图发现只有\(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;
}
真就您🐎乱搞嘛。
我们可以考虑在怎样的一个情况下才能把一个数称之为\(x^k\)：自然是所有质因数的次数都为\(k\)的倍数，即\(b_i \equiv 0 \pmod k\)。那么，我们可以考虑把一个数分解，表示成质因数的幂：只不过这个次数要模个\(k\)。然后，进行哈希，放到unordered_map中。做哈希的时候做两份，一份是自身，还有一份是凑足完全\(k\)次方的哈希。
但是比较麻烦的是，如果我们搞所有质数，那么会超时。所以，这个时候要给所有质数标号，然后算出质数之间编号差来乘上其哈希幂。
还是要勤思考，说不定是能想出来的。
考虑对这个序列做后缀和，女性代表-1，男性代表+1，然后发现只要保证后缀和一直大于\(-2\)即可。那么，我们可以维护每一段的后缀和，然后维护最大后缀和。
计算答案的时候需要知道要抬升多少才能让整个折线不会碰到\(-2\)的线，找到最大抬升的值就行了（这样都能合法）。
最近准备开始复习背包，看《背包九讲》之前正好随机到了这道题，所以来做一个简单的总结。
首先回忆 01 背包的 DP 递推式：
\[ dp[j] = \max\{ dp[j], dp[j – weight_i] + value_i \} \]
我们可以尝试加一维，记录为第\(x\)优解：\(dp[x][j]\)。如何从之前的更优解合并为次优解是这道题的难点。首先我们发现，对于每一个\(j\)，\(\{ dp[1][j], dp[2][j], dp[3][j], \dots \}\)是单调下降的。那么，我们如果要合并出一个新的单调下降序列，我们就可以使用归并排序的合并方式：只不过不是在两个序列上，而是在两种决策中选择，我们可以把选择第\(i\)个的和不选择的答案虚拟成两个长度为\(k\)的序列，然后用归并的方式合并。
// P1858.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050;
int dp[55][MAX_N], k, m, n, wi[MAX_N], vi[MAX_N], tmp[MAX_N];
int main()
{
scanf("%d%d%d", &k, &m, &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &wi[i], &vi[i]);
memset(dp, 128, sizeof(dp));
dp[1][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = m; j >= wi[i]; j--)
{
int ptr1 = 1, ptr2 = 1, ptr = 0;
while (ptr <= k)
if (dp[ptr1][j] > dp[ptr2][j - wi[i]] + vi[i])
tmp[++ptr] = dp[ptr1++][j];
else
tmp[++ptr] = dp[ptr2++][j - wi[i]] + vi[i];
for (int pt = 1; pt <= k; pt++)
dp[pt][j] = tmp[pt];
}
int ans = 0;
for (int i = 1; i <= k; i++)
ans += dp[i][m];
printf("%d", ans);
return 0;
}
蛮好想。考虑暴力，求完两者之间的\(\gcd\)之后枚举最大的因数即为答案。那么如何加速？我们发现\(gcd\)的最大因素也一定是\(a_1\)的因数之一，所以我们直接预处理\(a_i\)的因数，然后回答询问时直接\(\log n\)枚举即可。