# ACM刷题之-POJ-3662(Telephone Lines)

Description Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system. There are N (1 ≤ N ≤ 1,000) forlorn telephone poles conveniently numbered 1..N that are scattered around Farmer John’s property; no cables connect any them. A total of P (1 ≤ P ≤ 10,000) pairs of poles can be connected by a cable; the rest are too far apart. The i-th cable

# ACM刷题之-POJ-3333(Co-workers from Hell)

Description A watchman has to check a number of chambers in the factory each night according to a schedule which specifies the order in which the chambers must be visited and the time it takes to check each chamber. The watchman starts his job each night starting from the first chamber and leaves the factory and goes home when he checks the final chamber. He normally checks all other chambers, but in our story he may not actually do so. Having access to this schedule, a co-worker wants to

# ACM刷题之-POJ-3006(Dirichlet's Theorem on Arithmetic Progre)

Description If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, …, contains infinitely many prime numbers. This fact is known as Dirichlet’s Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837. For example, the arithmetic sequence beginning with 2 and i

# ACM刷题之-POJ-1405(Heritage)

Description Your rich uncle died recently, and the heritage needs to be divided among your relatives and the church (your uncle insisted in his will that the church must get something). There are N relatives (N <= 18) that were mentioned in the will. They are sorted in descending order according to their importance (the first one is the most important). Since you are the computer scientist in the family, your relatives asked you to help them. They need help, because there are some blanks i

# ACM刷题之-POJ-1192(最优连通子集)

Description 众所周知，我们可以通过直角坐标系把平面上的任何一个点P用一个有序数对(x, y)来唯一表示，如果x, y都是整数，我们就把点P称为整点，否则点P称为非整点。我们把平面上所有整点构成的集合记为W。 定义1 两个整点P1(x1, y1), P2(x2, y2)，若|x1-x2| + |y1-y2| = 1，则称P1, P2相邻，记作P1P2，否则称P1, P2不相邻。 定义 2 设点集S是W的一个有限子集，即S = {P1, P2,…, Pn}(n >= 1)，其中Pi(1 <= i <= n)属于W，我们把S称为整点集。 定义 3 设S是一个整点集，若点R, T属于S，且存在一个有限的点序列Q1, Q2, ?, Qk满足: 1. Qi属于S（1 <= i <= k）; 2. Q1 = R, Qk = T; 3. QiQi + 1(1 <= i <= k-1)，即Qi与Qi + 1相邻; 4. 对于任何1 <= i < j <= k有Qi ≠ Qj; 我们则称点R与点T在整点集S上连通，把点序列Q1, Q....

# ACM刷题之-POJ-1185(炮兵阵地)

Description 司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input 第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符(‘P’或者’H’)，中间没有空格。按顺序表示地图中每

# ACM刷题之-POJ-1021(2D-Nim)

Description The 2D-Nim board game is played on a grid, with pieces on the grid points. On each move, a player may remove any positive number of contiguous pieces in any row or column. The player who removes the last piece wins. For example, consider the left grid in the following figure. The player on move may remove (A), (B), (A, B), (A, B, C), or (B,F), etc., but may not remove (A, C), (D, E), (H, I) or (B, G). For purposes of writing 2D-