Phecda_

未归档

/ 注册

全部文章 / 未归档（共109篇）

ZROI#1000

ZROI#1000 第一印象:啊,数位\(DP\),第一题这么清爽吗(内心\(:mmp\)).不过,这应该可以数位\(DP\)吧...不知道不知道,没想. 冷静思考\(\times 1\):对于线性的好像可以前缀和,因为这玩意儿非常稀疏,判定合法的\(log\)完全可以不管. 冷静思考\(\ti...

数位DP nature enumerate

2019-09-15

0 374

LuoGuP1351联合权值

LuoGuP1351联合权值并不是很难的题目. 你考虑枚举中间点,然后所有与它相连的点都满足形成权值的条件. 所以我们就直接枚举中间点,取权值最大的两个相乘更新答案. 然后统计所有和它相连的点的权值和,每次统计总权值的时候加上(相连的点的权值和-它自身的权值)*它自身的权值即可. #includ...

enumerate 排序

2019-09-11

0 411

CodeForces1165

CodeForces1165A CodeForces1165A 水题,数一数后\(x\)位里的\(1\),注意\(y+1\)位是不是\(1\)就行了. #include <algorithm> #include <iostream> #include <cstdli...

CodeForces

2019-09-11

0 312

LuoGuP3667

LuoGuP3667 这题对我来说难的一批(题意理解错三遍,垃圾翻译,还是英文原题面好) 就是给你\(2n\)个串,要你找一个区间,使得前\(n\)个串的这个区间不能和后\(n\)个串中的区间有任何一个相同,求一个最短长度. 这显然可以二分,不过听取了\(dalao\)的建议,我选择了枚举左端点,二...

hash STL 二分答案

2019-09-10

0 336

ZROI#958

ZROI#958 ZROI#958 这题难吗?难! 考场上得分了吗?没. 为啥不得分?菜! 为啥这么菜?不知道...(知道就不这么菜了) 这题显然可以二分答案. 二分最多连续走过多少相同的边. 然后你可以选择拆点转移,也可以选择直接\(dis_{0/1,i}\)作为状态用最短路转移. 如果你拆点的...

并查集加权并查集二分答案拆点

2019-09-10

0 411

ZROI#957

ZROI#957 ZROI#957 难吗?倒不是很难. 为啥考场上没做出来?菜! 为啥菜?不知道...(知道了就不这么菜了) (灵魂三问.jpg) 那怎么做呢?我们先考虑怎么去找一个好的下标序列. 很简单,贪心即可.那么怎么去找优秀的下标序列呢? 我们发现,贪心得到的下标序列是所有好的序列中字典序...

贪心 nature

2019-09-10

0 394

KMP小结

模板题 \(KMP\)是个其实不是很难的算法吧...虽然我表面上学了好久,但其实只有一下午是在学,一下午就完事儿了. \(KMP\)应该是目前最优秀的单串匹配算法了吧.它的复杂度是\(O(n+m)\).其中,\(n\)为匹配串(即长串)的长度,\(m\)为模式串(即短串)的长度. 看起来确实很猛,我...

KMP

2019-09-08

0 444

LuoGuP2742[模板]二维凸包

LuoGuP2742[模板]二维凸包如你所见,这是二维凸包的模板题. 我用的是水平序的\(Andrew\) 算法,是从毒瘤汝佳那里学的. 先按照水平序对点排序.水平序就是先按照\(x\)坐标排序,相同再排\(y\)坐标. 然后从第一个点开始,构造下凸壳. 具体就是每次比较栈顶元素和当前元素组成的向...

二维凸包计算几何

2019-09-08

0 386

ZROI#999

ZROI#999 很有趣的一道题.本来我是想考虑枚举选几个盒子,但我发现这样并没有对问题有任何简化. 然后就考虑容斥嘛...发现,这个容斥比较简单. 假如令\(f(S)\)为\(S\)集合中的玩具不能选的方案数. 那么答案就是: \[\sum_{s\subseteq T}{(-1)^{|S|}f(S...

容斥原理子集容斥 FMT(高维前缀和)

2019-09-08

0 291

ZROI#997

ZROI#997 这是某场\(CF(Div.3)\)的\(C\)题.我当时是选择了现场码. 因为那场\(CF\)我没打.这个题我当时第一眼就觉得有循环节. 于是就直接考虑循环节,发现它是对的.于是就只需要处理一下细节就好. \(Code:\) #include <algorithm> ...

2019-09-08

0 508