zigzagk.top Open in urlscan Pro
47.237.114.27  Public Scan

Form analysis
0 forms found in the DOM

Text Content

 ZigZagK的博客
首页

  


正在努力加载中QAQ


游戏记录 | 女神异闻录5 皇家版
本文已经对重要剧情进行过滤，只含有轻微剧透并采取了折叠，应该可以放心阅读 😂
。前言久闻P5R大名，买了ns卡带，本来打算慢慢玩，留着上班午休玩之类的，结果没玩多久就沉迷了 👍 。花了100h...

ZigZagK
 2024年6月3日 14:18
 游戏
 查看标签
 * Persona系列

 2 条评论
阅读全文
Unity Shader 入门
前言前置知识：基础的图形学。参考链接：简单易懂的Unity5 Shader着色器入门教程Unity手册基础 Shader一个基础的 shader
，纯色。Shader "Custom/...

ZigZagK
 2024年4月18日 01:19
 Unity
 查看标签
 * Shader
 * Unity

 0 条评论
阅读全文
一个周末就学会光线追踪 - 中文翻译
Ray Tracing in One Weekend译注： 本文为 Ray Tracing in One Weekend
一书的中文翻译，某些地方与原文不同，因为我希望在最大限度保持原义的同时使...

AT4
 2024年3月31日 01:21
 图形学
 查看标签
 * 光线追踪

 2 条评论
阅读全文
GAMES101-现代计算机图形学入门 自用笔记
前言本文章为自用笔记，部分图片和部分内容版权归原出处所有。原网课链接为：GAMES101-现代计算机图形学入门-闫令琪。笔记可能存在纰漏，欢迎在评论区指出。1.线性代数点乘&叉乘点乘反映向量是否...

ZigZagK
 2024年3月30日 18:58
 图形学
 查看标签
 * 数学姿势
 * 光线追踪
 * 光栅化
 * 着色
 * 纹理

 1 条评论
阅读全文
四元数简单介绍
从三维旋转的角度简单介绍一下四元数。定义q^=xi+yj+zk+w=q^v+qw=(q^v,qw)\hat{q}=xi+yj+zk+w=\hat{q}_v+q_w=(\hat{q}_v,q_w)q^
=xi+yj+zk+w=q^ v +qw =(q^ v ,qw ) 。qwq_wqw 为实部，q^v\hat{q}_vq^ v 为虚部...

ZigZagK
 2024年3月30日 16:27
 图形学
 查看标签
 * 数学姿势

 2 条评论
阅读全文
真正的退役 | ACM生涯回忆录
ACM，作为OI生涯的延续，占据了我大学前三年的大部分时间。在三年ACM经历中，我获得过成功，也跌落过低谷，达到过新的高峰，也留下了一些遗憾。由于心境的成长，相比于OI退役时的遗憾不舍，ACM...

ZigZagK
 2023年7月8日 02:30
 其他
 查看标签
 * 自己的理解

 2 条评论
阅读全文
第47届ICPC EC-Final现场赛游记
Day
[-n,-1]这次是我和熊哥第一次EC（也是最后一次），柴老师是第二次。我们新组的杭电4队这赛季取得了不错的成绩，但是训练时还是偶尔会发现严重的短板，那就是乱搞题和脑子题，并不能稳定快速...

ZigZagK
 2023年3月30日 13:02
 游记
 查看标签
 * 大学生活
 * ACM

 5 条评论
