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

关注

CCPC-Wannafly Winter Camp Day1 (Div2, onsite)

B. 吃豆豆

Description:

$w l s$ 在玩一个游戏。

$w l s$ 有一个 $n$ 行 $m$ 列的棋盘，对于第 $i$ 行第 $j$ 列的格子，每过 $T [i] [j]$ 秒会在上面出现一个糖果，第一次糖果出现在第 $T [i] [j]$ 秒，糖果仅会在出现的那一秒存在，下一秒就会消失。

假如 $w l s$ 第 $k$ 秒在第 $i$ 行第 $j$ 列的格子上，满足 $T [i] [j] ∣ k$ ，则 $w l s$ 会得到一个糖果。

假如当前 $w l s$ 在第 $i$ 行第 $j$ 列的格子上，那么下一秒他可以选择往上下左右走一格或停在原地。

现在请问 $w l s$ 从指定的 $S$ 出发到达指定的 $T$ ，并且在路上得到至少 $C$ 个糖果最少需要多少时间？

$w l s$ 在 $S$ 的初始时间为第 $0$ 秒。

Input:

第一行三个整数 $n$ ， $m$ ， $C$ 。

接下来 $n$ 行，每行m个整数 $T [i] [j]$ 。

接下来四个整数 $x s$ , $y s$ , $x t$ , $y t$ ，其中 $(x s, y s)$ 表示 $S$ ， $(x t, y t)$ 表示 $t$ 。

$1 \leq n, m, T [i] [j] \leq 10$

$1 \leq C \leq 1018$

$1 \leq x s, x t \leq n$

$1 \leq y s, y t \leq m$

Output:

一行一个整数表示答案。

Sample Input:

1 3 2
1 2 3
1 1 1 3

Sample Output:

题目链接

$d p [i] [j] [k]$ 表示第 $k$ 秒在 $(i, j)$ 位置上能获得的最多糖果，从 $(i, j) 、 (i - 1, j) 、 (i + 1, j) 、 (i, j - 1) 、 (i, j + 1)$ 五个位置的 $k - 1$ 秒转移即可。

AC代码:

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

const int maxn = 1e1 + 5;

int N, M, C;
int T[maxn][maxn];
int XS, YS;
int XT, YT;
int Dp[maxn][maxn][20010];

void Transfer(int X, int Y, int Time) {
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (abs(i) == abs(j)) {
                if (i != 0 && j != 0) {
                    continue;
                }
            }
            Dp[X][Y][Time] = max(Dp[X][Y][Time], Dp[X + i][Y + j][Time - 1]);
        }
    }
    Dp[X][Y][Time] += Time % T[X][Y] == 0;
}

