搜索结果
查询Tags标签： 染色，共有 18条记录-
P3177 树上染色做题记录
树形 dp 好题。 做这题的思想历程： 定义 \(dp_{i,j}\) 表示以 \(i\) 为根的子树中，选择了 \(j\) 个节点的答案。感觉还要带上一维状态就是所有黑点距离 \(i\) 的距离，这违反了做题思路中间的简洁性的原则。于是我们 查看题解。 经过不明方法之后，我们想到了定义 \(dp_…
2022/9/17 23:16:14 人评论 次浏览 -
最终的归宿 自做自切
U231111 最终的归宿 题解 观察到题目中 \((x, y) \oplus (y, z) = (z, x)\) 的特殊二元组生成方式，我们很容易联想到三元环，于是思考到能不能用图论解决这个问题。 具体在这个题目上，也就是给定了一个有向图，无重边有自环，一旦有 \(x \to y, y\to z\)，我们能迭代出一…
2022/7/25 6:52:54 人评论 次浏览 -
[luogu4429]染色
显然每一个连通块独立，不妨假设原图连通，并建立dfs树 假设树上有$k$条返祖边，并记其覆盖的点集分别为$V_{1},V_{2},...,V_{k}$ 显然有奇环时无解，因此不妨假设$\forall 1\le i\le k,|V_{i}|\equiv 0(mod\ 2)$，进而$|V_{i}|\ge 4$ 结论：恒有解$\iff \forall 1\le i&l…
2022/7/7 23:23:34 人评论 次浏览 -
2022暑假集训队选拔赛补题
E ginger的染色 首先对于一个排列 ，如果看成环图的结构，那么 就向 连一条无向边。所以对于任意一个排列就会产生若干个环，连通性可以用并查集维护，现在对每个点进行黑白染色，题意转换为对于环中任意相邻两点颜色不能相同，那么只有偶数元环才能够染色成二分图，而每个…
2022/6/21 23:24:33 人评论 次浏览 -
五一欢乐赛 方程的解 染色 光 无向图问题
比赛链接 考场上顺序开题。 \(\mathrm{A.}\mathbb{方程的解}\)：\(\mathrm{exgcd}\) 板子 \(\mathrm{B.}\mathbb{染色}\)：树形 \(\mathrm{dp}\) \(\mathrm{C.}\mathbb{光}\)：优化 \(\mathrm{dfs}\) \(\mathrm{D.}\mathbb{无向图问题}\)：这道题说了个啥？ 打开发现又是原…
2022/5/2 6:13:02 人评论 次浏览 -
染色（贪心+堆）
tyy 模拟赛 T2，打了 20 分暴力滚粗。 题目内容 .md 文件不在手边，明天再放上来。 解题思路 如果像我一样按题意模拟：枚举染色方案 \(\rightarrow\) 构造序列 \(a\rightarrow\) 比较字典序，那只能得 20 分了。实际上，所谓 \((t_i,i)\) 从大到小排序，就是让多的尽量多…
2021/11/15 23:41:11 人评论 次浏览 -
染色（贪心+堆）
tyy 模拟赛 T2，打了 20 分暴力滚粗。 题目内容 .md 文件不在手边，明天再放上来。 解题思路 如果像我一样按题意模拟：枚举染色方案 \(\rightarrow\) 构造序列 \(a\rightarrow\) 比较字典序，那只能得 20 分了。实际上，所谓 \((t_i,i)\) 从大到小排序，就是让多的尽量多…
2021/11/15 23:41:11 人评论 次浏览 -
【题解】【BZOJ】AGC008F Blackout
AGC006F BlackoutAGC006F Blackout1 题外话什么神仙题目2 sol对黑格子\((x,y)\) ，连一条\(x->y\) 的边 此时问题变为如果存在\(x->y,y->z\) 的边，那么添加一条\(z->x\) 的边，最后统计总共有多少条边 现在我们只考虑每个弱连通块怎么统计 尝试对每一个弱连通…
2021/9/1 23:10:54 人评论 次浏览 -
【题解】【BZOJ】AGC008F Blackout
AGC006F BlackoutAGC006F Blackout1 题外话什么神仙题目2 sol对黑格子\((x,y)\) ，连一条\(x->y\) 的边 此时问题变为如果存在\(x->y,y->z\) 的边，那么添加一条\(z->x\) 的边，最后统计总共有多少条边 现在我们只考虑每个弱连通块怎么统计 尝试对每一个弱连通…
2021/9/1 23:10:54 人评论 次浏览 -
[jsoi2015]染色问题
题意:P6076 思路： 容斥+dp 有三种下限要求方案数？我们来层层降维。 首先\(ans=(-1)^{c-i}*C_c^i*f[i]\) f[i]表示至多i种颜色且满足另外两限制的方案数。 很多时候我们发现，"随便","至多","至少"要好求很多，而我们要"恰好"时…
2021/8/26 23:09:47 人评论 次浏览 -
[jsoi2015]染色问题
题意:P6076 思路： 容斥+dp 有三种下限要求方案数？我们来层层降维。 首先\(ans=(-1)^{c-i}*C_c^i*f[i]\) f[i]表示至多i种颜色且满足另外两限制的方案数。 很多时候我们发现，"随便","至多","至少"要好求很多，而我们要"恰好"时…
2021/8/26 23:09:47 人评论 次浏览 -
一类经典的树形染色问题
题目 1. 2种做法，一种是 $O(nk\log n)$，另一种是 $O(n)$。前者可以从深度大的开始填（优先队列维护）。后者只需要开 $f[0][x]$ 表示 $x$ 离关键点的最近距离，$f[1][x]$ 表示 $x$ 离没被控制的最远点的距离。考虑 $f[0][x]+f[1][x] \le k$ ，$x$ 就能被控制。$f[1][x]=…
2021/8/12 6:36:36 人评论 次浏览 -
一类经典的树形染色问题
题目 1. 2种做法，一种是 $O(nk\log n)$，另一种是 $O(n)$。前者可以从深度大的开始填（优先队列维护）。后者只需要开 $f[0][x]$ 表示 $x$ 离关键点的最近距离，$f[1][x]$ 表示 $x$ 离没被控制的最远点的距离。考虑 $f[0][x]+f[1][x] \le k$ ，$x$ 就能被控制。$f[1][x]=…
2021/8/12 6:36:36 人评论 次浏览 -
「ARC105F」Lights Out on Connected Graph
题目 点这里看题目。 分析 手玩容易发现 good graph 的第二条要求等价于 \(G\) 是二分图。说明： 设 \(x_u\) 表示某种方案中 \(u\) 是否被操作。 那么有 \(|E|\) 条方程。对于 \((u,v)\in E\)，方程的形式为 \(x_u\oplus x_v=1\)。 取出任意的相邻两条边，比如 \((u,v),(…
2021/8/9 23:37:17 人评论 次浏览 -
「ARC105F」Lights Out on Connected Graph
题目 点这里看题目。 分析 手玩容易发现 good graph 的第二条要求等价于 \(G\) 是二分图。说明： 设 \(x_u\) 表示某种方案中 \(u\) 是否被操作。 那么有 \(|E|\) 条方程。对于 \((u,v)\in E\)，方程的形式为 \(x_u\oplus x_v=1\)。 取出任意的相邻两条边，比如 \((u,v),(…
2021/8/9 23:37:17 人评论 次浏览
