ycyaw

分类

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

/ 注册

全部文章（共47篇）

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

PKUWC2020 进京记

Day -4，-3，-2，-1 前三天自闭赛，天天拿着的分，又列了一下坑发现自己的确什么都不会我好菜啊。但是看了看往年的题觉得没有模拟赛这么毒瘤于是充满了信心。 Day 0 火车坐了六个小时，前一天的做自闭了，卡了一个多小时最后还被叉了。订正了下题目然后看了部电影。到了后除了报道也没什么事，报道...

2020-01-07

0 1915

CSP-S 2019 退役记

Day -1 上午模拟赛，前两题签到，T3笛卡尔树，没啥思路。不过都写挂惹，我不会也没什么问题吧。（滑稽中午的时候发现某篇以前写的题解被叉了，修了一个中午。随后开始打开知乎...不知不觉一下午过去了（知乎它不香吗）。吃饭前总算订正完了。晚上估计又在颓废？心血来潮打开2018普及T3摆渡车，这不...

2020-01-07

1 797

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

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

构造数论卡特兰数

2019-08-31

0 1013

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

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

平衡树 LCA 倍增

2019-08-31

0 907

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

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

最短路二分

2019-08-31

0 700