int main(int argc, char *argv[]) {
    scanf("%d%d%d", &N, &M, &C);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            scanf("%d", &T[i][j]);
        }
    }
    scanf("%d%d%d%d", &XS, &YS, &XT, &YT);
    for (int k = 1; k < 20010; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                if (k == 0) Dp[i][j][k] = 0;
                else if ((abs(i - XS) + abs(j - YS) <= k)) Transfer(i, j, k);
            }
        }
    }
    for (int i = 0; i < 20010; ++i) {
        if (Dp[XT][YT][i] >= C) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

C. 拆拆拆数

Description:

读入 $A$ 和 $B$ ， $w l s$ 想请你把 $A$ 拆成 $a_{1}, a_{2}, . . ., a_{n}$ , 把 $B$ 拆成 $b_{1}, b_{2}, . . ., b_{n}$ ，满足

对于所有的 $i (1 \leq i \leq n) ， a_{i}, b_{i} \geq 2$ 且 $g c d (a_{i}, b_{i}) = 1$
$\sum_{i = 1}^{n} a_{i} = A$ ， $\sum_{i = 1}^{n} b_{i} = B$

如果有多组满足条件的 $a$ 和 $b$ ，请输出 $n$ 最小的任意一组即可。

如果无解，请输出 $- 1$ 。

Input:

第一行一个整数 $t e s t$ 表示数据组数。

接下来 $t e s t$ 行，每行两个整数 $A$ ， $B$ 。

$1 \leq t e s t \leq 100000$

$5 \leq A, B \leq 1 0^{18}$

Output:

对于每组数据，第一行输出一个整数 $n$ ；

接下来 $n$ 行每行输出两个整数 $a_{i}$ ， $b_{i}$ 表示答案。

Sample Input:

2
6 5
100000 100000

Sample Output:

1
6 5
2
49999 50001
50001 49999

题目链接

显然当 $g c d (A, B) \neq 1$ 时答案为 $2$ ，不知道为什么反正用前 $100$ 个素数枚举一下就可以。

AC代码:

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

bool IsPrime[110];
int Tot;
long long Prime[110];

void PrimeSieve() {
	for (int i = 2; i < 110; ++i) IsPrime[i] = true;
	for (int i = 2; i < 110; ++i) {
		if (IsPrime[i]) {
			Prime[Tot++] = i;
			for (int j = i * i; j < 110; j += i) IsPrime[j] = false;
		}
	}
}

int T;
long long A, B;

int main(int argc, char *argv[]) {
	PrimeSieve();
	scanf("%d", &T);
	for (int Case = 1; Case <= T; ++Case) {
		scanf("%lld%lld", &A, &B);
		if (__gcd(A, B) == 1) printf("1\n%lld %lld\n", A, B);
		else {
			for (int i = 0; i < Tot; ++i) {
				if (__gcd(Prime[i], B - Prime[i]) == 1 && __gcd(A - Prime[i], Prime[i]) == 1) {
					printf("2\n%lld %lld\n%lld %lld\n", Prime[i], B - Prime[i], A - Prime[i], Prime[i]);
					break;
				}
			}
		}
	}
	return 0;
}

F. 爬爬爬山

Description:

爬山是 $w l s$ 最喜欢的活动之一。

在一个神奇的世界里，一共有 $n$ 座山， $m$ 条路。

$w l s$ 初始有 $k$ 点体力，在爬山的过程中，他所处的海拔每上升 $1 m$ ，体力会减 $1$ 点，海拔每下降 $1 m$ ，体力会加一点。

现在 $w l s$ 想从 $1$ 号山走到 $n$ 号山，在这个过程中，他的体力不能低于 $0$ ，所以他可以事先花费一些费用请 $d l s$ 把某些山降低，将一座山降低 $l$ 米需要花费 $l * l$ 的代价，且每座山的高度只能降低一次。因为 $w l s$ 现在就在 $1$ 号山上，所以这座山的高度不可降低。

$w l s$ 从 $1$ 号山到 $n$ 号山的总代价为降低山的高度的总代价加上他走过的路的总长度。

$w l s$ 想知道最小的代价是多少。

Input:

第一行三个整数 $n$ ， $m$ ， $k$ 。

接下来一行 $n$ 个整数，第 $i$ 个整数 $h_{i}$ 表示第 $i$ 座山的高度。

接下来 $m$ 行，每行三个整数 $x$ ， $y$ ， $z$ 表示 $x y$ 之间有一条长度为 $z$ 的双向道路。

经过每条路时海拔是一个逐步上升或下降的过程。

数据保证 $1$ 号山和 $n$ 号山联通。

$1 \leq n, k, h_{i}, z \leq 100000$

$1 \leq m \leq 200000$

$1 \leq x, y \leq n$

$x \neq y$

Output:

一行一个整数表示答案。

Sample Input:

4 5 1
1 2 3 4
1 2 1
1 3 1
1 4 100
2 4 1
3 4 1

Sample Output:

题目链接

广搜路径，在搜索时贪心的降低山高即可。

AC代码:

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

const int maxn = 1e5 + 5;

struct Edge {
    int V;
    long long Weight;
    int Next;
};

int Tot;
int Head[maxn];
Edge edges[maxn << 2];


void AddEdge(int U, int V, long long Weight) {
    edges[Tot] = (Edge){V, Weight, Head[U]};
    Head[U] = Tot++;
}

int N, M, K;
int X, Y;
long long Z;
long long Height[maxn];

struct Status {
    long long Pos, Power, Cost, Reduce;

    bool operator < (const Status &Key) const {
        if (Cost == Key.Cost) {
            return Power < Key.Power;
        }
        return Cost > Key.Cost;
    }
};

long long Cost[maxn];

bool Check(int Pos, long long PreCost) {
    if  (Cost[Pos] != -1) {
        if (PreCost < Cost[Pos]) {
            return true;
        }
        return false;
    }
    return true;
}

long long Bfs() {
    priority_queue<Status> Que;
    for (int i = 1; i <= N; ++i) {
        Cost[i] = -1;
    }
    Que.push((Status){1, K, 0, 0});
    while (!Que.empty()) {
        Status Cur = Que.top(); Que.pop();
        if (Cur.Pos == N) {
            return Cur.Cost;
        }
        for (int i = Head[Cur.Pos]; ~i; i = edges[i].Next) {
            long long Diff = Height[edges[i].V] - (Height[Cur.Pos] - Cur.Reduce);
            if (Diff < 0) {
                if (Check(edges[i].V, Cur.Cost + edges[i].Weight)) {
                    Que.push((Status){edges[i].V, Cur.Power - Diff, Cur.Cost + edges[i].Weight, 0});
                    Cost[edges[i].V] = Cur.Cost + edges[i].Weight;
                }
            }
            else if (Diff <= Cur.Power) {
                if (Check(edges[i].V, Cur.Cost + edges[i].Weight)) {
                    Que.push((Status) {edges[i].V, Cur.Power - Diff, Cur.Cost + edges[i].Weight, 0});
                    Cost[edges[i].V] = Cur.Cost + edges[i].Weight;
                }
            }
            else {
                if (Check(edges[i].V, Cur.Cost + (Diff - Cur.Power) * (Diff - Cur.Power) + edges[i].Weight)) {
                    Que.push((Status){edges[i].V, 0, Cur.Cost + (Diff - Cur.Power) * (Diff - Cur.Power) + edges[i].Weight, Diff - Cur.Power});
                    Cost[edges[i].V] = Cur.Cost + (Diff - Cur.Power) * (Diff - Cur.Power) + edges[i].Weight;
                }
            }
        }
    }
}

int main(int argc, char *argv[]) {
    scanf("%d%d%d", &N, &M, &K);
    Tot = 0;
    for (int i = 1; i <= N; ++i) {
        Head[i] = -1;
    }
    for (int i = 1; i <= N; ++i) {
        scanf("%lld", &Height[i]);
    }
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d%lld", &X, &Y, &Z);
        AddEdge(X, Y, Z);
        AddEdge(Y, X, Z);
    }
    printf("%lld\n", Bfs());
    return 0;
}

