Colored

很有意义很有思维量的图论题。（摸了好久做出来了，很有感觉） 本文的「环」均指简单环，「路径」均指简单路径。 初步 考虑这个「存在一条三种颜色的路径」这个限制其实是很弱的，首先的感觉就是我们随便画出一些连通图，随便选择三条边，基本都能找到一条经过这三条边的路径。 于是我们考虑将难以描述的弱限制单步容斥 ......

前言 看了这道题的几篇题解，感觉讲的方法都比较麻烦，这里讲一个感觉比较简单的方法。 思路 首先判断是否有解。计算一下每一行和每一列的牌的数量，只要有一个是奇数就无解，否则有解。证明显然，偶数一定可以分成两组，在纸上模拟一下也可以得出。 其次看如何构造。对于竖着的牌，显然只对每行有影响，因为列上的颜色 ......

郑重声明：原文参见标题，如有侵权，请联系作者，将会撤销发布！ Published as a conference paper at ICLR 2023 ABSTRACT ......

## 思路 首先考虑保证每行的黑白数量一样，横着的一定是贡献一黑一白，所以只用考虑竖着的，同理竖着的任何方案也不会影响横着的要求。 因为两个同行的竖着的颜色可以互换，所以在满足条件的情况下，谁黑谁白无所谓。 考虑从上往下满足，因为 ```D``` 的格子已经在上一行中确定了，所以可以在上一行时就先把 ......

## [$POJ$ $2513$ $Colored$ $Sticks$](http://poj.org/problem?id=2513) ### 一、题目描述 一堆木棍左右两端涂有颜色,相同颜色的可以连接在一起，问所有木棍能否都连上 ### 二、解题代码 ```cpp {.line-numbers} ......

非常纯正的换根DP，都写在注释里了 题目链接：https://codeforces.com/contest/1796/problem/E 代码链接：https://codeforces.com/contest/1796/submission/209931430 ``` /* 题意：将一棵树划分成若干 ......

称一条边在**环外**当且仅当其两端点不全在环上 用总方案数减去不合法的方案数，并分类讨论—— - **Case1：**图中不存在某种颜色的边 - 否则，若存在简单环的颜色集合为$\{1,2,3\}$，则环上每种颜色的边恰有一条 > 否则，若颜色为$1$的边数$\ge 2$，则去掉其中一条后得到的简 ......