576

CF576 Codeforces Round 319 (Div. 1) CF576A link CF576A题意 给定一个数字 \(n\)，现在 Vasya 要从 \(1\sim n\) 中想一个数字 \(x\)。 Petya 向 Vasya 询问 “\(x\) 是否能整除 \(y\)?” ，通过 ......

Painting Edges 动态加边和二分图容易想线段树分治,分别维护 k 种颜色的并查集。 不过每条边的存在时间不能确定。 设边 i 的两次操作的时间为 \(x_i,y_i\),那么对于 \(t\in[x_i+1,y_i-1]\) 有两种情况,颜色改变或改色不变。 则我们把每次操作影响的时间放在 ......

CF576D 把矩阵定义为 \(f_{t,i,j}\) 表示恰好 t 步后 i,j 是否可达,则广义乘法为 \[f_{t+1,i,j}=\sum_{k=1}^{n}f_{t,i,k}\wedge f_{1,k,j} \]因为是或操作,所以 \(f_{i,j}=1\) 时答案或上另一个乘数的第 j 行 ......

根据不知从何而来的传统，考前需要写数据结构。 ### Part 1 如何判断二分图 你要是用染色法暴力过了这道题那就只能说是真神仙…… 但是我们可以使用染色的思想。 考虑到颜色数不多，可以开 $k$ 个**拓展域并查集**，对于原图每个点我们拆成两个：$i$ 和 $i+n$，如果 $i+n$ 和 $ ......

[空降锣鼓](https://www.luogu.com.cn/problem/P2024 "空降锣鼓") [空降OJ](http://oj.tfls.net/p/576 "空降OJ") 题解： ```c++ #include using namespace std; int n,k; int d, ......

# CF576E Painting Edges ~~关于我看完题解后改了一个位置就过题导致我都不知道我怎么过的~~ 当然现在真的大彻大悟了。 ## 题意 给定一张 $n$ 个点，$m$ 条边无向图，有 $k$ 种颜色，初始每条边无颜色，给定 $q$ 个操作，每个操作某条边染成颜色 $c$。只有一个操 ......