林思艺

题解

日常(1)

/ 注册

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

[SCOI2016]萌萌哒

题意在某些区间必须一样的情况下，可以组成多少个大数。思路将询问区间拆分成若干个小区间，将区间与区间合并，最后计算答案时将区间的信息下放到点上。具体的来讲：表示左端点为位置，长度为的区间所在集合的根的左端点。最终计算答案时，将所有层的对应端点合并即可，做法是将每层和他的上层合...

2020-11-28

7 848

Smile House

题意给你个点，条边的无向图，但一条无向边的两个方向的边权不同，求图上最小正环的大小。分析考虑转移式，设表示走了不超过条边，从到的最大边权(走不通为极小值)。那么转移为：在我们计算答案时，我们考虑使用倍增。先尝试走了不超过条边从走到了的最小边权和, 从大...

2020-11-26

3 671

[SCOI2015]国旗计划

题意给你一个环，有个区间,区间之间互相不覆盖。求当任意一个区间必须选择时，最少需要多少个区间能够覆盖整个环。思路对于一个战士，如果选了他，那么下一个战士一定是所有左端点小于等于的右端点的战士中最大的一个战士，因为这样子才是是最优的。所以我们只需要预处理加二分找到下一个战士就好了...

2020-11-26

6 865

A and B and Lecture Rooms

题意题目的意思就是每次询问点x，y，要你求其中离它们距离一样的点有多少个。分析我们可以先找到这两个点的，然后路径的中点肯定是一个解（没有就无解咯）。然后从这个点不经过这条路径任意一点能到达的点，就是其他解。求法的话，比较两个询问节点的深度深度相同：深度不同：代码 #inclu...

2020-11-25

2 771

疫情控制

题意给你一棵有个节点的树，要求在所有叶子节点到根节点的路径上有一个节点是特殊的（军队）。问如果要封死这棵树，移动距离最大的点移动的最小距离是多少？分析这题挺恼火的，一步一步慢慢来首先：树上倍增先预处理用存储节点的第个祖先的节点编号，存储节点到它的第个祖先的路径长度。在...

2020-11-25

9 998

[AHOI2008]MEET 紧急集合

题意 PS:（最近好多题题意都好难懂啊QAQ）给你一棵个节点的树，有次询问，每个询问给你三个节点，求树上一个节点使得这三个点到的距离之和最小。每次询问输出这个节点的编号以及路径之和。分析考虑每两个节点之间的最短距离就是求这两个点的，那么三个点我们可以先两两一组找到。我们可以发现...

2020-11-25

8 1039

Network

题意一个无向图可以有重边，下面个操作，每次在两个点间连接一条有向边，每次连接后整个无向图还剩下多少桥（注意是要考虑之前连了的边，每次回答是在上一次的基础之上）分析求出桥来之后缩点，缩点运用并查集实现，每一个点组用父亲节点代表。emm，好像就这样。 PS: 虽说楼上大佬说并查集实现更快，但我...

2020-11-20

5 784

Tree with Small Distances

题意你有一颗个节点的有根树(以号节点为根)，求最少加入多少条边之后使得根节点（即号节点）到这棵树上任意一点的距离不大于。分析考虑一种贪心，如果一个节点到根的距离大于的话，那么我们就从根节点连一条边到节点的父亲。来考虑正确性的证明，一个节点到根的距离如果大于了 ...

2020-11-18

6 974

Bookshelves

题意你有本书，每本书有一个权值 .你要将这本书分到个书架上，要求你分组之后的每组权值之和的按位与的值最大。思路位运算啊，按位考虑。贪心的从高位到低位的使得此位值为。我们就可以枚举最后的答案，从大到小，然后依次一下。我们设计方程：。表示在前个分为了组是否成立，最...

2020-11-16

6 1013

Propagating tree

题意给你一棵个结点的树, 以为根。每个结点有点权。有次操作：结点权值，的儿子权值，的孙子们，以此类推。询问的点权；思路又是单点查询，看看树状数组吧。区间修改就可以用差分。但是第一个操作有些麻烦，但这和每个节点的深度奇偶有关。所以只需判断一下深度，决定修改的值...

2020-11-10

6 704