2019-08-08 17:50 已编辑苏州大学算法工程师

关注

CCPC-Wannafly Winter Camp Day4 (Div2, onsite)

A. 夺宝奇兵

Description:

wls正在玩一个寻宝游戏。

宝藏一共有 $n$ 种，都藏在一个 $m$ 行 $m$ 列的网格中。

每种宝藏都恰好有两个。

$w l s$ 只能沿着网格走（上下左右四个方向）。

他想依次获得 $1... n$ 类宝藏，然后再以 $n . . . 1$ 的顺序获得剩下的宝藏。

$w l s$ 可以从任意点出发。

当 $w l s$ 到达某个宝藏的位置时，他可以选择取或不取这个宝藏。

请问他最少要移动多少距离？

Input:

第一行两个整数 $n$ ， $m$ 。

接下来 $n$ 组，每组两行表示一类宝藏，每行两个整数 $x$ ， $y$ 表示一个宝藏的坐标。

$1 \leq n, m \leq 100000$

$1 \leq x, y \leq m$

Output:

一行一个整数表示答案。

Sample Input:

2 10
1 1
2 2
3 3
4 4

Sample Output:

题目链接

对于第 $i$ 、 $i + 1$ 种宝藏（设 $i = {a, b} ， i + 1 = {c, d}$ ）其来回可走选择有两种

$a \to c$ ， $d \to b$
$b \to d$ ， $c \to a$

贪心地取两者中和的最小值即可

AC代码:

#include<bits/stdc++.h>
using namespace std;

struct Point {
    int X, Y;
};

int Dis(Point Key1, Point Key2) {
    return abs(Key1.X - Key2.X) + abs(Key1.Y - Key2.Y);
}

int N, M;
Point Treasure[100010][2];
long long Ans;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", &Treasure[i][0].X, &Treasure[i][0].Y);
        scanf("%d%d", &Treasure[i][1].X, &Treasure[i][1].Y);
    }
    for (int i = 1; i < N; ++i) {
        Ans += min(Dis(Treasure[i][0], Treasure[i + 1][0]) + Dis(Treasure[i][1], Treasure[i + 1][1]),
                Dis(Treasure[i][0], Treasure[i + 1][1]) + Dis(Treasure[i][1], Treasure[i + 1][0]));
    }
    Ans += Dis(Treasure[N][0], Treasure[N][1]);
    printf("%lld\n", Ans);
    return 0;
}

C. 最小边覆盖

Description:

给定一个无向连通简单图 $G$ （简单图的意思是无自环无重边），它的一个边覆盖是 $G$ 的边集 $E$ 的子集 $S$ ，使得 $G$ 的点集 $V$ 中的任意一个点都出现在 $S$ 中的至少一条边中。这个边覆盖的大小定义为 $S$ 包含的边数。如果 $S$ 是所有 $G$ 的边覆盖中最小的，则称 $S$ 是图 $G$ 的最小边覆盖。

Gallai证明了对任意无向连通简单图，它的最大匹配的大小加上最小边覆盖的大小一定等于它的点数。

于是，为了求出一个无向简单图的最小边覆盖，我们可以首先使用带花树算法求出它的最大匹配，然后仿照Gallai定理的证明构造出一个最小边覆盖。

这道题给定了无向连通简单图 $G$ 的点集，和图 $G$ 的边的一个子集 $S$ ，但没有给出边集 $E$ 。试判断 $S$ 有没有可能是图 $G$ 的最小边覆盖。

Input:

第一行两个正整数 $n$ 和 $m$ 表示图 $G$ 的点数和 $S$ 的大小（ $1 \leq n \leq 200000, 1 \leq m \leq 300000$ ）。接下来 $m$ 行每行两个正整数 $a, b$ 表示 $S$ 中的一条边 $a, b$ （点从 $1$ 到 $n$ 编号，保证 $S$ 中没有自环和重边）。

Output:

如果存在一个无向连通图 $G$ ，使得 $G$ 的点集是 $1, \dots, n$ ，且 $G$ 的边集包含 $S$ ，且 $S$ 是 $G$ 的一个最小边覆盖，则输出"Yes"。否则输出"No"。

Sample Input:

4 2
1 2
3 4

Sample Output:

Yes

Sample Input:

4 3
1 2
2 3
3 4

Sample Output:

题目链接

对每个顶点统计度数

枚举每条边，若边上两端点度数均大于 $1$ 则表示此边可删即不是最小边覆盖

AC代码:

#include<bits/stdc++.h>
using namespace std;

int N, M;
int A[200010];
int B[200010];
map<int, int> Cnt;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d", &A[i], &B[i]);
        Cnt[A[i]]++;
        Cnt[B[i]]++;
    }
    for (int i = 1; i <= M; ++i) {
        if (Cnt[A[i]] >= 2 && Cnt[B[i]] >= 2) {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

I. 咆咆咆哮

Description:

wls手上有 $n$ 张牌，每张牌他都可以选择召唤一个攻击力为 $a_{i}$ 的生物，或者使得场上所有生物的攻击力加 $b_i $。

请问如何抉择，使得场攻（场上生物攻击力的总和）最高。

$w l s$ 可以任意选择出这nn张牌的顺序。

Input:

第一行一个整数 $n$ 。

接下来 $n$ 行，每行两个整数 $a_{i}$ 和 $b_{i}$ 。

$1 \leq n \leq 1000$

$0 \leq a_{i}, b_{i} \leq 1000000$

Output:

一行一个整数表示答案。

Sample Input:

3
20 1
15 10
20 2

Sample Output:

题目链接

判断比较每张牌抉择的贡献

若召唤生物则贡献为 $a_{i}$ ，若增加攻击力则贡献为 $k b_{i}$ （ $k$ 为全场召唤生物数量）（显然先召唤所有生物再用剩下的牌增加攻击力的方案最优）

所以考虑枚举全场生物召唤数量 $k$ 对每张牌计算贡献并排序计算总场攻

取最高场攻即可

AC代码:

#include<bits/stdc++.h>
using namespace std;

struct Monster {
    long long A, B;
};

int N;
Monster Card[1010];
long long Ans;
long long Res;

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%lld%lld", &Card[i].A, &Card[i].B);
    }
    for (int k = 0; k <= N; ++k) {
        Res = 0;
        sort(Card + 1, Card + N + 1, [&](Monster Key1, Monster Key2) {
            return (Key1.A - Key1.B * k) > (Key2.A - Key2.B * k);
        });
        for (int i = 1; i <= k; ++i) {
            Res += Card[i].A;
        }
        for (int i = k + 1; i <= N; ++i) {
            Res += Card[i].B * k;
        }
        Ans = max(Ans, Res);
    }
    printf("%lld\n", Ans);
    return 0;
}