威风镰鼬

题解

/ 注册

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

题解 | #H(n)#

思路数论分块模板，式子res=(res+n/i)的i枚举时会超时，注意到n/i的结果会有连续的一段相等，我们使用数论分块，直接返回每一段的答案。对于常数n，使得式子[ni]=[nj][\frac{n}{i}]=[\frac{n}{j}][in]=[jn]成立的最大的满足的i≤j≤n的j的值为...

C++ 数论分块暴力

2021-11-18

1 333

题解 | #树的距离#

首先感谢TheOnlyMan为我们带来主席树的精彩讲解，但说到底不管在不在线，本题只用普通的线段树就够了。时间空间都更优秀。AC结果：287ms 42300KB 思路先跑一个dfs（因为最近写惯了所以树链剖分没改回来），然后把树拍平去建线段树。我们知道以x为根的子树表示的范围就是[dfn[x...

C++ 树链剖分线段树主席树

2021-11-17

1 506

题解 | #Dropping tests#

思路 01分数规划模板题。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f //#define int long long using namespace std; const int N=1007; const int mod=1e9...

01分数规划二分

2021-11-16

1 379

题解 | #Desert King#

思路分数规划问题。我们可以求得每两个村子的距离和花费，然后列举最大的ans使得∑（costi−ans∗leni）=0\sum （cost_i-ans*len_i）=0 ∑（costi−ans∗leni）=0 我们固定住1号作为根节点，只需要建一棵最小生成树，二分答案即可求出。（每个点都是与最...

最小生成树 MST 分数规划二分

2021-11-16

1 293

题解 | #圆的面积并#

转载一个板子自适应辛普森法乱搞 https://blog.csdn.net/qq_45735851/article/details/115309408 #include<bits/stdc++.h> #define x first #define y second using name...

数学计算几何

2021-11-16

1 420

题解 | #[SDOI2014]旅行#

思路以树链剖分+主席树可解决。要动态开点（不然的话肯定会爆啊）然后就是对每种颜色（宗教）为根的树进行单点修改还有区间查询。注：这道题容易被卡常，我宏定义就写炸了很多次。代码 #include<bits/stdc++.h> #define int long long using ...

主席树动态开点树链剖分

2021-11-12

1 417

题解 | #翻硬币#

思路水题没必要写得像楼上那么复杂吧…… 从左到右出现和目标状态不同的字符和下一个字符改变，这个操作的次数就是答案了，递推复杂度O(n) 代码 #include<bits/stdc++.h> //#define int long long using namespace std; co...

贪心递推

2021-11-06

1 472

题解 | #翻硬币问题#

思路水题，m保证是偶数，那么Alice在剩下没翻硬币个数为奇数时永远也赢不了。只要第一轮没有把硬币全部翻完，那么Bob就可以使坏让没翻的硬币数为奇，也就是说，n和m不相等的情况下，永远是Bob赢。代码 #include<bits/stdc++.h> using namespace...

博弈 ACM C++ 程序设计

2021-11-06

1 382

题解 | #[JSOI2010]连通数#

思路 bitset优化传递闭包模板。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f3f #define int long long using namespace std; const int maxn=2007; bitset<...

字符串 bitset 图论

2021-10-29

1 339

题解 | #骑士#

思路图可能会有多个连通块，整个图最多有一个环。基环树的题目，对每一块找环切断，然后树形dp。环的切断方式有两种，从那条边的起始点出发做两次dp，当前块的答案就加上两次dp结果的较大值。代码 #include<bits/stdc++.h> #define inf 0x3f3f3f...

树形dp 基环树

2021-10-19

1 367