HerioOvO

分类

BFS(5) CF题解(3) DFS(20) DP(20) LCA(2) Leetcode(1) Nowcoder题解(4) ST(1) Tarjan(1) 二分(4) 二分法(1) 二叉树题目(4) 位运算(2) 前缀和(4) 博弈论(3) 图论(1) 字符串(5) 学习笔记(1) 并查集(2) 快速幂(1) 思维(7) 排序(1) 数状数组(3) 数论(20) 暴力(5) 最短路(5) 未归档(5) 标记处理(1) 栈(1) 概率论(1) 模拟(2) 浮点数(1) 生成树(4) 算法(5) 素数筛(3) 线段树(6) 组合数学(8) 蓝桥杯(1) 计算几何(1) 贪心(26) 递推(3) 题解(3) 高精度(2)

/ 注册

全部文章（共199篇）

P1410 子序列

P1410 子序列思路：看到最大是。就应该想到用写写。根据别人大佬的思路，我再来说说。。。首先我们可以假设为前位以结尾子序列长度为是否满足。但是我们用这一个递推是不能判断另外一个子序列是否满足的，因此我们需要用来表示前位不以结尾长度为的最后一位的最小值(根据贪心越小越有利后面的数)。这样就可以同时...

2020-06-01

1 545

P1939 【模板】矩阵加速（数列）

P1939 【模板】矩阵加速（数列）传送门矩阵加速的难点就在于构造转移矩阵。根据题目的提示显然我们的初始矩阵为假设我们当前矩阵需要求的矩阵为根据递推公式有观察可得即为状态转移矩阵。所以答案为 AC代码： #include<bits/stdc++.h> using na...

2020-05-30

0 672

莫比乌斯反演定理的证明。

莫比乌斯反演定理的证明。初学给自己做个笔记，怕以后忘了。前置知识：莫比乌斯函数的两个性质：（这里证明用不到) 定理：若有定义在上的函数满足关系：，则有：证明：我们只需证上述等式右边等于左边即可。 = （定义) (1) = (分配律) (2) = (的地位是可交...

2020-05-28

1 1100

求前n个数因数和的三种方法。

求前个数因数和的三种方法。纯暴力，对每个数，遍历时间复杂度: #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<string...

2020-05-28

1 601

欧拉函数(学习笔记)

欧拉函数(学习笔记) 欧拉函数：,为的质因数。 . 每种质因数只有一个。性质： 1.当为质数。证明：显然当为质数,显然与互质。 ,当互质。 [特别地：当为奇质数时，] 证明:为积性函数，具体不详细证明。 3.当为质数的次幂。证明：显然的倍数都不与互质，这样的数个数为所以互质的个数为当互质，...

2020-05-28

1 604

F - Crixalis's Equipment(贪心)

F - Crixalis's Equipment(贪心) 题意：给定个物品的体积和能装下该物品的最小剩余容量和背包体积，问能否装下所有物品。思路：贪心，因为要让所有物品能被装下，显然要为较大的留下更大的空间，又因为要使后面的物品也能被装下，腾出更多空间，所以要尽可能地小，因此可以想到贪心的策略是尽...

贪心

2020-05-28

1 554

E. Are You Fired?(贪心&分类）

E. Are You Fired?(贪心&分类）传送门思路：首先要知道，因为假设满足条件，那么也显然满足。接下来对正负进行讨论，，只需对进行判断。如果则输出，反之不成立。 , 因为要满足因为，所以区间右端肯定包含。因此将含的项移到一边：因为所以最终等式为只需让即可。因...

2020-05-27

0 716

P2863 [USACO06JAN]The Cow Prom S(Tarjan)

P2863 [USACO06JAN]The Cow Prom S(Tarjan) 传送门思路：模板题。 ==注意==：不能根据的来判断连通块的大小。举个例子个结点，一条边即显然遍历到2时，此时栈中有两个数，但是.会进入到涂色。但是只会涂一个点，因为它是孤立点。事实上可以有另外一种判断方法，因为...

Tarjan

2020-05-26

0 548

I - Swordfish(最小生成树）

I - Swordfish(最小生成树）题意：给定个点的坐标，求最小生成树。思路：因为最大只有100，用或者都可以。这里重新温习一下两个算法：对所有边排序，每次取最小边，取条边，同时用并查集维护当前图点的集合，如果不在集合里则加入该边。时间复杂度:为边数。用一个数组维护当前子图与所有结...

最小生成树

2020-05-20

1 701

数列分块1(学习）

数列分块1(学习）题目传送门适用范围：区间修改，单点查询。思想：分块操作，将个数作为一组(一块)。每次操作会涉及最多个块和包括左右区间不完整最多个元素。即每次操作的复杂度大约在：根据均值不等式最合适。总复杂度：树状数组做法待补 AC代码： #include<bits/std...

分块

2020-05-18

0 620