博文

字符串读入的一点点细节

 fgets(s, sizeof(s), stdin): 一直读入到换行,换行符会读入到字符串中 因为最后有个'\0'占位,所以只能读sizeof(s)-1个字符(包括换行) cin.getline(s, sizeof(s), '\n'): 一直读入到第三个参数指定的字符(可以省略,默认为换行),指定的终止字符会被吞掉 因为最后有个'\0'占位,所以只能读sizeof(s)-1个字符(虽然终止字符被吞掉了,但也算在里面) 当sizeof(s)-1不够读取完到终止字符的所有字符时会产生failbit,搞得自己和cin之类也不能用,需要cin.clear之后才可以正常读取。不过scanf和fgets之类又可以正常用,搞不懂为什么了,以后再慢慢研究吧…… 还有用scanf("%[^\n]", s)也能读整行,不过换行符得自己单独处理 还有个就是整行读取读win造的数据时因为换行符是'\r\n',所以会多读一个'\r',有时得单独处理下(虽然好像都知道,但还是写个免得自己忘了吧 总结:用getline(cin, s)

部分复活

活了, 但没完全活 好像已经AFO快一年了,我一直感觉才大半年来着,时间过得真**快 打ABC都已经手速和脑子双掉线了,完蛋了完蛋了,没学上了 之后一段时间估计都靠着ABC来复健吧(逃 2022.1.30

AFO

2021.2.6  AFO

长链剖分

  https://www.cnblogs.com/cjyyb/p/9479258.html O(nlogn)-O(1)求k级祖先: https://zhuanlan.zhihu.com/p/25984772

五边形数定理

$$ \prod_{i = 1}(1 - x^i) = \sum_{i = 0} (-1)^i x^{i * (3 * i \pm 1) \over 2} $$

DDP及全局平衡二叉树

https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p4643

XJ3531 【毒奶】题解

灰常暴力美学的一道题

广义后缀自动机

https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139

洛谷P4383 【[八省联考2018]林克卡特树】题解

https://www.luogu.com.cn/blog/EternalAlexander/solution-p4383 凸函数的证明: https://www.luogu.com.cn/blog/zyc2003/p4383-lin-ke-ka-te-shu-post

关于三模数NTT

 把mod改成const效果是真的好 之前的板子为了偷懒直接是一个mod然后一直换值,和const比起来常数是真的大

AGC047F 【Rooks】题解

  https://www.youtube.com/watch?v=SN0dyP2kJgo&t=22m

CF1142E 【Pink Floyd】题解

https://www.luogu.com.cn/blog/105254/solution-cf1142e

CF1179E 【Alesya and Discrete Math】题解

https://blog.csdn.net/qq_35950004/article/details/106505535 https://www.cnblogs.com/xzz_233/p/11070827.html

NOIP2020退役记

 考场不能吃东西差评

某种基于SPFA的复杂度并不正确但跑的飞快的求图上单个点的多个不同走法要求的最短路且各种走法相互关联的算法既CF553E 【Kyoya and Train】题解

不要问我为什么标题这么奇怪,我也不知道我在写什么( 做CF题的时候碰到的

LOJ6070 【2017 山东一轮集训 Day4」基因】题解

发现自己变菜了,回来补个档

字符串border及最小回文分解

 发现自己忘的差不多了,当时又没写博客,回来补个档

LOJ6065 【「2017 山东一轮集训 Day3」第一题】题解

 显然正方形的构成是1+1+1+3或1+1+2+2,然后瞎搞就行 细节有点容易写挂

Hall定理的推论

https://www.cnblogs.com/cly-none/p/Hall_Theorem.html

类欧几里得

https://oi-wiki.org/math/euclidean/

阶与原根

https://www.luogu.com.cn/blog/codecodeakioi/solution-p6091

CSP-S2020退役记

开头亲切的问候一个人的全家,这个人是谁不用说了吧(

二项式反演

https://www.cnblogs.com/GXZlegend/p/11407185.html

CF516E 【Drazil and His Happy Friends】题解

https://www.luogu.com.cn/blog/PinkRabbit/solution-cf516e https://www.luogu.com.cn/blog/xht37/solution-cf516e

最小生成树Boruvka算法

https://luckyglass.github.io/2019/19Oct31stArt1/

KDTree时间复杂度

 发现自己忘了,mark一波 最近点:O(能过) 矩形搜索:O(k*n^(1-1/k))

LOJ2978 【「THUSCH 2017」杜老师】题解

见20200804讲课课件及 https://blog.csdn.net/qq_42555009/article/details/98353445

LOJ2977 【「THUSCH 2017」巧克力】题解

 https://www.cnblogs.com/yijan/p/12319010.html 这里里面概率算的有点问题,一次随机的正确率是0.03左右

LOJ2979 【「THUSCH 2017」换桌】题解

 bfs版KM直接艹过去即可 正解应该是费用流+线段树优化建图 https://www.cnblogs.com/Narh/p/10841141.html

FWT

 https://oi-wiki.org/math/poly/fwt/

洛谷P3232 【[HNOI2013]游走】题解

 https://siyuan.blog.luogu.org/solution-p3232

min-max反演的推广

https://www.cnblogs.com/Mr-Spade/p/9636968.html

min-max反演

图片
 设 $S$ 是一个集合, $max(S)$ 和 $min(S)$ 分别表示集合的最大值和最小值,那么有 $$max(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}min(T)\\min(S) = \sum_{T \subseteq S}(-1)^{|T| + 1}max(T)$$

洛谷P3747 【 [六省联考2017]相逢是问候】题解

 https://www.luogu.com.cn/blog/user15268/solution-p3747

生成函数

 见20200730讲课课件

不同根的有理展开定理

图片
如果 $R(x) = \frac{P(x)}{Q(x)}$ ,其中 $Q(x) = q_0(1 - \rho_1x) \cdots (1 - \rho_lx)$ 而各 $\rho_i$ 均不相同,又如果 $P(x)$ 是一个次数小于 $l$ 的多项式,那么 $[x^n]R(x) = \sum_{i=1}^la_i\rho_i^n$ ,其中 $a_i = \frac{-\rho_iP(\frac{1}{\rho_i})}{Q'(\frac{1}{\rho_i})}$

TC13764 SumOverPermutations题解

https://www.cnblogs.com/HarryGuo2012/p/4777063.html

最坏复杂度为线性时间的序列第k大查找算法

 逛知乎看到有人提到算法导论上有最坏复杂度也能保证为线性的找序列第k大就去学了一波 虽然貌似没啥用,而且有重复元素还会假掉,nth_element真香( 参考自《算法导论》P123

检测未定义行为

使用clang的诊断模式: 在编译选项中加上一条: -fsanitize=undefined PS:Linux下的g++也提供这一编译选项

斐波那契循环节

https://www.cnblogs.com/cjoierShiina-Mashiro/p/11385287.html https://www.luogu.com.cn/blog/oieremtkotori/solution-p4000

二次互反律

https://www.zhihu.com/question/59572768/answer/254653900

VIJOS1891 【学姐的逛街计划】题解

所有数据均为64位无符号整数这句话是忽悠人的,int就*过去了 https://blog.csdn.net/hongkongreporter/article/details/107467406

SGU278 【Fuel】题解

图片
  latex粘上来有些问题,就直接传截图算了

二次剩余

  https://blog.csdn.net/stevensonson/article/details/85845334 https://www.jianshu.com/p/ad5bb5b8fa7d https://www.luogu.com.cn/blog/beili233/solution-p5277

BZOJ2654 【tree】题解

  https://blog.csdn.net/zxyoi_dreamer/article/details/82843464 https://www.cnblogs.com/CQzhangyu/p/7189787.html

HIHO1236 【Scores】题解

 对于每个成绩,求出所有满足条件的人的编号,bitset合并即可 由于空间不够,所以要分一下块

HIHO1145 【幻想乡的日常】题解

 因为这些点在树上,因此区间数等于点数-边数 离线下来按照r排序树状数组维护l即可

BZOJ2143 【飞飞侠】题解

对于这种一个点连出去的每条边权值都相等的图的最短路,我们可以考虑使用并查集优化。

BZOJ3103 【Palindromic Equivalence】题解

 zxyoi yyds! https://blog.csdn.net/zxyoi_dreamer/article/details/96501133

BZOJ3707 【圈地】题解

  https://blog.csdn.net/cdsszjj/article/details/78610609 http://hzwer.com/4097.html

BZOJ2288 【[POJ Challenge]生日礼物】题解

  http://hzwer.com/2929.html

圆的反演

oi-wiki讲的挺好:  https://oi-wiki.org/geometry/inverse/

洛谷 P4049 【[JSOI2007]合金】题解

显然第三位是废的 根据高一数学 ,一个向量能被x a +y b 表示当且仅当在这个向量在 a , b 的连线上

SP839 【OPTM - Optimal Marks】

 异或的各位互不相干,所以分开对每一位数考虑 这道题可以转化为两个点集,题中的每条边相当于在点之前连一条流量为1的边,而将所有点分为两个点集也就需要把部分边拆掉,所以跑最小割即可

洛谷 P2569 【[SCOI2010]股票交易】题解

瞎推推状态转移就出来了   https://www.luogu.com.cn/blog/Sooke/solution-p2569

洛谷 P3294 【[SCOI2016]背单词】题解

显然情况1灰常不优,3就是2的特殊情况 所以只考虑2

洛谷 P2512 【[HAOI2011]防线修建】题解

 挺裸的动态凸包 离线下来倒着处理把删除变成插入即可

洛谷 P5479 【 [BJOI2015]隐身术】题解

  https://www.luogu.com.cn/blog/wzp-blog/new-solution-p5479

洛谷 P5618 【[SDOI2015]道路修建】题解

  https://www.luogu.com.cn/blog/AAAbbb123/solution-p5618

洛谷 P3468 【[APIO2014]序列分割】

 答案与切的顺序无关 显然斜率优化

POJ2411 【Mondriaan's Dream】题解

  https://blog.csdn.net/lvmaooi/article/details/79702273

整体二分

oi wiki讲的挺好: https://oi-wiki.org/misc/parallel-binsearch/

线段树合并

本文转载自 https://blog.csdn.net/hongkongreporter/article/details/107116155 并对部分内容进行了补充

cdq分治

 oi wiki上讲的挺好: https://oi-wiki.org/misc/cdq-divide/

洛谷 P6515 【[QkOI#R1] Quark and Game】题解

我们将所有二元组看成平面直角坐标系上的点 我们可以分别将操作看成翻转空间和砍掉平面上的点,那么我们其实就是在看最小花费多少可以使所有点被砍掉

洛谷 P3348 【[ZJOI2016]大森林】题解

对于操作0,我们可以发现其实完全可以对于每个树都进行操作,因为所有的这样只会使树多长出一些节点,显然我们询问的节点不可能由这些节点拓展而来,因此其路径上必然不存在这些节点,因此这些节点并不会影响询问的答案

洛谷 P4124 【[CQOI2016]手机号码】题解

数位dp板子题

莫队

并不打算写莫队的博客,这里就只提一个容易错的点 (调了我半天)

计算几何入门

PS:Latex加载可能有点慢 首先提一下精度问题

模拟退火

图片
模拟退火(Simulate Anneal,SA)用于寻找一个方案量极大且不为单峰函数的问题的全局最优解的随机化算法。

CSP-S2019退役记

这是第几次退役了来着?

20191114测试总结

CSP-S模拟总算有点CSP的样子了 正解仍然十分不CSP-S

20191112测试总结

图片
T1搞得心态崩了。。。

易错点总结

CSP-S前收集一波

20191111测试总结

三道题两道计数,出题人过于毒瘤。。。

20191109测试总结

不用女装了)雾 T1、T3两个省选原题,T2一个骗分就可以过的题, 真有趣

20191108测试总结

又爆零了。。。明天再爆零我女装(flag)

作文素材

文化课知识储备

20191106测试总结

图片
题目过于毒瘤。。。假のCSP,真のNOIplus

20191105测试总结

什么毒瘤题啊。。。爆零了

20191102测试总结

咕咕咕 T1被卡常数了,求逆元的时候把ksm换成exgcd就过了,毒瘤出题人

20191101测试总结

咕咕咕 脑残的读错了T1数据范围,T2还没注意常数。。。被卡掉60

20191030测试总结

今天貌似没那么自闭了 调正解还是很自闭

多重背包

朴素的多重背包没什么好讲的。不过由于复杂度过高(O(vnm))很容易被卡,下面讲两种优化。

20191029测试总结

继续没睡醒状态)雾

20191026测试总结

图片
说好的大家一起考CSP-S模拟赛,然而事实是大家一起考NOI模拟赛)雾

20191024测试总结

在T2费了太多时间了,时间安排策略还要注意啊

20191022测试总结

虽然今天做的是NOI模拟题,但是做的太自闭了, 因此总结的是CSP-S模拟题 。

Kuhn-Munkres

Kuhn-Munkres算法(KM算法)的作用是求解二分图最大权最佳完美匹配。

20191017测试总结

这套题的区分度可谓十分之高,让大家分数没啥差距。

20191015测试总结

T1:WOJ4218 就是一个大暴力。忘记了判断一个是否存在了导致得分很低,以后大暴力还是不能对自己的正确性太自信,要多检查啊。

20191012测试总结

原地爆炸。。。

20191011测试总结

T1:CF402D 分解质因数再判断一下是好还是坏就可以算出初始得分。

20191009测试总结

T1:SOJ 2197 很傻的一个背包问题,没啥好说的

BZOJ 2118 【墨墨的等式】题解

显然是同余最短路。

LOJ 6008 【「网络流 24 题」餐巾计划】题解

显然是一个费用流的题

快速输出

整理一下快输的板子, 方便自己复制

快速读入

整理一下快读的板子, 方便自己复制

DLX(舞蹈链)

DLX(dancing links)是一种优化的X算法,用于求解精确覆盖问题。

主席树

主席树就是可持久化线段树,至于它为什么叫这个名字, 不要问我我也不知道 。

二分图匹配

首先我们引入二分图的定义:顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

分块

万能算法

Miller Rabin

Miller Rabin是一种快速判定素数的方法,可以在log的时间内判断一个数是否为素数。

SCOI2019退役记

NOIP2018不是就已经退役过一次了吗? 不要在意这些细节

2019寒假七林集训

Day1

EOJ 140 【神仙互掐】题解

这道题的思路并不难,就是DFS+强剪枝。 没什么好说的,直接粘代码。

强连通分量(二)——tarjan

开这篇文章之前可以先看一下 强连通分量(一)——kosaraju 。个人认为kosaraju要更容易理解一些,但是要慢一些。一些概念性的东西在这篇博客中就不作说明了。

UVa 307 【小木棍 Sticks】题解

这道题总体来说还是非常简单的,就是搜索+剪枝。

董乙己

我从十四岁起,便在EOJ里当管理员,cyy说,样子太傻,怕侍候不了后端开发,就在前端做点事罢。外面的题目管理,虽然容易搬题,但留下的坑的也很不少。

树链剖分

终于开始填暑假的坑了 首先是 概念 :总的来说,就是把一棵树剖分成若干条链,然后利用数据结构维护每一条链。 复杂度:O(logn)

NOIP2018退役记

Day -1 半期考试。。。

洛谷 P2251 【质量检测】题解

这一道题的主要思路: 单调队列 (不熟的可以做一下滑动窗口这一道题) 建立一个从小到大的单调队列,每次如果读入到比队尾的数小就将队尾的数弹出( 贪心 思想:你后面都有更小值的了你还要前面

洛谷 P1441 【砝码称重】题解

做这道题之前建议先看一下 洛谷P2347 这一道题,总体思路与这一道题十分相似(这一道题主要是多了一个DFS的过程),下面来说一下这道题(敲黑板): 使用的算法:DFS+DP(看到数据范围这么小应该首先想到的就应该是DFS)

洛谷 P3068 【[USACO13JAN]派对邀请函Party Invitations】题解

因为直接按照存每组的奶牛会存在 浪费 的情况, 会超内存 ,因此这里采用线性存储的方法,将 所有奶牛存在一个数组 中,然后每个组保存一个 头和尾标记 来表明这个组的奶牛在数组中的什么位置。然后就是一个大暴力,

强连通分量(一)——kosaraju

强连通分量主要有两种算法——kosaraju和tarjan。其中,两个算法的时间复杂度均为O(m+n),kosaraju算法更易于理解,而tarjan虽然概念更难,但是速度更快,更不容易爆栈超内存。本篇博客将介绍的是kosaraju算法。

2018暑假七林集训(一)

图片
day1 考试…… orz dyh大佬rank1

2018暑假七林集训(二)

图片
day0 我一个蒟蒻为什么会到2期

Codeforces 527D 【Clique Problem】 题解

这是一道神奇的贪心题 对于每一个点,你可以把它视为一条线段, 左端点为x-w,右端点为x+w 。这样对于每个abs(xi-xj)>=wi+wj,我们默认xi>=xj,那么就可以转化为

洛谷 P4889 【kls与flag】 题解

对于每一个竿子,你都可以记录下他倒下的点的位置。到这里的思路还是差不多的。但是我们并不需要将每个杆子倒下的位置作为下标来存入数组,而是直接放在数组尾部。当记录完所有杆子后,将他们倒下的位置排一下