挖土机 CSP-J 模拟赛 ~ 第九场

隔岸观火

假设我们肯定希望每只猫咪的救火时间越短越好，假设救火时间是 $len$，那么 $x-len\sim x+len$ 共 $2\ast len+1$ 个位置就可以由一只猫咪监控到。

总共有 $n$ 个位置，所以需要满足 $(2\ast len+1)\ast k\le n$，由此可以数学方式或者二分算出 $len$ 的最小值。

然后用这个最小值来放置猫咪就好。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int len;
int main()
{
	freopen("ge.in", "r", stdin);
	freopen("ge.out", "w", stdout);
    cin >> n >> k;
    // (len*2+1)*k >= n
    // len >= (n/k-1)/2
    // len >= (n-k)/(k*2)
    len = (n - k) / (k * 2);
    if ((n - k) % (k * 2) != 0)
        len++;
    int pos = 1;
    for (int i = 1; i <= k; i++)
    {
        //           len         len
        // pre_pos xxxxxxx pos xxxxxxx
        pos = min(n, pos + len);
        cout << pos << "\n";
        pos = min(n, pos + len + 1);
    }
    return 0;
}

笑里藏刀

每个 v 为右下角的刀的方案数为上方连续 v 的数量乘以左边连续 v 的数量（乘法原理）。

而这个子问题是个非常经典的递推了。

#include <bits/stdc++.h>
using namespace std;
int n, m;
char a[2005][2005];
int up[2005][2005];
int le[2005][2005];
int main()
{
	freopen("xiao.in", "r", stdin);
	freopen("xiao.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i][j] == 'v')
                up[i][j] = le[i][j] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (up[i][j])
                up[i][j] += up[i - 1][j];
            if (le[i][j])
                le[i][j] += le[i][j - 1];
        }
    long long res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (up[i][j] && le[i][j])
                res += (up[i][j] - 1) * (le[i][j] - 1);
    cout << res;
    return 0;
}

李代桃僵

其实比较容易想到用 dp 做，但是如果状态定义为 $d{p}_{i,j}$ 表示前 $i$ 个人选 $j$ 个，那么是有后效性的，选不选第 $i$ 个人会影响到 $i+\frac{n}{2}$ 那个人的贡献。所以这样显然不好做。

此时考虑把朋友打包，状态定义为前 $i$ 对朋友选 $j$ 个人，这就很好做了。第 $i$ 对显然就四种情况，不选或者选第一个人或者选第二个人或者都选。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[5005];
int b[5005];
int f[2505][5005];
int main()
{
	freopen("li.in", "r", stdin);
	freopen("li.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    int nn = n / 2;
    for (int i = 0; i <= nn; i++)
        for (int j = 0; j <= k; j++)
            f[i][j] = -1;
    f[0][0] = 0;
    for (int i = 1; i <= nn; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= 1 && f[i - 1][j - 1] != -1)
            {
                int nxt = f[i - 1][j - 1] + max(a[i], a[i + nn]);
                if (f[i][j] == -1 || f[i][j] < nxt)
                    f[i][j] = nxt;
            }
            if (j >= 2 && f[i - 1][j - 2] != -1)
            {
                int nxt = f[i - 1][j - 2] + b[i] + b[i + nn];
                if (f[i][j] == -1 || f[i][j] < nxt)
                    f[i][j] = nxt;
            }
        }
    }
    cout << f[nn][k];
    return 0;
}

顺手牵羊

一个比较经典的二分套路。如果 check(mid) 是检查 mid 能不能做第 k 名，那显然不具有单调性，可以做第 k 名的位置是离散的。

可以考虑 check(mid) 检查答案是否大于等于 mid。那就只需要检查是否存在一条路劲使得大于等于 mid 的数不少于 k 个了。此时就有单调性了，答案就是符合条件的 mid 中最大的一个。

这个检查也是个经典的套路，显然只有 $\ge mid$ 的数有贡献，那么可以把所有 $\ge mid$ 的数看作 $1$，所有 $<mid$ 的数看作 0。然后看看左上到右下的最大路径和。此时就是最多路上能经过的 $\ge mid$ 的数的数量了。如果大于等于 $k$，那么 check 就是真。

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[1005][1005];
int f[1005][1005];
bool check(int x)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            bool now = a[i][j] >= x;
            f[i][j] = max(f[i - 1][j], f[i][j - 1]) + now;
        }
    return f[n][n] >= k;
}
int main()
{
	freopen("shun.in", "r", stdin);
	freopen("shun.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    int l = 1;
    int r = 1'000'000'000;
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    cout << ans;
    return 0;
}