2021 - ICPC 网络赛 (第一场)Problem A . Busiest Computing NodesProblem B . Convex PolygonProblem C . Driver LicensesProblem D . Edge of TaixuanProblem E . Infinite File SystemProblem F . Land Overseer （√）Problem G . Longest Prefix MatchingProblem H . Mesh A

90 阅读 0 评论 60 点赞

我是靠谱客的博主眼睛大雨，这篇文章主要介绍2021 - ICPC 网络赛 (第一场)Problem A . Busiest Computing NodesProblem B . Convex PolygonProblem C . Driver LicensesProblem D . Edge of TaixuanProblem E . Infinite File SystemProblem F . Land Overseer （√）Problem G . Longest Prefix MatchingProblem H . Mesh A，现在分享给大家，希望可以做个参考。

借鉴的博客网址

本人第一次参加 ICPC 的打铁记录…把当时的私人笔记搬过来了，现在看看有点羞耻（

Problem A . Busiest Computing Nodes

题意：

一道思维线段树题，有k个机器，从0 - k-1编号。n次操作，告诉你一个工程的开始时间和持续时间，每次从第（i % k）台机器开始分配（i从0开始），如果当前机器空闲，就会让它负责这个工程，否则从 i + 1 到 k - 1、0 到 i - 1搜索是否有机器空闲，是就让它负责。最后输出负责了最多工程的机器编号（有重复的就从小到大输出）。

复制代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof (a))
#define ios_sync (std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0))
#define sca scanf
#define pri printf
#define xx first
#define yy second
#define ul u << 1
#define ur u << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 100010, M = 10010;
const int INF = 0x3f3f3f3f, mod = 998244353;
int n, m, k, T;
ll sum[N];
struct pro
{
    int l, r;
    ll mintim;//记录一个区间内所有机器中最早完成任务的时间(即什么时候开始空闲)
} tr[4 * N];

inline void pushup(int u)
{
    tr[u].mintim = min(tr[ul].mintim, tr[ur].mintim);
    //每次修改了某个机器的时间后，会对这个机器在的区间内的mintim产生影响，所以要pushup维护
}

void build(int u, int l, int r)//标准建树
{
    if (l == r)tr[u] = { l, r };
    else
    {
        tr[u] = { l, r };
        int mid = l + r >> 1;
        build(ul, l, mid);
        build(ur, mid + 1, r);
    }
}

bool modify(int u, int l, int r, ll arr, ll pro)//修值返回一个布尔变量，判断是否这个区间内可以找到一台机器处理工程
{
    //arr是工程开始时间，pro是工程持续时间
    if (tr[u].l > r || tr[u].r < l)return false;//超出区间范围的情况

if (tr[u].mintim > arr)return false;//区间内最早完成任务的时间都比工程开始时间晚的话，肯定找不到

if (tr[u].l == tr[u].r)//一旦抵达单点
    {
        tr[u].mintim = arr + pro;
        sum[tr[u].l]++;//单点修改，此点负责数++
        return true;
        //成功匹配
    }
    else
    {
        //用一个||的性质，bool只要满足了其中一个就成功，满足左边就不会执行右边的modiify。每次尽可能往左搜，离 i 更近的机器能完成就让它执行
        if (modify(ul, l, r, arr, pro) || modify(ur, l, r, arr, pro))
        {
            pushup(u);
            return true;//能完成就成功
        }

return false;//否则失败
    }
}

int main()
{
    ios_sync;

cin >> k >> n;
    build(1, 0, k - 1);//符合题意去建树

for (int i = 0; i < n; i++)
    {
        ll arr, pro;
        cin >> arr >> pro;

//同样使用一个||
        if (modify(1, i % k, k - 1, arr, pro) || modify(1, 0, (i - 1) % k, arr, pro));
    }

ll mx = 0;

for (int i = 0; i < k; i++)mx = max(mx, sum[i]);//找到最大工程负责数

for (int i = 0; i < k; i++)//输出
        if (sum[i] == mx)cout << i << ' ';

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof (a))
#define ios_sync (std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0))
#define sca scanf
#define pri printf
#define xx first
#define yy second
#define ul u << 1
#define ur u << 1 | 1
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 100010, M = 10010;
const int INF = 0x3f3f3f3f, mod = 998244353;
int n, m, k, T;
ll sum[N];
struct pro
{
    int l, r;
    ll mintim;//记录一个区间内所有机器中最早完成任务的时间(即什么时候开始空闲)
} tr[4 * N];

