__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 847人学习

22篇文章 1707人学习

全部文章（共169篇）

[HAOI2008]硬币购物来自专栏

分析背包题。因为朴素的的时间复杂度为应该过不去。那么换种思路，先考虑没有个数限制，令为考虑前种物品，体积为时，总的方案数。发现我们对个数的限制可以考虑子集容斥。考虑到，恰好选个的方案数是等于至少选个的方案数减去至少选的方案数。那么现在是让我们求恰好选到个...

2020-09-23

4 783

POJ - 2976

分析找来的分数规划模板题。我们要求的是，所以直接二分，那么贪心的选取最大的个，最后再判断就好了。代码 // #include<bits/stdc++.h> #include<iostream> #include<cstdio> #inc...

2020-09-23

3 550

[HNOI2009]最小圈

分析说句人话，题目的意思是要我们求这个，这个类似分数规划的式子，先钦定答案，那么满足，通分移项，那么二分，而新图边权为当图中出现负环时，那么这个是一个可行的。但是判负环的时间复杂度较高，加上二分可能会超时，所以当我们入队超过一个常数。虽然正确性出现了问题，但是...

2020-09-23

3 586

[JSOI2016]灯塔

分析读完题，我们发现为了满足所有节点。通过不等式变形。那么我们就有了的做法，是过不了的，所以必须优化，我们现在为了去掉绝对值符号，所以考虑从左到右和从右到左分别进行一次转移。令。那么，根据的函数图像非常容易得到那么满足这个式子的，我们直接通过决策单调性优化就好了，时间复杂度...

2020-09-23

2 674

原根来自专栏

原根这个的用处还是非常大的在模意义下的乘法可以通过原根转换为加法。 NTT 需要原根。定义，且。则称是的一个原根。是否有原根只有，其中为奇素数，为正整数。计算最小原根这里直接使用最常见的作法。由小到大枚举。。那么只需要判断就可以了，如果有一个...

2020-09-23

1 782

rmq 问题一种 O(n) 预处理，O(1) 回答询问的方法

引入现在市面上大多数解决问题的一般是预处理，回答的线段树，平衡树。预处理，回答的表，猫树。预处理，回答的分块加表，这种神仙算法。这里考虑使用的预处理，回答的算法，这里用求区间最大举例。 Cartesian-tree 对于笛卡尔树，我们可以...

2020-09-22

2 0

HDU - 1506

分析去专门学了笛卡尔树，找了一道模板题来做。由于我们建立的笛卡尔树满足小根堆性质，因此的子树内的结点的高度都大于等于。而我们又知道子树内的下标是一段连续的区间。所以。通过单调栈构建笛卡尔树，时间复杂度为。代码 #include<bits/stdc++.h> usi...

2020-09-22

2 592

[AHOI2009]MINCUT 最小割

分析主要考察最小割的性质。我们发现如果一条边是可行边，那么一定要满足以下性质。满流，没有第二条增广路。考虑证明，如果没有满流，那么我们完全没必要割去这条边。如果有，那么证明这个路径还可以继续增广，不满足最小割的定义。那么如果一条边是必须边。满流，直接链接所在集合。这里考虑最小割的定义...

2020-09-22

2 0

最后的晚餐(dinner) 来自专栏

分析一眼的数学题。因为原问题并不好做，按照正难则反，我们先考虑容斥。定义表示至少有对情侣坐在了一起。那么。为容斥系数。考虑单独的如何求解。那么我们发现这是在求一个圆排列，根据元素构成的圆排列方式为。所以。表示个有标号的元素的圆排列方式。最后。注意一下空间...

2020-09-22

4 1245

超能粒子炮 · 改来自专栏

分析如果我们读完题发现我们要求的是这个，定义一个二元组，根据定理，可以推导到在一波无情的推式子之后，这道题就做完了。代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL rea...

2020-09-22

4 754