最近都在学些科技，做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。

子集

首先，我们先考虑奇数长度段的情况（\(\{a_n\}\)已经排序）：确定中位数为\(a_{mid}\)，则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和，并除以元素个数。欲使价值最大，那么显然右侧需要靠近右端点进行选择， 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化：简化对长度的枚举复杂度。

Continue reading →

主要思路

欲覆盖整个直线，那么只需要让这些步数能合成一个\(1\)即可。那么根据 Bézout 定理，有\(ax + by = \gcd(a, b)\)，那么我们可以用这个做 DP：不停地合成新的\(\gcd\)来找最小代价。

代码

// CF510D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330;

int li[MAX_N], ci[MAX_N], n;
map<int, int> ump;
map<int, int>::iterator it;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &li[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ci[i]);
    for (int i = 1; i <= n; i++)
    {
        int tmp = ump[li[i]];
        if (tmp == 0)
            ump[li[i]] = ci[i];
        else
            ump[li[i]] = min(tmp, ci[i]);
        for (it = ump.begin(); it != ump.end(); it++)
        {
            int di = gcd(it->first, li[i]);
            tmp = ump[di];
            if (tmp == 0)
                ump[di] = it->second + ci[i];
            else
                ump[di] = min(tmp, ci[i] + it->second);
        }
    }
    printf("%d", ump[1] ? ump[1] : -1);
    return 0;
}

简述

最近准备开始复习背包，看《背包九讲》之前正好随机到了这道题，所以来做一个简单的总结。

原理

首先回忆 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;
}

主要思路

首先需要知道一个性质：如果第一行和第一列确定，那么这个方案就已经完全确定了。这个可以用归纳法证明：

证明  如果格子\((i – 1, j)\)、\((i, j – 1)\)和\((i – 1, j – 1)\)的颜色确定，那么显然\((i, j)\)的颜色就能被唯一确定。如果第一行和第一列可以被确定，那么根据上述描述，便可生成一个唯一的方案。

所以欲记录方案的个数，那么就要记录合法的第一行和第一列的方案数。这样我们把问题转换到了长条上。

设置\(dp[i][0/1][0/1]\)为到第\(i\)位是否连续、最后一位填的数字。那么转移非常自然，可以自行推导（确实啊）。

最后答案就是把所有情况加起来，再减去非法的两种情况（也就是左上角的三格同色的情况）。

Continue reading →