POJ

POJ-2154 Color

置换群,burnside引理的题目。

这道题代表了一类题目的优化

裸的算法是 ∑n^(gcd(n,i)) 1<i<=n

复杂度过高,进行优化。

置换群种循环的个数L = n / gcd(n, i)

因为如果L | n, 则有n / L | n

则环的长度L的范围是1 ~ sqrt(L)

令a = gcd(n, i), 设i = at

则只有i与t互质的时候,gcd(i, t) = a

则最后可以优化为 ∑(Φ(i) * n ^ (i)) % p

POJ-2409 Let it Bead and POJ-1286 Necklace of Beads

###POJ-2409 Let it Bead

m个珠子n种颜色,求一共能制造出多少串不同的珠子。

Pólya定理,先求置换群。

1.旋转置换

依次顺时针旋转1 ~ n个,循环个数为gcd(i, n)

2.翻转置换

当n为偶数时,分两种情况,一种是中心轴在两个对称对象上,则循环个数为n/2+1,另一种是对称轴两边分别有n/2个对象,则循环个数为n/2;

当n为奇数时,对称轴就只能在一个对象上,则循环个数为n/2+1;

POJ-1328 Radar Installation

题目传送门: POJ 1328

给一个平行与 x 轴的海岸线,y < 0 部份为土地,y > 0部份为海,在海上有小岛,小岛的坐标给出,现在在海岸线上装雷达,雷达的覆盖范围为半径为 d 的圆,求最少要多少雷达能够覆盖所有岛,若是无法覆盖所有的岛,输出 -1 。

具体来说,先以 x 坐标排序,对于一个岛,求出可以覆盖它的雷达的位置在 x 轴上的范围,若两可检测的两小岛的雷达范围有重叠,则两小岛可公用一个雷达检测,最后用贪心来求雷达的最小数量就行。

若小岛的 y 坐标大于雷达的半径,就无法检测到了。

POJ-2965 The Pilots Brothers‘ refrigerator

题目传送门: POJ 2965

给一个矩阵,矩阵中只有“+”和“-”,“+”代表关闭的开关,“-”代表打开的开关,现在需要把所有的开关打开。

每次改变一个开关的状态,就同时会改变同一行或者同一列的开关的状态。

使用枚举就可以了,运用二进制来表示开关的状态= w=

POJ-1753 Flip Game

题目传送门: POJ 1753

给一个4 * 4的网格,每个格子中放白棋子或者黑棋子。

定义一个翻转操作,白子变黑子,黑子变白子。

每次可以对棋子进行一个操作,若操作的棋子是第i行第j列,则(i,j) (i - 1, j) (i + 1, j) (i, j - 1) (i, j +1)均进行翻转,越界的棋子就不翻转了。

最后问操作至全白或全黑的最小操作数。

具体就是一个不难的枚举题。

具体枚举方法是先对第一行进行操作(共16种)。

以后每一行操作,使上一行全为白或全为黑。

最后如果最后一行不满足全为白或黑,就无法达到操作要求,否则可以达到要求。

POJ-2195 Going Home

题目传送门: POJ 2195

给一张图,图上标记号小人与房子,小人的数目等于房子的数目,要求每个小人都走入不同的房子,小人能够水平或者竖直移动,每移动一格花费一,可以走过房子而不进入,问最小的花费。

KM模板题,用最大权匹配做,把边权变为负值就变成了最小权匹配。

POJ-3026 Borg Maze

题目传送门: POJ 3026

题目大概意思是#是墙,不能走,S是起点,A是目标点,要求从S出发走到所有点,路径不可交叉,然后求最小的路径和。

就是一个BFS+MST的题,自己BFS写的有问题,真是够糟糕的。。。

POJ-3020 Antenna Placement

题目传送门:POJ 3020

题意就是用圈来圈,求用多少圈能把圈完。

属于最大独立集问题,开始不知道这个,想了半天Orz。

最大独立集的定义是图中两两互不相邻的顶点构成的集合。

有个结论是最大独立集+最小覆盖集=V,而最小覆盖集=最大匹配,所以我们可匈牙利算法来做这个题。