inline void pushup(int u)
{
    tr[u].mintim = min(tr[ul].mintim, tr[ur].mintim);
    //每次修改了某个机器的时间后，会对这个机器在的区间内的mintim产生影响，所以要pushup维护
}

void build(int u, int l, int r)//标准建树
{
    if (l == r)tr[u] = { l, r };
    else
    {
        tr[u] = { l, r };
        int mid = l + r >> 1;
        build(ul, l, mid);
        build(ur, mid + 1, r);
    }
}

bool modify(int u, int l, int r, ll arr, ll pro)//修值返回一个布尔变量，判断是否这个区间内可以找到一台机器处理工程
{
    //arr是工程开始时间，pro是工程持续时间
    if (tr[u].l > r || tr[u].r < l)return false;//超出区间范围的情况

    if (tr[u].mintim > arr)return false;//区间内最早完成任务的时间都比工程开始时间晚的话，肯定找不到

    if (tr[u].l == tr[u].r)//一旦抵达单点
    {
        tr[u].mintim = arr + pro;
        sum[tr[u].l]++;//单点修改，此点负责数++
        return true;
        //成功匹配
    }
    else
    {
        //用一个||的性质，bool只要满足了其中一个就成功，满足左边就不会执行右边的modiify。每次尽可能往左搜，离 i 更近的机器能完成就让它执行
        if (modify(ul, l, r, arr, pro) || modify(ur, l, r, arr, pro))
        {
            pushup(u);
            return true;//能完成就成功
        }

        return false;//否则失败
    }
}

int main()
{
    ios_sync;

    cin >> k >> n;
    build(1, 0, k - 1);//符合题意去建树

    for (int i = 0; i < n; i++)
    {
        ll arr, pro;
        cin >> arr >> pro;

        //同样使用一个||
        if (modify(1, i % k, k - 1, arr, pro) || modify(1, 0, (i - 1) % k, arr, pro));
    }

    ll mx = 0;

    for (int i = 0; i < k; i++)mx = max(mx, sum[i]);//找到最大工程负责数

    for (int i = 0; i < k; i++)//输出
        if (sum[i] == mx)cout << i << ' ';

    return 0;
}

Problem B . Convex Polygon

题意：

一道裸的凸包题，没学过（寄），求平面上几个点是否能形成凸多边形，三点及以上不允许共线；若就从最靠近原点的点开始顺时针输出凸包的每一个点的坐标。

复制代码

#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define ios_sync (std::ios::sync_with_stdio(false),cout.tie(0),cin.tie(0))
#define sca scanf
#define pri printf
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 510, M = 1000010;//icpc网络赛 ——— 裸凸包板子题

//题意：给出一系列点，求能否用所有点形成凸包（不能漏），同时要求没有三个及三个以上的点共线，若满足则找到距离原点最近的点然后开始顺时针全部输出

const int INF = 0x3f3f3f3f, B = 1e10;
int n, m, k, T;
struct book
{
    double x, y;
}z[N], stk[N];//标准模拟栈处理凸包
int cnt;

bool cmp(book a, book b) {//根据坐标轴x、y排序
    return a.x != b.x ? a.x < b.x : a.y > b.y;
    //一定不能忘了 x 相同时也要排 y
    //根据题意顺时针还是逆时针存点
    //对应a.y > b.y和a.y < b.y
}

double xmul(book a, book b) {//叉乘：左上*右下-左下*右上
    return a.x * b.y - b.x * a.y;
}

