讨论详情 - QY code

8.6总结

今天的题目我有点不想评价，老师说的最难的题目我比较轻松的写出来了，但是老师说的简单的题目成功的让我在赛后调了2个小时

考试题目：

T1:Jumping on Walls

链接：Jumping on Walls - 题目详情 - QY code

题意：

有一个深 n 米的峡谷，左右两面墙。墙壁从下到上分为 1 到 n 个区域。
忍者初始在左墙的第 1 个区域。
峡谷被水淹没，水位每秒上升 1 米。初始时水位在第 1 个区域的下边界。
忍者每秒可以执行以下三种操作之一：
1. 向上爬：当前墙的高度 +1 。
2. 向下爬：当前墙的高度 −1 。
3. 跳跃：跳到对面的墙，且高度变为当前高度 +k 。
忍者不能停留在标记为 X（危险）的区域。
核心限制：水位每秒上升 1 米。这意味着在第 t 秒（即忍者执行了 t 次操作后），水位会达到高度 t 。因此，忍者在第 t 步时，绝对不能停留在高度 ≤t 的区域，否则会被淹死。
胜利条件：只要忍者到达的高度 >n ，即可逃出峡谷。

思路：

普通的迷宫 BFS 只需要记录 (墙, 高度)，但这道题的水位是随时间变化的。代码巧妙地引入了 step（步数）变量，将状态扩展为 (墙, 高度, 步数)。这样，在搜索的每一步，程序都能准确知道当前的时间，从而计算出当前的水位。

在 BFS 的 while 循环中，代码对当前状态 cur 尝试了三种可能的移动：

向上爬：高度 +1，所在墙不变。
向下爬：高度 -1，所在墙不变（需保证高度 ≥1 ）。
跳跃：所在墙取反 (1 - w)，高度 +k。

在尝试每一种移动时，代码并不是盲目入队，而是进行了严格的合法性检查。对于目标状态 (nw, np)，必须同时满足：

未访问过：!vis[nw][np]，防止死循环。
地形安全：s[nw][np] == '-'，不能踩到危险区域 X。
水位限制（最关键）：np > t + 1。因为执行完这一步后时间变成了 t + 1，水位也是 t + 1，忍者必须在水位之上才能存活。

在执行“向上爬”或“跳跃”时，代码首先检查目标高度 np 是否大于峡谷总高度 n。只要 np > n，说明忍者已经跃出峡谷，立即将标志位 flag 设为 true 并跳出循环，最终输出 YES。

如果 BFS 队列被完全清空（q.empty()），说明所有可能的安全路径都已经探索完毕，且没有找到任何能跳出峡谷的路径。此时 flag 仍为 false，程序输出 NO。

代码：

#include <bits/stdc++.h>
using namespace std;
struct NODE {
    int wall, high, step;
};
int n, k;
char s[2][100010];
bool vis[2][100010];
queue <NODE> q;
int main () {
    scanf ("%d%d", &n, &k);
    scanf ("%s", s[0] + 1);
    scanf ("%s", s[1] + 1);
    q.push ({0, 1, 0});
    vis[0][1] = true;
    bool flag = false;
    while (!q.empty ()) {
        NODE cur = q.front ();
        q.pop ();
        int w = cur.wall, p = cur.high, t = cur.step;
        int nw = w, np = p + 1;
        if (np > n) {
            flag = true;
            break;
        }
        if (!vis[nw][np] && s[nw][np] == '-' && np > t + 1) {
            vis[nw][np] = true;
            q.push ({nw, np, t + 1});
        }
        nw = w, np = p - 1;
        if (np >= 1) {
            if (!vis[nw][np] && s[nw][np] == '-' && np > t + 1) {
                vis[nw][np] = true;
                q.push ({nw, np, t + 1});
            }
        }
        nw = 1 - w, np = p + k;
        if (np > n) {
            flag = true;
            break;
        }
        if (!vis[nw][np] && s[nw][np] == '-' && np > t + 1) {
            vis[nw][np] = true;
            q.push ({nw, np, t + 1});
        }
    }
    if (flag) puts ("YES");
    else puts ("NO");
    return 0;
}

这道题目就是给我们签到的，太简单了

T2:Igor and his way to work

链接：Igor and his way to work - 题目详情 - QY code

题意：

有一个 n 行 m 列的网格地图，代表小镇 Bankopolis。地图上包含起点 S（Igor的家）、终点 T（银行办公室）、普通道路 . 和施工禁行区 *。

