Codeforces Round#432 简要题解

时间:2022-05-02 14:38:49

来自FallDream的博客,未经允许,请勿转载,谢谢。


Div2A 小判断题

Div2B 小判断题,合法的条件是|AB|=|BC|且三点不共线

Div1A 类比二维、三维空间,可以猜测n太大的时候没有答案。这样n小的时候我们就暴力就行啦。

Div1B 首先枚举gcd,然后每个数要么删除,要么向上补到第一个倍数。对个数做前缀和,然后枚举之前枚举的gcd的倍数,统计答案。细节比较多。

Div1C 不同质因数分开做。把1次是否出现、2次是否出现....压成一个数,求sg函数时枚举所有转移。这样n<=20的时候可以O(2^n*n)处理,质数是2的时候我们记忆化搜索搜一次就好啦。

Div1D 根据他给你的定律做,把ai排序一下。枚举点数m,f[i][j][k]表示前i个点,做到了第aj,出度之和是k是否可行,并且记录转移路径。如果f[m][n][m*(m-1)/2]可行,那么答案就是m。至于方案,跑一次简单的网络流就行啦。

Div1E 谁赢都是一样的,所以枚举赢两个人分别是什么状态赢的,然后分开每一位考虑,如果都赢了/都输了,那么方案数×2,不然方案数×1。也就是枚举两个赢的状态,答案加上2的(他们相同的位数)次方。这样就变成了一个FWT,把他给你的数组卷积上自己就行啦。当然最后答案乘以3

Div1F ...