Codeforces Round 214 (Div. 2)

概述

没啥难题，也没有什么特别推荐的题。（快来做前几天的题！！）

A

Description

有四个房间，每个房间有两个守卫，每个守卫可以用不小于一给定价钱的巧克力或果汁贿赂。

现在你有 $n$ 元要恰好花完，要贿赂一个房间里的两个守卫，问怎么分配钱。

Solution

关键在于读懂英文题面，转化成上面的意思，然后就做完了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int x = std::min(a, b), y = std::min(c, d);
        if (x + y <= n)
        {
            cout << i << " " << x << " " << n - x << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

B

Description

有 $n$ 个任务，你每次可以做连续的 $k$ 个，做完这 $k$ 个之后会接着做连续的 $k$ 个任务。一直做到不能做结束。你每次开始做任务时会得到一个对应的怒气值，而连续做的任务不会得到怒气值。

问从哪个任务开始做得到怒气值最小。（建议看英文题面）

Solution

发现从第 $i$ 个任务开始做，就会得到任务 $i,i+k,i+2k…$ 的怒气值。也就是说任务被分成了 $k$ 组。

没啥可说的，直接预处理每组任务怒气值然后输出最小值就可以了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 1e5 + 10;

int a[maxn], n, k;
int sum[maxn];

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= k; i++)
    {
        for (int j = i; j <= n; j += k)
            sum[i] += a[j];
    }
    int ans = 0;
    sum[0] = 1 << 30;
    for (int i = 1; i <= k; i++)
        if (sum[i] < sum[ans])
            ans = i;
    cout << ans << endl;
}

C

Description

有 $n$ 个水果，每个水果有两个属性：美味值 $a$ 和卡路里值 $b$ 。现在选用若干个（至少 $1$ 个）水果制作一份特殊的沙拉，沙拉的美味值为所选的水果的美味值的和，沙拉的卡路里值为所选水果的卡路里值的和。沙拉的美味值恰好是卡路里值的 $k$ 倍。请计算该沙拉美味值最大为多少。

$n,a_i,b_i\leq100,k\leq10$

Solution

把卡路里值乘一下 $k$，问题转化为美味值和卡路里相等。

这个东西就非常背包。

随便乱写一个 DP：$f(i,j,k)$ 表示前 $i$ 个水果，美味值和为 $j$，卡路里和为 $k$ 的最大美味值。然后 $f(i,j,k)=\max(f(i-1,j,k),f(i-1,j-a_i,k-b_i)+a_i)$。这玩意稍微算一下就知道过不去。

因为转移已经是 $O(1)$ 的了，只能从状态入手。发现 $j,k$ 的转移都只和 $i$ 有关，可以搞成一维（类似emiya家今天的饭）：$f(i,d)$ 表示前 $i$ 个水果，卡路里与美味值差为 $d$ 的最大美味值。然后 $f(i,d)=\max(f(i-1,d),f(i-1,d-(b_i-a_i))$。

这样就解决了。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 110, maxm = 3e5 + 10;

int f[maxm], a[maxn], b[maxn], n, k;

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i], b[i] *= k;
    const int M = 1e5, D = 2e5;
    memset(f, -1, sizeof(f));
    f[D] = 0;
    for (int i = 1; i <= n; i++)
    {
        int d = b[i] - a[i];
        if (d > 0)
        {
            for (int j = -M; j + d <= M; j++)
            {
                if (f[j + D + d] != -1)
                    f[j + D] = std::max(f[j + D], f[j + d + D] + a[i]);
            }
        }
        else
        {
            for (int j = M; j + d >= -M; j--)
                if (f[j + D + d] != -1)
                    f[j + D] = std::max(f[j + D], f[j + d + D] + a[i]);
        }
    }
    cout << (f[D] == 0 ? -1 : f[D]) << endl;
}

D

Description

给出一个 $n$ 个点，$m$ 条边的无向图，每条边有区间 $\left[l_i,r_i\right]$，求从 $1$ 到 $n$ 路径组成的边集，使该边集中所有区间的交内的正整数元素个数最多。