Igor 从起点 S 出发，每次只能向上、下、左、右四个方向移动一格，且不能走到施工禁行区 * 上。

Igor 的车方向盘有问题，在从起点到终点的整个过程中，最多只能转弯 2 次。

转弯的定义：在移动过程中，改变行驶方向（例如：从向上走变成向右走，算作 1 次转弯）。
初始方向：在起点 S 刚出发时，Igor 可以自由选择任意一个方向，这不算作转弯。

判断是否存在一条从 S 到 T 的合法路径，使得路径上的转弯次数不超过 2 次。如果存在，输出 YES；否则，输出 NO。

思路：

把搜索的状态从二维坐标 (x, y) 扩展为四维状态 (x, y, dir, turn)。

x, y：当前坐标。
dir：当前朝向（决定了下一步直行去哪）。
turn：已转弯次数（作为限制条件，不能超过2）。

因为起点没有“前一个方向”，所以代码没有把起点入队，而是直接把起点周围4个方向的相邻合法格子入队，且初始转弯次数为0。

对于队列中弹出的每个状态，尝试两种移动：

直行：方向不变，转弯次数不变，往前走一格。
转弯：方向改变（3个新方向），转弯次数+1，往前走一格。如果转弯次数超过2，直接丢弃。

用三维数组 dis[x][y][dir] 记录到达某点某方向的最小转弯次数。如果当前路径的转弯次数 >= 已记录的最小值，说明这条路更差，直接跳过。

BFS过程中，只要某个状态到达终点 T，因为BFS按层扩展，第一次到达就是最优解，直接返回 YES。队列空了还没到，返回 NO。

代码：

#include <bits/stdc++.h>
using namespace std;
struct NODE {
    int x, y, dir, turn;
};
int n, m;
char g[1010][1010];
int dis[1010][1010][4];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int sx, sy, tx, ty;
queue <NODE> q;
bool bfs () {
    for (int d = 0; d < 4; d++) {
        int nx = dx[d] + sx;
        int ny = dy[d] + sy;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] != '*') {
            dis[nx][ny][d] = 0;
            q.push ({nx, ny, d, 0});
        }
    }
    while (!q.empty ()) {
        NODE cur = q.front ();
        q.pop ();
        int x = cur.x, y = cur.y, d = cur.dir, t = cur.turn;
        if (x == tx && y == ty) return true;
        if (t > 2) continue;
        int nx = dx[d] + x;
        int ny = dy[d] + y;
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] != '*') {
            if (dis[nx][ny][d] > t) {
                dis[nx][ny][d] = t;
                q.push ({nx, ny, d, t});
            }
        }
        for (int nd = 0; nd < 4; nd++) {
            if (nd == d) continue;
            int nt = t + 1;
            if (nt > 2) continue;
            nx = dx[nd] + x;
            ny = dy[nd] + y;
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] != '*') {
                if (dis[nx][ny][nd] > nt) {
                    dis[nx][ny][nd] = nt;
                    q.push ({nx, ny, nd, nt});
                }
            }
        }
    }
    return false;
}
int main () {
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf ("%s", g[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == 'S') sx = i, sy = j;
            if (g[i][j] == 'T') tx = i, ty = j;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int d = 0; d < 4; d++) dis[i][j][d] = 1e9;
        }
    }
    bool flag = bfs ();
    if (flag) puts ("YES");
    else puts ("NO");
    return 0;
}

T3:Rudolf and CodeVid-23

链接：Rudolf and CodeVid-23 - 题目详情 - QY code

思路：

Rudolf 感染了病毒，身上有 n 种症状（ n≤10 ）。他可以通过服用 m 种药物来治疗，但每种药都有“消除症状”和“增加副作用症状”的效果，且每种药需要服用一定的天数。

求 Rudolf 消除所有症状（即身上没有任何症状）所需的最少天数。如果无法治愈，输出 -1。

症状种类最多只有 10 种，这暗示了我们可以使用状态压缩（用二进制位来表示当前拥有的症状集合）。
每种药可以重复使用，但每次使用都需要花费天数。这相当于在一个有向图中寻找最短路径。

思路：

因为症状最多只有 10 种，所以所有的症状组合最多只有 $2^{10}=1024$ 种。代码把每一种症状组合（比如“有症状1和3”）用一个整数（二进制掩码）来表示，作为图中的一个节点。

把“吃药”看作在节点之间连边：

