gyh20

分类

题解(5)

/ 注册

全部文章（共5篇）

题解 B 七彩线段

状态压缩DP。先将所有位置离散化，然后在每一个的 vector 中插入和，当枚举到时，可以从转移而来，令当前状态为，则，其中表示离散化后某个位置代表的真实位置。时间复杂度 #include<bits/stdc++.h> #define re //regis...

2020-07-28

2 698

题解 E 我不爱她

我用的是一个 hash+KMP 的做法。首先，先把所有后缀的 hash 值记录下来，存入 map 中。然后查询每一个前缀，求出 hash 值相同的后缀数量乘上长度的和即为答案。但有些情况会算重复，比如 ababa 中 a 的答案在 aba 处被多算了,aba 的答案在 ababa 的地方被多算...

2020-07-28

3 719

题解 D 刺客信条

很明显是一道最短路的题，可以用迪杰斯特拉算法求解。可以把每一个点拆成入点和出点，入点向出点连点权的边。从 S 的出点开始跑最短路，求出到 T 的入点的最短路即可。 #include<bits/stdc++.h> #define re using namespace std; inl...

2020-07-28

1 817

题解 C 成绩分析

由于原数列已有序，可直接在中间找中位数，平均数即为所有数的和除以。当为偶数时，要取和的平均值。这里的平均数和中位数在为偶数时可能不为整数，需要特殊处理一下。 #include<bits/stdc++.h> #define re register using name...

2020-07-28

1 626

题解 A 生成树

由于要求边完全相同，所以在 A 中存在的边但 B 中不存在的一定会被删掉，其它边保留，连边就连 B 中剩下没连的。所以，只用统计 A 中出现过的但 B 中没有出现过的边，对于一条边，如果交换，然后查询数对是否出现过即可。用一个 map 维护。 #include<bits/stdc+...

2020-07-28

1 636