![P6076 [JSOI2015]染色问题 题解](/images/covers/1.jpg)
P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ …
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=…
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为…
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$…
点分治学习笔记
定义 点分治，顾名思义，就是通过基于点的分治的一种算法。 通常用于处理树上问题，如树上所有路径统计。 我们设一次操作的时间复杂度为 $O(1)$ ，那么一次点分治复杂度为 $O(n \log n)$ 。 具体流程 操作->分治->操作……（不知道怎么讲） 点分治的核心主要在于高…
CF1661D Progressions Covering 题解
link 简化题意 给定一个长度为 $n$ 的数组 $A$ ，和一种操作。 每次操作选定长度为 $k$ 的区间 $[L,R]$ , 将 $A_L-1$，$A_{L+1}-2$ …… $A_R-k$ 。 求使 $A$ 中所有元素小于等于0所需的最小操作个数。 Sulution 一个显然的贪心…
P5289 皮配 题解
（注 ：第一次打这种超出目前能力的 dp ，调了四个晚上。 简化题意： 有四位导师，他们被两两一组分成了红 / 蓝阵营，另外两两一组分成了鸭 / R 派系 有 $n$ 所**学校**，来自 $c$ 个**城市**，第 $i$ 个学校有 $s_i$ 名选手。 同一所学校的…
欧拉函数小结
定义 $\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。 也就是小于等于 $x$ 的正整数中与其互质的数的个数。 基本推论 $\varphi(x)=x-1\quad(x\in \mathbb{P})$ $ \b…
P2572 [SCOI2010]序列操作 题解
线段树全家桶，还是挺考验码力的。 注意点： 三种 tag 的覆盖关系（隔壁调了半年） push_up 和 push_down 的更新细节 query2 的去最值细节（我举得我的方法蛮好的）。 总之坑点还是蛮多的。 code #include<bits/stdc++.h> …
模拟退火学习笔记
模拟退火，RP检测器，玄学算法，yyds。 看什么学习笔记，当然是看日报了。 过程 就是模拟冶金学的退火过程，乱搞，具体理论的证明我也不是很懂。 流程图(自己懂就好)： 优化/乱搞 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温…