从当前状态 mask 出发，尝试吃第 i 种药。
状态转移公式：新状态 = (旧状态 & ~消除症状) | 副作用。
这条边的权重就是吃这种药需要的天数。
以初始症状状态为起点，放入优先队列。
每次从队列中取出当前耗时最少的状态，尝试吃所有 m 种药，生成新状态。
如果新状态的耗时更小，就更新距离并放入队列。
终止条件：一旦从队列中弹出的状态是 0（即没有任何症状），直接返回当前耗时，这就是最少天数。如果队列空了还没遇到 0，说明无解，返回 -1。

代码拆解：

这段代码将每种“症状组合”看作图中的一个节点，将“服药”看作节点之间的边，然后使用 Dijkstra 算法寻找从初始状态到全 0 状态的最短路径。

int Mask (char s[]) {
    int res = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '1') res |= (1 << i); 
    }
    return res;
}

因为 n≤10 ，所以所有的症状组合最多只有 $2^{10}=1024$ 种状态。代码通过 Mask 函数将长度为 n 的 01 字符串转换成一个整数（二进制掩码）。

代码并没有显式地建图，而是在 Dijkstra 的松弛操作中动态生成边：

节点：一个整数 mask，代表当前的症状集合。
边：对于当前状态 mask，尝试使用第 i 种药。

int temp = mask & (~rmove[i]); int nmask = temp | add[i];
边权：该药物需要服用的天数 days[i]。

Dijkstra 算法求最短路

int dijk (int start) {
    for (int i = 0; i < (1 << n); i++) dist[i] = INF;
    priority_queue <PII, vector <PII>, greater <PII>> q;
    dist[start] = 0;
    q.push ({0, start});
    while (!q.empty ()) {
        auto cur = q.top (); q.pop();
        int day = cur.first;
        int mask = cur.second;
        if (mask == 0) return day; 
        if (day > dist[mask]) continue; 
        for (int i = 0; i < m; i++) {
            int temp = mask & (~rmove[i]);
            int nmask = temp | add[i];
            if (dist[nmask] > day + days[i]) {
                dist[nmask] = day + days[i];
                q.push ({dist[nmask], nmask});
            }
        }
    }
    return -1;
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
typedef pair <int, int> PII;
int n, m; 
int rmove[1010];
int add[1010];
int days[1010];
int dist[1 << 10];
int Mask (char s[]) {
    int res = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '1') res |= (1 << i); 
    }
    return res;
}
int dijk (int start) {
    for (int i = 0; i < (1 << n); i++) dist[i] = INF;
    priority_queue <PII, vector <PII>, greater <PII>> q;
    dist[start] = 0;
    q.push ({0, start});
    while (!q.empty ()) {
        auto cur = q.top ();
        q.pop ();
        int day = cur.first;
        int mask = cur.second;
        if (mask == 0) return day;
        if (day > dist[mask]) continue;
        for (int i = 0; i < m; i++) {
            int temp = mask & (~rmove[i]);
            int nmask = temp | add[i];
            if (dist[nmask] > day + days[i]) {
                dist[nmask] = day + days[i];
                q.push ({dist[nmask], nmask});
            }
        }
    }
    return -1;
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &n, &m);
        char s[20];
        scanf ("%s", s);
        int st = Mask (s);
        for (int i = 0; i < m; i++) {
            int d;
            scanf ("%d", &d);
            scanf ("%s", &s);
            int rm = Mask (s);
            scanf ("%s", &s);
            int ad = Mask (s);
            days[i] = d;
            rmove[i] = rm;
            add[i] = ad;
        }
        int ans = dijk (st);
        printf ("%d\n", ans);
    }
    return 0;
}

老师说这道题目很难，但是我觉得这道题目还好，没有真的那么难

T4:Mad City

链接：Mad City - 题目详情 - QY code

城市有 n 个建筑物和 n 条无向边。因为连通且边数等于点数，所以这个图是一个基环树（即包含且仅包含一个环的连通图，环上挂着若干棵树）。
Marcel（抓人者）在节点 a ，Valeriu（逃跑者）在节点 b 。
两人每轮同时行动（可以移动到相邻节点或原地不动）。
抓住的条件：两人在同一节点，或者在相邻节点之间相遇（即两人相向移动在同一条边上）。
Valeriu 的优势：Valeriu 知道 Marcel 的下一步，且两人都绝顶聪明。