double xl(book a, book b, book p) {//传递叉乘需要的向量
    //A是原凸包末端两点的向量
    //B是加入新点后凸包末端两点的向量
    //顺序不要错
    book A = { b.x - a.x,b.y - a.y };
    book B = { p.x - a.x,p.y - a.y };
    return xmul(A, B);
}

double dist(book a) {//计算点到原点的距离
    return sqrt(a.x * a.x + a.y * a.y);
}

int andrew() {
    sort(z, z + n, cmp);
    //凸包最重要的优化，对点进行坐标排序，把n^2时间复杂度降到nlogn

stk[0] = z[0], stk[1] = z[1];
    cnt = 1;
    for (int i = 2; i < n; i++) {
        while (cnt && xl(stk[cnt - 1], stk[cnt], z[i]) >= 0)
            //叉乘结果大于0代表末向量相对于原向量向上偏移
            //小于0代表末向量相对于原向量向下偏移
            //等于0相当于延长线

//由于这里算的是一个顺时针上凸包，所以加入的点形成的向量应该是逐渐向下偏移，形成向下包裹状凸壳
            cnt--;
        stk[++cnt] = z[i];
    }

stk[++cnt] = z[n - 2];
    //上凸包处理完处理下凸包（还有点没用到呢）
    //加入倒数第一个点形成下凸包的第一个向量

for (int i = n - 3; i >= 0; i--) {
        while (cnt && xl(stk[cnt - 1], stk[cnt], z[i]) >= 0)
            //顺时针相对于倒转过来了，所以也是“向下”偏移，形成向上包裹凸包
            cnt--;
        stk[++cnt] = z[i];
    }
    return cnt;
    //返回凸包用到的点的数量
}

