A. 夺宝奇兵

Description:

wls正在玩一个寻宝游戏。

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

每种宝藏都恰好有两个。

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

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

$wls$wls 可以从任意点出发。

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

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

Input:

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

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

$1\le n,m\le 100000$1≤n,m≤100000

$1\le x,y\le m$1≤x,y≤m

Output:

一行一个整数表示答案。

Sample Input:

2 10
1 1
2 2
3 3
4 4

Sample Output:

10

题目链接

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

1. $a\to c$a→c ， $d\to b$d→b
2. $b\to d$b→d ， $c\to a$c→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（简单图的意思是无自环无重边），它的一个边覆盖是 $G$G 的边集 $E$E 的子集 $S$S ，使得 $G$G 的点集 $V$V 中的任意一个点都出现在 $S$S 中的至少一条边中。这个边覆盖的大小定义为 $S$S 包含的边数。如果 $S$S 是所有 $G$G 的边覆盖中最小的，则称 $S$S 是图 $G$G 的最小边覆盖。

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

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

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

Input:

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

Output:

如果存在一个无向连通图 $G$G ，使得 $G$G 的点集是 $1,\dots ,n$1,…,n，且 $G$G 的边集包含 $S$S ，且 $S$S 是 $G$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:

No

题目链接

对每个顶点统计度数

枚举每条边，若边上两端点度数均大于 $1$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$n 张牌，每张牌他都可以选择召唤一个攻击力为 $a_i$ai​ 的生物，或者使得场上所有生物的攻击力加 $b_i $。

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

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

Input:

第一行一个整数 $n$n 。

接下来 $n$n 行，每行两个整数 $a_i$ai​ 和 $b_i$bi​ 。

$1\le n\le 1000$1≤n≤1000

$0\le a_i,b_i\le 1000000$0≤ai​,bi​≤1000000

Output:

一行一个整数表示答案。

Sample Input:

3
20 1
15 10
20 2

Sample Output:

60

题目链接

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

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

所以考虑枚举全场生物召唤数量 $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;
}