ycyaw

题解

学习笔记(3) 未归档(22) 杂(1) 游记(2)

/ 注册

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

题解 luoguP1772 【[ZJOI2006]物流运输】

模拟赛居然考了这道题，前一天刚看过，结果看了舍不得(不会)做，结果只骗到30pt讲课人：很容易想到最短路+(我靠一点都不容易) 模拟赛后分析，才知道是处理出第i天到第j天都走同一条最短路的花费为然后进行，表示前i天的最小花费转移方程很好想:，预处理要赋值为方程的意思，即在第天改变路线，第天~...

动态规划

2020-10-15

0 620

三角形和线段题解

某集训原题（逃直接枚举5个点check。复杂度，期望得分20分固定三角形，线段两个端点要么都在里面，要么都在外面，要么一里一外。都在里面一定合法，一里一外一定不合法，只要计算都在外面的合法对数。可以发现如果线段两个端点都在三角形外面且不合法的话，一定会穿过三角形的两条边 (没有三点共线）。设...

计算几何

2020-06-07

4 746

题解 luoguP5368 【[PKUSC2018]真实排名】

签到题。分两种情况，一种自己不翻倍，一种翻倍。不翻倍的情况：对于一个数，设不翻倍大于等于它的个数翻倍了还小于它的个数这两者的和为，那么方案为。翻倍的情况：对于一个数，设有个数翻倍后大于等于它（它指的是这个数翻倍后的值，下同），个数大于等于它，个数翻倍后还是小于它，以及这个数翻倍后增长的...

组合数学

2020-01-07

0 608

题解 CF1067A 【Array Without Local Maximums 】

记表示前个数，第个数取，左边一个数是否大于等于这个数（满足条件为，否则为）的方案数。转移时，如果这一位为，枚举这一位的数字，枚举上一位的数字转移。代码如下： for(int j=1;j<=200;j++){//当前位 for(int k=1;k<=200;k++){//上一位...

动态规划

2020-01-07

0 630

题解 luoguP5008 【[yLOI2018] 锦鲤抄】

首先考虑有向无环图怎么做。有一个贪心的想法，按权值从大到小取，那么我们可以发现除了入度为的一定取不到以外，总能安排一种顺序使得我们取到想要取的点。考虑有环的情况：缩点后整张图仍然是一个有向无环图，那么对于一个有入度的强连通分量，发现也能安排一种顺序取完这个强联通分量内所有的点。对于缩完点之后的根...

贪心 tarjan

2020-01-07

0 681

《信息学奥赛一本通提高篇》题解有趣的数列

很好的一道思维题。警告：文字较多，没有耐心者勿入。首先我们命名为奇数位，其余为偶数位。观察题目条件：奇数位与偶数位上的数字都满足从左到右递增，相邻的满足。首先很容易发现，一个偶数位上的数，比它左边的所有偶数位上的数要大，每个偶数位上的数又比它左相邻奇数位上的数要大。这两条信息，我们可以得出，一个...

构造数论卡特兰数

2019-08-31

0 1013

《信息学奥赛一本通提高篇》题解异象石

看到建虚树的做法？？？不会这题要求每一次加减操作都计算答案，那么我们考虑加入一个点的贡献。慢慢分析：首先一个点或者没有点，肯定没有贡献，为0。然后是两个点，随便从一个点开始，走到另一个点再返回，贡献为2 。回忆一下树上两点距离：到的距离到根的距离到根的距离到根的距离 2。(想怎么求怎...

平衡树 LCA 倍增

2019-08-31

0 907

《信息学奥赛一本通提高篇》题解架设电话线

这道题没有那么难的吧咳咳我们开始正题题意简述一下，就是在加权无向图上求出一条从号结点到号结点的路径，使路径上第大的边权尽量小恩，作为一名OIER，我们先看一下题解数据范围好的不大，我们可以跑好多次最短路(逃由于题目求最值，那就二分答案喽我们转化问题：二分，每次判断是否能使到的路径上第大的...

最短路二分

2019-08-31

0 700

题解 NOIP2018D2T3【列队】

传送门题做的好心累。。最后一列维护一个平衡树，每行维护一个动态开点的权值线段树。我们给所有操作过的点一个权值，再用数组，表示值映射的编号，这样是为了在平衡树内有序。考虑一行内经过一系列操作会变成什么样，首先本来是有序的，之后我们删除了一些点，再从行末尾插入了一些点，那么这一行的前半段还是有序...

2019-08-17

0 693

题解【[TJOI2018]教科书般的亵渎】

传送门先算出所需亵渎个数，观察就可以发现，有一个小细节，如果从开始有一段连续的空位，应该把它去掉，因为不会需要多余的亵渎。我们计算每一次亵渎的贡献，第一次亵渎我们认为是在位置。显然第一次的贡献是空位的贡献。之后我们考虑在一个空位上使用亵渎，设空位为，那么有贡献的区间为。贡献为。最后我们减...

2019-08-17

0 867