其他
[题解]NOIP2018模拟赛 plutotree
题目描述 给定一棵有(n)个节点的树，根节点为(1)，节点(i)有权值(w[i])。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的边。给定(q)次询问，每次给定(u,v)，请计算出一条(u)到(v)的路径（每条边最多经过(1)次），最小化该路径上的点权之和，并在其基础上最大化该路径上的最大点权。 输入的第(1)行(2)个整数表示(n)和(q)；第(2)行有(n-1)个正整数，第(i)个正整数
Note - 概率与期望
[ZOJ3329]One Person Game 期望倒着推。 设 (f_i) 表示期望还需多少次结束。 我们可以得到式子 [f_i=(sum f_{x+i}p_i)+f_0p_0+1 tag{$1$} ]发现每一项都与 f0 有关。 我们直接换元得 [f_i=a_i f_0+b_itag{$2$} ]将 ((2)) 代入 ((1)) 得 [begin{gather} f_i=(sum(a_{x+
2024.10.16 模拟赛
2024.10.16 模拟赛 T1 divide 简要题意 给定一棵树的 (n) 个结点以及每个结点的 (fa_i)，每个点的点权 (v_i)，删除树中的两条边，将树拆分为三个非空部分。每个部分的权值等于该部分包含的所有节点的权值之和。出一种合理的拆分方案。根节点的 (fa_i = 0) (n≤10^6) solution 首先可以算出所有的点的点权和，如果不是 (3) 的倍数，那么一定不存在合法
ICPC WF 2022 2023 Bridging the Gap 过桥
https://qoj.ac/problem/8683 https://loj.ac/p/6937 是个十足的 DP 题。刷完了 YeahPotato 的 DP 博客，你觉得有什么方法能套进来呢？ 前面“基于特殊结构的技巧”没有一个能用。 如何分析性质？分析样例： 明显先排序。 猜想，一定有几个人在跑腿送灯，一定是前 C 个人的前缀，从对岸往回跑的一定是对岸用时最少的一个人。 搓出几个看上去很
HNCPC2024 2024湖南省赛 题解
目录写在前面I 签到C 签到E 二进制，枚举，子集 DPK 转化，分层图最短路A 枚举，DP，简单计算几何J 单调性，枚举，数据结构H DP，字符串，KMPD 莫比乌斯反演，枚举写在最后 写在前面 比赛地址：https://codeforces.com/gym/105423。 以下按个人难度向排序。 利益相关：现场赛 Au。 没有和去年一样整场犯唐，好！感谢队友带飞成功一雪前耻。 题解见官方，这里
Sorting a Grid
怎么洛谷又没了。 怕下次又忘了所以写。 习惯了谎话，早已分不清真假。 不妨给 D 的每一行染一个颜色，那么 C 每一行的是一种颜色即可。 可以发现有 (n) 种颜色，每种颜色数量为 (m)。每一行颜色不是一样的。 考虑 B 如何一定合法。显然每一列不能有重复元素，等价于每一列有 m 种元素。 考虑 A 变到 B，也就是每次有一堆颜色可重集 (S)，给 (S) 中的每个元素分配一个列。 发现这
Typora代码块默认语言设置
找到文件路径 Typoraresourcesappappwindow 记事本打开文件（先备份下）frame.js。搜索下方关键字： "select a language")+"'></span>",t.childNodes[0].textContent=e 修改""中关键字为需要默认的类型
浏览器安装 AtCoder Better 和 Codeforces Better 插件
你首先需要篡改猴。 如果你用的Google浏览器，请用这个 Link，不过你可能需要挂个梯子。 如果你用的Firefox浏览器，请用这个 Link，这个不需要梯子。 如果你用的edge浏览器，请用这个 Link，这个也不需要梯子。 下载好篡改猴之后，无论什么浏览器， 点击这个 链接，安装 AtCoder Better 插件； 点击这个 链接，安装 Codeforces Better 插件。
二项式反演的三道练习题
已经没有什么好害怕的了 板子题，所用到的柿子为 [f(n)=sum_{i=n}^mmathrm{C}_i^ng(i)Leftrightarrow g(n)=sum_{i=n}^m(-1)^{i-n}mathrm{C}_i^nf(i) ]先考虑需要多少组糖果比药片能量大的，就是(frac{n+k}{2})，这个随便推推就有了。 考虑dp，设(f_{i,j})表示前(i)中 糖果比恰好糖果比药片能量大
2024.10.16 鲜花
PRAGMATISM -RESURRECTION 凭什么没词就不是好歌！！！ 取模优化 就不讲怎么减少取模了。 比较广为流传的有两种，Barrett reduction，Montgomery Algorithm。 对于固定常数模数，计算机已经优化的很好了，一般不会有太大效果（确实有，用 Barrett reduction 有时可以卡常）。 对于输入的固定模数（即不会改变），可以用一下算法优化。
CodeForces - 1364D
通常的想法是：如果图是一棵树，那么通过对顶点进行双色染色，并从更频繁的颜色中选取顶点，就可以轻松找到大小为 (lceilfrac{n}{2}rceil) 的独立集合。否则，图就是循环的。让我们得到一个没有任何边 “穿过 ”的循环。换句话说，它没有任何一对不相邻的顶点由边连接。如果它的长度最多为 (k)，则打印出来。否则，取其他每一个顶点（取一个顶点，留下一个顶点），最后就会得到一个足够大的独立集合
「CEOI2023」Balance
感觉这种题天克我啊。。 题目给出了 (S=2^k) 的限制，让我们有一些奇怪的思考，再加上有 (S=2) 的部分分，我们可以考虑从 (S=2) 拓展到任意情况。故我们先研究 (S=2) 的情况。 我们对颜色建点，对于每一行的两种颜色之间连一条边。然后我们考虑钦定每一条边的方向以表示这一行的交换情况。那么显然合法的充要条件就是每个点的入度与出度之差不超过 (1)。据说，这是经典图论问题。我们可以将奇
Openstack deployment
Openstack deployment https://zhuanlan.zhihu.com/p/25433651#:~:text=Fuel%EF%BC%9A%20Mi 部署工具 RDO：REDHAT出品，支持Redhat、CentOS等系统。RDO基于puppet部署各个组件，支持单节点或多节点部署，在Redhat系操作系统上使用非常方便。 devstack：这个应该是最
2024.10.16~2024.10.18 模板清理
20241016 区间DP - 回文字串 记 (f[i][j]) 表示把 (s[i sim j]) 变成回文，最少补几个，从 (f[i][j - 1], f[i + 1][j], f[i + 1][j - 1]) 三种情况转移过来即可。感性理解一下这样的状态定义是有最优子结构的。 区间DP - 合唱队 肯定可以区间 (dp)，再注意到状态的转移和上一步有关，所以记 (f[i][j][0/1])