int main() {
    ios_sync;

char a, b;
    while (sca("%lf%c%lf%c", &z[n].x, &a, &z[n].y, &b)) {
        n++;
        if (b == 'n')break;
        //特殊输入，点从0到n-1
    }

int t = andrew();

if (n < 3 || t != n) {//点数小于3肯定不是凸包
        //没用到所有点不满足此题题意
        cout << "ERROR" << endl;
    }
    else {
        //输出题面要求
        int id = 0;
        double d = dist(stk[0]);
        for (int i = 1; i < cnt; i++)//找到最靠近原点的点
            if (dist(stk[i]) < d)
                id = i, d = dist(stk[i]);

cout << stk[id].x << ',' << stk[id].y;
        for (int i = id + 1; i < cnt; i++)//狠狠地跑
            cout << ',' << stk[i].x << ',' << stk[i].y;
        for (int i = 0; i < id; i++)
            cout << ',' << stk[i].x << ',' << stk[i].y;
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define ios_sync (std::ios::sync_with_stdio(false),cout.tie(0),cin.tie(0))
#define sca scanf
#define pri printf
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 510, M = 1000010;//icpc网络赛 ——— 裸凸包板子题

//题意：给出一系列点，求能否用所有点形成凸包（不能漏），同时要求没有三个及三个以上的点共线，若满足则找到距离原点最近的点然后开始顺时针全部输出

const int INF = 0x3f3f3f3f, B = 1e10;
int n, m, k, T;
struct book
{
    double x, y;
}z[N], stk[N];//标准模拟栈处理凸包
int cnt;

bool cmp(book a, book b) {//根据坐标轴x、y排序
    return a.x != b.x ? a.x < b.x : a.y > b.y;
    //一定不能忘了 x 相同时也要排 y
    //根据题意顺时针还是逆时针存点
    //对应a.y > b.y和a.y < b.y
}

double xmul(book a, book b) {//叉乘：左上*右下-左下*右上
    return a.x * b.y - b.x * a.y;
}

double xl(book a, book b, book p) {//传递叉乘需要的向量
    //A是原凸包末端两点的向量
    //B是加入新点后凸包末端两点的向量
    //顺序不要错
    book A = { b.x - a.x,b.y - a.y };
    book B = { p.x - a.x,p.y - a.y };
    return xmul(A, B);
}

double dist(book a) {//计算点到原点的距离
    return sqrt(a.x * a.x + a.y * a.y);
}

int andrew() {
    sort(z, z + n, cmp);
    //凸包最重要的优化，对点进行坐标排序，把n^2时间复杂度降到nlogn

    stk[0] = z[0], stk[1] = z[1];
    cnt = 1;
    for (int i = 2; i < n; i++) {
        while (cnt && xl(stk[cnt - 1], stk[cnt], z[i]) >= 0)
            //叉乘结果大于0代表末向量相对于原向量向上偏移
            //小于0代表末向量相对于原向量向下偏移
            //等于0相当于延长线

            //由于这里算的是一个顺时针上凸包，所以加入的点形成的向量应该是逐渐向下偏移，形成向下包裹状凸壳
            cnt--;
        stk[++cnt] = z[i];
    }

    stk[++cnt] = z[n - 2];
    //上凸包处理完处理下凸包（还有点没用到呢）
    //加入倒数第一个点形成下凸包的第一个向量

    for (int i = n - 3; i >= 0; i--) {
        while (cnt && xl(stk[cnt - 1], stk[cnt], z[i]) >= 0)
            //顺时针相对于倒转过来了，所以也是“向下”偏移，形成向上包裹凸包
            cnt--;
        stk[++cnt] = z[i];
    }
    return cnt;
    //返回凸包用到的点的数量
}

int main() {
    ios_sync;

    char a, b;
    while (sca("%lf%c%lf%c", &z[n].x, &a, &z[n].y, &b)) {
        n++;
        if (b == 'n')break;
        //特殊输入，点从0到n-1
    }

    int t = andrew();

    if (n < 3 || t != n) {//点数小于3肯定不是凸包
        //没用到所有点不满足此题题意
        cout << "ERROR" << endl;
    }
    else {
        //输出题面要求
        int id = 0;
        double d = dist(stk[0]);
        for (int i = 1; i < cnt; i++)//找到最靠近原点的点
            if (dist(stk[i]) < d)
                id = i, d = dist(stk[i]);

        cout << stk[id].x << ',' << stk[id].y;
        for (int i = id + 1; i < cnt; i++)//狠狠地跑
            cout << ',' << stk[i].x << ',' << stk[i].y;
        for (int i = 0; i < id; i++)
            cout << ',' << stk[i].x << ',' << stk[i].y;
    }

    return 0;
}

Problem C . Driver Licenses

题意：

~~大致是（带权）并查集，类似食物链，翻译不能，蒙古~~

实际上是图论题，拓扑然后时间 / 空间处理不能（寄）

Problem D . Edge of Taixuan

题意：

看似是一个并查集（一开始往这方面想了），其实是个线段树区间覆盖问题；n次操作，每次把闭区间 [ l , r ] 每一个点互相之间连一条权值为 W 的边，但最后 只需要留下 n - 1 条边且边的权值累计最小、同时点全连通 即可，同时输出多余的需要去除的边的权值总和。如果n次操作也没能使得点全连通，就输出error

听说这道题理论极限数据会爆longlong，要开int128，但出题人没给这种数据

复制代码

typedef long long ll;
typedef pair<int, int> PII;

const int N = 100010, M = 200010;
const int INF = 0x3f3f3f3f, mod = 998244353;

//思路：根据区间建立线段树，对于每一个闭区间[l,r]，modify去标记对应的区间即可；对所有覆盖操作进行一个贪心排序，优先覆盖权值小的边，不需要重复覆盖，覆盖的操作用类似懒标记下传即可；预处理累计所有操作加边的总权值，总权值减去最后线段树内含有的权值就是需要去除的权值

int n, m, k, T;
ll w[N];//预处理删边累计权值
struct tree
{
    int l, r;
    ll sum, d;//记录覆盖的边权之和与边权
    bool ple;//标记是否覆盖，是否覆盖完全
} tr[N * 4];

struct nod
{
    int l, r;
    ll w;
}node[N];

bool cmp(nod a, nod b)
{
    return a.w < b.w;//贪心，从小到大，覆盖过就停止
}

inline void pd(int u, ll x) {
    if (!tr[u].d) tr[u].d = x;
    //如果没有被标记过，先下放到的肯定是最小的边权
    //被标记过就代表有更小的曾经标记了
}

inline void pushdown(int u) {
    pd(ul, tr[u].d);
    pd(ur, tr[u].d);
}

inline void pushup(int u)
{
    if (!tr[u].ple)tr[u].ple = tr[ul].ple && tr[ur].ple;
    //回传区间是否完全覆盖的信息
    //切记 if (!tr[u].ple) 不然bug调一上午
    //如果该区间已经确定被覆盖了，就没必要根据子区间覆盖的信息去修改
    tr[u].sum = tr[ul].sum + tr[ur].sum;
    //维护树的总权值
}

void build(int u, int l, int r)
{
    tr[u] = { l, r };
    if (l != r)
    {
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
    }
}

void modify(int u, int l, int r, ll d)
{
    if (tr[u].l >= l && tr[u].r <= r)//满足范围
    {
        if (tr[u].d)return;//覆盖过了肯定不需要再覆盖了
        tr[u].ple = 1;
        tr[u].d = d;
    }
    else
    {
        pushdown(u);
        //下传区间覆盖信息
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= l)modify(ul, l, r, d);
        if (mid < r)modify(ur, l, r, d);
        pushup(u);//上升覆盖标记
    }
}

void fin(int u, int l, int r)
{
    //全遍历线段树，把所有能下传的都下传，修改底层点值
    if (tr[u].l == tr[u].r) {
        tr[u].sum = tr[u].d;//再由底层更新sum
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= l)fin(ul, l, r);
        if (mid < r)fin(ur, l, r);
        pushup(u);//维护回tr[1].sum
    }
}