判断 Valeriu 是否能够永远不被抓住（输出 YES），否则输出 NO。

思路：

Valeriu 想要永远不被抓住，他必须成功逃入图中的“环”中，并且到达环上某个节点的时间比 Marcel 早。

为什么？

如果 Valeriu 在树枝（非环部分）上，由于 Marcel 也在追，树枝是死胡同，Valeriu 迟早会被逼到尽头抓住。
如果 Valeriu 成功进入了环，因为环是一个闭合回路，且 Valeriu 能预知 Marcel 的行动，只要他进入环时 Marcel 还没到，Valeriu 就可以一直在环上绕圈，永远不被抓住。

代码正是基于这个核心逻辑展开的：

void find_cyrcle () {
    for (int i = 1; i <= n; i++) cyrcle[i] = true;
    queue <int> q;
    for (int i = 1; i <= n; i++) {
        if (dep[i] == 1) {
            q.push (i);
            cyrcle[i] = false;
        }
    }
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        for (int v : g[u]) {
            dep[v] --;
            if (dep[v] == 1 && cyrcle[v]) {
                cyrcle[v] = false;
                q.push (v);
            }
        }
    }
}

利用类似拓扑排序的方法，剥去基环树外围的树枝，剩下的节点 cyrcle[i] == true 即为环上的节点。

计算最短距离：

bfs (a, dA);
bfs (b, dB);

因为边权都是 1，直接使用 BFS 计算两人到图中所有节点的最短距离。

核心判定条件:

for (int i = 1; i <= n; i++) {
    if (cyrcle[i] && dB[i] < dA[i]) {
        flag = true;
        break;
    } 
}

遍历所有节点，如果存在某个环上的节点 i，使得 Valeriu 到达该节点的距离严格小于 Marcel 到达该节点的距离（dB[i] < dA[i]），那么 Valeriu 就可以抢先到达该节点，然后进入环中无限绕圈，永远不被抓住。

整体思路：

识别出图的基环树结构，找出环。
计算两人到所有点的最短距离。
判断逃跑者能否抢先到达环上的任意一个节点。如果能，输出 YES；如果不能，说明逃跑者无处可逃，输出 NO。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a, b;
vector <int> g[200010];
int dep[200010];
bool cyrcle[200010];
int dA[200010], dB[200010];
void find_cyrcle () {
    for (int i = 1; i <= n; i++) cyrcle[i] = true;
    queue <int> q;
    for (int i = 1; i <= n; i++) {
        if (dep[i] == 1) {
            q.push (i);
            cyrcle[i] = false;
        }
    }
    while (!q.empty ()) {
        int u = q.front ();
        q.pop ();
        for (int v : g[u]) {
            dep[v] --;
            if (dep[v] == 1 && cyrcle[v]) {
                cyrcle[v] = false;
                q.push (v);
            }
        }
    }
}
void bfs (int st, int dist[]) {
    for (int i = 1; i <= n; i++) dist[i] = -1;
    queue <int> q;
    dist[st] = 0;
    q.push (st);
    while (!q.empty ()) {
        int u = q.front ();
        q.pop ();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push (v);
            }
        }
    }
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d%d", &n, &a, &b);
        for (int i = 1; i <= n; i++) {
            g[i].clear ();
            dep[i] = 0;
            cyrcle[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            int u, v;
            scanf ("%d%d", &u, &v);
            g[u].push_back (v);
            g[v].push_back (u);
            dep[u] ++, dep[v] ++;
        }
        find_cyrcle ();
        bfs (a, dA);
        bfs (b, dB);
        bool flag = false;
        for (int i = 1; i <= n; i++) {
            if (cyrcle[i] && dB[i] < dA[i]) {
                flag = true;
                break;
            } 
        }
        if (flag) puts ("YES");
        else puts ("NO");
    }
    return 0;
}

T5:Colored Portals

链接：Colored Portals - 题目详情 - QY code

题意：

有 n 个城市排成一条直线，编号 1 到 n 。
每个城市有两个传送门（颜色为 B, G, R, Y 中的两种）。
如果两个城市拥有至少一种相同颜色的传送门，它们之间就可以直接互相到达，花费为两城市编号之差的绝对值 ∣i−j∣ 。

回答 q 个询问，求从城市 x到城市 y 的最小花费。

思路：

虽然题目是一个图论最短路问题，但仔细观察可以发现：任意两点之间的最短距离，最多只需要 2 步（即最多经过 1 个中转城市）。

