Painting
Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting
题目链接 Tree Painting 题面翻译 给定一棵 \(n\) 个点的树 初始全是白点 要求你做 \(n\) 步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。 第一次操作可以任意选点。 求可获得的最大权值 思路 假如说，第一次我 ......
[CF576E] Painting Edges
Painting Edges 动态加边和二分图容易想线段树分治,分别维护 k 种颜色的并查集。 不过每条边的存在时间不能确定。 设边 i 的两次操作的时间为 \(x_i,y_i\),那么对于 \(t\in[x_i+1,y_i-1]\) 有两种情况,颜色改变或改色不变。 则我们把每次操作影响的时间放在 ......
CF1132C Painting the Fence 题解
@目录DescriptionSolutionCode Description 有一面长为 \(n\) 的墙以及 \(q\) 个工人，第 \(i\) 个工人粉刷 \(l_i\) 到 \(r_i\) 的墙面，现在要去掉两个工人，问剩余 \(q-2\) 个工人最多能粉刷多少墙面。 Solution 注意数 ......
CF1479B1 Painting the Array I
如果两种方案末尾两数有一数相同，那么答案较大的方案不劣于答案较小的方案。答案较大的方案只需\textbf{模仿}答案较小的方案即可，在状态变成相同之前答案最多只会少 \(1\)。 所以只需要考虑末尾两数 \(a,b\) 与新进来的数 \(c\) 各不相同时该替换哪个。 假设 \(a\) 下次出现的位 ......
Educational Codeforces Round 152 (Div. 2) D. Array Painting（双指针）
Educational Codeforces Round 152 (Div. 2) D. Array Painting //思路：双指针找连续正数段 //若段中出现2，则更新两头的0的情况，若为涂色则改为true //若无2，则优先更新左侧0，若左0已经为true，则更新右侧0 //数组开头结尾特判 ......
CFgym103260K-Rectangle Painting
### 前言 断续地调了一天一夜，终于做出来了！ ### 题目链接-[Rectangle Painting](https://codeforces.com/gym/103260/problem/K) 大概就是：给 $n$ 个集合 $S_i$，两种操作， 1. `1 {[l,r],x }l r` 向 ......
洛谷_[P4084]Barn Painting G题解
[题目链接](https://www.luogu.com.cn/problem/P4084) 这题我们可以定义一个二维的 dp 数组， 在 dp[i][j]中： i 表示对于节点 i， j 有 1,2,3 三种状态， 表示当点 i 选择被染成颜色 j 时，以 i 为根的这颗子树有多少种染色方法。 那 ......
Painting the Fence 题解
[题目传送门](https://www.luogu.com.cn/problem/CF1132C) 一道枚举题。 我们可以直接枚举那 $2$ 个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到，然后枚举第一个被去掉的粉刷匠，然后计算剩下的粉刷匠会将每个栅栏刷到多少次，我们只需要看只能被刷 $1$ ......
Educational Codeforces Round 152 (Rated for Div. 2) D. Array Painting
初始所有点都是蓝色的，给定一个数组，每个元素为0，1，2等值，两种操作，选定一个点花1元变红，或者选定一个为1或者2的红色点，减去一个价值，让周围的点变红，最后所有点都要变红 思路：贪心，对于一个数组来说我们找寻连续的不等于0的一段，判断每一段最多所能变红的 存在两种情况 010，这种情况花1可以最 ......
CF576E Painting Edges
根据不知从何而来的传统，考前需要写数据结构。 ### Part 1 如何判断二分图 你要是用染色法暴力过了这道题那就只能说是真神仙…… 但是我们可以使用染色的思想。 考虑到颜色数不多，可以开 $k$ 个**拓展域并查集**，对于原图每个点我们拆成两个：$i$ 和 $i+n$，如果 $i+n$ 和 $ ......
CF576E Painting Edges 题解
# CF576E Painting Edges ~~关于我看完题解后改了一个位置就过题导致我都不知道我怎么过的~~ 当然现在真的大彻大悟了。 ## 题意 给定一张 $n$ 个点，$m$ 条边无向图，有 $k$ 种颜色，初始每条边无颜色，给定 $q$ 个操作，每个操作某条边染成颜色 $c$。只有一个操 ......
AtCoder Beginner Contest 235 Ex Painting Weighted Graph
[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc235_h "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc235/tasks/abc235_h "AtCoder 传送门") 为啥洛谷唯一一篇题 ......
AtCoder Beginner Contest 242 Ex Random Painting
[洛谷传送门](https://www.luogu.com.cn/problem/AT_abc242_h "洛谷传送门") [AtCoder 传送门](https://atcoder.jp/contests/abc242/tasks/abc242_h "AtCoder 传送门") 好久没复习过 mi ......