- 博客(191)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 Opencv3学习笔记[1]
文章目录打开图片打开图片使用 IplImageIplImageIplImage 类型在控制台输入程序名和要打开图片位置#include<opencv2/opencv.hpp>#include<iostream>#include <string>#include <io.h>using namespace cv;int main(int argc, char** argv) { /* int _access(const char *path
2021-03-11 11:34:48
226
原创 原根
文章目录阶原根我搬我自己借鉴1借鉴2借鉴3阶定义： (a,n)=1(a,n)=1(a,n)=1 使得 at≡1 (mod n)a^t\equiv 1\ (mod\ n)at≡1 (mod n) 的最小的 ttt 成为 aaa 在模 nnn 意义下的阶，记为 ordnaord_naordna性质： 此时 aφ(n)≡1(mod n)a^{\varphi(n)}\equiv1(mod\ n)aφ(n)≡1(mod n) ，于是 ordn
2021-02-01 16:07:40
199
1
原创 S-T Mincut [CodeChef][最小割树][Kruskal]
文章目录题目思路代码题目给定矩阵 ai,ja_{i,j}ai,j ，然后可以让边权+1,求调整后存在一个图满足 ai,ja_{i,j}ai,j 为 i,ji,ji,j 间的最小割问最小代价思路直接从最小割树考虑就变成构造树的问题考虑从大到小加边构造树，如果某个时刻加边后形成圈，那么此时加的边就是最小边，但是圈上边权大的边无法变小，就只能它变大实现就是求出最小割森林后求现在割边和减去给定的代码#include<set>#include<map>#include
2021-01-19 21:32:07
253
原创 星系探索 黑暗爆炸 - 3786[LCT][平衡树]
文章目录题目思路代码题目3e5维护操作：子树加，换父亲、 uuu 到根路径和思路借助欧拉序和平衡树可实现子树平移，具体 uuu 到 vvv 就是将 [inu,outu][in_u,out_u][inu,outu] 接到 invin_vinv 后面到根路径和类似带修改树上第 kkk 大， inuin_uinu 处 +++ outuout_uoutu 处-需要维护欧拉序上子树内多少个 ((( 括号LCT 可用标记永久化代码#include<set> #include
2021-01-17 11:12:17
130
原创 ELCA[CF482E][LCT]
文章目录题目思路题目思路维护 ∑au∗(sizu2−∑sizv2)\sum a_u*(siz^2_u-\sum siz^2_v)∑au∗(sizu2−∑sizv2)主要是写法，注意 LCTLCTLCT 的真实形式是：两个儿子地位不等价那么一些信息 MakerootMakerootMakeroot 后就会变得不可合并（因为需要更新全部儿子的答案）然后需要更改 linklinklink 和 cutcutcut 的写法（因为此题节点操作时候都为根）siz[x]表示x的虚子树大小(包括x)
2021-01-09 12:03:30
157
原创 Set Merging[CF1375H][分块+权值线段树]
文章目录题目思路代码题目Luogu思路n≤4096n\le 4096n≤4096发现对于合并时候权值限制比较强然后放在值域上搞，那么合并相当于值域上分两边选合起来那么原序列[al,..,ar][a_l,..,a_r][al,..,ar] 在值域上是离散的，但是没关系，我们可以分块 BBB 那么块和块之间直接相连时间复杂度 O(qnBlogn)O(\frac{qn}{B}logn)O(Bqnlogn)我们尝试处理出 fi,l,rf_{i,l,r}fi,l,r 表示第 iii 块内位
2021-01-02 20:37:43
156
原创 函数调用[拓扑排序]
文章目录题目思路代码题目思路考场上思考时候怎么也无法合并，下来发现如果是 a∗b+a∗c∗da*b+a*c*da∗b+a∗c∗d 可以合并为 a∗(b+d∗d)a*(b+d*d)a∗(b+d∗d) ，也就是可以维护系数或者说执行次数首先来看看这个例子：首先要倒着来那么就应该是：+5∗2+5*2+5∗2假设 333 函数执行次数是 333然后经历了 222 函数变成 ∗2*2∗2那么相当于 111 执行 666 次数发现一个 111 的贡献为 a∗sufmula*sufmula∗s
2020-12-03 08:30:21
246
原创 six[Dp]
我是个 SBSBSB ，TMTMTM 嵌套写反了好的，O(n+m23m)O(\sqrt n+m^23^m)O(n+m23m) 吊打出题人#include<set>#include<map>#include<stack>#include<queue>#include<vector>#include<cmath>#include<cstring>#include<cstdio>#include.
2020-12-02 19:37:59
159
原创 parentrises[Balkan OI 2018][Dp][括号]
题目思路结论： 对于一个串 SSS 如果有：对任意前缀ppp: ))) 个数 ≤\le≤ 2 ((( 个数对任意后缀qqq: ((( 个数 ≤\le≤ 2 ))) 个数那么这个串就是合法的本质上是考虑模拟弹栈的过程如果有 ((∣))))((|))))((∣))))显然右括号太多可以变成两种颜色为什么此时不考虑左括号太多？因为此时是后缀判断了然后 fi,j,kf_{i,j,k}fi,j,k 前 iii 个放了 jjj 个左括号最小为 kkk 的方案数时间复杂度： O(n3)O
2020-12-02 19:20:51
150
原创 二分图染色[容斥]
文章目录题目思路代码题目思路首先，我还是不会容斥，然后这道题爆0了思路：可以看成可以转化为棋盘染色问题相当于每一行/每一列同一种颜色只能放一个，并且格子颜色不能重复然后考虑只有一种颜色的答案显然为：fn=∑i=0n(ni)2i!f_n=\sum_{i=0}^n \binom{n}{i}^2i!fn=i=0∑n(in)2i!然后由于有两个颜色会算重，重复的时候就是重点，那么此时可以看作一种混合色然后就可以容斥了：总的方案数相当于：随便放-钦定重复一个+钦定重复两个-…也就是：
2020-12-02 18:43:21
141
原创 Dynamic Diameter[CEOI2019][欧拉序]
文章目录题目思路代码Luogu题目思路借鉴这位大佬的：返回主页liouzhou_101由于一段连续欧拉序一定是一个连通块，那么区间合并相当于两个连通块相交合并，根据直径性质可知一定是原来端点中的两个然后根据dis(u,v)=depu+depv−2∗deplca=depu+depv−mineu≤i≤evdepidis(u,v)=dep_u+dep_v-2*dep_{lca}=\\dep_u+dep_v-min_{e_u\le i\le e_v}dep_idis(u,v)=depu+depv
2020-12-01 20:18:36
211
原创 Solitaire[ARC068D][Dp+思维]
文章目录题目思路代码题目n≤2000n\le 2000n≤2000思路首先队列里面一定是这个样子：然后我们取完前 kkk 个：发现此时相当于取两个序列然后满足其中一个最小值大于剩下数中最大值然后发现 红色序列固定后显然剩下蓝色序列取法固定假设前面 kkk个取法算出来了，剩下数的方案显然为：2n−k−12^{n-k-1}2n−k−1设 fi,jf_{i,j}fi,j 表示确定最终序列前 iii 个，红色序列最小值为 jjj 的方案数首先假设此时取出 xxx假设 xxx 在红的里面
2020-11-29 20:20:53
159
原创 Hall定理
设二部图两集合分别为 X,YX,YX,Y (∣X∣≤∣Y∣|X|\le|Y|∣X∣≤∣Y∣)若任意 W∈XW\in XW∈X 有 ∣W∣≤∣N(W)∣|W|\le |N(W)|∣W∣≤∣N(W)∣那么二部图存在X部匹配完的方案二分图的最大匹配数：∣X∣−maxW∈S(∣W∣−∣N(W)∣)|X|-max_{W\in S}(|W|-|N(W)|)∣X∣−maxW∈S(∣W∣−∣N(W)∣)...
2020-11-27 20:35:33
325
原创 最小乘积生成树[BalkanOI2011][最小生成树]
文章目录题目思路代码题目思路然后就是求下凸壳上 xyxyxy 最小值抄的代码#include<set>#include<map>#include<cmath>#include<deque>#include<stack>#include<ctime>#include<queue>#include<vector>#include<cstdio>#include<
2020-11-27 20:13:07
277
原创 道路费用[APIO2013][最小生成树]
文章目录题目思路代码题目Luogu题目大意：nnn 个点 mmm 条边无向连通图，有些边是你的可以收费，建立最小生成树方式你定，问最大获利k≤20k\le 20k≤20思路由于收费边集很小首先把所有收费边加入集合建立最小生成树，去掉收费边剩下构成了 k+1k+1k+1 个连通块，进行缩点，然后枚举收费边集跑 KruskalKruskalKruskal ,那么对于一条边的最大收费可以利用破圈思想进行取 minminmin 更新，这里由于点很少，暴力爬链时间复杂度 O(mlogm+2kk2)O
2020-11-27 19:35:50
215
原创 Two Trees[AGC018F][欧拉回路][构造]
文章目录题目思路代码题目Luogu思路对于一个点的儿子所在子树都是 +1/−1+1/-1+1/−1 那么猜测当 uuu 向下度数为奇数 valu=0val_u=0valu=0 为偶数 valu=±1val_u=\pm1valu=±1当点在两棵树奇偶性不同时候显然不合法(uuu点奇偶性不匹配)除此之外尝试构造方案然后向下度数为偶数点相互连接，然后根节点之间再连接然后跑欧拉回路，根据相同点之间边的决定权值尝试证明为什么是对的首先所有点度数为偶数，一定能构造欧拉回路然后对于一个子树内部
2020-11-25 20:27:13
219
原创 Snuke Line[ARC068C][分块][主席树][BIT]
文章目录题目思路法一法二法三题目Luogu思路法一首先 O(nm)O(nm)O(nm) 检验 li≤kd≤ril_i\le kd\le r_ili≤kd≤ri意味着检验⌈lik⌉≤d≤⌊rik⌋\lceil\frac{l_i}{k}\rceil\le d\le \lfloor \frac{r_i}{k}\rfloor⌈kli⌉≤d≤⌊kri⌋此时发现右边可以数论分块，对于 k∈[l,r]k\in[l,r]k∈[l,r] 一段相同的右边值显然 kkk 取 rrr 最优 for
2020-11-22 20:42:03
149
原创 Favorite Colors G[USACO20OPEN][并查集][启发式合并]
文章目录题目思路代码题目注意是都仰慕一头喜欢颜色 c 的奶牛，奶牛不一定相同思路发现其实就是一个模拟。。。首先每个点看成一个集合，然后发现出度 ≥2\ge2≥2 就加入队列队列里面元素 uuu 代表儿子们需要合并，并且只保留一条边然后出边继承可用启发式合并所以一条边最多继承 logloglog 次时间复杂度 O(nlogm)O(nlogm)O(nlogm)代码#include<set> #include<map> #include<st
2020-11-20 17:22:01
205
原创 Borrow[hdu-6829][期望dp][公式推导]
文章目录题目思路代码题目思路首先说一说我考场思路f(x,y)f(x,y)f(x,y) 最小值为 xxx，次小值为 yyy 到终点期望步数然后有：f(x,y)=12(f(trans1)+f(trans2))+1f(x,y)=\frac{1}{2}(f(trans1)+f(trans2))+1f(x,y)=21(f(trans1)+f(trans2))+1然后高斯消元求解可得 40opt40opt40opt正解状态设置比较神仙，可能这类题目能比较套路地可以转化成组合数问题？然后起始状
2020-11-18 21:31:21
172
原创 Mr. Kitayuta vs. Bamboos[二分+贪心][图像分析]
文章目录题目思路代码题目思路首先最大值最小考虑二分，假设我们检验 xxx但是发现检验比较难写尝试从图像分析那么画出来图像大致如下：然后我们发现可以将图像上移末端重合至 (m,x)(m,x)(m,x) 点那么只需要倒推改成每天减小 aia_iai 高度，每天有 kkk 次机会增加 ppp，保证初始高度大于hih_ihi 即可然后首先可以想到一个类似堆的做法，每次要死了就加，没来得及加的机会存下来最后调整高度时间复杂度 O(mklognlogA)O(mklog nlogA)O(
2020-11-18 21:04:01
146
原创 大佬[AHOI2017/HNOI2017][搜索][Dp][综合]
文章目录题目思路题目Luogu并且生命上限为 mcmcmc ，最多怼大佬两次思路思路倒是都想到了,但是实现…首先发现我死不死和大佬死不死是两个步骤fi,jf_{i,j}fi,j 前 iii 个选 jjj 个最大生命然后可以处理出剩余天数然后由于 (f,t)(f,t)(f,t) 二元组比较小，考虑爆搜但是要注意存储什么，如果 (f,t,l)(f,t,l)(f,t,l) 都存会多出许多无用状态，并且 (f,t)(f,t)(f,t) 当 ttt 较大时可能后面有用（levellevelle
2020-11-17 22:34:59
185
原创 Equilateral Triangles P[USACO20FEB][切比雪夫距离]
文章目录题目思路代码题目Luogu给定一些点坐标计算曼哈顿意义下等边三角形个数n≤400n\le 400n≤400思路转化成切比雪夫距离转化后面积会扩大 2\sqrt22 倍然后发现一个边框绕着另外一个边框平移必定经过和它同行同列的点然后枚举两次计算即可注意角上的点会被算两次反转的的时候原来不能直接反转原坐标的点…代码#include<set> #include<map> #include<stack> #inc
2020-11-17 09:20:16
128
原创 Connecting Cities[AT4569][最小生成树优化]
文章目录题目思路代码题目Luogu思路假设所有 AiA_iAi 不同，那么一条边肯定是 AAA 一边小，一边大假设 j<i,Aj<Aij<i,A_j<A_ij<i,Aj<Ai 并且此时 jjj 是 iii 在左边值比 AiA_iAi 小的最小边尝试证明只用保留这种边 O(n)O(n)O(n)当存在 kkk 满足 Ak>AiA_k>A_iAk>Ai 我们认为此时是 iii 的选择方式，和 kkk 无关当 i<ki<
2020-11-15 20:19:06
189
原创 诗人小G[决策单调性][四边形不等式优化][单调栈]
文章目录题目思路代码题目Luogu决策单调性二分思路fi=min(fj+cal(i,j))f_i=min(f_j+cal(i,j))fi=min(fj+cal(i,j))然后 calcalcal 有决策单调性，单调栈实现代码#include<set>#include<map>#include<stack>#include<queue>#include<vector>#include<cmath>#incl
2020-11-05 17:46:43
118
原创 Number of Multisets[ARC107D][Dp][思维题]
文章目录题目思路题目给你一个数 kkk ，用集合大小为 nnn 的可重集凑出 kkk ，每个数是形如 12i\frac{1}{2^i}2i1 的形式，问方案数思路绝了由于放数的种类很多难以计算我们操作分为两类：放 111 和整体除以 222fi,jf_{i,j}fi,j iii 个数凑出 jjj 的方案数转移就很显然了:fi,j=fi−1,j−1+fi,2jf_{i,j}=f_{i-1,j-1}+f_{i,2j}fi,j=fi−1,j−1+fi,2j以后可以多思考操作如何表示更
2020-11-03 22:57:40
297
原创 Shuffling[AGC065F][Dp][代码实现]
文章目录题目思路/实现过程代码题目Luogu思路/实现过程首先可以发现包含关系显然可以去掉很容易想到一个类似 fi,jf_{i,j}fi,j 前 iii 个，(iii 到 i+1i+1i+1 有 jjj 个 111) 之类的 dpdpdp 定义但是发现不好打，而且思路比较混乱我们可以将操作区间处理成前缀做差具体而言 nxtnxtnxt 表示添加了一个 [nxti−1+1,nxti][nxt_{i-1}+1,nxt_i][nxti−1+1,nxti] 的操作区间然后我们定义 dpd
2020-11-02 17:21:12
116
原创 Rotated Palindromes [ARC064D][容斥][dp]
文章目录题目思路题目Luogu思路首先发现移位后变成两个回文串拼起来了然后发现没有什么用，因为很容易算重复我们暂时不考虑移位来看的话，很容易写出fi=k⌈i/2⌉−∑j∣ifjf_i=k^{\lceil i/2\rceil}-\sum_{j|i}f_jfi=k⌈i/2⌉−∑j∣ifjfif_ifi 表示最小循环节为 iii 回文串的方案数然后考虑移位,发现奇数长度会算 lenlenlen 次，偶数是 len/2len/2len/2 次然后就做完了...
2020-11-02 15:49:46
128
原创 The Hidden Pair (Hard Version)[Div2651F][交互题]
文章目录题目思路代码题目Luogu思路首先问所有点，问出这条路径长度和其中一个点然后再二分问出较深的端点最后在问出另外一个点次数=2+⌈log2(500)⌉=11次数=2+\lceil log_2(500)\rceil=11次数=2+⌈log2(500)⌉=11flushflushflush 函数：清空缓冲区用于交互代码#include<set>#include<map>#include<stack>#include<queue>
2020-10-31 16:55:05
129
原创 Simple Subsequence Problem[AGC024F][Dp][序列自动机]
文章目录题目思路代码题目Luogu思路如何有效判断 TTT 是 SSS 的子序列？我们可以建立出 SSS 的序列自动机然后用 TTT 跑，如果是非空节点即可注意序列自动机中定义:transu,c：trans_{u,c}：transu,c： uuu 后面第一个 ccc 的位置毫无疑问，这样我们匹配出的 TTT 在 SSS 中是第一个注意到是 010101 串，意味着我们可以预处理出所有 nxtnxtnxt但是 010101 和 001001001 是有区别的，实现的时候每个数最高位+
2020-10-27 13:29:50
112
原创 Monochrome Cat[ARC097D/F][思维题]
文章目录题目思路代码题目Atcoder思路最后差一点首先发现黑色连通块显然不用去，删掉然后所有叶子都是白色了发现可以选择一条链走一次，剩下边都是两次假设没有这条链 走完所有点 nnn 会花费 2∗(n−1)+白点2*(n-1)+白点2∗(n−1)+白点 的代价此时白点是往返后仍然为白点的点再考虑链的情况选择一段往返，那么会使得[起点+中间点]变色白色变为黑色，少走一次+少按一下，代价-2黑色变白色，少走一次但会多按一下那么找覆盖最多白点的链即可总代价：2(n−1)−2∗w2
2020-10-26 15:39:39
121
原创 Gachapon[AGC038E][MinMax容斥]
文章目录题目思路代码题目Luogu思路之前 TTT 神用生成函数讲过，可惜不会了。。。记录 iii 达成条件时间为 sis_isi,抽中概率为 aia_iai，集合为 SSS也就是求 E(max(S))E(max(S))E(max(S))那么容斥可得E(max(S))=∑T⊆S,T≠ϕ(−1)∣T∣−1E(min(T))E(max(S))=\sum_{T\subseteq S,T\not=\phi}(-1)^{|T|-1}E(min(T))E(max(S))=T⊆S,T=ϕ∑(
2020-10-25 09:41:55
290
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人