0 步： x==y 。
1 步： x 和 y 有相同颜色的传送门，直接到达，花费 ∣x−y∣ 。
2 步： x 和 y 没有相同颜色，但存在某个中转城市 d ，使得 x 和 d 同色，且 d 和 y 同色。花费为 ∣x−d∣+∣d−y∣ 。
无解：如果连 2 步都走不到，说明 x 所在的连通块和 y 所在的连通块根本不相连，返回 -1。

代码正是利用了上述“最多中转 1 次”的性质，将复杂的图论最短路问题转化为了查找最近中转点的问题。

1.数据预处理:

bool have[4][MAXN];
vector <int> pos[6];

get_id：将颜色字符映射为 0~3。
get_type：将两种颜色的组合映射为 0~5 的整数（例如 BG=0, BR=1）。
在读入数据时，将每个城市按其颜色组合归类到 pos 数组中。因为城市编号是递增读入的，所以 pos 数组天然是有序的。

2. 处理单次询问

对于每个询问 (x,y) ：

0 步判断：如果 x==y ，直接输出 0。
1 步判断：调用 common(x, y) 检查 x 和 y 是否有同色传送门。如果有，直接更新答案 ans = |x - y|。
2 步判断（核心）：

找出 x 拥有的所有颜色 cx 和 y 拥有的所有颜色 cy。
枚举 x 的颜色 ca 和 y 的颜色 cb，得到一种可能的颜色组合 t = get_type(ca, cb)。
在 pos[t]（拥有这种颜色组合的所有城市）中，寻找距离 x 最近和距离 y 最近的城市作为候选中转点 cand

2。验证中转点：

遍历所有候选中转点 d。
检查 d 是否真的能和 x 连通（common(x, d)），并且能和 y 连通（common(d, y)）。
如果满足，更新最小花费 ans = min(ans, |x - d| + |d - y|)。

3.二分查找最近点