阅读全文
[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。好像看到了很多Pushdown在原...

ZigZagK
 2022年12月1日 21:10
 洛谷
 查看标签
 * 可持久化
 * 平衡树

 0 条评论
阅读全文
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这...

ZigZagK
 2022年12月1日 19:58
 洛谷
 查看标签
 * 可持久化
 * 平衡树

 0 条评论
阅读全文
[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 k≤10k\le 10k≤10 ，其实就是个暴力题。记录 prexpre_xprex 表示 xxx
前面第一个颜色相同的位置（没有就记成 000 ），如果不能跳过，那么一定是在...

ZigZagK
 2022年11月29日 17:30
 ICPC
 查看标签
 * 树状数组
 * 线段树
 * 平衡树

 1 条评论
阅读全文
上一页
1/49
下一页
ZigZagK的博客
Never give up fighting!

首页

归档

2024年6月
1
2024年4月
1
2024年3月
3
2023年7月
1
2023年3月
1
2022年12月
2
2022年11月
16
2022年10月
19
2022年9月
2
2022年8月
9
2022年7月
12
2022年4月
1
2022年3月
4
2021年11月
1
2021年9月
2
2021年8月
5
2021年7月
9
2021年6月
2
2021年4月
1
2021年3月
3
2021年2月
5
2021年1月
1
2020年12月
11
2020年11月
4
2020年10月
24
2020年9月
19
2020年8月
3
2020年7月
1
2020年6月
1
2020年5月
2
2020年4月
2
2020年2月
2
2020年1月
1
2019年12月
2
2019年9月
2
2019年8月
1
2019年7月
2
2019年6月
1
2019年5月
1
2019年4月
21
2019年3月
31
2019年2月
39
2019年1月
22
2018年12月
5
2018年11月
12
2018年10月
36
2018年9月
24
2018年8月
50
2018年7月
21
2018年6月
2
2018年5月
22
2018年4月
11
2018年3月
10
2018年2月
4

最新评论

NordLandeW
SkyWT
泽泽
道麟笔记
道麟笔记


游戏开发

游戏开发
4
图形学
3
Unity
1

网站相关

网站相关
7
PHP
1
Typecho
6

学习笔记

学习笔记
17
DP
3
图论
3
字符串
1
数学相关
10

颓废生活

颓废生活
5
游戏
5

ACM

ACM
23
CCPC
8
ICPC
12

Online Judge

Online Judge
421
BZOJ
112
LOJ
44
UOJ
4
HDU
39
POJ
3
ZOJ
1
EOJ
1
洛谷
20
牛客
19
计蒜客
5
51Nod
4
HHHOJ
20
SPOJ
1
COCI
1
Hydro
1
AtCoder
13
TopCoder
6
CodeChef
6
Codeforces
116
HackerRank
2

其他

其他
19
游记
10
日记
5

标签云


关于

友链

日记

追番

留言板

实验室


文章总数
490

运行天数
2151
 1. 1 感情の摩天楼　～ Cosmic Mind 上海アリス幻樂団
 2. 2 秘匿されたフォーシーズンズ 上海アリス幻樂団
 3. 3 Ideal and the Real 小西利樹
 4. 4 Undertale Toby Fox
 5. 5 First Steps Lena Raine
 6. 6 City of Tears Christopher Larkin
 7. 7 The truth that you leave Pianoboy高至豪
 8. 8 Blaze A Trail October
 9. 9 Tower Of Heaven (You Are Slaves) Feint

感情の摩天楼　～ Cosmic Mind - 上海アリス幻樂団
00:00 / 07:43




作曲 : ZUN

纯音乐，请欣赏


  

Copyright © 2024 ZigZagK的博客
Powered by Typecho
Theme by MDUI2333
文章
游戏记录 | 女神异闻录5 皇家版

[Meting][Music server="netease" id="1403087332" type="song"/][/Meting]本文已经对重要剧情进

Unity Shader 入门

前言前置知识：基础的图形学。参考链接：简单易懂的Unity5 Shader着色器入门教程Unity手册基础 Shader一个基础的 shader ，纯色。Sha

一个周末就学会光线追踪 - 中文翻译

Ray Tracing in One Weekend译注： 本文为 Ray Tracing in One Weekend 一书的中文翻译，某些地方与原文不同，因

GAMES101-现代计算机图形学入门 自用笔记

前言本文章为自用笔记，部分图片和部分内容版权归原出处所有。原网课链接为：GAMES101-现代计算机图形学入门-闫令琪。笔记可能存在纰漏，欢迎在评论区指出。1.

四元数简单介绍

从三维旋转的角度简单介绍一下四元数。定义$\hat{q}=xi+yj+zk+w=\hat{q}_v+q_w=(\hat{q}_v,q_w)$ 。$q_w$ 为实

真正的退役 | ACM生涯回忆录

[Meting][Music server="netease" id="39224658" type="song"/][/Meting]ACM，作为OI生涯的延

第47届ICPC EC-Final现场赛游记

Day [-n,-1]这次是我和熊哥第一次EC（也是最后一次），柴老师是第二次。我们新组的杭电4队这赛季取得了不错的成绩，但是训练时还是偶尔会发现严重的短板，那

[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解

题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。

[可持久化平衡树]洛谷3835【可持久化平衡树】题解

题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，

[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解

题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0

[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解

题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lflo

[Splay+并查集]AGM 2020 Qualification Round【Unpredictable Tree】题解

题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$

[后缀自动机+线段树合并]Codeforces1037H【Security】题解

题目概述CF1037H解题报告算法不难得出：对于 $x$ 的每个前缀 $x[1,i]$ ，往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ，$i$ 越大

[广义后缀自动机+DP+单调队列]洛谷4022(CTSC2012)【熟悉的文章】题解

题目概述Luogu4022解题报告不难想到二分答案 $mid$ ，然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\

[广义后缀自动机]Codeforces316G3【Good Substrings】题解

题目概述CF316G3解题报告用广义后缀自动机做可以避免很多复杂的情况。把 $s$ 和所有 $p$ 都扔进广义SAM里，然后把 $s$ 扔进SAM匹配得出所有属

[后缀自动机+线段树合并]HydroH1079【‘Minami Kotori’ Pantw 和他的召唤物二元葡萄】题解

题目概述HydroH1079解题报告建出SAM，找到 $[A,B]$ 对应节点 $p$ ，然后在 $p$ 的 $Right$ 集合上考虑。$[C,D]$ 中出现

[离线+线段树+堆]洛谷4747(CERC2017)【Intrinsic Interval】题解

题目概述Luogu4747解题报告找性质题过于困难……首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是

[离线+ODT+扫描线+线段树]2022 CCPC 广州 B【Ayano and sequences】题解

题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发

[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解

题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$

[后缀自动机+线段树合并+后缀数组]LOJ2720【「NOI2018」你的名字】题解

题目概述LOJ2720解题报告毒瘤字符串题……这题的关键在于，给出串 $T$ ，在 $S$ 的 $[L,R]$ 子串中查询每个后缀的最长匹配前缀。倒着考虑 $T

[NTT]Codeforces528D【Fuzzy Search】题解

题目概述CF528D解题报告奇怪的字符串匹配，并且字符集很小，考虑卷积。对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i

[离线+线段树套单调栈+线段树二分]2019 ICPC 香港 H【Hold the Line】题解

题目概述Hold the Line解题报告直接线段树套set是过不了的，我们需要一个小常数的做法。考虑离线，这样第 $i$ 次事件插入 $x$ 位置时，就可以认

[多项式ln+多项式exp+分治NTT]LOJ2320【「清华集训 2017」生成树计数】题解

题目概述LOJ2320解题报告学到了好多多项式套路。如果 $i$ 连通块度数是 $d_i$ ，则每条边都有 $a_i$ 个选择，把 $a_i$ 放进答案式子里，

[容斥+分治NTT]LOJ575【「LibreOJ NOI Round #2」不等关系】题解

题目概述LOJ575解题报告有个比较好想的想法是 $f_{i,j}$ 表示前 $i$ 末尾放第 $j$ 大的方案数，转移方程很显然是前缀和、后缀和的形式，但是前

[分治NTT+倍增]2022 CCPC 桂林 D【Alice's Dolls】题解

题目概述Alice's Dolls解题报告定义 $f_{n,k}$ 表示要得到 $n$ 个物品，$x^k$ 的期望。$n>1$ 的情况十分复杂，但是根据期

[后缀自动机+线段树合并]Codeforces GYM102411L【Lengths and Periods】题解

题目概述给一个字符串 $S$ ，选一个子串 $T$ ，使 ${T\over T-Border(T)}$ 最大。解题报告每个串的Border并不好考虑，但是可以考

[单位根反演+Bluestein套路]LOJ3058【「HNOI2019」白兔之舞】题解

题目概述LOJ3058解题报告这个 $m\bmod k=t$ 以及 $k$ 是 $MOD-1$ 因子显然是单位根反演，所以考虑用生成函数表示答案。令转移矩阵为

cdq分治FFT

非自身卷积$f_i=\sum_{k=0}^{i-1}f_kg_{i-k}$ ，$f_0$ 已知，给出 $g_{1..n}$ 。（ $k>i$ 同理）cdq

[DP+多项式exp]HDU5279【YJC plays Minecraft】题解

题目概述HDU5279解题报告首先每个连通块里必须是森林，然后连接每个连通块的 $n$ 条边只要删掉一条，就肯定不会存在全局环，这样每个连通块就独立了。定义 $

[Min25筛]2021牛客暑期多校训练营6 G【Hasse Diagram】题解

题目概述Hasse Diagram解题报告考虑 $f(n)$ 的递推式，但是如果只考虑单个素数，很明显会数重复，因此一次性考虑完一个素数，即 $p^k$ 。对于

[生成函数+分治NTT+多项式ln]洛谷4705【玩游戏】题解

题目概述Luogu4705解题报告二项式展开后：$$ {t!\over nm}\sum_{k=0}^{t}{1\over k!}(\sum_{i=1}^{n}a

[除法分块+Min25筛]2021 CCPC 威海 I【Distance】题解

题目概述Distance解题报告$i$ 走到 $j$ 不管怎么走，每个相差的素数都必须走一遍，所以：$$ dis(i,j)=\sum_{p}p|e_{p,i}-

[NTT]AtCoder Grand Contest 005F【Many Easy Problems】题解

题目概述AGC005F解题报告考虑每个点对 $k$ 的贡献：$$ \sum_{i=1}^{n}[{n\choose k}-\sum_{(i,j)\in E}{s

Lyndon分解

性质$S$ 是Lyndon串当且仅当 $S$ 本身是所有后缀中的最小串。$S$ 是Lyndon串可以推出 $S$ 是所有循环表示中字典序最小的。各种性质与推论：

[DP+分治NTT]HDU5322【Hope】题解

题目概述HDU5322解题报告考虑连通块是什么样的，对于 $n$ 的排列，$n$ 所在位置之前的点肯定都是 $n$ 连通块中的，并且 $n$ 没有往后的边。然后

[容斥+分治NTT]LOJ2541【「PKUWC2018」猎人杀】题解

题目概述LOJ2541解题报告可以把题目转化为，有一个外人向 $n$ 个人开枪，打到第 $i$ 个人的概率是 $w_i\over \sum w$ ，并且可以对死

[分数规划+长链剖分+线段树]洛谷4292【[WC2010]重建计划】题解

题目概述洛谷4292解题报告题解里很多点分治，但其实用长链剖分十分的直白。首先先用01分数规划，二分答案 $mid$ ，然后问题转化为边权为 $w-mid$ 的

[长链剖分+DP]BZOJ4543【[POI2014]Hotel加强版】题解

题目概述给出一棵树，求多少个 $(a,b,c),a<b<c$ 满足三个点两两距离相同。解题报告考虑以这三个点的LCA $x$ 统计答案，则只有两种情

[长链剖分+DP]Codeforces1009F【Dominant Indices】题解

题目概述CF1009F解题报告定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\

[cdq分治+阈值优化+NTT]2022ICPC网络赛第一场 I【Permutation】题解

题目概述给出一个排列 $\{a_n\}$ ，对于这个排列的所有循环同构，求出排列的排名，对所有排名求和。解题报告对于一个固定的 $\{a_n\}$ ，根据康托展

[分治+矩乘NTT]2022牛客暑期多校训练营（加赛）L【Lndjy and the mex】题解

题目概述Lndjy and the mex解题报告首先不难发现长度为 $len$ 的区间的方案数是相同的，因此只需要考虑区间长度而不需要考虑区间位置（乘 $n-

[Palindrome Series+exgcd]HDU6320【Cut The String】题解

题目概述HDU6320解题报告暴力想法：枚举 $L$ 开始的回文串 $A$ ，和 $R$ 结尾的回文串 $B$ ，如果 $|A|+|B|=R-L+1$ 则找到一

[思维+Palindrome Series]Codeforces932G【Palindrome Partition】题解

题目概述CF932G解题报告首先原题意有点恐怖，我们需要进行一定的转化。原题意需要分成偶数个串，然后前后对称相同，如果我们把串的后一半翻转，那么就会发现前后对应

[链分治+分治NTT]LOJ6289【花朵】题解

题目概述LOJ6289解题报告这题显然是一个树形背包 $f_{x,j,0},f_{x,j,1}$ 表示 $x$ 没选 / 选了，子树里选了 $j$ 个的方案数。

[离线+后缀自动机+LCT]2022牛客暑期多校训练营（加赛）C【Cmostp】题解

题目概述Cmostp解题报告建出SAM，考虑离线，每次添加一个前缀节点 $p_i$ 的时候，就是把 $p_i$ 到 $fail$ 树根路径上的节点的最右终止端点

[离线+可持久化树+线段树分治+并查集按秩合并+哈希]2022牛客暑期多校训练营8 I【Equivalence in Connectivity】题解

题目概述Equivalence in Connectivity解题报告好像确实有维护动态图的方法……但是可能是考场上写不出的那种……考虑离线，建出可持久化树，如

[后缀数组+复杂度分析]2022牛客暑期多校训练营7 I【Suffix Sort】题解

题目概述Suffix Sort解题报告一直在想Hash，然后寄了……实际上应该分析一下性质。首先有一个比较显然的想法是将 $S$ 变为另一个数组，$a_i$ 表

[KMP+后缀数组+主席树]2022牛客暑期多校训练营6 L【Striking String Problem】题解

题目概述Striking String Problem解题报告神仙题，根本想不到。记 $n$ 为 $S$ 长度，$m$ 为 $T$ 长度，$U_i$ 表示 $S

[DP+复杂度分析]2022“杭电杯”中国大学生算法设计超级联赛（7）【Counting Good Arrays】题解

题目概述HDU7217解题报告一个显然的想法：定义 $f_{i,j}$ 表示放了 $i$ 位，第 $i$ 位为 $j$ 的方案数，那么：$$ f_{i,j}=\

[Bluestein套路+多项式ln]2022“杭电杯”中国大学生算法设计超级联赛（7）1010【Connectivity of Erdős-Rényi
Graph】题解

题目概述HDU7218解题报告这道题看起来和城市规划很像，但是由于要考虑概率，所以卷积式子和求方案数的式子不一致。定义 $f_i$ 表示 $i$ 个点成为一个连

[容斥+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（8）1013【Shattrath City】题解

题目概述HDU7232解题报告比赛的时候想的是正着做，写完DP式子发现是个看起来很可做的东西，结果实际上不能做，寄掉了。实际上应该倒着做，$f_{i}$ 表示

[多项式exp]2022“杭电杯”中国大学生算法设计超级联赛（6）1003【Find the Number of Paths】题解

题目概述HDU7199解题报告多项式套路题，需要把题目中两种路径对应到比较容易处理的多项式形式。首先是 $i\to i+1$ ，有 $n+k-i$ 条路径，这个

[珂朵莉树+线段树]2022“杭电杯”中国大学生算法设计超级联赛（5）1001【Pandaemonium Asphodelos: The First
Circle (Savage)】题解

题目概述HDU7185解题报告其实并不难。由于每次区间操作都是直接覆盖成一种颜色，所以我们可以考虑用set维护所有的颜色相同的线段，然后每次操作就是对set中的

[回文自动机回退]2020 ICPC 昆明 F【Generating Strings】题解

题目概述Generating Strings解题报告裸的回文自动机回退。对于一个长度为 $len$ 的回文串，在 $s$ 中出现一次的权值为 $(N-len+1

[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解

题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点

[离线+分块+Tarjan缩点+bitset维护传递闭包]The 19th Zhejiang Provincial Collegiate Programming
Contest K【Dynamic Reachability】题解

题目概述CF GYM103687K解题报告科技题过于困难。考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2

[离线+bitset维护传递闭包+卡空间]2022“杭电杯”中国大学生算法设计超级联赛（3）10【Range Reachability Query】题解

题目概述HDU7171解题报告题目保证了DAG，所以是个DAG上的传递闭包问题，考虑用bitset做。定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的

[随机化+线段树维护凸包+最小圆覆盖]2022“杭电杯”中国大学生算法设计超级联赛（3）1006【Dusk Moon】题解

题目概述HDU7167解题报告被队内计算几何选手演了😡，本来写个最小圆覆盖就过了。首先很显然 $n$ 个点的最小圆覆盖和这个 $n$ 个点求完凸包之后的最小圆

[离线+Trie+倍增]2022牛客暑期多校训练营2 F【NIO with String Game】题解

题目概述NIO with String Game解题报告感觉赛时榜都歪飞了……这题明明不难却只有20个队过。由于对 $t_i$ 只有单字符加的操作，因此最终所有

[树上解方程+组合数化简]2022牛客暑期多校训练营3 D【Directed】题解

题目概述Directed解题报告这题竟是脑子题……显然这是个树上解方程的题目，设 $D_x$ 为 $x$ 的度数，$fa$ 为 $x$ 的父亲，$u$ 为 $x

[容斥+DP+多项式求逆]2022“杭电杯”中国大学生算法设计超级联赛（1）1010【Walk】题解

题目概述HDU7147解题报告从来没做过这种容斥，长见识了😭。定义 $f_i$ 表示走了 $i$ 行都合法的权值和，以及 $g_i$ 表示走了 $i$ 行全非

[后缀自动机parent树+虚树]2022牛客暑期多校训练营1 B【Spirit Circle Observation】题解

题目概述Spirit Circle Observation解题报告找性质题最烦了.jpg。首先建SAM，考虑一个直观的做法。直接考虑枚举SAM里的节点，然后在节

[线段树合并/分裂]2022牛客暑期多校训练营1 F【Cut】题解

题目概述Cut解题报告这题思路是不难的，但是如果没写过类似的就会巨难写（细节比较多）……把 $[l,r]$ 内的排序其实就是认为 $[l,r]$ 这一块按照权值

[背包回退+二进制状压DP+NTT]2022牛客暑期多校训练营1 H【Fly】题解

题目概述Fly解题报告首先想到DP：$f_{i,j,0/1/2}$ 表示前 $i$ 个二进制位（从低位到高位），到 $i$ 这位时背包大小为 $j$ ，并且状态

[阈值优化+分块]洛谷5309【[Ynoi2011] 初始化】题解

题目概述Luogu5309解题报告题目保证 $y\le x$ ，因此每次都是全局 $i\bmod x=y$ 的 $a_i$ 加上 $z$ 。不难想到 $x>

[后缀自动机+拓扑]LOJ3049【「十二省联考 2019」字符串问题】题解

题目概述LOJ3049解题报告把串反过来，那么 $B$ 是 $A$ 前缀就变成 $B$ 是 $A$ 后缀，也就是 $B$ 是 $A$ 在SAM上的parent树

[矩阵乘法+线段树]Codeforces1701F【Points】题解

题目概述CF1701F解题报告对于 $x$ ，设 $[x-d,x-1]$ 上共有 $cnt$ 个点，那么以 $x$ 作为结尾的三元组个数为 ${cnt\choo

[广义后缀自动机]2021 ICPC 澳门 I【LCS Spanning Tree】题解

题目概述LCS Spanning Tree解题报告听说这题卡倍增SA，表示强烈谴责😡（不过我没想到SA怎么做）。由于需要求任意两个字符串之间的最长公共子串，因

[后缀自动机]The 2021 ICPC Asia Shenyang Regional Contest M【String Problem】题解

题目概述String Problem解题报告首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。用后缀数组可以做，但是思考起来比较麻烦。考虑后缀自

[AC自动机+倍增]The 2021 China Collegiate Programming Contest (Harbin) L【Karshilov's
Matching Problem】

题目概述Karshilov's Matching Problem解题报告首先不难想到对 $n$ 个匹配串建AC自动机，在 $fail$ 树上求和就可以得知匹配到

[矩阵乘法+线段树]The 2021 ICPC Asia Nanjing Regional Contest E【Paimon Segment Tree】题解

题目概述Paimon Segment Tree解题报告首先肯定考虑离线，把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[

[广义后缀自动机+二分]2021-2022 ACM-ICPC Brazil Subregional Programming Contest
B【Beautiful Words】题解

题目概述Beautiful Words解题报告先把 $A$ 复制一份，令 $B_i=A[i-n+1,i]$ 。然后二分答案 $mid$ ，这样就只需要验证是否存

[后缀数组+离线+扫描线+线段树二分]2021 CCPC 桂林 J【Suffix Automaton】题解

题目概述Suffix Automaton解题报告被时限骗了，以为做法是两个 $\log$（空间爆炸），其实只要离线就可以一个 $\log$ 。求出后缀数组后，第

[生成函数+多项式除法求系数]2021牛客暑期多校训练营8 H【Scholomance Academy】题解

题目概述Scholomance Academy解题报告伪装成数论题的多项式全家桶题。首先我们可以把 $\varphi(n)$ 拆成 $\prod\varphi(

[线性代数+多项式取模]洛谷4723【常系数齐次线性递推】题解

题目概述给出递推 $f$ 的 $[0,K-1]$ 项，给出系数 $\{a_K\}$ ，$f_n=\sum_{i=1}^{K}a_if_{n-i}(n\ge K)

[生成函数+记忆化搜索]HDU7057【Buying Snacks】题解

题目概述HDU7057解题报告首先这道题很显然可以用生成函数做，但是 $n$ 太大了，因此需要考虑类似矩阵快速幂或者分治的办法。定义 $F_i$ 表示花费

[差分+二分+主席树]2021牛客暑期多校训练营7 K【xay loves sequence】题解

题目概述xay loves sequence解题报告先对数组差分，令 $c_i=a_i-a_{i-1}$ 。每次区间加或者区间减就是对 $c$ 的两个位置 $+

[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解

题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题，定义 $Find(p,l,r,i)$ 表示在 $[l,r]

[期望DP+分治FWT]2021牛客暑期多校训练营6 D【Gambling Monster】题解

题目概述Gambling Monster解题报告显然是个期望DP，倒着考虑正常一点（因为在 $n-1$ 处结束，步数为 $0$ ），所以我们倒着DP。定义 $f

[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解

题目概述Starch Cat解题报告正解是猫树，但是我不会，所以我选择黑科技。首先我们能想到一个比较暴力的做法，每次询问 $x,y$ 路径上的最大独立集，就是求

[二进制分块]2021牛客暑期多校训练营3 I【Kuriyama Mirai and Exclusive Or】题解

题目概述Kuriyama Mirai and Exclusive Or解题报告第一种操作没什么好讲的，我们关注第二种。这种加法和异或混合的一般都只能考虑按位统计

[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解

题目概述Prof. Pang's sequence解题报告首先根据经典套路，我们记录 $pre_i$ 表示 $i$ 上次的出现位置，这样的话对于一个左端点 $L

[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解

题目概述United in Stormwind解题报告太久没做过这种题了，其实非常套路。题目里给出了 $n$ 个 $01$ 串，把两个串异或就可以得到两个串不同

ICPC2020沈阳区域赛现场赛游记

Day [-n,-2]考前天天gym VP，感觉状态神神鬼鬼的，我的发挥比较看题目。某天晚上梦见飞机坠机了，可能是某种预兆（迫真）。Day -1本来还想考前最后

[仙人掌DP]BZOJ4316【小C的独立集】题解

题目概述图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些

[仙人掌+圆方树]BZOJ2125【最短路】题解

题目概述给一个 $n$ 个点 $m$ 条边的连通无向图，满足每条边最多属于一个环，有 $Q$ 组询问，每次询问两点之间的最短路径。解题报告不难想到建出圆方树，然

[Splay维护序列]Codeforces GYM103145F【Permutation】题解

题目概述CF GYM103145F解题报告其实两个反转操作是独立的，我们可以用两棵Splay来维护位置的序列（A树）以及数值的序列（B树）。每次询问位置 $i$

[思维]Codeforces1527B【Palindrome Game】题解

题目概述CF1527B解题报告我来翻译题解啦！由于不是回文串的时候才能进行操作2，所以我们可以认为操作2是执行一次“啥都不干”。如果 $s$ 是回文串（B1）：

[贪心+DP]Codeforces GYM103049A【Atomic Energy】题解

题目概述CF GYM103049A解题报告物品体积小，背包容量大的题，我们可以采用大范围贪心，小范围DP的办法。当询问的背包容量超过 $V$ 时，我们选取性价比

[莫比乌斯函数+数学]Codeforces1139D【Steps to One】题解

题目概述CF1139D解题报告这是2021天梯赛L3-3的弱化版，吉老师加强版又要杜教筛又要快速乘，懒得写了XD。直接推式子（ $1\over n$ 是长度为

[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解

题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时，相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$

[DP]Codeforces1499E【Chaotic Merge】题解

题目概述CF1499E解题报告这道题想法不难，但是实现的时候很注重细节。首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ，第二个字

[分块+复杂度分析]Codeforces1491H【Yuezheng Ling and Dynamic Tree】题解

题目概述CF1491H解题报告这么诡异的操作，考虑分块。每个元素记录 $last_i$ 表示 $i$ 往前跳，最后一个没有跳出 $i$ 所在块的位置。查询的时候

[Kruskal重构树+树状数组套线段树]EOJ4120【雨（yù）雪霏霏】题解

题目概述EOJ4120解题报告本题难点就在于快速选出海拔 $\le L$ 的连通块，可以利用Kruskal重构树：网格按照海拔从小到大考虑对于 $(x,y)$

[线段树维护DP]Codeforces1479B【Painting the Array】题解

题目概述CF1479B1 & CF1479B2解题报告在本算法下，B1和B2其实没有很大区别，所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i

[二分]Codeforces1479A【Searching Local Minimum】题解

题目概述CF1479A解题报告如果 $a_i<a_{i+1}$ 则称 $i$ 为上点，否则称 $i$ 为下点。首先如果 $1$ 是上点，或者 $n-1$

[几何+思维]Codeforces1477C【Nezzar and Nice Beatmap】题解

题目概述CF1477C解题报告呜呜呜，几何学太差了，根本不会。三角形大边对大角，所以最小边一定是锐角。随便选一个点开始走，每次选距离最远的，那么夹角一定是锐角。

[拓扑]Codeforces1476E【Pattern Matching】题解

题目概述CF1476E解题报告如果用模式串来匹配给出的串，复杂度显然炸了。但是我们发现，字符串长度很短，所以如果用给出的串来匹配模式串（枚举哪些位置改成_），复

2020 CCPC 长春站 部分题解

F. Strange Memory呜呜呜，想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ，之后发现其实根本没有好的处理方法，只能拆位计算贡

[Trie+复杂度分析]2020 ICPC 济南 K【Kth Query】题解

题目概述Kth Query解题报告这道题给了我01 Trie的新思路QAQ。首先我们考虑没有限制的情况，我们对于每个节点 $x$ 维护 $MIN_{x,k}$

2020 CCPC 威海站 部分题解

比赛链接我是代码工具人，打的都是代码题2333。B. Labyrinth如果终点起点构成的矩阵中没有黑洞，那么答案显然就是曼哈顿距离。否则最优解一定会贴着至少一

[贪心]Codeforces1464B【Grime Zoo】题解

题目概述CF1464B解题报告我太菜了，这种题的思路其实挺经典的。考虑相邻两个?之间的情况，假设他们之间有 $s_0$ 个 $0$ 和 $s_1$ 个 $1$

单位根反演

单位根性质单位根一个神奇的性质：$$ {1\over k}\sum_{i=0}^{k-1}\omega_{k}^{ni}=[k\mid n] $$证明：当 $k

[带花树]UOJ79【一般图最大匹配】题解

题目概述UOJ79解题报告带花树板子题。由于一般图可以有奇环，所以不能直接匈牙利算法增广。但是一个奇环中我们是可以调配使得只有一个点连向外部，因此奇环是可以当成

[DP]Codeforces1453F【Even Harder】题解

题目概述CF1453F解题报告考虑路径计数 $cnt_i=\sum_{j=1}^{i-1}[j+a_j\ge i]cnt_j$ ，如果想要 $cnt_n=1$

游戏记录 | Ori and the Blind Forest

入坑又是看到WYX在玩这个游戏然后入的坑。 :orz11:游戏体验画面 & 音乐简直就是视听盛宴，吹爆。经典的每张画面都可以当壁纸。加上本人比较喜欢发光的特效，

[思维+二分+ST表]2020-2021 ACM-ICPC Brazil Subregional Programming Contest M【Machine
Gun】题解

题目概述CF GYM 102861M解题报告首先要仔细读题，题目保证了覆盖的点的个数总和不超过 $10^6$ ，因此只需要想办法快速找到被覆盖的点就行了。如果按

[背包+构造]Codeforces1444D【Rectangular Polyline】题解

题目概述CF1444D解题报告这题演我啊，我看三个 $1000$ 以为有什么高级的分半算法，结果写背包能过QAQ。首先显然 $h\not=v$ 时无解，然后我们

[思维+DP]Codeforces1446C【Xor Tree】题解

题目概述CF1446C解题报告画下Trie树，不难发现如果一个节点 $0$ 子树中只有一个元素，$1$ 子树中只有一个元素，那么这两个元素就会形成重边。由于题目

[并查集按秩合并]Codeforces1444C【Team-Building】题解

题目概述CF1444C解题报告首先我们对于每个相同颜色的块，求出是否存在奇环，如果存在那么这种颜色显然不能选。排除了不能选的颜色之后，我们发现只有有边相连的两种

[思维]Codeforces1442B【Identify the Operations】题解

题目概述CF1442B解题报告定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标，然后将 $\{a_n\}$ 递增排序，问题转化为在

[思维+最短路]Codeforces1442C【Graph Transpositions】题解

题目概述CF1442解题报告首先有个基础想法：$dis_{i,j}$ 表示走到 $i$ ，反转了 $j$ 次的最短路，那么答案就是 $\min\{dis_{n,

[单调栈+扫描线+线段树]2020 ICPC 小米 网络选拔赛热身赛 H【Equivalent Prefixes】题解

题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间（ $a_i$ 最小的

[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解

题目概述有 $m$ 条边，每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过，如果人数 $x$ 能够从 $1$ 到 $n$ 则可

[树状数组]2020 ICPC 小米 网络选拔赛热身赛 B【Beauty Values】题解

题目概述求数列 $\{a_n\}$ 所有子区间不同数个数的和。解题报告套路题，令 $nxt_i$ 表示 $a_i$ 下一个和 $a_i$ 相同的位置。对于一个

[计数+DP]2020 CCPC 秦皇岛站 H【Holy Sequence】题解

题目概述一个合法的整数数列 $\{a_n\}$ 需要满足：$1\le a_i\le n$ 。令 $p_i=\max\{a_k|1\le k\le i\}$ ，则

[主席树求区间mex]Codeforces1436E【Complicated Computations】题解

题目概述CF1436E解题报告呜呜呜，忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树，第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后

[数学]Codeforces1435E【Solo mid Oracle】题解

题目概述你有一种法术 $a,b,c,d$ ，在 $t$ 时刻使用时将对敌人造成 $a$ 伤害，但是在 $[t+1,t+c]$ 秒时敌人将每秒回复 $b$ 的血量

[扫描线+线段树]Codeforces1435C【Perform Easily】题解

题目概述CF1435C解题报告将 $a$ 排序，令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ，然后对于每个 $i$ 我们采用第一个 $\ge

[计数]Codeforces1428F【Fruit Sequences】题解

题目概述CF1428F解题报告不是很难，但是要考虑的周全一些。对于一块连续的 $1$（假设区间是 $[L,R]$ ），我们枚举 $[L,i](i>L)$

[贪心+堆]Codeforces1428E【Carrots for Rabbits】题解

题目概述CF1428E解题报告这就是换了皮的贪心+堆套路题，但是我不会QAQ。设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间，显然是分成

[思维+最大生成树]Codeforces1408E【Avoid Rainbow Cycles】题解

题目概述CF1408E解题报告呜呜呜，这就是个沙雕题，但是我不会。如果多个集合之间的边组成了环说明就有彩虹路，但是显然我们不可能把一个集合中的所有边建出来。考虑

[思维+构造+倍增+exgcd]Codeforces1427E【Xum】题解

题目概述CF1427E解题报告神仙构造题，我又来翻译题解啦QAQ！如果 $(x,y)=1$ ，根据裴蜀定理，一定能求出两个正整数 $a$ 和 $b$ 使得 $a

[并查集]洛谷6786【GCDs & LCMs】题解

题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ，然后推式子：$$ BA+CA+A={BA\cdot

[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解

题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的，所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并，考虑用set维护一个块

[离散+DFS+计数]AtCoder Regular Contest 104E【Random LIS】题解

题目概述AtCoder Regular Contest 104E解题报告这题还是挺可做的。我们发现 $n$ 小的一批，因此考虑离散。我们没必要对于每个 $i$

[容斥+计数]HHKB Programming Contest 2020 D【Squares】题解

题目概述HHKB Programming Contest 2020 D解题报告其实不难，就是烦的一批，考试的时候写复杂了然后调不出来。首先补集转化，我们求相交的

[构造]Codeforces1427D【Unshuffling a Deck】题解

题目概述CF1427D解题报告题目中疯狂暗示你做 $n$ 次，往这方面考虑就行了。假如我们现在已经有了连续的 $1,2,3,\cdots,k$ ，我们想要把 $

[DP]Codeforces1427C【The Hard Work of Paparazzi】题解

题目概述CF1427C解题报告我又被傻子题干翻了😭，首先 $O(n^2)$ DP非常好想，需要优化。由于保证了 $t_i<t_{i+1}$ ，所以当 $

[思维+贪心+最短路]Codeforces1407E【Egor in the Republic of Dagestan】题解

题目概述CF1407E解题报告这题好妙啊……如果正着做，那么一个城市的颜色决定了好多边，但是倒着做的话，一条边决定了一座城市的颜色，明显好考虑了很多。从 $n$

[思维+区间DP]AtCoder Regular Contest 104F【Visibility Sequence】题解

题目概述AtCoder Regular Contest 104F解题报告我又来翻译题解了😭。我们在最前面加上一个 $+\infty$ ，然后把 $P$ 中的

[计数+背包]AtCoder Regular Contest 104D【Multiset Mean】题解

题目概述AtCoder Regular Contest 104D解题报告对于每个 $x$ ，我们认为第 $i$ 个物品大小为 $x-i$ ，共有 $K$ 个，现

[容斥+生成函数+分治NTT]ACL Beginner Contest F【Heights and Pairs】题解

题目概述ACL Beginner Contest F解题报告直接求不太可做，我们考虑容斥，用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……$2n$

[DP]AtCoder Regular Contest 104C【Fair Elevator】题解

题目概述AtCoder Regular Contest 104C解题报告我英语太渣题目读错了😭，以为只要存在某两个人满足 $C_i=C_j$ 就行了，实际上应

[倍增]Codeforces1408F【Two Different】题解

题目概述CF1408F解题报告我们可以把 $2$ 个不同的变成相同的，$4$ 个不同的先变成 $2$ 个不同的，再变成相同的。以此类推，$2^k$ 个不同的可以

[离线+线段树]Codeforces1405E【Fixed Point Removal】题解

题目概述CF1405E解题报告显然有贪心：当有多个可以删除的元素同时存在时，先删除后面的，因为删后面的不影响前面。既然如此，我们从左往右考虑一个位置能否被删除。

[扫描线]Codeforces853C【Boredom】题解

题目概述CF853C解题报告直接求很麻烦，我们求不满足的个数。对于询问的矩形 $A$ ，我们划分出八个区域： | 0 | 1 | 2 | ----------

[思维+树状数组]ACL Contest 1E【Shuffle Window】题解

题目概述ACL Contest 1E解题报告神仙转化题我根本做不来……我又来翻译题解了。按顺序random_shuffle可以转化为以下形式：有一个数组 $A$

[容斥]Codeforces1425D【Danger of Mad Snakes】题解

题目概述CF1425D解题报告把和的平方拆开：$$ (\sum_{i=1}^{m}B_i)^2=\sum_{i=1}^{m}B_i^2+\sum_{i=1}^{

[Trie]Codeforces1417E【XOR Inverse】题解

题目概述CF1417E解题报告比赛结束之后想出来了……我做D题的时候不SB可能能做出来？很显然我们需要考虑每个二进制位的贡献，第 $i$ 位取反之后只会影响到

[思维]Codeforces1417D【Make Them Equal】题解

题目概述CF1417D解题报告本来已经会做了，但是我把小根堆写成大根堆然后暴毙了QAQ……我们发现 $a_1$ 可以随意向其他位置分配，因此我们考虑将其他位置都

[斜率优化+cdq分治]HDU3842【Machine Works】题解

题目概述HDU3842解题报告先按 $D$ 排个序，然后不难想到DP（注意，根据题目要求 $f_j$ 必须 $\ge 0$ ）：$$ f_i=\max\{f_j

[线段树]ACL Beginner Contest E【Replace Digits】题解

题目概述ACL Beginner Contest E解题报告不知道各位数学课上有没有求过这个数列的通项公式……$$ 9,99,999,9999,\cdots $

[cdq分治+动态凸包]HDU5127【Dogs' Candies】题解

题目概述HDU5127解题报告我们分析在甜度热爱为 $x$ ，酸度热爱为 $y(y>0)$ 时，$A(p_1,q_1),B(p_2,q_2)(p_1<

[动态凸包]Codeforces70D【Professor's task】题解

题目概述动态加点维护凸包，每次询问 $(x,y)$ 是否在凸包中。解题报告终于写了下动态凸包……其实就是用set维护凸包中的点，动态做Andrew算法。我用的是

[思维+倍增]ACL Contest 1D【Keep Distances】题解

题目概述ACL Contest 1D解题报告根本不会做，我来翻译原题解了QAQ。如果要求的是 $[L,R]$ 中最长的good set，我们直接 从 $L$ 开

[思维+最大费用最大流]ACL Contest 1C【Moving Pieces】题解

题目概述ACL Contest 1C解题报告这题还是挺可做的，首先考虑棋子之间拦路的问题，在一颗棋子穿过了另一颗棋子时，我们可以认为两颗棋子互换位置，显然移动次

[扩展欧几里得]ACL Contest 1B【Sum is Multiple】题解

题目概述求最小 $k$ 使得 $k(k+1)\over 2$ 是 $n$ 的倍数。解题报告AC的题太难了，我全都不会做 😭 。移下项：$k(k+1)\equi

[二分+后缀数组]HDU2328【Corporate Identity】题解

题目概述HDU2328解题报告首先将所有串中间隔开接起来（注意中间隔开的字符不能相同）。二分枚举答案 $len$ ，然后根据 $Height$ 数组分块，每个块

[后缀数组]HDU3518【Boring counting】题解

题目概述HDU3518解题报告枚举子串的长度 $len$ ，然后将后缀数组按照 $Height\ge len$ 分块，每个块中检查最左和最右的子串是否交叉就行了

两种常见的树上差分

树上差分忘完了……康复一下。记 $x$ 节点的父亲为 $fa(x)$ 。记 $x,y$ 节点的LCA为 $lca$ 。记权值数组为 $w_x$ ，差分数组为 $

[拉格朗日插值]Codeforces622F【The Sum of the k-th Powers】题解

题目概述求 $f(n,k)=\sum_{i=1}^{n}i^k$ 。解题报告我们知道 $f(n,k)$ 的公式可以由组合数推导，并且由推导方式可知 $f(n,k

[DP+单调栈+线段树动态开点]Codeforces1407D【Discrete Centrifugal Jumps】题解

题目概述有 $n$ 个建筑物，高度 $h_i$ 。要从 $1$ 跳到 $n$ ，求最少跳跃步数。$i\to j$ 的跳跃要求：$i+1=j$$\max(h_{i

[思维]Codeforces1407C【Chocolate Bunny】题解

题目概述交互题。有一个 $1\sim n$ 的排列 $\{p_n\}$ ，每次可以询问 $(x,y)$ ，得知 $p_x\bmod p_y$ 。在 $2n$ 次

拉格朗日插值

求多项式我们知道 $n$ 个点可以确定 $n-1$ 次多项式（比如三点求抛物线）。假设 $f(x)=\sum_{i=0}^{n-1}a_ix^i$ ，如果我们要

天池超级码力在线编程大赛初赛第1场 题解

太久没打比赛，手感极差，而且题意问题导致我T3 WA了 :tieba17: 。比赛链接1.树木规划二分+DP。#include<cstdio> #i

吐槽浙江省满分作文背后的阅卷组

起因8月初，网上疯传了一篇浙江省满分作文《生活在树上》，我父母也是立刻给我分享了这篇文章。然而，和大部分人一样，我草草看了第一遍，就发现读不懂文字。对，不是文章

康复训练

准备打ACM了，进行康复训练。洛谷P1045 麦森数快速幂+高精度，因为要的是最后500位，所以只存500位就行了。[panel title="示例程序"]#i

逃离高三 | 2020年7月浙江省高考&选考游记

[Meting][Music title="君の銀の庭" author="Kalafina" url="/usr/uploads/2020/07/3811365

写在高考前一个月

[Meting][Music server="netease" id="1440936344" type="song"/][/Meting]回校之后的两个月原本

让Typecho文章加密兼容PJAX

问题Typecho自带了文章加密（给文章设置访问密码），但是存在奇怪的bug，以及不兼容PJAX。由于加密文章返回403状态码，所以无法PJAX跳转页面。存在多

A Hymn To Playful Students - 献给颓废生的圣歌

[Meting][Music server="netease" id="25539263" type="song"/][/Meting]前言起源纵使遭受了家长老

对网课和高考的一些思考

下文均为作者个人观点，如果感到厌恶请不要继续阅读，请不要对我的观点进行恶意抨击。回望网课也算是告一段落了，我终于要回学校了。网课期间我并没有好好学习，颓得很愉快

吐槽年级组拍脑袋的决策

负能量爆棚警告，请谨慎观看！！！这一切的一切都要从家中早读开始说起……现在上网课，年级组要求在家中早读也可以理解，虽然心里不是很情愿，但是督促下学习也不错，至少

MDUI2333 - 基于MDUI的单栏typecho主题

MDUI2333这是一款基于MDUI的typecho主题。它并不是为了纯粹的美观而设计出来的产物，它甚至有些随意，您可以从它的起名和logo看出作者并没有花费较

2020年1月浙江省选考游记

[Meting][Music server="netease" id="39227637" type="song"/][/Meting]考前考前停课的时候回归课

游戏记录 | Undertale

[Meting][Music server="netease" id="365158027" type="playlist"/][/Meting]入坑大概在B站

Typecho输出评论骚操作

[Meting][Music server="netease" id="39224651" type="song"/][/Meting]可能是没啥用的骚操作QA

魔改Links插件实现友链随机输出

一时兴起逛MonsterX博客的时候发现了友链随机输出的这个方式，我觉得的确挺不错的，于是开始折腾。研究了一下Links插件发现……并不能在不改动插件的情况下实

游戏记录 | 星之卡比 梦之泉DX

前言星之卡比补全计划，就从梦之泉DX开始啦。梦之泉DX应该是很多人的童年（包括我），但实际上这个GBA版本是FC版的重置版，至于FC版我还没有玩过，之后应该也会

机房大佬语录API | PHP编写API入门

2020.2.24UPD：之前这篇文章是一篇毫无意义的水文……现在重新写过了，记录了一点PHP编写API的入门知识。机房大佬语录：“” $.ajax({

自定义MDUI2333的评论表情框

吐槽由于网友的鞭策……我决定处理一下这个大坑……本来想做个插件，发现根本没有教程……所以就使用了常规的Json版配置。配置指南图示下面的某些参数所在位置可以在这

高二下的这半个学期

啊暑假第一天……修仙是必须要修仙的……说说退役后的半个学期内的划水状况。期末考试前语文课：一如既往地听不懂。数学课：起码还是能听懂的。英语课：一如既往地划水，被

在PJAX的基础上使用AJAX评论等功能

终于把AJAX评论搞好了QwQ，效果可以在这篇文章下面评论试试（所以在本页可以随意划水2333333）。AJAX评论方法1：AJAX提交评论2020.2.16

游戏记录 | Hollow Knight

入坑我吹爆空洞骑士！最开始是看到JZ和WYX在打这个游戏，我发现画面非常萌（并不）就草草入坑了。开始打的时候我才发现一点都不萌……这是个硬核动作游戏，地图十分复

AFO | OI生涯回忆录

[Meting][Music server="netease" id="139774" type="song"/][/Meting]二试翻盘失败啦，AFO。作为

ZJOI2019 Round2 告别记

[Meting][Music server="netease" id="1301395546" type="song"/][/Meting]Day [-n,-2

[KDT+DP]BZOJ1171【大sz的游戏】题解

题目概述有 $n$ 个基地，每个基地可以发射和接收 $[x_i,y_i]$ 频率内的信号，坐标为 $l_i$ ，且 $i$ 号基地只能往前发射到距离不超过 $L

[线性筛+除法分块]BZOJ4407【于神之怒加强版】题解

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd^K(i,j)$ 。解题报告水题吧……先用莫比乌斯函数处理一下：$$ \sum_{d

[KDT]BZOJ4066【简单题】题解

题目概述单点加，矩阵求和，强制在线。解题报告强制在线还卡空间，所以我们用KDT吧QAQ！每个节点记录一下控制区域和控制区域内的和，每次查询的时候不停找和询问区域

[KDT]BZOJ2648【SJY摆棋子】题解

题目概述维护一个点集，有两种操作：1.加入一个点。2.询问 $(x,y)$ 到点集中曼哈顿距离最小值。解题报告KDT入门可以看这里。KDT玄学玩意……我没写重构

[DP]BZOJ4321【queue2】题解

题目概述求不存在 $|a_i-a_{i+1}|=1,i<n$ 的 $n$ 的排列 $\{a_n\}$ 的个数。解题报告定义 $f_{i,j,0/1}$ 表

CodeChef April Challenge 2019 Division 2

上次打完之后分数还是不够Div1……只能再打Div2。UPD：这次打完分数还是不够QAQ。Maximum Remaining去重后第二大。#include<

[主席树+哈希]HackerRank(101 Hack 49)【Sorting Lists】题解

题目概述有 $n$ 条线段 $(a_i,b_i)$ ，定义 $C(i)$ 表示包含 $i+{1\over 2}$ 的有序线段列表，求字典序第 $K$ 小的 $C

[单调栈+线段树]HackerRank(101 Hack 50)【Boxes for Toys】题解

题目概述有 $n$ 个箱子，每个箱子的长宽高为 $(a_i,b_i,c_i)$（可以任意旋转），把 $[l,r]$ 的箱子装入一个大箱子需要满足区间内任意的箱子

[状压DP+复杂度优化]BZOJ4197(Noi2015)【寿司晚宴】题解

题目概述把 $[2,n]$ 分成两半（不需要全部选），求两边不存在不互质的数的方案数。解题报告如果素数个数少的话可以直接状压 $f_{s,t}$ 表示第一组的素

数据结构水题选讲(By AwD)部分题解

课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也

[DP套DP+期望]LOJ3042(ZJOI2019)【麻将】题解

题目概述解题报告考试的时候看到这种题只能想不到+打不出来……一道SB剪枝我没加然后就只有暴力分 $20$ 了……一副牌怎么样能胡？1.选出一种牌当对子，剩下的牌

[DP]Codeforces1110D【Jongmah】题解

题目概述有 $m$ 种牌共 $n$ 张，求最多组成多少面子（即顺子 $i,i+1,i+2$ 或者刻子 $i,i,i$ ）。解题报告题目名称是将麻可还行……CF泄

[DP套DP]HDU4899【Hero meet devil】题解

题目概述给出长度为 $m$ 的基因串 $S$ ，对于每个 $i$ 求有多少个长度为 $n$ 的基因串 $T$ 使得 $LCS(S,T)=i$ 。解题报告DP套D

[线段树]LOJ3043(ZJOI2019)【线段树】题解

解题报告ZJOI又双叒叕出线段树，我又双叒叕没做出来。Orz%%%zhouzhendong。定义 $f_{i,0} $ 表示线段树节点 $i $ 没有标记，但是

[杜教筛+Min_25筛]LOJ572(LibreOJ Round #11)【Misaka Network 与求和】题解

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{n}f^K[gcd(i,j)]$ ，其中 $f(n)$ 表示 $n$ 的次大质因子（相同质因子

[Min_25筛]UOJ188(UR #13)【Sanrd】题解

题目概述求 $\sum_{i=L}^{R}f(i)$ ，$f(n)$ 表示 $n$ 的次大质因子（相同质因子算多次），若次大质因子不存在则 $f(n)=0$ 。

[二次剩余+BSGS]CodeChef(FN)【Fibonacci Number】题解

题目概述求最小的 $n$ 使得 $fib_n\equiv C(mod\ P)$ 。解题报告模板题调这么久我是不是没救了……题目要求：$$ {1\over\sqr

[Min_25筛]LOJ6053【简单的函数】题解

题目概述定义积性函数 $f(n)$ 满足 $f(p^k)=p\ xor\ k$ ，求 $\sum_{i=1}^{n}f(i)$ 。解题报告不难发现除了 $f(2

Min_25筛

一类问题已知积性函数 $f(n)$ ，其中 $f(p)$ 是简单多项式，且 $f(p^k)$ 可以快速计算（ $p$ 是素数），求其前缀和。上杜教筛？如果 $f

ZJOI2019 Round1 退役记

Day [-n,-2]天天考试，天天爆炸+被学弟吊打。Day -1在家休息（颓废）了一天，下午去找放学了的同学打了下乒乓球。内心虚的一批，和同学聊了下未来规划发

[广义SAM]BZOJ3926(Zjoi2015)【诸神眷顾的幻想乡】题解

题目概述有一棵 $n$ 个节点的树，每个节点有一个字符。定义一条路径 $(x,y)$ 形成的字符串为从 $x$ 走到 $y$ 路径上所有字符按顺序接起来形成的字

[思维+区间DP]BZOJ4574(Zjoi2016)【线段树】题解

题目概述有一个序列 $\{a_n\}$ ，定义一次操作 $[L,R]$ 表示将 $[L,R]$ 中的数改成 $[L,R]$ 中的最大数。现在要进行 $q$ 轮，

[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解

题目概述有 $n$ 棵树和 $m$ 个操作，操作有：1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $

[容斥+三元环]BZOJ5407【girls】题解

题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪，但是三个妹子之间不能有冲突，一种方案 $(i,j,k),i<j<k$ 的贡献为：$Ai+

[思维+第二类斯特林数]BZOJ5413【color】题解

题目概述用 $K$ 种颜色对 $n\times m$ 的网格进行染色，需要保证无论怎么样纵切将棋盘分为左右两个部分， 两个部分的颜色种类数都必须相等，求方案数。

[第一类斯特林数+广义容斥]BZOJ5406【Gift】题解

题目概述定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列，有些位置还没有确定，求相似度为

[思维+组合+NTT]LOJ6261【一个人的高三楼】题解

题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告就是这题套个NTT，水博客真开心。可能略有卡常……示例程序#incl

[bitset+树链剖分+线段树+霍尔定理]BZOJ5404【party】题解

题目概述有 $n$ 个点的有根树，每个节点只能往上走，且每个节点有一个特产。现在有 $q$ 个询问，每次询问 $c$ 个点，求这些点走到他们的公共祖先，在满足：

[后缀平衡树]BZOJ5084【hashit】题解

题目概述给出一个操作串：如果是小写字母，表示在当前字符串后面添加这个小写字母。如果是 $−$ ，表示删除当前字符串最后的小写字母（保证合法）。求每次操作后当前字

[思维+组合]Codeforces223C【Partial Sums】题解

题目概述给出一个数组，求这个数组的 $k$ 次前缀和（前缀和的前缀和的前缀和……）。解题报告可能大力找规律就可以很快做出来？不过我们可以考虑这个东西的组合意义，

[霍尔定理+复杂度分析+贪心+线段树]Codeforces533A【Berland Miners】题解

题目概述有 $n$ 个点带点权的树和 $m$ 个物品，一个物品能放在树上一个节点的条件是树上这个节点到根路径上点权最小值大于等于这个物品的权值。现在能够把一个点

[二分图+矩阵树定理]LOJ6044(雅礼集训 2017 Day8)【共】题解

题目概述有 $n$ 个点的树，$1$ 为根，每个节点的深度定义为到根的点数。求深度为奇数的点恰好为 $K$ 的树的个数。解题报告emm……我们把树按照深度奇偶分

[思维]Codeforces632F【Magic Matrix】题解

题目概述有 $n\times n$ 的矩阵 $a$ ，判断该矩阵是否满足：1. $a_{i,j}=a_{j,i}$ 。2. $a_{i,i}=0$ 。3. $\

[DP]Codeforces660E【Different Subsets For All Tuples】题解

题目概述求长度为 $n$ ，元素值域为 $[1,m] $ 的所有序列的本质不同子序列的个数的和。解题报告不难发现长度为 $i$ 的子序列的出现次数是相同的，所以

CodeChef March Challenge 2019 Division 2

像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。Chef and Number Game最优解只能是正负分两半。#include

[最大费用可行流]BZOJ5403【marshland】题解

题目概述有 $n\times n$ 的网格，如果 $(i,j)$ 满足 $i+j$ 是奇数那么这个格子就有危险度，现在可以放 $m$ 个占地为 $3$ 的 $L

[思维]BZOJ5401【s】题解

题目概述有 $n\times n$ 的网格，每次可以选择一个 $m\times m(m={n+1\over 2})$ 的子网格将数字进行取反，求最大数字和。解题

[模拟退火]BZOJ2428(HAOI2006)【均分数据】题解

题目概述把 $n$ 个数分成 $m$ 份，求最小的均方差 $\sqrt{\sum_{i=1}^m(sum_i-ave)\over m}$ ，其中 $ave={\

[模拟退火]BZOJ3680【吊打XXX】题解

题目概述有 $n$ 个砝码，第 $i$ 个砝码在 $x_i,y_i$ ，重量为 $w_i$ 。现在把所有砝码绑在一起，求绳结平衡在哪个位置。解题报告玄学大法模拟

[wqs二分+贪心+DP]BZOJ5400【y】题解

题目概述有 $n-1$ 座城市，$n$ 个乡村，每个城市有一条公路和一条铁路连进来（乡村没有连进来的路），每个乡村有参数 $a_i,b_i,c_i$ ，如果乡村

[奇技淫巧]LOJ152【乘法逆元 2】题解

题目概述有 $n$ 个数 $a_i$ ，求每个数的逆元。解题报告$O(n)$ 求 $n$ 个数逆元？？？Orz WA自动机，感觉这个技巧非常有用，帮助我解决了C

[指数型生成函数+倍增+NTT]BZOJ5381【or】题解

题目概述求多少序列 $\{A_n\},A_i\in[1,2^K)$ 满足 $B_1=A_1,B_i=B_{i-1}\ or\ A_i$ 的序列 $\{B_n\}

[BFS]HHHOJ208【圈地游戏】题解

解题报告题目里已经告诉我们怎么判断宝藏和陷阱是否被圈起来了……由于只和奇偶性有关，所以可以状压：$f_{x,y,A,B}$ 表示目前在 $(x,y)$ ，宝藏的

[凸包]HHHOJ222【简单题】题解

解题报告我不会“简单题”.jpg。可以考虑从 $(a,b)$ 到 $(c,d)$ 的两种走法：先上再右 $A_a(c-a)+B_d(d-b)$ 以及先右再上 $

[贪心+树形DP]LOJ6042(雅礼集训 2017 Day7)【跳蚤王国的宰相】题解

题目概述给出一棵 $n$ 个节点的树，求每个点成为与其他点距离和最小点最少需要删除并加上的边数 $k$（新加边之后依然是一棵树）。解题报告我根本发现不了性质.j

[划水]LOJ6513(雅礼集训 2018 Day10)【足球大战】题解

题目概述这题太水了，鸽了。解题报告这题太水了，鸽了。答案就是 $\sum_{i=1}^{n}{n\choose i}p^i(1-p)^{n-i}\sum_{j=

[指数型生成函数+分治NTT+广义容斥]LOJ6503(雅礼集训 2018 Day4)【Magic】题解

题目概述有 $n $ 种颜色的膜法卡，每种颜色有 $a_i $ 种，总共有 $m $ 张。现在要把所有卡片排成一排，如果相邻两个卡片颜色相同则产生一个膜法对，求

[思维+LCT]TopCoder【TreeColoring】题解

题目概述有 $n$ 个点的带边权树和 $m$ 次操作，每次操作：1.将一个点变成黑色。2.求 $x$ 到所有黑色点的距离。解题报告好像可以大力点分树……我没有想

[复杂度分析]LOJ6043(雅礼集训 2017 Day7)【蛐蛐国的修墙方案】题解

题目概述给出一个 $n$ 的排列 $\{p_n\}$（满足 $i\not=p_i$ ），求一个括号序列满足：1.是合法的括号序列。2.对于所有左括号 $i$ ，

[DP]LOJ6501(雅礼集训 2018 Day4)【Cube】题解

题目概述定义 $0$ 维基础图形为点，$1$ 维基础图形为边，$2$ 维基础图形是正方形，$3$ 维基础图形是正方体，以此类推。问 $n$ 维基础图形由多少个

[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解

题目概述原来有 $n $ 个点的一棵树，现在加进了 $K $ 条边。问多少种方案删边使得图依然连通。解题报告非正解警告……接下来要讲的是原题解中的算法七，不过这

[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解

题目概述给出一个 $n\times m$ 的巧克力，每个位置有形状和美味值，求一个个数最小的连通块满足形状数 $\ge K$ ，且在个数最小的前提下，美味值的中

[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解

题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下

[斯坦纳树+随机]HHHOJ200【稗田的梦中之梦】题解

解题报告题目里要我们找出的实际上是一个满足条件的连通块，又因为数据范围这么小，所以想到斯坦纳树来做这种连通块最小值问题。令 $f_{i,j,s}$ 表示 $i,

[斯坦纳树]BZOJ2595(Wc2008)【游览计划】题解

题目概述在 $n\times m$ 的网格上有 $k$ 个景点，选取每个网格都有代价，求最小代价使得景点之间全部连通。解题报告感觉这个东西好mogical啊……

[期望的线性性+概率DP]TopCoder【RockPaperScissors】题解

题目概述有 $n$ 个骰子，每个骰子投出剪刀、石头、布的概率已知。现在每次随机拿出剩余骰子中的一个进行投掷（并不知道这个骰子的概率分布），投完后扔掉。你要出 $

[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解

题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。

[霍尔定理+主席树+复杂度分析+DP]HHHOJ197【古明地】题解

解题报告题解里有个很厉害的 $O((n+s)log_2n) $ 做法，但是我不会……我只会这种比较好想的做法。首先这明显是一个二分图完全匹配问题，我们可以把每项

[单调栈+DP]Codeforces1131G【Most Dangerous Shark】题解

题目概述有 $n$ 个骨牌，每个骨牌有高度和推倒代价，骨牌可以往左往右推倒，如果两个骨牌的距离小于推倒骨牌高度那么就会向同一个方向倒下，求最小代价使得所有骨牌都

[线段树+矩阵快速幂]Codeforces446C【DZY Loves Fibonacci Numbers】题解

题目概述有两种操作：1.将 $a_i,i\in[L,R]$ 加上 $fib_{i-L+1}$ 。2.求 $\sum_{i=L}^{R}a_i$ 。解题报告水Bl

[思维]HHHOJ189【Garrafeira】题解

解题报告陈老师的题解和没讲一样……考虑每一个二进制位的贡献，发现只要存在 $a_i$ 有 $j$ 这个二进制位，这个二进制位就有 $2^{n-1}2^{j}$

[贪心]Codeforces1131E【String Multiplication】题解

题目概述定义字符串 $A$ 和 $B$ 的乘法 $A\times B$ 的结果为将 $B$ 插入 $A$ 的每个空隙中（包含两端），给出 $n$ 个串，求按顺序

[二维偏序+三维偏序]HHHOJ183【Drinks】题解

解题报告很明显至多选 $3$ 个就能构成一种方案，所以我们只需要考虑选 $1,2,3$ 个的情况就行了。考虑不合法的情况，即物品之间有包含的情况，如：1 1 1

[除法分块+杜教筛]HHHOJ173【B】题解

解题报告重新看一遍发现这题十分斯波……我们要求的是：$$ \sum_{\{a_k\}}e[(a_1,a_2,\cdots,a_k)]\\ \sum_{\{a_k

[点分治]HHHOJ174【C】题解

解题报告摆明了要你点分治……每次统计 $x$ 子树的时候记录两个值：到 $x$ 路径最大值和到 $x$ 路径点权和。按照最大值排序之后，枚举 $i$ ，只要看前

[STL乱搞+压位]BZOJ5087【Polycomp】题解

题目概述给出 $f(x),g(x),h(x)$ ，求 $f(g(x))\ mod\ h(x)$ ，系数在 $mod\ 2$ 意义下。解题报告直接就有一个 $O(

[IDDFS]HHHOJ110【布加勒斯特的人偶师/Bucureşti】题解

解题报告考虑决策树，每次枚举操作，根据返回的结果把符合当前状态的排列分成三份（当然如果符合当前状态的只有 $1$ 个排列就不需要继续分了），我们要做的是把决策树

[多项式+牛顿二项式定理]HHHOJ108【爱丽丝/Alice】题解

解题报告题目中显然给出了一个卷积形式，所以我们移下项，凑凑常数，得到：$$ {A(x)-A_0\over x}-A_1=A(x)A(x)-A_0^2\\ A(x

[第二类斯特林数+NTT]BZOJ5093(Lydsy1711月赛)【图的价值】题解

题目概述一个 $n$ 个点的简单无向图的价值定义为每个点度数 $K$ 次方的和，求所有 $n$ 个点的简单无向图的价值的和。解题报告只需要知道这两个前置姿势，这

[第一类斯特林数+倍增+NTT]Codeforces960G【Bandit Blues】题解

题目概述求有多少 $n$ 的排列满足从左边会更新 $A$ 次最大值，从右边会更新 $B$ 次最大值。解题报告第一类斯特林数：$s(n,k)$ 表示把 $n$ 个

[多项式多点求值]洛谷5050【多项式多点求值】题解

题目概述给出一个多项式 $F(x)$ ，有 $m$ 个询问，每次求 $F(a_i)$ 。解题报告将 $F(x)$ 在 $x=a$ 处进行泰勒展开：$$ F(x)

[多项式exp]洛谷4726【多项式指数函数】题解

题目概述求 $B(x)=e^{A(x)}\ mod\ x^n$ 。解题报告前置姿势：多项式求逆，多项式ln。第一种方法是两边求导：$$ B'(x)=e^{A(x

[生成函数+多项式开根+多项式求逆]Codeforces438E【The Child and Binary Tree】题解

题目概述求用集合 $S$ 中的点权构造点权和为 $[1,m]$ 的二叉树的方案数。解题报告生成函数什么的好大啊，我好菜啊。令 $C(x)$ 表示所有点权的生成函

[指数型生成函数+多项式ln]BZOJ3456【城市规划】题解

题目概述求 $n$ 个点简单无向连通图的个数。解题报告我感觉好像重新学了一遍指数型生成函数的样子……普通型生成函数解决的是组合问题，而指数型生成函数解决的是排列

[多项式ln]洛谷4725【多项式对数函数】题解

题目概述求 $B(x)=lnA(x)(mod\ x^n)$ ，即满足 $A(x)=e^{B(x)}$ 。解题报告前置姿势：多项式求逆，多项式求导，多项式积分。多

[多项式除法]洛谷4512【多项式除法】题解

题目概述给出多项式 $A(x),B(x)$ ，求 $C(x),D(x)$ 满足 $A(x)=C(x)B(x)+D(x)$ 。解题报告显然求出 $C(x)$ 或

[多项式开根]洛谷5205【多项式开根】题解

题目概述给出一个多项式 $A(x)$ ，求 $B(x)$ 使得 $B^2(x)\equiv A(x)(mod\ x^n)$ ，保证 $A(x)_0=1$ 。解题

杂七杂八的整理

2023.4.22：ACM也退役力，不再更新。奎若小哥镇楼！ヾ(≧∇≦*)ゝ！！！因为首页摆着很多置顶文章感觉很奇怪而且看不到新文章了QAQ。于是就整理了一些

[插头DP]BZOJ2331(SCOI2011)【地板】题解

题目概述有 $n\times m$ 的客厅，要用 $L$ 型地板覆盖整个客厅，求方案数。解题报告棋盘覆盖问题，$min\{n,m\}\le 10$ ，想到插头D

[插头DP]BZOJ1814(Ural 1519)【Formula 1】题解

题目概述给出 $n\times m$ 的网格图，其中有些格子是障碍，求有多少种方法用一条哈密顿回路覆盖没有障碍的格子。解题报告ps：大量图片来自于cdq的课件Q

[插头DP]HDU1693【Eat the Trees】题解

题目概述给出 $n\times m$ 的网格图，其中有些格子是障碍，求有多少种方法用若干个哈密顿回路覆盖没有障碍的格子。解题报告万年神坑插头DP，插头DP可以解

Typecho如何输出根据文章数量改变字体大小和颜色的标签云

这是我的Blog里第一篇技术向的文章，有点小激动QwQ（并不）。Hexo里那种可以根据文章数量改变字体大小和颜色的标签云我一直很喜欢：但是Typecho关于这方

[凸包]HHHOJ166【蚂蚁】题解

解题报告可能是沙雕题，但是我又做不来又写不来QAQ。只要求出所有直线的凸包（分界点），就可以分类讨论树上倍增搞了。注意分界点相同标号的大小问题，处理不好就会GG

[树状数组套线段树]HHHOJ165【归并排序】题解

解题报告这题好像挺水的……手玩下会发现如果两个相邻元素没有正确排序，那么他们就会在最终序列里并起来。比如：4 1 3 2 -> (4 1) (3 2) -

[期望的线性性+概率DP]HHHOJ164【排列统计】题解

解题报告其实不用管期望……只要算出总贡献然后最后除以 $(n^2)^k $ 就行了（Manchery：期望就是层壳），不过也可以利用期望的线性性把期望转成概率。

[扩展Min-Max容斥+DP]洛谷4707【重返现世】题解

题目概述有 $n$ 种物品，每单位时间出现 $i$ 物品的概率为 $p_i$ ，求恰好出现 $K$ 个不同物品的期望时间。解题报告Min-Max容斥？但是出现

[DP+广义容斥]BZOJ3622【已经没有什么好害怕的了】题解

题目概述有 $n$ 个带权糖果和 $n$ 个带权药片，求一一配对后糖果权值大于药片权值比药片权值大于糖果权值对数多 $K$ 的方案数。解题报告emm……我刚开始

[Min-Max容斥+树上解方程]LOJ2542(PKUWC2018)【随机游走】题解

题目概述有一棵树，刚开始你在 $X $ ，每次随机走到相邻的点。有 $q $ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。解题报告不难想到Mi

[容斥+二项式反演]BZOJ2839【集合计数】题解

题目概述有一个 $n$ 个元素的集合，求选出若干个子集（不可以不选）相交后元素个数刚好为 $K$ 的方案数。解题报告学Min-Max容斥的时候没有考虑过怎么构造

[Min-Max容斥+高维前缀和]BZOJ4036(HAOI2015)【按位或】题解

题目概述我写过了来着，鸽了。解题报告用Min-Max容斥再做一遍这题，学习自memset0。Min-Max容斥，对于一个集合 $S$ ，他的最大值 $max(S

PKUWC2019没约记

Day [-n,-2]填了一堆算法坑（然后都没有用到）。Day -1从13:00跑图到22:00。Day 0下午报到，试机的时候发现是Win7，里面真的是应有尽

[BSGS+矩阵求逆]BZOJ4128【Matrix】题解

题目概述给出矩阵 $A,B$ ，求最小的 $x$ 满足 $A^x\equiv B(mod\ p)$ 。解题报告哇 $A^x\equiv B(mod\ p)$ ，

[三元环计数]HDU6184【Counting Stars】题解

题目概述给出一张无向图，求 $4$ 个点构成两个有公共边的三元环的方案数。解题报告填坑填坑，如果我们知道每条边所在的三元环个数 $num_i$ ，那么 $\su

[伯努利数+拆系数FFT+多项式求逆]51Nod1258【序列求和 V4】题解

题目概述求 $\sum_{i=1}^{n}i^K,K\le 50000$ 。解题报告同51Nod1228，只不过 $K\le 50000$ 所以不能 $O(K^

[伯努利数]51Nod1228【序列求和】题解

题目概述求 $\sum_{i=1}^{n}i^K$ 。解题报告这个东西可以用二项式定理和组合数 $O(n^2)$ 递推来着，但是 $n$ 太tm大了，不过 $K

[FMT]WC2018【州区划分】题解

解题报告搜FMT搜到这道题，其实我都想到怎么做了……结果以为自己解法是错的就没写了……FMT除了集合并卷积之外还有一个经典应用就是子集卷积，他是这样的：$$ h

[FMT]BZOJ4036(HAOI2015)【按位或】题解

题目概述刚开始 $x$ 为 $0$ ，每秒会产生一个 $[0,2^n)$ 的随机整数使 $x$ 或上这个数，生成 $i$ 的概率为 $p_i$ ，问 $x$ 变

[cdq分治+NTT]洛谷4721【分治 FFT】题解

题目概述给出 $g$ 以及 $f(0)=1$ ，求：$f(i)=\sum_{j=1}^{i}f(i-j)g(j)$ 。解题报告其实我是想学分治+NTT来着的，结

[贪心]NOIP2018Day2【旅行】题解

解题报告树的情况直接贪心做，基环树枚举环上的边断开然后贪心做。乱优化代码害人不浅，少 $20$ 分送我爆炸。测评鸭上面有 $O(n)$ 加强版，大佬们可以去切啊

[矩阵树定理]BZOJ4894【天赋】题解

题目概述有 $n$ 个技能，每个技能有一些前置技能，现在 $1$ 技能已学习，求学完所有技能的方案数。解题报告矩阵树定理求有向图中外向树和内向树的个数：外向树：

[莫比乌斯函数+线性筛]BZOJ3309【DZY Loves Math】题解

题目概述令 $f(x)$ 表示 $x$ 质因数分解之后最大的次幂，$m$ 次询问，每次求 $\sum_{i=1}^{A}\sum_{j=1}^{B}f[(i,j

[矩阵树定理]BZOJ4766【文艺计算姬】题解

题目概述求二分图 $K_{n,m}$ 的生成树个数。解题报告我骗我自己：$A+B=d(dA+dB)$ ，导致我做不出来。二分图的基尔霍夫矩阵的一个主子式长这样（

[矩阵树定理]BZOJ4031(HEOI2015)【小Z的房间】题解

题目概述有 $n\times m$ 的网格，每个网格是房间或者柱子，周围都有墙，问打破墙使得房间连成一棵树的方案数。解题报告矩阵树裸题，问题是行列式取模，因为不

[矩阵树定理]SPOJ(HIGH)【Highways】题解

题目概述给出一张无向图，求生成树个数。解题报告大佬传送门：*ZJ，Candy?。矩阵树定理裸题，先来讲（瞎扯）一波行列式：行列式定义式：$Det(A)=\sum

[原根+NTT+快速幂]BZOJ3992(SDOI2015)【序列统计】题解

题目概述有 $S$ 个数，取 $n$ 次（可重复取），将得到的数乘起来模 $m$ 为 $x$ 的概率。解题报告做过这道题的弱化版……这道题只需要把循环矩乘换成N

[思维+背包]BZOJ5003【与链】题解

题目概述有权值为 $0\sim n$ 的 $n+1$ 个点，如果 $u\ and\ v=v$ 那么 $u$ 有一条到 $v$ 的有向边，现在问点数为 $k$ ，

[点分树]BZOJ1095(ZJOI2007)【Hide 捉迷藏】题解

题目概述有一棵黑白两种颜色的树，两种操作：1.修改一个节点的颜色。2.询问最远的黑点之间的距离。解题报告如果没有修改的话就是裸的点分治，但是有修改的话就凉了……

[第二类斯特林数+多项式求逆]BZOJ4555(Tjoi2016&Heoi2016)【求和】题解

题目概述求 $f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\cdot2^j\cdot j!$ ，$S(i,j)$ 表示第二类斯

[最小割]TopCoder【SurroundingGame】题解

题目概述有 $n\times m$ 的网格，有两种方法占领一个格子：1.花费 $c_{i,j}$ 。2.该格子上下左右的格子已经被占领。占领一个格子之后有 $b

[莫比乌斯函数+线性筛+离线+除法分块+调和级数]BZOJ3529(Sdoi2014)【数表】题解

题目概述有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$ , 计算数

[扫描线+线段树]LOJ6276【果树】题解

题目概述一棵 $n$ 个节点的树，每个节点有颜色，求路径上没有相同颜色的路径个数，每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑，模拟考的时候我疯狂想

[LCT+泰勒展开]LOJ2289(THUWC 2017)【在美妙的数学王国中畅游】题解

题目概述有 $n$ 个点，每个点是一个函数：$sin(ax+b),e^{ax+b},ax+b$ 。有 $4$ 种操作：1.连接 $x,y$ 。2.断开 $x,y

[线段树+复杂度分析]LOJ6507(雅礼集训 2018 Day7)【A】题解

题目概述区间与，区间或，区间最小值。解题报告完了我连吉利线段树裸题都不会做。这种题一般都是考虑差分数组来分析复杂度，如果 $[L,R]$ 与(或)上 $x$ ，

[莫队+STL乱搞]BZOJ4810(Ynoi2017)【由乃的玉米田】题解

题目概述给出一个序列 $\{a_n\}$ 和 $m$ 次询问，每次询问 $[L,R]$ 中是否有两个数相加为 $x$ 或两个数相减为 $x$ 或两个数相乘为 $

NOIP2018挂题记

Day [-n,-2]最近法老的题都好难啊……Day -1本来早上考试，结果到了机房之后说不考了QAQ。那当然是tuituitui啦。Day 0新校区都这么豪华

[启发式分裂]BZOJ4059(Cerc2012)【Non-boring sequences】题解

题目概述判断一个序列是否满足所有子序列都有一个数只出现了一次。解题报告可以用矩形覆盖+扫描线的方法，不过可以像NWERC2017F一样启发式分裂。一个数左边第一

[线性筛+启发式分裂]NWERC2017F【Factor-Free Tree】题解

题目概述如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。解题报告首先有结论：如果

[阈值优化+可持久化Trie+哈希]CodeChef(BINSTR)【Binary Strings】题解

题目概述有一个二进制数序列 $\{A_n\}$ ，现在有 $Q$ 个询问，每次询问 $(L,R,X)$ 表示询问 $[L,R]$ 中与二进制数 $X$ 异或值最

[欧拉序+树的直径+复杂度分析]CodeChef(MXPATH)【Maximum Tree Path】题解

题目概述有一棵既有点权又有边权的树，求 $max\{dist(u,v)\cdot min(u,v)\cdot gcd(u,v)\}$ ，其中 $dist(u,v

[思维+FFT]BZOJ4259【残缺的字符串】题解

题目概述有两个串 $A,B$ ，有些位置是通配符，求 $A$ 可以在 $B$ 的哪些位置匹配。解题报告早就听说了这题，今天来填坑。判断两个字符串相等可以用式子：

[思维+容斥]51Nod1317【相似字符串对】题解

题目概述字符串对 $(A,B)$ 是相似的需要满足两个串等长，且存在 $C$ 使得 $A+C=C+B$ 。求长度为 $n$ ，出现字母是小写字母前 $K$ 个的

[组合+容斥]PE595【Incremental Random Sort】题解

解题报告抄题解时间到，令 $f(i)$ 表示长度为 $i$ 的答案，则可以得出这样的方程：$$ f(1)=0,f(i)=\sum_{j=2}^{i}[f(j)+

[记忆化搜索]NOIP2017Day1【逛公园】题解

解题报告吃我一记万年神坑。考场上我想到了 $f_{i,j}$ 表示到 $i$ 点比最短路多 $j$ 的方案数，但是我不会转移，写了玄学转移骗了60。不会转移？记

[状压DP]NOIP2017Day2【宝藏】题解

解题报告吃我一记万年神坑。去年考场上做这题的时候一直在想二进制状压，现在回头看看那时候的自己真是蠢爆了。很明显可以三进制状压 $f_{i,s}$ 表示深度为 $

[思维]liu_runda NOIP模拟题【斯诺】题解

解题报告补集转化，则统计有数超过区间一半的区间的个数，由于是超过区间一半所以只会是 $012$ 中的一个。分开统计 $012$ ，考虑前缀和，其实就是个逆序对问

[wqs二分套wqs二分]Codeforces739E【Gosha is hunting】题解

题目概述有 $n$ 个物品，可以用两种方式获得（可以一起用，一种获得了即可），两种方式成功的概率分别为 $a_i,b_i$ ，第一种方式可以用 $A$ 次，第二

[哈夫曼树]BZOJ4198(Noi2015)【荷马史诗】题解

题目概述有 $n$ 个单词，要给每个单词对应一个 $k$ 进制数，使得所有单词变为 $k$ 进制数之后接起来长度最小，并且满足在长度最小的前提下最长 $k$ 进

[思维+DP]AtCoder Grand Contest 022E【Median Replace】题解

题目概述有一个长度为奇数的 $01$ 串（有些位待定），每次可以把相邻三个合并成 $01$ 中数量多的，求最终能够变成 $1$ 的方案数。解题报告题解好像是大力

[思维]HDU4473【Exam】题解

题目概述令 $f(x)=\sum_{a=1}^{+\infty}\sum_{b=1}^{+\infty}[ab|x]$ ，求 $\sum_{i=1}^{n}f(

[分块+虚树]Codeforces966E【May Holidays】题解

题目概述有一棵树，每个节点有一个权值 $t_i$ 。现在有 $m$ 次操作，每次操作表示一个节点被删除了或被重新添加了，每次操作后统计子树中被删除节点 $>

[贪心+后缀自动机+线段树合并]Codeforces700E【Cool Slogans】题解

题目概述给定一个字符串 $S$ ，要求构造字符串序列 $s_1, s_2, \ldots, s_k$ ，满足任意 $s_i$ 都是 $S$ 的子串，且任意 $i

[莫队+阈值优化+哈夫曼树]Codeforces700D【Huffman Coding on Segment】题解

题目概述给出 $n$ 个数和 $m$ 个询问，每次询问给 $[L,R]$ 中的数进行哈夫曼编码得到的长度总和。解题报告挺强的题，给 $[L,R]$ 中的数进行哈

[边双连通分量]Codeforces700C【Break Up】题解

题目概述给出一张带边权无向图，现在要砍掉最多两条边，使得 $s$ 到 $t$ 不连通，求最小边权。解题报告其实就是考虑 $s$ 和 $t$ 所在的边双连通分量，

[思维]Codeforces700B【Connecting Universities】题解

题目概述一棵 $n$ 个点的树，给出 $2k$ 个关键点，现在要把这 $2k$ 个点组成 $k$ 对，每对的贡献为点之间的距离，求最大贡献。解题报告完全想不到…

[树形DP]liu_runda NOIP模拟题【蚊子】题解

解题报告这题在现在看来好像不是很难啊……把每对蚊子分开考虑，那么就是考虑每个节点作为LCA时的贡献，而每个节点作为LCA时又可以拆成两半处理，这样问题就简化得比

[思维+线性基]BZOJ2115(Wc2011)【Xor】题解

题目概述给出一张有边权的无向图，求从 $1$ 到 $n$ 路径异或最大值，可以重复走点并且可以重复经过 $n$ 。解题报告好妙的题！无向图中的环是可以经过也可以

[原根+循环矩阵快速幂]liu_runda NOIP模拟题【随】题解

解题报告先来介绍一波原根：如果 $\forall i\not=j,g^i\not\equiv g^j\ (mod\ P)$ ，那么 $g$ 是 $P$ 的一个原

[Burnside引理+背包]BZOJ1004(HNOI2008)【Cards】题解

题目概述有 $R$ 张红牌，$B$ 张蓝牌，$G$ 张绿牌。现在给出 $m$ 种洗牌法（把 $i$ 位的放到 $x_i$ 上），如果两套牌可以通过 $m$ 种洗

[BFS+链表]BZOJ1098(POI2007)【办公楼biu】题解

题目概述有 $n$ 个人和 $m$ 条关系 $(x,y)$ 表示 $x$ 和 $y$ 有联系方式。如果两个人没有联系方式就需要在同一个连通块，求出连通块个数和每

[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解

题目概述交互题，有 $n$ 个点，你需要指定每个点的坐标 $(x,y)$ ，每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两

[最短路]Codeforces1064D【Labyrinth】题解

题目概述给出一张地图，有障碍和空地。问从 $(s,t)$ 出发最多往左走 $max_L$ 步，往右走 $max_R$ 步能到达多少点。解题报告翰爷秒了Orz。看

[区间DP]BZOJ1939(Croatian2010)【Zuma】题解

题目概述有 $n$ 个珠子，可以把不少于 $K$ 个同样颜色的连续珠子消去并把两端接起来。现在可以随意加珠子，问最少加多少珠子使得所有珠子都消去。解题报告挺妙的

[Dsu on tree+主席树优化建图+最大流]BZOJ3681【Arietta】题解

题目概述一棵 $n$ 个节点带点权的树，有 $m$ 种取节点的方法，第 $i$ 种 $[L,R,D,T]$ 表示只能取点权在 $[L,R]$ ，$D$ 子树中的

[数位DP+堆]BZOJ3131(Sdoi2013)【淘金】题解

题目概述有 $n\times n$ 的网格，每个格子有 $1$ 块金子，现在处在 $(i,j)$ 的会变到 $(f(i),f(j))$ ，其中 $f(i)$ 表

[KMP-border]BZOJ4974(Lydsy1708月赛)【字符串大师】题解

题目概述如果 $S$ 是 $T$ 重复无数次之后的前缀，那么 $T$ 就是 $S$ 的循环节，现在给出一个串每个前缀 $i$ 的最短循环节 $per_i$ 表示

[划水]CodeChef(SURCHESS)【Chef and Surprise Chessboard】题解

题目概述给出 $n\times m$ 的 $01$ 棋盘，有 $q$ 个询问，每个询问 $k$ 表示能够修改最多 $k$ 个格子的颜色，问能选出的边长最长的 $

[倍增+线性基]BZOJ4568(Scoi2016)【幸运数字】题解

题目概述给出一棵树，求从 $x$ 到 $y$ ，经过的每个点都可以决定异或还是不异或，求能够得到的最大异或值。解题报告倍增+线性基就好啦，复杂度为 $O(60^

[调和级数+DP]Codeforces1047E【Region Separation】题解

题目概述有一棵树，现在要把树分成若干个级别，每个级别是若干个权值加和相等的连通块。第一个级别是所有节点，之后的级别需要满足第 $i$ 个级别中的连通块均在 $i

[倍增+并查集+贪心]Codeforces1059E【Split the Tree】题解

题目概述把一棵有权值的树分成若干条儿子到祖先的路径，每条路径节点个数不能超过 $L$ ，节点权值和不能超过 $S$ ，问最少分成多少路径。解题报告一个不知道正确

[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解

题目概述有一个 $R\times C$ 的网格，其中 $n$ 个格子有资源点，问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化，那么就是用总方案数减

[二分]Codeforces1059D【Nature Reserve】题解

题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定

[Manacher+离线+线段树]2015计蒜之道初赛第三场【商品推荐走马灯】题解

题目概述给出一个序列，一个回文区间的权值是区间权值和，问 $[L,R]$ 中所有回文区间的权值和。解题报告刚开始想用回文自动机 $O(n\sqrt n)$ 暴搞

[BFS序+线段树]HDU5957【Query on a graph】题解

题目概述给一棵基环树，有两种操作：1.将到 $x$ 的距离 $\le K$ 的点权值均加上 $d$ 。2.询问到 $x$ 距离 $\le K$ 的点的权值和。解

[Manacher+DP]BZOJ3790【神奇项链】题解

题目概述有一个字符串，用若干个回文串覆盖该串，回文串可以重叠，问需要的最少的回文串数 $-1$ 。解题报告很容易想到DP $f_i=f_j+1$ 其中以 $i$

[莫队]BZOJ4542(Hnoi2016)【大数】题解

题目概述有一个字符串，现在问这个字符串的一个子串中有多少子串是给出的素数 $p$ 的倍数（ $0$ 也算）。解题报告$10^5$ ？莫队？先把满足条件的子串的式

[期望DP]BZOJ4832(Lydsy1704月赛)【抵制克苏恩】题解

题目概述刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。

[wqs二分+决策单调性]POJ1160【Post Office】题解

题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了

[树形DP]入门BZOJ3004(Noi2016十连测第一场)【访问计划】题解

题目概述有一棵带边权的树，现在要从根节点出发，至少经过所有边一次，可以传送 $K$ 次，代价为 $C$ 。问走回根节点经过的最小边权和。解题报告先考虑把传送换成

[贪心+阈值优化+精度]入门BZOJ3003(Noi2016十连测第一场)【奥义商店】题解

题目概述有 $n$ 个有权值的物品，现在给出若干个询问：$m$ 个颜色，每种颜色有 $c_i$ 个且和为 $n-1$ ，现在要在 $K$ 这个位置选择一个颜色，

[线段树+复杂度分析]Codeforces793F【Julia the snail】题解

题目概述有 $n$ 个点和 $m$ 个传送点 $(l,r)$ 表示可以从 $l$ 传送到 $r$ ，只能往下爬或者传送。问从 $x$ 出发在不超过 $y$ 且不

[生成函数+FFT]计蒜客NAIPC2016E【K-Inversions】题解

题目概述有一个AB字符串，问间距为 $k$ 的BA对有多少，其中 $k\in[1,n-1]$ 。解题报告emm……应该算是生成函数吧？令A的位置的权值为下标，B

[矩阵快速幂]BZOJ4870(Shoi2017)【组合数问题】题解

题目概述求 $\sum_{i=0}^{+\infty}{nk\choose ik+r}$ 。解题报告我好斯波啊……这个式子很明显不可算，应该考虑实际意义，发现就

[可并堆]BZOJ4003(JLOI2015)【城池攻占】题解

题目概述有一棵 $n$ 个节点的树，每个节点有个防御值。有 $m$ 个骑士在树的节点上，如果骑士攻击力大于等于防御值就可以攻占这个节点获得收益并向上攻占，否则凉

[随机堆]BZOJ2333(SCOI2011)【棘手的操作】题解

题目概述加边；单点加；连通块加；整体加；单点询问；连通块最大值；整体最大值。解题报告平衡树启合好像会TLE来着，加边只求最大值就是个可并堆嘛……连通块加打tag

[可持久化Trie]BZOJ3261【最大异或和】题解

题目概述有 $m$ 个操作：1.在末尾添加一个数 $a_{n+1}$ 。2.询问 $max\{a_p\ xor\ a_{p+1}\ xor\ \cdots\

[单调栈+线段树]Codeforces407E【k-d-sequence】题解

题目概述有 $n$ 个数，求最长的子区间使得添加 $K$ 个数，排序之后得到一个公差为 $D$ 的等差数列。解题报告我太斯波了，式子都没仔细看就写了个二分，显然

[二分图增广路+Tarjan]BZOJ2140【稳定婚姻】题解

题目概述有 $n$ 对CP，和 $m$ 对前男女友关系，一对CP（因抢着打隔膜导致电脑爆炸所以）解散之后可能会旧情复燃，导致很多CP都解散。问第 $i$ 对CP

[线段树+复杂度分析]HDU5634【Rikka with Phi】题解

题目概述有一个序列 $\{a_n\}$ ，现在有三种操作：1.令 $i\in[L,R],a_i=\varphi(a_i)$ 。2.令 $i\in[L,R],a_

[二分+树状数组]Codeforces1058F【Putting Boxes Together】题解

题目概述有 $n$ 个物品，第 $i$ 个物品在 $a_i$ ，移动一格需要 $w_i$ 的代价。现在有两种操作：1.把 $w_x$ 变成 $y$ 。2.询问把

[贪心+虚树+状压DP]51Nod1673【树有几多愁】题解

题目概述有一棵树，现在要给这棵树重编号，叶子节点的权值为到根路径的最小值，现在求叶子节点权值的积的最大值，保证叶子节点的个数不超过 $20$ 。解题报告可以想到

[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解

题目概述有 $n$ 个组 $V$ 张票，假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会，令 $S_i$ 表示目前 $i$ 组被钦点了几次，每次

[结论+暴力]Codeforces1041F【Ray in the tube】题解

题目概述一个管道，从一端向另一端发射一条射线，问最多能够经过多少两端指定的点。解题报告可能很斯波……隐约会感觉到有用的发射间距 $d$ 很少……实际上真的很少…

[构造+贪心]Codeforces1041E【Tree Reconstruction】题解

题目概述有一棵树，切掉一条树边后会得到两棵树，求出两棵树中的最大编号，记为 $(x,y)$ 。现在给出 $(\{x_{n-1}\},\{y_{n-1}\})$

[LCT+构造]BZOJ3091【城市旅行】题解

题目概述维护森林，每次询问一条路径 $(X,Y)$ 上任意选出两个点 $(x,y)$ 的路径权值和的期望。解题报告刚开始竟然极其斯波的想成了路径权值和的 $si

[随机+差分]Codeforces799F【Beautiful fountains rows】题解

题目概述有 $m\times n$ 的矩阵，第 $i$ 行的 $[L_i,R_i]$ 是好的。现在要选出 $[A,B]$ 使得在所有行中要么没有好的元素要么有奇

[离线+霍尔定理+线段树]BZOJ2138【stone】题解

题目概述有 $n$ 堆石子，每堆 $a_i$ 个，现在要取 $m$ 次，第 $i$ 次在 $[L_i,R_i]$ 中取 $K_i$ 个（不够 $K_i$ 就取完

[计数]Codeforces1040E【Network Safety】题解

题目概述有 $n$ 个点 $m$ 条边，每个点的点权是 $a_i(0\le a_i\le 2^{K}-1)$ ，现在要把一个点集 $A$ 的点权异或上 $x$

[LCT维护最大生成树+二分图判定]BZOJ4025【二分图】题解

题目概述有 $n$ 个点 $m$ 条边，每条边有个出现时间 $s$ 和消失时间 $t$ ，问每个时刻是不是二分图。解题报告法老给我们上课用的PPT表示：把边加到

[莫比乌斯函数+线性筛求积性函数]BZOJ4804【欧拉心算】题解

题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\varphi(gcd(i,j))$ 。解题报告推式子：$\sum_{T=1}^{n}\l

[KMP-fail树]BZOJ3670(Noi2014)【动物园】题解

题目概述一个字符串，令 $num_{i}$ 表示前缀 $i$ 的长度 $\le{i\over 2}$ 的 $border$ 数量，求 $\prod_{i=1}^

[二分+随机]Codeforces1040D【Subway Pursuit】题解

题目概述交互题，现在要猜一个数 $x$ ，可以询问 $x$ 是不是 $l\le x\le r$ ，但是每次询问完成后 $x$ 会移动一个到距离 $\le K$

[DFS树+差分+二分图判定]BZOJ4424(Cf19E)【Fairy】题解

题目概述CF19E数据加大版。解题报告不能分治+LCT啦。由于只删除一条边所以可以大力分类讨论。先用DFS树+差分求出树边被多少个奇环覆盖以及被多少个偶环覆盖，

[分治+LCT+二分图判定]Codeforces19E【Fairy】题解

题目概述有 $n$ 个点 $m$ 条边，问有多少边删除了之后让原图是二分图。解题报告远古CF题。删除一条边可以考虑分治，然后用LCT判断有没有奇环就行了。这是斯

[DP]Codeforces1028G【Guess the number】题解

题目概述交互题，现在有一个数 $x(1\le x\le 10004205361450474)$ ，每次可以询问 $k(k\le x\land k<1000

[离线+复杂度分析]Codeforces1028H【Make Square】题解

题目概述有一个序列 $\{a_n\}$ ，如果区间 $[L,R]$ 里存在 $i<j$ 使得 $a_ia_j$ 是完全平方数就称这个区间是好的。一次操作可

[几何+复杂度分析]Codeforces1028F【Make Symmetrical】题解

题目概述有 $q$ 次操作，每次操作：1.加入一个整点。2.删除一个整点。3.询问以一条 $y\over x$ 为斜率过原点的线为对称轴，需要添加多少个点使得所

[构造]Codeforces1028E【Restore Array】题解

题目概述有一个序列 $\{a_n\}$ ，令 $\{b_i=a_i\ mod\ a_{i\ mod\ n+1}\}$ ，现在给出 $\{b_n\}$ ，求出一组

[计数]Codeforces1028D【Order book】题解

题目概述有 $n$ 次操作，每次操作可以：1.加入一个A/B类型值为 $p$ 的元素（保证 $p$ 互不相同）。2.删去值为 $p$ 的元素，保证之前出现过。同

[two-pointer+线段树]BZOJ4653(Noi2016)【区间】题解

题目概述有 $n$ 个区间，求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。解题报告我不会做题啦……很显然区间越多交

[DP]Codeforces1013E【Hills】题解

题目概述$x$ 轴上按顺序有 $n$ 座山，每座山有海拔 $h_i$ ，如果一座山比周围两个山高就可以建房子。可以花费 $1$ 的代价把山铲去 $1$ 的海拔，

[思维+并查集]Codeforces1013D【Chemical table】题解

题目概述如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(

Codeforces Contest & Virtual Participation合集

场次编号完成状态题解Codeforces Round #721 (Div. 2)1527QwQBEducational Codeforces Round 106

[期望DP+高斯消元+复杂度分析]Codeforces963E【Circles of Waiting】题解

题目概述从原点出发，每次往上下左右走都有一定的概率，问第一次走到离原点距离超过 $R$ 的点的期望步数。解题报告很显然可以期望DP，令距离超过 $R$ 但最接近

[计数]Codeforces963C【Cutting Rectangle】题解

题目概述有 $n$ 种小矩形，第 $i$ 种小矩形长为 $w_i$ 宽为 $h_i$ ，有 $c_i$ 个，问有多少种 $(A,B)$ 使得存在一种切割方案将其

[离线+AC自动机+复杂度分析]Codeforces963D【Frequency of String】题解

题目概述有一个文本串，现在有 $m$ 个模板串（互不相同），问文本串中长度最小的子串使得模板串出现了 $k_i$ 次。解题报告$m$ 个模板串互不相同奥妙重重，

[几何+计数]Codeforces1025F【Disjoint Triangles】题解

题目概述有 $n$ 个点，选出 $6$ 个点使得能够组成两个不相交的三角形，求方案数。解题报告几何神题，可以证明两个不相交的三角形之间恰好有两条切线（画了几个好

[树链剖分+线段树]Codeforces1023F【Mobile Phone Network】题解

题目概述有 $n$ 个点，$K$ 条特殊边，边权待定，保证无环，还有 $m$ 条普通带权边，现在确定特殊边的边权，使得最小生成树（边权相同选特殊边）包含所有特殊

[Pollard-Rho+高维前缀和]Codeforces1016G【Appropriate Team】题解

题目概述给出 $X,Y$ 和 $\{a_n\}$ ，问有多少 $(i,j)$ 存在 $v$ 满足 $(a_i,v)=X,[a_j,v]=Y$ 。解题报告来分析一

[贪心]Codeforces1016F【Road Projects】题解

题目概述有一棵带边权的树，询问 $m$ 次，每次新建一条边权为 $x$ 的边（不能建重边），问如何建使得 $1$ 到 $n$ 的最短路最大。解题报告可能不难吧，

[几何+二分]Codeforces1016E【Rest In The Shades】题解

题目概述有一个光源按照 $(a\to b,s_y)$ 移动，还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问，问一个点 $(x,y)$ 被板挡住

[计数+分段打表]BZOJ5383(湖南省队集训2018 Day2)【游戏】题解

题目概述在 $n\times n$ 的棋盘上放 $n$ 个车(ju)，使得车之间不会吃到，且在不经过车的情况下能够从 $(1,1)$ 走到 $(n,n)$ ，求

[Pollard-Rho+分块枚举子集]BZOJ5382(湖南省队集训2018 Day2)【走路】题解

题目概述有一棵树，如果 $w_i|w_j$ 且 $j$ 是 $i$ 的祖先那么 $j$ 可以直接到达 $i$ ，问从第一个点到所有点的方案数。解题报告$O(n^

[去绝对值]HDU6435(2018多校训练赛第十场)【CSGO】题解

题目概述你在play♂CSGO，被第 $i$ 种枪打跪体现你有 $S_i$ 的手残值，并且有 $K$ 个参数 $\{x_{i,K}\}$ ，被第 $j$ 种刀捅

[Dsu on tree]HDU6430(2018多校训练赛第十场)【TeaTree】题解

题目概述给出一棵带点权的树，求每个节点 $i$ 的 $max\{(a_x,a_y)|LCA(x,y)=i,x\not=y\}$ 。解题报告因为 $10^5$ 内

[构造]Codeforces1025E【Colored Cubes】题解

题目概述$n\times n(n\le 50)$ 的网格上有 $m(m\le n)$ 个方块，现在要把 $m$ 个方块归位，移动过程中不能碰到其他方块。求一种方

[Miller-Rabin+Pollard-Rho]Codeforces1025B【Weakened Common Divisor】题解

题目概述有 $n$ 组数对 $(a_i,b_i)$ ，求一个数使得 $\forall i,d|a_i\lor d|b_i$ 。解题报告因为随便求所以找共有的素因

[DP]HDU6415(2018多校训练赛第九场)【Rikka with Nash Equilibrium】题解

题目概述有 $n\times m$ 的网格，现在要不重复的填入 $1\sim nm$ ，如果一个格子比同行同列的数都大就称这个格子占领了这行这列。求只有一个格子

[DP]Codeforces1027E【Inverse Coloring】题解

题目概述有 $n\times n$ 的矩阵，现在给矩阵黑白染色，需要满足相邻行和相邻列要么全相同要么全不同，还需要满足最大同色子矩阵的面积小于 $K$ ，求方案

[树形DP]LOJ2485(CEOI2017)【Chase】题解

题目概述有 $n$ 个点的树，每个点上有 $p_i$ 只咕咕咕。从任意点出发开始走，有 $k$ 次放面包的机会，放下面包后相邻点的咕咕咕就会凑到该点，问先走一遍

[转化+并查集]Codeforces1027F【Session in BSU】题解

题目概述有 $n$ 场考试，第 $i$ 场考试可以在 $a_i,b_i$ 两天中的一天完成，问至少什么时候能考完所有试，无解输出 $-1$ 。解题报告我图样图森

[线段树]Codeforces1023D【Array Restoration】题解

题目概述按顺序将 $1\sim q$ 涂到长度为 $n$ 的板上（范围自定），问是否能够涂成目标状态（目标状态中有些通配符）。解题报告被翰爷秒掉了，目标状态中相

[构造]Codeforces1023E【Down or Right】题解

题目概述交互题。有一个 $n\times n$ 的网格图，每个格子是空地或者障碍。每次可以往右或者往下走，你可以询问 $(A,B)\to(C,D)$ 是否存在一

[贪心+ST表]BZOJ4444(Scoi2015)【国旗计划】题解

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，问第 $i$ 个线段必选时至少需要多少线段能够覆盖这个环。解题报告和BZOJ53

[贪心+ST表]BZOJ5397(湖南省队集训2018 Day3)【circular】题解

题目概述在一个长为 $m$ 的环上有 $n$ 个线段 $(s_i,t_i)$ ，在线段不交的情况下最多选择多少个线段？解题报告思路还停留在以前的斯波解法上……然

[倍增]Codeforces1008E【Guess two numbers】题解

题目概述交互题，让你猜两个 $[1,n]$ 的数 $a,b$ ，每次会回复四种情况之一，如果多条满足随机回复一条合法的：$x=a,y=b$ 。$x<a$

[划水,贪心]Codeforces1008C【Reorder the Array】题解

题目概述给出一个序列 $\{a_n\}$ ，重排列这个序列使得新序列 $\{b_n\}$ 中 $b_i>a_i$ 尽量多。解题报告这啥啊……田忌赛马？将

[容斥+组合]Codeforces1008D【Pave the Parallelepiped】题解

题目概述求有多少个小长方体 $(a,b,c),a\le b\le c$ 能够拼成大长方体 $(A,B,C)$ 。解题报告其实就是求有多少个 $(a,b,c)$

[构造]Codeforces1020E【Sergey's problem】题解

题目概述给出一张 $n$ 个点 $m$ 条有向边的图，可以有环但没有自环。现在要选出一个集合 $Q$ 使得 $Q$ 内的点不连通，但 $Q$ 到其他不在 $Q$

[二分]Codeforces1020D【The hat】题解

题目概述交互题，$n(n\le 10^5)$ 个人接成环，手上拿着一个数 $a_i$ 。$i$ 和 $i\ mod\ n+1$ 相邻，保证相邻人之间的数之差绝对

[离线+斜率优化+二分]BZOJ5380【Function】题解

题目概述$$ f(x,y)=\begin{cases}A_y&x=1\\f(x-1,y)+A_y&y=1\land x\not=1\\min\{

[莫比乌斯函数+调和级数]HDU6390【GuGuFishtion】题解

题目概述咕咕咕。求 $f(a,b)={\varphi(ab)\over\varphi(a)\varphi(b)},\sum_{a=1}^{n}\sum_{b=1

[除法分块+矩阵快速幂]HDU6395【Sequence】题解

题目概述$f_1=A,f_2=B,f_n=Cf_{n-2}+Df_{n-1}+\lfloor{P\over n}\rfloor$ ，求 $f_n$ 。解题报告这

[Kruskal重构树+ST表]LOJ2718(NOI2018)【归程】题解

题目概述给出 $n$ 个点 $m$ 条无向边的连通图，每条边有距离和高度，如果高度 $\le$ 水的高度这条边就会被淹没，令 $dis_i$ 表示到达 $1$

[Kruskal重构树]BZOJ3732【Network】题解

题目概述给出一张无向图，多次询问两个点之间最长边的最小值为多少。解题报告因为最小生成树神奇的性质，我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案

[凸包同构]Codeforces1017E【The Supersonic Rocket】题解

题目概述判断两个凸包是否同构，即是否能平移+旋转使得两个凸包重合。解题报告原题意是说两个点之间都会建新点，建完之后新点之间也会建新点，那么其实很明显所有点构成了

[二分+后缀树+ST表+DFS序+主席树]LOJ2059(TJOI / HEOI2016)【字符串】题解

题目概述给出一个字符串 $S$ ，求 $max\{LCP(S_{[i,j]},S_{[c,d]})|a\le i\le j\le b\}$ 。解题报告先二分答案

[压位+空间优化]Codeforces1017F【The Neutral Zone】题解

题目概述给出 $f(x)=Ax^3+Bx^2+Cx+D$ ，令 $x=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},g(x)=a_1f(

[辗转相除+莫比乌斯函数+组合+调和级数]HDU6363(2018多校训练赛第六场)【bookshelf】题解

题目概述有 $n$ 个物品，分配到 $m$ 个箱子里（可以为空），问 $(2^{fib_{a_1} }-1,2^{fib_{a_2} }-1,\cdots,2^

[DFS树+线性基]BZOJ3569【DZY Loves Chinese II】题解

题目概述给出 $n$ 个点 $m$ 条无向边，有 $Q$ 个询问每次删除 $k_i$ 条边（之后还原），问图是否连通。解题报告先特判掉没删边就不连通，然后我们建

[DP]HDU6356(2018多校练习赛第五场)【Glad You Came】题解

题目概述给出长度为 $n$ 的数字串，求最长非降子序列的长度，允许翻转一个区间 $[l,r]$ 。解题报告因为数字串，所以我们可以利用数值定义状态来快速转移，而

[ST表]Codeforces1011F【Mars rover】题解

题目概述给出一个逻辑运算树，每个节点有一个逻辑运算或输入框（ $0$ 或 $1$ ）以及 $0/1/2$ 个儿子（根据符号定）。问每次只把所有输入框中的一个改成

[DP+线段树维护矩阵转移]Codeforces573D【Bear and Cavalry】题解

题目概述给出 $\{a_n\}$ 和 $\{b_n\}$ 以及刚开始 $P_i=i$ 的排列 $\{P_n\}$ ，有 $m$ 个询问，每次询问先交换 $P_x

[莫比乌斯函数+调和级数]洛谷U32290【LJJ爱数数】题解

题目概述求 ${1\over a}+{1\over b}={1\over c}(a,b,c\in N^{*},a,b,c\le n)$ 解的个数。解题报告被学弟

[圆方树+树链剖分+线段树]Codeforces487E【Tourists】题解

题目概述给出 $n$ 个带权点和 $m$ 条无向边的图，给出 $q$ 个操作：1.修改某个节点的点权。2.询问 $x\to y$ 路径上所有简单路径的最小点权。

[莫队]HDU6333(2018多校练习赛第四场)【Harvest of Apples】题解

题目概述求 $\sum_{i=0}^{m}{n\choose m}$ ，多组询问 $(n,m)$ 。解题报告莫队大法好，由 $n\choose m$ 可以 $O

[Tarjan求割点]BZOJ2730(HNOI2012)【矿场搭建】题解

题目概述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设

[二分+后缀树+ST表]BZOJ5405【platform】题解

题目概述给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,

[单调队列+单调栈]HDU6319(2018多校练习赛第三场)【Ascending Rating】题解

题目概述给出一个长度为 $n$ 的序列，求每个长度为 $m$ 的序列中的最大值以及最大值被更新的次数。解题报告最大值单调队列，更新次数可以这么搞：先预处理 $n

[哈希]BZOJ2795(Poi2012)【A Horrible Poem】题解

题目概述给出一个长度为 $n$ 的字符串和 $q$ 个询问，每个询问形如 $(l_i,r_i)$ 表示求 $s_{[l_i,r_i]}$ 的最短循环节的长度（最

[复杂度分析+线段树]HDU6315(2018多校练习赛第二场)【Naive Operations】题解

题目概述给出排列 $\{b_n\}$ 和刚开始都是 $0$ 的 $\{a_n\}$ ，有两种操作：1.把 $a_{[L,R]}$ 都 $+1$ 。2.询问 $\

[线段树二分]HDU6301(2018多校第一场)【Distinct Values】题解

题目概述有一个长度为 $n$ 的序列，给出 $m$ 个限制，每个限制形如 $(l_i,r_i)$ 表示 $l_i$ 到 $r_i$ 的数互不相同，求字典序最小的

[DP]BZOJ2424(HAOI2010)【订货】题解

题目概述在第 $i$ 个月月初需要提供 $w_i$ 的货物，购买货物的单位价格为 $p_i$ 。货物可以存在上限为 $S$ 的仓库，但每月月底需要支付的单位价格

[非互质CRT]LOJ2721(NOI2018)【屠龙勇士】题解

题目概述求方程组 $atk_ix\equiv a_i\ (mod\ m_i)$ 最小的解。示例程序如果把系数去掉就是裸的非互质CRT，根据同余方程的同除性，我们

[DFS序上DP]一种带依赖的树上背包

题目概述BZOJ4182弱化版，原版是要求选出来的点是连通的（我不会），弱化版只需要满足儿子选了父亲必选。解题报告其实之前做过带依赖的一道题，但是并没有体积，所

[分数规划+树形DP]BZOJ4753(Jsoi2016)【最佳团体】题解

题目概述有 $n+1$ 个人，选第 $i$ 个人需要花费 $s_i$ ，得到 $p_i$ 的贡献，第一个人必选，没有花费和贡献。$2\sim n+1$ 都有一个

[数位DP,矩阵快速幂]BZOJ3329【Xorequ】题解

题目概述求 $[1,n]$ 中满足 $x\ xor\ 3x=2x$ 的 $x$ 的个数以及 $[1,2^n]$ 中 $x$ 的个数。解题报告我竟然分析成了 $x

[DP]BZOJ1190(HNOI2007)【梦幻岛宝珠】题解

题目概述有 $n$ 个物品，每个物品的体积满足 $a\cdot 2^b$ ，背包体积为 $W$ ，求最大价值。解题报告直接上背包！因为每个物品体积满足 $a\c

[LIS]洛谷3365【改造二叉树】题解

题目概述给出一棵 $n$ 个节点的二叉树，现在可以修改任意个节点的权值（只能改成整数），问至少多少次能把这棵二叉树改成BST。解题报告先中序遍历得到序列，然后就

[状压DP]BZOJ2734(HNOI2012)【集合选数】题解

题目概述如果选了 $x$ 就不能选 $2x$ 和 $3x$ ，求 $1..n$ 满足条件的子集个数。解题报告这种神题完全做不来，一波转化日神仙： x 3x

[数位DP]Codeforces55D【Beautiful numbers】题解

题目概述问 $[L,R]$ 多少个整数是每个位上的数的倍数（$0$ 不算）。解题报告这道题想法不是特别难，但是要考虑优化。首先可以发现只需要记录 $mod\ 5

[Tarjan+拓扑]HDU6165【FFF at Valentine】题解

题目概述问一张 $n$ 个点 $m$ 条有向边的图是否满足两两点 $x,y$ 之间均有 $x$ 与 $y$ 连通或 $y$ 与 $x$ 连通。解题报告FFF团还

[计数]Codeforces GYM101194H【Great Cells】题解

题目概述构造一个 $n\times m$ 的矩阵，矩阵元素的值是 $[1,K]$ 中的整数。如果一个元素的值是同行同列中最大的，那么就是一个JZ数。令 $A_g

[扩展欧几里得]BZOJ1407(Noi2002)【Savage】题解

题目概述有 $n$ 个JZ在一个长度为 $m$ 的环上，第 $i$ 个JZ刚开始在 $c_i$ ，每天会顺时针走 $p_i$ 的路程到那里虐人，共虐 $l_i$

[二分图匹配]BZOJ1191(HNOI2006)【超级英雄Hero】题解

题目概述有 $n$ 个ZZK $m$ 个JZ，每个JZ可以虐两个指定的ZZK中的一个，一个ZZK被虐之后就心态爆炸不能再被虐，问从第一个JZ开始按顺序连续不断的

[莫比乌斯函数]BZOJ2005(Noi2010)【能量采集】题解

题目概述一个整点 $(x,y)$ 的代价 $w(x,y)$ 是与 $(0,0)$ 连线上的整点的个数的两倍减三，求 $\sum_{i=1}^{n}\sum_{j

[DFS序换根+线段树]BZOJ5379【Tree】题解

题目概述有一棵 $n$ 个点的点权树，刚开始根是 $1$ ，现在有 $q$ 次操作：把根换成 $x$ 。把 $LCA(x,y)$ 子树中节点的权值均加上 $w$

[贪心+树状数组]COCI2012【RASPORED】题解

题目概述有 $n$ 个任务，第 $i$ 个任务需要 $T_i$ 的时间完成，加分为 $L_i−s_i$ ，其中 $s_i$ 表示完成该任务的时间。有 $q$ 组

THUSC2018划水记

6.1 Day-1由于要给两位签PKU的大佬当陪衬，所以提前了一天去BJ。儿童节好评，暗示我只有小学生水平。6.2 Day0早上睡到9点，看了看Emacs配置。

[霍尔定理+线段树]LOJ6062(2017 山东一轮集训 Day2)【Pair】题解

题目概述两个数 $x,y $ 可以匹配定义为 $x+y\ge H $ 。现在给出 $\{a_n\} $ 和 $\{b_m\} $ ，问 $\{a_n\} $ 有

[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解

题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le

[计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解

题目概述有 $n$ 个矩阵，问多少三元组 $(i,j,k),i<j<k$ 满足三个矩阵至少有一个相交的格子。解题报告我怎么连计数题都不会……这种题目

[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解

题目概述给出一棵 $n $ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0 $ ）的数，现在给出 $m $ 个询问 $(x

[随机]BZOJ5365(2018年5月赛)【回文树】题解

题目概述给你 $n$ 个点，每个点有一个 $[1,n]$ 的随机权值，问有多少回文路径。解题报告因为是随机的……所以你要有信仰，假装回文路径长度最多只有 $5$

[线段树动态开点]BZOJ5358(Lydsy1805月赛)【口算训练】题解

题目概述给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a

NTT

快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 $A(x)B(x)$

[矩阵乘法]BZOJ4417(Shoi2013)【超级跳马】题解

题目概述现有一个 $n$ 行 $m$ 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。试求跳法种

[主席树+平衡树]BZOJ4548【小奇的糖果】题解

题目概述有 $n$ 个有颜色的点，颜色有 $K$ 种，现在选一条线段并获取上面或下面的所有点，规定获得的点不能包含所有颜色，问你能获得多少点。解题报告我怎么套路

[裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解

题目概述给你 $n$ 种物品，每种物品有无数个，体积为 $V_i$ ，选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ，问方案数。解

[SG函数]LOJ2126(HAOI2015)【数组游戏】题解

题目概述有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格

[矩阵快速幂]LOJ2128(HAOI2015)【数字串拆分】题解

题目概述你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数，你可以将这个数字串分割成若干个数

[拆系数FFT]洛谷4245【任意模数NTT】题解

题目概述求 $A(x)B(x)$ ，系数对任意模数 $p$ 取模。解题报告任意模数NTT好像需要三模数NTT搞。然而我不会NTT……所以我来愉快的讲一波任意模数

[区间DP]LOJ2063(HAOI2016)【字符合并】题解

题目概述有一个长度为 $n $ 的 $01 $ 串，你可以每次将相邻的 $k $ 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k $ 

[状压DP+组合]LOJ2540(PKUWC 2018)【随机算法】题解

题目概述我们知道，求任意图的最大独立集是一类NP完全问题，目前还没有准确的多项式算法，但是有许多多项式复杂度的近似算法。例如，小C常用的一种算法是：对于一个 $

[后缀数组+线段树]LOJ2064(HAOI2016)【找相同字符】题解

题目概述给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。解题报告先套路一波：把两个串

[DP+组合]LOJ2538(PKUWC 2018)【Slay the Spire】题解

题目概述有 $n$ 张攻击牌（造成攻击牌数值的伤害）和 $n$ 张强化牌（攻击牌伤害均 $\times$ 强化牌数值），从中抽出 $m$ 张并选出最优秀的 $K

[拓扑+DP]LOJ2060(HAOI2016)【食物链】题解

题目概述给出 $n$ 个生物 $m$ 条能量流动，求食物链个数。解题报告脑子不好用了，划波水。生物题了解一下。食物链的开始通常是绿色植物（生产者）,从绿色植物开

[线段树]LOJ2529(ZJOI2018)【胖】题解

题目概述一条直线上有 $n$ 个点，只有相邻点之间有边。刚开始 $dis_i=10^{18}$ ，给出 $K$ 个关键点的 $dis$ ，用Bellman–Fo

Codeforces Round #483(Div.2)题解

神tm结论大赛日神仙。A求中位数。#include<cstdio> #include<algorithm> using namespac

[线段树动态开点+启发式合并]LOJ2537(PKUWC 2018)【Minimax】题解

题目概述一个节点 $i$ 的权值有 $p_i$ 的可能是儿子节点权值最大值，$1-p_i$ 的可能是儿子节点权值最小值（至多两个儿子），假设根节点(1)权值有

[Trie]2018计蒜之道初赛第二场【阿里巴巴的手机代理商】题解

题目概述有 $n$ 个询问：$Insert\ s\ x$ ：增加 $x$ 个 $s$ 。$Delete\ s$ ：删除所有 $s$ 。$Query\ s$ ：查

[树形背包+复杂度分析]LOJ2124(HAOI2015)【树上染色】题解

题目概述有一棵点数为 $n$ 的树，树边有边权。给你一个正整数 $K$ ，你要在这棵树中选择 $K$ 个点，将其染成黑色，并将其他的 $n−K$ 个点染成白色。

ZJOI2018爆炸记

看来我和去年相比完全没有什么长进Orz。Day1一试放在本校日神仙，Manchery学长演讲好评。听课的时候发现自己和去年比好像没有什么长进。Day1点开试卷发

[折半搜索]TopCoder【EllysRPS】题解

题目概述你要跟一共 $m$ 个人玩剪刀石头布的游戏，其中 R(Rock) 胜 S(Scissors)、S(Scissors) 胜P(Paper)、P(Paper

[二分+上下界费用流]HDU5263【平衡大师】题解

题目概述有 $n$ 个点 $m$ 条单向边，每个点的不平衡度为出度减入度的差的绝对值，现在可以删除至多 $m-K$ 条边，求最大不平衡度的最小值。解题报告其实不

[树形DP+two-pointer]2016计蒜之道初赛第六场【微软的员工福利】题解

题目概述有 $n$ 个ZZK给JZ打工，他们的上下级关系是一棵树。现在JZ要给蒟蒻ZZK输送一定的神犇之力，每个ZZK可以得到 $r_i$ 点神犇之力或者 $p

[最小割]TopCoder【FoxAndCity】题解

题目概述有 $n$ 个由双向边连通的城市，$1$ 号城市里住着神犇JZ。$i$ 号城市想要离JZ所在城市距离为 $want_i$ ，如果实际的距离为 $real

[TC交题指南]TopCoder【RangeEncoding】题解

题目概述给出一个递增的数组，求 $a_i=a_{i-1}+1$ 的段数。解题报告TC交题方法比较鬼畜，不是读入输出，而是让你实现一个指定名称的class，里面写

[最小割]BZOJ3144(Hnoi2013)【切糕】题解

题目概述有一块 $X\times Y\times Z$ 的切糕，每个点 $(x,y,z)$ 都有不和谐值 $v(x,y,z)$ 。现在要切这块切糕，为每个直线

[二分+后缀数组]BZOJ4310【跳蚤】题解

题目概述有一个串 $S$ ，现在要把 $S$ 分成不超过 $k$ 段，从每一个子串选出最大的子串，再从这些最大的子串中选出最大的串"JZ串"，求最小的"JZ串"

[DP]UOJ300(CTSC2017)【吉夫特】题解

题目概述求不上升OrzJZ子序列的个数，OrzJZ子序列需要满足 $\prod_{i=2}^{k}{a_{i-1}\choose a_i}\ mod\ 2=1$

[最大密度子图]2017计蒜之道初赛第三场【腾讯狼人杀】题解

题目概述有 $n$ 个神犇JZ，某两个JZ配合有神犇值，共有 $m$ 组这样的JZ。现在要选出若干个JZ（假设选了 $k$ 个），贡献为存在于这些JZ中的所有配

[决策单调性]BZOJ2369【区间】题解

题目概述有 $n$ 个区间 $A_i=[L_i,R_i]$ ，现在选 $m$ 个 $(m>1)$ 区间，贡献为 $|A_{k_1}\cap A_{k_2}

[DP]BZOJ1566(NOI2009)【管道取珠】题解

题目概述有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i

[wqs二分+DP]POJ1160【Post Office】题解

题目概述有 $n$ 个村庄，现在要建 $m$ 个邮局，一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告显然是 $O(n^2m)$ DP吧？数据小的可怜，

[最大密度子图]POJ3155【Hard Life】题解

题目概述有 $n$ 个员工 $m$ 条矛盾，现在要炒若干个员工的鱿鱼，一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经

[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解

题目概述给出一张 $n$ 个点 $m$ 条有向边的图，现在要求 $S,T$ 的最小割，问每一条边：有没有可能出现在最小割中。是否一定出现在最小割中。解题报告先跑

[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解

题目概述题目太复杂了QAQ，自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件，发现带有很多“强制”操作，比如吃了

[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解

题目概述有 $n$ 个点 $m$ 条边，每个点需要花费 $p_i$ 购买，每条边可以得到 $c_i$ 的价值。现在要购买一些点，如果一条边两端的点都被购买了，就

最小割模型

对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割：ZOJ2676

[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解

题目概述有 $n$ 种无数个的物品，每种物品带有ZZK的蒟蒻值 $weak_i$ 和JZ的神犇值 $strong_i$ ，你现在可以选任意个物品，将得到所有物品

[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解

题目概述有一个 $n$ 个点 $m$ 条双向边的图，每条边的边权是 $w_i$ 。JZ为了防止神犇之力外泄，想切断 $1$ 到 $n$ 的连接（切断一条边的代价

[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解

题目概述有 $n$ 个软件和 $m$ 的容量，每个软件需要 $w_i$ 的容量，有 $v_i$ 的价值，同时依赖 $d_i$ 软件( $d_i=0$ 则没有依赖

[裴蜀定理]BZOJ2299(HAOI2011)【向量】题解

题目概述问能否用任意个向量 $(\pm a,\pm b)$ 和 $(\pm b,\pm a)$ 组合出向量 $(x,y)$ 。解题报告显然只有这么几种方法：$x

[树状数组]BZOJ3192(JLOI2013)【删除物品】题解

题目概述一共有两堆物品，分别有 $n$ 个和 $m$ 个。所有物品都是一样的，但是它们有不同的优先级。只能够移动某堆中位于顶端的物品，你可以把任意一堆中位于顶端

欢迎来到ZigZagK的博客！

[Meting][Music server="netease" id="440241194" type="song"/][/Meting]欢迎来到ZigZagK

BZOJ刷题记录

题号日期题解备注BZOJ11712019.4.17QwQ BZOJ44072019.4.16QwQ BZOJ40062019.4.16QwQ BZOJ26482

页面
追番

这里是ZigZagK的bilibili追番列表。欢迎在评论里友好聊番，或者给我推荐番QwQ。[panel title="ZigZagK的推荐"]注：1.仅代表个

日记
标签云
实验室
友链
关于

[Meting][Music title="Flower Dance" author="DJ Okawari" url="/usr/uploads/2019/0

留言板

欢迎留言和交换友链！申请友链的时候请顺便提供一下网站信息QwQ，格式示例：名称ZigZagK地址https://zigzagk.top图标https://gra

分类
游戏游戏
UnityUnity
图形学图形学
其他其他
游记游记
洛谷洛谷
ICPCICPC
牛客牛客
Codeforcescodeforces
HydroHydro
CCPCCCPC
LOJloj
数学相关数学相关
HDUhdu
AtCoderAtCoder
字符串字符串
BZOJbzoj
EOJEOJ
UOJuoj
ACMACM
图论图论
Online JudgeOnline-Judge
日记日记
TypechoTypecho
PHPPHP
CodeChefCodeChef
HackerRankHackerRank
HHHOJHHHOJ
TopCodertopcoder
DPdp
51Nod51Nod
SPOJSPOJ
计蒜客计蒜客
POJpoj
COCIcoci
ZOJzoj
标签
Persona系列Persona系列
ShaderShader
UnityUnity
光线追踪光线追踪
数学姿势数学姿势
光栅化光栅化
着色着色
纹理纹理
自己的理解自己的理解
大学生活大学生活
ACMACM
可持久化可持久化
平衡树平衡树
树状数组树状数组
线段树线段树
复杂度分析与优化复杂度分析与优化
并查集并查集
后缀自动机后缀自动机
DPDP
单调栈和单调队列单调栈和单调队列
离线离线
堆和可并堆堆和可并堆
扫描线扫描线
珂朵莉树珂朵莉树
后缀数组后缀数组
思维思维
FFT&NTT&FWT&FMTFFT-NTT-FWT-FMT
二分二分
分治分治
多项式多项式
容斥容斥
倍增倍增
单位根反演单位根反演
BluesteinBluestein
Min_25筛Min_25筛
生成函数生成函数
Lyndon分解Lyndon分解
分数规划分数规划
树链剖分树链剖分
树形DP树形DP
矩阵优化转移矩阵优化转移
欧几里得算法欧几里得算法
Palindrome SeriesPalindrome-Series
链分治链分治
LCTLCT
哈希哈希
KMPKMP
回文自动机回文自动机
高维前缀和高维前缀和
强连通分量强连通分量
分块分块
STL乱搞STL乱搞
传递闭包传递闭包
奇技淫巧们奇技淫巧们
随机随机
凸包凸包
几何几何
TrieTrie
树上解方程树上解方程
虚树虚树
状压DP状压DP
背包相关技巧背包相关技巧
拓扑拓扑
AC自动机AC自动机
差分差分
概率DP和期望DP概率DP和期望DP
仙人掌仙人掌
圆方树圆方树
贪心贪心
狄利克雷卷积和莫比乌斯反演狄利克雷卷积和莫比乌斯反演
KruskalKruskal
树套树树套树
Miller-Rabin&Pollard-RhoMiller-Rabin-Pollard-Rho
带花树带花树
OriOri
构造构造
最短路最短路
离散离散
计数计数
KDTKDT
区间DP区间DP
斜率优化斜率优化
网络流和线性规划网络流和线性规划
拉格朗日插值拉格朗日插值
吐槽吐槽
划水划水
高中生活高中生活
Typecho主题Typecho主题
UndertaleUndertale
星之卡比星之卡比
PHPPHP
APIAPI
Hollow KnightHollow-Knight
线性筛线性筛
DFS序上DPDFS序上DP
莫队莫队
DP套DPDP套DP
杜教筛杜教筛
BSGSBSGS
二次剩余二次剩余
斯特林数斯特林数
组合组合
二分图二分图
后缀平衡树后缀平衡树
矩阵树定理矩阵树定理
线性基线性基
DFS树和BFS树DFS树和BFS树
斯坦纳树斯坦纳树
点分治&点分树点分治-点分树
轮廓线DP和插头DP轮廓线DP和插头DP
Min-Max容斥Min-Max容斥
二项式反演二项式反演
矩阵求逆矩阵求逆
伯努利数伯努利数
原根原根
DFS序和BFS序DFS序和BFS序
哈夫曼树哈夫曼树
双连通分量双连通分量
置换群和Burnside引理置换群和Burnside引理
链表链表
优化建图优化建图
数位DP数位DP
ManacherManacher
决策单调性决策单调性
two-pointertwo-pointer
高斯消元高斯消元
后缀树后缀树
中国剩余定理中国剩余定理
博弈博弈
折半搜索折半搜索