$2\leq n\leq10^3,0\leq m\leq3\times10^3$。

Solution

数据范围这么小，我们直接枚举。

考虑枚举一个区间的左端点，然后二分找最大的右端点，再 check 一下图是否联通即可。

时间复杂度 $O(mn\log m)$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 3e3 + 10;

struct UFS
{
    int father[maxn], siz[maxn];
    void init(int n = 1e3)
    {
        for (int i = 1; i <= n; i++)
            father[i] = i, siz[i] = 1;
    }
    int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); }
    void uni(int x, int y)
    {
        int xx = find(x), yy = find(y);
        if (siz[xx] > siz[yy])
            std::swap(xx, yy);
        father[xx] = find(yy), siz[yy] += siz[xx];
    }
    bool ask(int x, int y) { return find(x) == find(y); }
} ufs;

struct edge
{
    int x, y, l, r;
    bool operator<(const edge &b) const { return r < b.r; }
} e[maxn];

int n, m;

bool check(int x, int y)
{
    ufs.init(n);
    for (int i = 1; i <= m; i++)
        if (e[i].l <= x && e[i].r >= y)
            ufs.uni(e[i].x, e[i].y);
    return ufs.ask(1, n);
}

int solve(int x)
{
    int l = 1, r = m, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(x, e[mid].r))
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    //cout << x << " " << e[ans].r << endl;
    return e[ans].r - x + 1;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].l, &e[i].r);
    std::sort(e + 1, e + 1 + m);
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = std::max(solve(e[i].l), ans);
    cout << (ans == 0 ? "Nice work, Dima!" : std::to_string(ans)) << endl;
}

E

Description

给你一个 $n\times m$ 矩阵。矩阵中有 $k$ 种元素。给你一个序列，你要将序列中的每一个元素转化为矩阵上的对应数字的坐标，并使得相邻元素表示的坐标的曼哈顿距离中的最大值最大，求出这个最大值。（建议看原题面）。

$n,m\leq2000$。$k\leq9$。

Solution

我们考虑算出每两种元素之间最大曼哈顿距离。

有一个比较套路的做法：把曼哈顿距离展开： $$ dis=\begin{cases}(x_1+y_1)-(x_2+y_2)\\(x_1-y_1)-(x_2-y_2)\\-(x_1-y_1)+(x_2-y_2)\\-(x_1+y_1)+(x_2+y_2)\end{cases} $$ 也就是说最大曼哈顿距离一定是这四种中的一个，我们对每个颜色维护 $x_1+y_1,x_1-y_1$ 的最大值和最小值然后在上面四种情况里取最大值即可。

Code

#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

const int maxn = 2010;
//const int dx[] = {0, 0, 1, -1};
//const int dy[] = {1, -1, 0, 0};

int ans[10][10], a[maxn][maxn];
int mxadd[10], miadd[10], mxmus[10], mimus[10], q[maxn], n, m, k, s;

inline void upd(int &x, int y) { x = std::max(x, y); }
inline void upd2(int &x, int y) { x = std::min(x, y); }

struct point
{
    int x, y;
};

int main()
{
    scanf("%d%d%d%d", &n, &m, &k, &s);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    memset(mimus, 1, sizeof(mimus)), memset(miadd, 1, sizeof(miadd));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            upd(mxadd[a[i][j]], i + j);
            upd2(miadd[a[i][j]], i + j);
            upd(mxmus[a[i][j]], i - j);
            upd2(mimus[a[i][j]], i - j);
        }
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
        {
            ans[i][j] = std::max(std::max(abs(mxadd[i] - miadd[j]), abs(mxadd[j] - miadd[i])), 
                    std::max(abs(mxmus[i] - mimus[j]), abs(mxmus[j] - mimus[i])));
        }
    int res = 0;
    for (int i = 1; i <= s; i++)
        scanf("%d", &q[i]);
    for (int i = 1; i < s; i++)
        res = std::max(res, ans[q[i]][q[i + 1]]);
    cout << res << endl;
}

概述¶

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

概述

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code