void get_nearest (vector <int>& vec, int val, vector <int>& cand){
    // 二分查找 vec 中第一个 >= val 的位置 p
    // 将 vec[p]（右侧最近）和 vec[p-1]（左侧最近）加入候选集 cand
}

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
const int INF = 1e9;
bool have[4][MAXN];
vector <int> pos[6];
int get_id (char ch) {
    if (ch == 'B') return 0;
    if (ch == 'G') return 1;
    if (ch == 'R') return 2;
    return 3;
}
int get_type (int a, int b){
    if (a > b) swap (a, b);
    if (a == 0 && b == 1) return 0;
    if (a == 0 && b == 2) return 1;
    if (a == 0 && b == 3) return 2;
    if (a == 1 && b == 2) return 3;
    if (a == 1 && b == 3) return 4;
    return 5;
}
bool common (int i, int j){
    for (int c = 0; c < 4;c++){
        if(have[c][i] && have[c][j]) return true;
    }
    return false;
}
void get_nearest (vector <int>& vec, int val, vector <int>& cand){
    int l = 0,r = (int)vec.size() - 1;
    int p = vec.size();
    while(l <= r){
        int mid = (l + r) / 2;
        if(vec[mid] >= val){
            p = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    if (p < (int)vec.size ()) {
        cand.push_back (vec[p]);
    }
    if (p - 1 >= 0) {
        cand.push_back (vec[p - 1]);
    }
}
int main () {
    int T;
    scanf ("%d", &T);
    while (T--) {
        int n, q;
        scanf ("%d%d", &n, &q);
        for (int i = 0; i < 6;i++) pos[i].clear ();
        for (int c = 0; c < 4;c++) {
            for(int i = 1; i <= n;i++) {
                have[c][i] = false;
            }
        }
        for (int i = 1; i <= n;i++) {
            char s[3];
            scanf ("%s", s);
            int c1 = get_id (s[0]);
            int c2 = get_id (s[1]);
            have[c1][i] = true;
            have[c2][i] = true;
            int t = get_type (c1, c2);
            pos[t].push_back (i);
        }
        while (q--) {
            int x, y;
            scanf ("%d%d", &x, &y);
            if (x == y){
                printf ("0\n");
                continue;
            }
            int ans = INF;
            if (common (x, y)) {
                ans = abs (x - y);
            }
            vector <int> cand;
            vector <int> cx, cy;
            for (int c = 0; c < 4;c++) {
                if (have[c][x]) cx.push_back (c);
                if (have[c][y]) cy.push_back (c);
            }
            for (int ca : cx) {
                for (int cb : cy) {
                    int t = get_type (ca, cb);
                    vector <int>& vec = pos[t];
                    if (vec.empty ()) continue;
                    get_nearest (vec, x, cand);
                    get_nearest (vec, y, cand);
                }
            }
            for (int d : cand) {
                if (common (x, d) && common (d, y)) {
                    ans = min (ans, abs (x - d) + abs (d - y));
                }
            }
            if (ans >= INF) printf ("-1\n");
            else printf ("%d\n", ans);
        }
    }
    return 0;
}

我认为这是今天题目中最难的一道

T6:Great Graphs

链接：Great Graphs - 题目详情 - QY code

题意：

有 n 个节点（牧场），以及若干条有向边。图中不存在负环（即不存在无限回到过去的循环）。
已知从节点 1 到所有节点的最短距离数组 d （保证 $d_1=0$ ）。
我们可以自己“脑补”建图，只要建出来的图满足“从 1 出发的最短路正好是 d ”即可。

核心目标：求满足条件的图的最小可能代价（即所有边权之和的最小值）。

隐藏的数学性质：为了让总代价最小，我们肯定希望尽可能多地使用负权边。但是，负权边不能破坏 d 数组的最短路性质。

对于任意一条从 u 到 v 的边，权值为 w ，必须满足三角不等式： $d_v \le d_u + w$ ，即 $d_v-d_u \le w$  。
因此，从 u 到 v 的边，其权值最小只能是 $d_v-d_u$ 。

思路：

既然任意两点 u→v 的边权最小只能是 $d_v−d_u$ ，为了让总代价最小，我们是不是应该把所有可能的边都加上？因为加上更多的边（只要不形成负环）只会让总代价更小或不变。由于 d 数组是最短路，以 $d_v−d_u$ 为权值建完全图，绝对不会产生负环（绕一圈的权值和 ≥0 ）。所以我们应该把所有可能的边

所以，问题转化为了一个纯数学计算：计算完全图中所有边权之和。

1.排序

sort (d + 1, d + n + 1);

首先将 d 数组从小到大排序。因为节点编号不重要，我们只关心距离的相对大小

2.数学公式推导

对于排序后的相邻差值 pre，我写的代码计算了它对总代价的贡献：

ans += 1LL * (i - 1) * (n - i + 1) * pre - pre;

这个公式是怎么来的？

在完全图中，跨越 $d_{i−1}$ 和 $d_i$ 的边（即起点 $d_u ≥ d_i$ ，终点 $d_v≤d_{i−1}$ 的边）一共有 (i−1)×(n−i+1) 条。
如果全建负权边，这些边对差值 pre 的总贡献是 −pre×(i−1)×(n−i+1) 。
但是，为了保证最短路成立，必须保留一条正权边（权值为 +pre ）作为桥梁。
因此，这个差值 pre 对最终总代价的实际贡献是： −pre×(i−1)×(n−i+1)+pre 。
提取负号后，就变成了代码中的：pre * ((i-1)*(n-i+1) - 1)。

整体思路：

将图论中的边权最值问题，转化为排序后的组合数学计算。

明确任意边权的最小值为 $d_v−d_u$ 。
贪心地建出所有负权边，并保留最少必要的正权边。
对 d 数组排序，利用差分法 O(n) 计算出所有边权的总和。

完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll d[100010];
int main () {
	int T;
	scanf ("%d", &T);
	while (T--) {
		int n;
		scanf ("%d", &n);
		for (int i = 1; i <= n; i++) scanf ("%lld", &d[i]);
        sort (d + 1, d + n + 1);
        ll pre = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            pre = d[i] - d[i - 1];
            ans += 1LL * (i - 1) * (n - i + 1) * pre - pre;
        }
        printf ("%lld\n", -ans);
	}
	return 0;
}

8.6总结

今天的题目我有点不想评价，老师说的最难的题目我比较轻松的写出来了，但是老师说的简单的题目成功的让我在赛后调了2个小时

考试题目：

Dijkstra 算法求最短路

2. 处理单次询问

0 条评论

目前还没有评论...

8.6总结

今天的题目我有点不想评价，老师说的最难的题目我比较轻松的写出来了，但是老师说的简单的题目成功的让我在赛后调了2个小时

考试题目：

Dijkstra 算法求最短路

2. 处理单次询问

0 条评论

目前还没有评论...

还没有账户？

登录