此方法已经被hack掉了,不过大家也可以继续看看本蒟蒻的一些想法TAT
7.16的更新:
昨晚我调试了一下,发现好像……和搜索的起点有关系?
换了下搜索起点,有时候就是对的,有时候就是错的。。。?
于是启用了随机交换点的编号这种方法。。。
然后(又一次)通过了。。(大雾)
7.16 11:25
然而算法本质还是错误的。。
然后(又一次)被hack了。。
QAQ
本贴就此完结。。。
拿到这个题的时候,因为我太弱了,根本没想到题解的公式方案什么的。
感觉可以通过按照一定顺序确定点的颜色,进而求出求每个点能染几种颜色,然后用乘法原理乱搞搞。
于是整了这么个做法:
对每个位置,求出在确定一些点的颜色之后,其可用的颜色种数,记为$c_i$。
答案就是$\prod_{i=1}^{n}c_i$
于是每个联通块进行bfs:
对于当前队头的点,它的c是与它相邻的,已经计算完的不同的$c_i$。
这个可以直接计算得到。
算完之后,将其相邻点入队。
然后这么做就能A了。。。
稍微给点注释:
flag:是否已经统计过$c_i$。
inq:是否已入过队。
c:刚才提到的那个$c_i$。
就直接搜……也没用到题解的相关知识啊QAQ
所以我想问的就是:这个做法是不是对的呢?
如果是对的,如何证明其正确性?
如果是错的,如何hack它?
恳请诸位dalao指教QAQ
UPD:刚刚发现被hack了,正在研究中。。。(我果然还是太弱了)
UPD2:确实这样会有问题,我的算法应该是错误的(这种数据明明很好造啊 QAQ)
感谢闷声hack我的一位神犇 bvvqdlpo 。