int main()
{
    for (int i = 1; i <= 100005; i++)//预处理总边权值
        w[i] += w[i - 1] + i;
    //区间[1,3]加了(3-1)的累加—— 2 + 1 条边，所以是边权*3

sca("%d", &T);

for (int v = 1; v <= T; v++)
    {
        ll ans = 0;//数据理论上是可以爆longlong的
        //如果ll过不了就要考虑__int128
        sca("%d%d", &n, &m);

mem(tr, 0);
        build(1, 1, n - 1);//重置与重建

for (int i = 0; i < m; i++)
        {
            int a, b;
            ll c;
            sca("%d%d%lld", &a, &b, &c);
            node[i] = { a, b, c };//存下所有操作

ans += w[b - a] * c;//计算总边权
        }

sort(node, node + m, cmp);//贪心

for (int i = 0; i < m; i++)
        {
            int l = node[i].l, r = node[i].r;
            ll d = node[i].w;
            if (!tr[1].ple)modify(1, l, r - 1, d);//因为是区间所以r - 1
            //当判断区间已经覆盖完全，后面就不需要更改了，节省时间
        }

pri("Case #%d: ", v);

//判断是否覆盖完全直接查询tr[1].ple即可
        if (tr[1].ple) {
            fin(1, 1, n - 1);//全遍历树
            pri("%lld", ans - tr[1].sum);
        }
        else pri("Gotta prepare a lesson");

if (v < T)puts("");//小心结尾空格的判定
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define ios_sync (std::ios::sync_with_stdio(false),cout.tie(0),cin.tie(0))
#define sca scanf
#define pri printf
#define fi first
#define se second
#define ul u << 1
#define ur u << 1 | 1
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 100010, M = 200010;
const int INF = 0x3f3f3f3f, mod = 998244353;

//思路：根据区间建立线段树，对于每一个闭区间[l,r]，modify去标记对应的区间即可；对所有覆盖操作进行一个贪心排序，优先覆盖权值小的边，不需要重复覆盖，覆盖的操作用类似懒标记下传即可；预处理累计所有操作加边的总权值，总权值减去最后线段树内含有的权值就是需要去除的权值

int n, m, k, T;
ll w[N];//预处理删边累计权值
struct tree
{
    int l, r;
    ll sum, d;//记录覆盖的边权之和与边权
    bool ple;//标记是否覆盖，是否覆盖完全
} tr[N * 4];

struct nod
{
    int l, r;
    ll w;
}node[N];

bool cmp(nod a, nod b)
{
    return a.w < b.w;//贪心，从小到大，覆盖过就停止
}

inline void pd(int u, ll x) {
    if (!tr[u].d) tr[u].d = x;
    //如果没有被标记过，先下放到的肯定是最小的边权
    //被标记过就代表有更小的曾经标记了
}

inline void pushdown(int u) {
    pd(ul, tr[u].d);
    pd(ur, tr[u].d);
}

inline void pushup(int u)
{
    if (!tr[u].ple)tr[u].ple = tr[ul].ple && tr[ur].ple;
    //回传区间是否完全覆盖的信息
    //切记 if (!tr[u].ple) 不然bug调一上午
    //如果该区间已经确定被覆盖了，就没必要根据子区间覆盖的信息去修改
    tr[u].sum = tr[ul].sum + tr[ur].sum;
    //维护树的总权值
}

void build(int u, int l, int r)
{
    tr[u] = { l, r };
    if (l != r)
    {
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
    }
}

void modify(int u, int l, int r, ll d)
{
    if (tr[u].l >= l && tr[u].r <= r)//满足范围
    {
        if (tr[u].d)return;//覆盖过了肯定不需要再覆盖了
        tr[u].ple = 1;
        tr[u].d = d;
    }
    else
    {
        pushdown(u);
        //下传区间覆盖信息
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= l)modify(ul, l, r, d);
        if (mid < r)modify(ur, l, r, d);
        pushup(u);//上升覆盖标记
    }
}

void fin(int u, int l, int r)
{
    //全遍历线段树，把所有能下传的都下传，修改底层点值
    if (tr[u].l == tr[u].r) {
        tr[u].sum = tr[u].d;//再由底层更新sum
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (mid >= l)fin(ul, l, r);
        if (mid < r)fin(ur, l, r);
        pushup(u);//维护回tr[1].sum
    }
}

int main()
{
    for (int i = 1; i <= 100005; i++)//预处理总边权值
        w[i] += w[i - 1] + i;
    //区间[1,3]加了(3-1)的累加—— 2 + 1 条边，所以是边权*3

    sca("%d", &T);

    for (int v = 1; v <= T; v++)
    {
        ll ans = 0;//数据理论上是可以爆longlong的
        //如果ll过不了就要考虑__int128
        sca("%d%d", &n, &m);

        mem(tr, 0);
        build(1, 1, n - 1);//重置与重建

        for (int i = 0; i < m; i++)
        {
            int a, b;
            ll c;
            sca("%d%d%lld", &a, &b, &c);
            node[i] = { a, b, c };//存下所有操作

            ans += w[b - a] * c;//计算总边权
        }

        sort(node, node + m, cmp);//贪心

        for (int i = 0; i < m; i++)
        {
            int l = node[i].l, r = node[i].r;
            ll d = node[i].w;
            if (!tr[1].ple)modify(1, l, r - 1, d);//因为是区间所以r - 1
            //当判断区间已经覆盖完全，后面就不需要更改了，节省时间
        }

        pri("Case #%d: ", v);

        //判断是否覆盖完全直接查询tr[1].ple即可
        if (tr[1].ple) {
            fin(1, 1, n - 1);//全遍历树
            pri("%lld", ans - tr[1].sum);
        }
        else pri("Gotta prepare a lesson");

        if (v < T)puts("");//小心结尾空格的判定
    }

    return 0;
}

Problem E . Infinite File System

题意：

看似是个Trie树上字符操作，题解说是求dfs序后在树上建线段树，暂且蒙古。（考察树链剖分）

Problem F . Land Overseer （√）

题意：

签到题，简单的距离贪心，画图就能看出来。

Problem G . Longest Prefix Matching

题意：

全场最长的题面，跟网域编码有关，翻译直接大寄！好像是个最长什么什么序列，dp

Problem H . Mesh Analysis

题意：

第二道签到题，比一三难一点，主要是翻译后理解题意。然后会发现输入的部分数据完全没用，只是用来唬人，读懂后就是个简单的对数据分组归类（当时没写出来kora，跑去肝A了，还是要跟着榜做）

Problem I . Neighborhood Search （√）

题意：

第三道签到题，比第一道还不用脑子…就是个读入输出判断。如何评价当时卡了几小时，因为数据数字间有空格，用scanf读会出错（当时想着icpc不至于卡这个吧…然后就寄，虽然最后用 stringstream 无赖过了）

Problem J . Red-Black Paths

题意：

看起来像二分图，翻译不能。

Problem K . Segment Routing

题意：

就是道翻译图论题，题面信息与路由器数据传输有关。

有n个点，每个点有 Di 条出边，每条边对应标上编号1、2、3…

然后是m次询问，每次给出一个起点 Si

接着一个操作数 Li ，之后 Li 个 Rij 整数代表每次从当前点出发使用的边的编号，走过去后新的起点就是脚下的点。一旦有哪次发送数据失败（当前点没有 Rij 编号的边）就输出Packet Loss，否则输出操作完后停留在的点的编号。签到题（x）翻译后签到题（√）
在这里插入图片描述
注意选取一下样例，有些地方有隐藏的空格

复制代码

typedef long long ll;
typedef pair<int, int> PII;

const int N = 100005, M = 200005;
int INF = 0x3f3f3f3f, mod = 998244353;
int n, m, k, T, S;
vector<int> dot[N];

int main()
{
    sca("%d", &T);
    for (int i = 1; i <= T; i ++ ) {
        
        sca("%d%d", &n, &m);
        for (int j = 1; j <= n; j++) {
            int t, g;
            sca("%d", &t);

while (t--)
            {
                sca("%d", &g);
                dot[j].push_back(g);
            }
        }

pri("Case #%d: n", i);//注意空格

while (m--)
        {
            int s, t;
            sca("%d%d", &s, &t);
            while (t--)
            {
                int g;
                sca("%d", &g);

if (dot[s].size() < g) {
                    s = -1;
                    break;
                }

s = dot[s][g - 1];
            }

if (s == -1)pri("Packet Loss");
            else pri("%d", s);

puts("");//其实保守为好，最后一项输出后面不要接换行，看他们题解都是避免这个
        }

for (int i = 1; i <= n; i++)dot[i].clear();
    }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define ios_sync (std::ios::sync_with_stdio(false),cout.tie(0),cin.tie(0))
#define sca scanf
#define pri printf
#define ul u << 1
#define ur u << 1 | 1
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int N = 100005, M = 200005;
int INF = 0x3f3f3f3f, mod = 998244353;
int n, m, k, T, S;
vector<int> dot[N];

int main()
{
    sca("%d", &T);
    for (int i = 1; i <= T; i ++ ) {
        
        sca("%d%d", &n, &m);
        for (int j = 1; j <= n; j++) {
            int t, g;
            sca("%d", &t);

            while (t--)
            {
                sca("%d", &g);
                dot[j].push_back(g);
            }
        }

        pri("Case #%d: n", i);//注意空格

        while (m--)
        {
            int s, t;
            sca("%d%d", &s, &t);
            while (t--)
            {
                int g;
                sca("%d", &g);

                if (dot[s].size() < g) {
                    s = -1;
                    break;
                }

                s = dot[s][g - 1];
            }

            if (s == -1)pri("Packet Loss");
            else pri("%d", s);

            puts("");//其实保守为好，最后一项输出后面不要接换行，看他们题解都是避免这个
        }

        for (int i = 1; i <= n; i++)dot[i].clear();
    }

    return 0;
}