思博题，考虑两端和奇偶性即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n, A, B, ans = 0x7fffffffffffffff;
scanf("%lld%lld%lld", &n, &A, &B);
ans = min(A - 1, n - B) + 1 + ((B - A - 1) >> 1);
if (!((A^B) & 1))
ans = min(ans, (B - A) >> 1);
printf("%lld\n", ans);
return 0;
}
Continue reading → 这个题还是比较简单的。
发现在生成树上放一个 \(2\) 之后，剩下与该点距离为偶数的点都已经确定了。所以对于一个连通块而言，被染成 \(2\) 的方式只有两种。
那么我们可以对这些连通块做一个背包，然后来判断是否有 \(n_2\) 的染色方案。
剩下的点随便染色即可。
Continue reading →规律题。只要能发现合法序列的极差不超过 \(1\) 这个性质就可以算了。直接：
\[ ans = 2 – n + \sum_{i = 1}^{n – 1} 2^{\gcd(i, n)} \]
然后这个显然可以用某些 Polya 题的方式用数论函数进行优化，就没了。
Continue reading →最近准备开始复习背包，看《背包九讲》之前正好随机到了这道题，所以来做一个简单的总结。
首先回忆 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;
}
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。