sunny_forever

题解

/ 注册

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

题解 | #[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

题解 | #与众不同#

离散化 + dp + ST 表参考楼上大佬的题解，总结出下面的思路 r[i]：以 i 作为左端点时，其右端点的位置. 则以 i 为起点时，目标序列的最大长度为 r[i] - i + 1 r[i] 具有非减性质，这为二分提供了前提条件对于区间[L,R]，求其内部最长"好序列"...

ST表离散化动态规划

2021-08-12

0 490

题解 | #超级钢琴#

ST 表 + 优先队列 + 前缀和题意给一个长度为 n 的序列，让你从中选 k 个长度在 [L,R] 范围内的区间 (同一个区间不可选多次) 要求：这 k 个区间的区间和相加得到的值应该最大思路 (1):求出前缀和 (2):枚举 i 令其作为区间左边界，则右边界ri可取值 [i+L-...

ST表优先队列前缀和

2021-08-11

1 489

题解 | #[JSOI2008]最大数MAXNUMBER#

线段树或 ST 表法1：线段树 #include <bits/stdc++.h> using namespace std; const int N = 2e5+10; int m,d; struct node{ int l,r; int maxm; }tr[N*...

ST表线段树

2021-08-11

1 489

题解 | #程序自动分析#

并查集 + 离散化思路离散化之后，先执行 op = 1 的，再执行 op = 0 的执行 op = 1 的时：直接合并执行 op = 0 的时：进行判断Code #include <bits/stdc++.h> using namespace std; const int N...

并查集离散化

2021-08-08

0 722

题解 | #[JSOI2008]星球大战STARWAR#

并查集 + 邻接表 + 逆向思维逆向思维: 原题意：共要删除 k 个点，问：每次删除过后，连通块个数是多少？逆向思维：删点 ==> 加点、连边对！没错，变成了加点与连边所以最开始，我们只对 n-k 个点进行合并操作就行，然后枚举每个要删除的点（注意是从后向前枚举）对于每个枚举到...

并查集邻接表

2021-08-07

3 587

题解 | #食物链#

法1：三倍空间，种类并查集类似于：https://ac.nowcoder.com/acm/problem/16591 Code #include <bits/stdc++.h> using namespace std; const int N = 3e5; int fa[N]; ...

并查集

2021-08-06

4 460

题解 | #[USACO 2018 Jan G]MooTube#

并查集思路：对于每次询问，我们找出所有边权 >=k 的边，对于每个找出的边，对其两端的点进行合并操作，最后 v点所在联通块所含的点的数目减一(减去自身) 就是本次询问的答案但因为数据过大，每次询问我们都将所有边权>=k 的边找出来对其两端点进行合并操作的话，会超时而且还会有...

并查集

2021-08-06

1 489

题解 | #[NOIP2010]关押罪犯#

思路 M 对互相仇恨的罪犯，我们按仇恨值从大到小排序，对于每一对互相仇恨的罪犯，我们要设法将他们分配在不同的监狱里，反正不能在同一监狱里如果不可避免的在同一监狱了也就是与我们的策略发生冲突了，那么此时的仇恨值就是答案如果到最后都不曾发生冲突，那么答案是 0，因为此时：任意一对会冲突的罪犯都...

并查集

2021-08-06

2 824