__故人__

题解

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

/ 注册

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

快速傅立叶之二来自专栏

分析联系一下基础卷积。，虽然这个不是最基本的卷积形式，但是我们可以通过，令，那么原式变为而是一个常数，所以我们成功的构造了卷积形式。做一次就好了。代码 #include<bits/stdc++.h> using namespace std; int read() ...

2020-09-24

3 602

[HAOI2008]硬币购物来自专栏

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

2020-09-23

4 783

[HNOI2009]最小圈

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

2020-09-23

3 586

[JSOI2016]灯塔

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

2020-09-23

2 674

[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

排列

分析我们对于一个节点考虑，如果有一个点两维都大于，那么这个节点肯定不可能作为结尾。因为考虑一下，如果排列先出现，那么这个两维都是单调不降的，所以不可能转移到，反之，如果先出现，它一定保持不住结尾，最后整个图构成了一个有向无环图，每一个节点可以等概率转移到后置节点。那么一个...

2020-09-21

5 1019

[SDOI2010]古代猪文来自专栏

分析读完题，我们发现就是求。因为是一个素数，那么我们根据欧拉定理。那么我们其实就是求。好像到这里我们没法快速计算组合数了，可以考虑定理，但是并不是一个素数。那么我们先考虑唯一分解，对于的每个素因子，发现最大的素因子才，最后在通过中国剩余定理合并。时间复杂度为。 ...

2020-09-21

1 735

牛客小白月赛28 J 来自专栏

分析其实如果一条边链接了两个颜色不一样的节点，其实这个边根本没有任何意义，因为你从任意方向都不可能进入这条边，那么我们只需要用并查集维护集合数量就可以了。代码 #include<bits/stdc++.h> using namespace std; int read() { ...

2020-09-21

6 624