J. 夺宝奇兵

Description:

$w l s$ 所在的王国有 $n$ 个居民（不包括 $w l s$ ），他们共有 $m$ 件神奇的宝物。

对于第 $i$ 件宝物， $w l s$ 可以花费 $a_{i}$ 的金币把它从原来的主人那里买过来。

请问 $w l s$ 最少要准备多少金币，才能使他成为宝物最多的人（ $w l s$ 的宝物件数严格比其他所有人多）？

Input:

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

接下来 $m$ 行，每行两个整数 $a_{i}$ , $c_{i}$ ，表示第 $i$ 件宝物属于居民 $c_{i}$ ， $n x s$ 可以花费 $a_{i}$ 的代价得到它。

$1 \leq n, m \leq 1000$

$1 \leq a_{i} \leq 1000000000$

$1 \leq c_{i} \leq n$

Output:

一行一个整数表示答案。

Sample Input:

4 11
10 1
1 1
10 2
1 2
10 3
1 3
15 4
15 4
15 4
15 4
15 4

Sample Output:

题目链接

枚举 $w l s$ 要购买的宝物数量，先将大于等于次数量的人的最偏的宝物买来，之后若为达到枚举量则买所有宝物中国最便宜的宝物

AC代码:

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

const int maxn = 1e3 + 5;

int N, M;
vector<long long> P[maxn];
int Max;
long long Ans;

int main(int argc, char *argv[]) {
    scanf("%d%d", &N, &M);
    for (int i = 1, A, C; i <= M; ++i) {
        scanf("%lld%d", &A, &C);
        P[C].push_back(A);
    }
    Max = -1;
    for (int i = 1; i <= N; ++i) {
        Max = max(Max, (int)P[i].size());
        sort(P[i].begin(), P[i].end());
    }
    Ans = 1e18;
    for (int k = Max + 1; k > 0; --k) {
        vector<long long> Residue;
        long long Res = 0; int Cnt = 0;
        for (int i = 1; i <= N; ++i) {
            int Size = P[i].size();
            for (int j = 0; j < Size; ++j) {
                if (Size >= k && j < Size - k + 1) {
                    Res += P[i][j];
                    Cnt++;
                }
                else Residue.push_back(P[i][j]);
            }
        }
        sort(Residue.begin(), Residue.end());
        if (Cnt < k) {
            for (int i = 0; i < k - Cnt; ++i) {
                Res += Residue[i];
            }
        }
        Ans = min(Ans, Res);
    }
    printf("%lld\n", Ans);
    return 0;
}