sunny_forever

题解

/ 注册

全部文章 / 题解（共17篇）

题解 | # F Train Wreck#

F 题邻接表 + 优先队列 + 贪心思路 (1) 建树 — 邻接表初始时，只有根节点 (序号0)，遇到 '(' 即入栈时则建立新节点，遇到 ')' 即出栈时，则执行"退后操作" 建立新节点时，新节点的序号为入栈序号，新节点的父亲为 now 结点 now 结点，指当前我...

思维优先队列 dfs 邻接表贪心

2021-09-16

3 584

题解 | #War of Inazuma (Easy Version)#

H 题前置知识假设 A 、B相邻，A 二进制表示中 1 的个数为 x ，B 二进制表示中 1 的个数为 y 那么，y 必为 x+1 或 x-1（x = 0 时，y 只能为 x+1 ）因此，x 和 y 的奇偶性，必不同思路我们令，二进制表示中 1 的个数为偶数的顶点的属性为 ‘0’，反之为 ...

思维位运算

2021-09-15

2 568

题解 | #花神游历各国#

不需要懒标记，区间修改转为单点修改思路已知：0 或 1 开根号后仍是 0 或 1，又因为 1e9 最多开 5 次根号就会变成 1（每个数最多修改 5 次）所以本题的区间修改可以变为单点修改 + 剪枝为什么不会超时？对于查询操作，单次查询时间复杂度为 O(logn)，最多执行 m 次，所...

线段树思维

2021-08-18

1 750

题解 | #[NOIP2011]选择客栈#

思路枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点显然：位置 j < 位置 i...

思维 dp

2021-08-12

2 767

题解 | #选择客栈#

思路枚举右端点 i 当 fee[i] <= p 时，对其有贡献的左端点是：i 左侧所有与 i 同色的点当 fee[i] > p 时，对其有贡献的左端点分为两种： (1) i 左侧，所有与 i 同色的，fee[j] <= p 的 j 点显然：位置 j < 位置 i...

dp 思维

2021-08-12

2 511

题解 | #LCS#

C 题题解思路：构造参考：https://blog.nowcoder.net/n/9efb42ac11a64a5ebcf0d604115df70d Code #include <bits/stdc++.h> using namespace std; string s1,s2,s3...

思维构造

2021-07-28

3 413

题解 | #Inverse Pair#

I 题题解思路题意:通过对 a 中若干个元素加1(每个元素只能加1次)，使得逆序对的数目变少，问逆序对数目最少可变为几因为 a 是 1 到 n 的全排列，即 [1,n] 中每个元素均出现且只出现一次所以我们每次加1操作最多消掉一个逆序对，该逆序对满足 i < j &&...

树状数组思维

2021-07-28

1 694

题解 | #Black and white#

B题题解队友别骂了，别骂了，我不该以为这题是最短路思路为了实现最少花费，需满足：在我们涂完若干个点后，其他的点对总花费不再有贡献（涂黑这些点时不花钱了）我们会发现：最少，我们需要涂黑 n + m - 1 个点，且涂完这些点后所有的行和所有的列会都在一个联通块里面举例如下：不妨令 n...

最小生成树 Kruskal 思维

2021-07-25

11 745

题解 | #Stack#

K题题解法1：构造拓扑关系思路：先假设我们要求的序列 a 为: 1、2、3、...... 、n然后对序列 a 进行题目描述中的单调栈操作，构造出满足所给b[i] 的拓扑关系拓扑关系：在这里指位置间的拓扑关系，比如 pos1 指向 pos2 , 代表 a[pos1] 需大于 a[pos...

拓扑思维模拟

2021-07-21

2 492

题解 | #迷宫2#

思路题意：求让蜥蜴没办法达到终点所必须花费的最小总代价我们通过把特殊的走道转化为墙壁（转换代价为g[i][j] ），来使蜥蜴最终无法到达终点 g[i][j]取不同值的意义：-1代表墙壁，0代表走道，而1到10^9之间的正整数代表特殊的走道。因为 g[i][j] = -1 代表已经是墙壁，故转...

最短路思维

2021-07-11

7 905