正式开始做网上流传甚广的poj训练计划。
poj1753 - Flip Game
大意：4*4的黑白硬币。每翻动一个，四个相邻的硬币也会跟着翻动。问最少能翻出全黑或全白的次数。
题解：每枚硬币要么翻要么不翻，列出所有情况得出答案。
1 #include <stdio.h> 2 3 const int M = 100; 4 5 int choose[16]; 6 int go[5][2] = {{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; 7 int a[4][4], b[4][4]; 8 int ans = M; 9 10 11 int check(int b[4][4]) { 12 int flag1 = 0, flag2 = 0; 13 for (int i = 0; i < 4; i++) 14 for (int j = 0; j < 4; j++) 15 if (!b[i][j]) { 16 flag1 = 1; 17 } else { 18 flag2 = 1; 19 } 20 return !(flag1 && flag2); 21 } 22 23 int ok(int x, int y) { 24 return x >= 0 && x < 4 && y >= 0 && y < 4; 25 } 26 27 void search(int w) { 28 if (w == 16) { 29 int cnt = 0, u, v; 30 for (int i = 0; i < 4; i++) 31 for (int j = 0; j < 4; j++) { 32 b[i][j] = a[i][j]; 33 } 34 for (int i = 0; i < 16; i++) { 35 if (choose[i]) { 36 cnt++; 37 u = i / 4; 38 v = i % 4; 39 for (int i = 0; i < 5; i++) { 40 int x = u + go[i][0]; 41 int y = v + go[i][1]; 42 if (ok(x, y)) { 43 b[x][y] = 1 - b[x][y]; 44 } 45 } 46 } 47 } 48 if (check(b) && cnt < ans) { 49 ans = cnt; 50 } 51 return; 52 } 53 for (int i = 0; i < 2; i++) { 54 choose[w] = i; 55 search(w + 1); 56 } 57 } 58 59 60 int main() { 61 int choose[16]; 62 char c; 63 for (int i = 0; i < 4; i++) { 64 for (int j = 0; j < 4; j++) { 65 scanf("%c", &c); 66 if (c == ‘b‘) { 67 a[i][j] = 1; 68 } else { 69 a[i][j] = 0; 70 } 71 } 72 getchar(); 73 } 74 search(0); 75 if (ans == M) { 76 printf("Impossible\n"); 77 } else { 78 printf("%d\n", ans); 79 } 80 return 0; 81 }
poj2965 - The Pilots Brothers‘ refrigerator
大意：4*4的开关。每改变一个开关的状态，同行同列的也会被改变状态，问最少改变状态的次数。
题解：类似1753，每个开关要么动要么不动，枚举。
1 #include <stdio.h> 2 3 int a[4][4]; 4 int b[4][4]; 5 int table[16], s[16]; 6 int ans = 100; 7 8 int check(int a[4][4]) { 9 for (int i = 0; i < 4; i++) 10 for (int j = 0; j < 4; j++) 11 if (a[i][j]) { 12 return 0; 13 } 14 return 1; 15 } 16 17 void search(int w) { 18 if (w == 16) { 19 int cnt = 0; 20 for (int i = 0; i < 4; i++) 21 for (int j = 0; j < 4; j++) { 22 b[i][j] = a[i][j]; 23 } 24 for (int i = 0; i < 16; i++) { 25 if (s[i]) { 26 cnt++; 27 int u = i / 4; 28 int v = i % 4; 29 for (int j = 0; j < 4; j++) { 30 b[u][j] = 1 - b[u][j]; 31 b[j][v] = 1 - b[j][v]; 32 } 33 b[u][v] = 1 - b[u][v]; 34 } 35 } 36 if (check(b) && cnt < ans) { 37 ans = cnt; 38 int w = 0; 39 for (int i = 0; i < 16; i++) 40 if (s[i]) { 41 table[w++] = i; 42 } 43 } 44 return; 45 } 46 for (int i = 0; i < 2; i++) { 47 s[w] = i; 48 search(w + 1); 49 } 50 } 51 52 int main() { 53 char c; 54 for (int i = 0; i < 4; i++) { 55 for (int j = 0; j < 4; j++) { 56 scanf("%c", &c); 57 a[i][j] = (c == ‘-‘ ? 0 : 1); 58 } 59 getchar(); 60 } 61 search(0); 62 printf("%d\n", ans); 63 for (int i = 0; i < ans; i++) { 64 printf("%d %d\n", table[i] / 4 + 1, table[i] % 4 + 1); 65 } 66 return 0; 67 }
poj1328 - Radar Installation
大意：x轴上方有n个岛屿，用半径为d的圆去圈（圆心在x轴上）。问最少要用到几个这样的圆。做不到则输"-1"。
题解：贪心。若只考虑某一岛屿，算出圆尽可能往左偏和尽可能往右偏对应的两个圆心x和y，那么圆心在[x, y]范围内的圆都能圈住该岛屿。按x从小到大排序。
当考虑某岛屿时，若此之前的所有岛屿对应的y值比该岛屿的x值要大。那新的圆心只要在[x, min(y)]之前，就能覆盖所有岛屿。反之，说明前面有岛屿和当前岛屿的圆心范围不重叠，那就增加一个新圆把之前所有岛屿覆盖掉，然后不再考虑那些被覆盖的岛屿，继续往下看。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 double *a[1003]; 9 int d; 10 11 double getPos(double x, double y, double w) { 12 return x + w * sqrt(d * d - y * y); 13 } 14 15 bool func(const double *a, const double *b) { 16 return a[0] < b[0]; 17 } 18 19 int getAns(double **a, int n) { 20 int all = 1; 21 double compare = a[0][1]; 22 for (int i = 1; i < n; i++) { 23 if (a[i][0] > compare) { 24 compare = a[i][1]; 25 all++; 26 } else if (a[i][1] < compare) { 27 compare = a[i][1]; 28 } 29 } 30 return all; 31 } 32 33 void print(double **a, int n) { 34 for (int i = 0; i < n; i++) { 35 cout << a[i][0] << " " << a[i][1] << endl; 36 } 37 cout << endl; 38 } 39 40 int main() { 41 int n; 42 int z = 0; 43 int x, y; 44 for (int i = 0; i < 1003; i++) { 45 a[i] = (double *)malloc(sizeof(double) * 2); 46 } 47 while ((cin >> n >> d) && n && d) { 48 int flag = 1; 49 for (int i = 0; i < n; i++) { 50 cin >> x >> y; 51 if (y > d) { 52 flag = 0; 53 } 54 a[i][0] = getPos(x, y, -1); 55 a[i][1] = getPos(x, y, 1); 56 } 57 cout << "Case " << ++z << ": "; 58 if (flag) { 59 sort(a, a + n, func); 60 //print(a, n); 61 cout << getAns(a, n) << endl; 62 } else { 63 cout << "-1" << endl; 64 } 65 } 66 return 0; 67 }
poj2109 - Power of
Cryptography
大意：给出n和p。存在k^n=p。求k。
题解：nlog10(k)=log10(p). p是个很大的数字。先把它分解成r*10^k的形式(r是x.xxxx的形式)。k可以根据位数直接判断出来。答案是10^((k + log10(r)) / n).
View Code
poj2524 - Ubiquitous Religions
大意：n个人。给出m对同信仰的人。问信仰种类的最大可能数。
题解：简单并查集，同一信仰的归到一起。
1 #include <stdio.h> 2 3 int f[50003]; 4 int flag[50003]; 5 6 int get(int x) { 7 return f[x] == x ? x : f[x] = get(f[x]); 8 } 9 10 int main() { 11 int n, m, x, y; 12 int w = 0; 13 while (~scanf("%d%d", &n, &m) && (n || m)) { 14 for (int i = 1; i <= n; i++) { 15 f[i] = i; 16 flag[i] = 0; 17 } 18 for (int i = 0; i < m; i++) { 19 scanf("%d%d", &x, &y); 20 int u = get(x); 21 int v = get(y); 22 f[u] = v; 23 } 24 int all = 0; 25 for (int i = 1; i <= n; i++) { 26 int k = get(i); 27 if (!flag[k]) { 28 flag[k] = 1; 29 all++; 30 } 31 } 32 printf("Case %d: %d\n", ++w, all); 33 } 34 return 0; 35 }
poj2506 - Tiling
大意：用1*2和2*2的矩阵填2*x的大矩阵。总方案数。
题解：F[i] = 2 * F[i - 2]（2个横向的1*2矩阵或者1个2*2矩阵填在最后） + F[i - 1]（竖立的1*2矩阵填在最后）;
1 import java.util.*; 2 import java.math.BigInteger; 3 4 public class Main 5 { 6 public static void main(String arg[]) 7 { 8 Scanner in = new Scanner(System.in); 9 BigInteger f[] = new BigInteger[251]; 10 f[0] = BigInteger.valueOf(1); 11 f[1] = BigInteger.valueOf(1); 12 for (int i = 2; i <= 250; i++) 13 f[i] = f[i - 1].add(f[i - 2].add(f[i - 2])); 14 while (in.hasNext()) 15 { 16 System.out.println(f[in.nextInt()].toString()); 17 } 18 } 19 }
poj1068 - Parencodings
大意：S (((()()()))) P：4 5 6 6 6 6 W：1 1 1 4 5 6， s是配对好的括号序列。P[i]代表第i个‘)‘前有多少个‘(‘。W[i]代表从和第i个‘)‘配对的‘(‘开始到该’)‘间，有多少个‘)‘(包括自己)。给出P序列，求W序列。
题解：记下标从0开始。right[i]代表当前右括号的位置, 那么right[i] = p[i] + i - 1; left[i]代表当前右括号所对应的左括号的位置，count[pos]表示从位置pos开始往前，配对好的括号序列长度。例如(()())。下标若从0开始，当前操作第3个右括号。那么right[3] = 5, count[4] = 4, left[3] = 0. 容易发现 left[i] = right[i] - count[right[i] - 1] - 1; count[pos] = count[left[i] - 1] + right[i] - left[i] + 1（之前连续配对好的加上刚配对好的区间）; 在新配对好的区间内有一半是右括号，所以ans[i] = (right[i] - left[i] + 1) / 2;
1 #include <stdio.h> 2 #include <string.h> 3 4 int count[100], ans[100]; 5 6 int main() { 7 int t, n, x; 8 scanf("%d", &t); 9 while (t--) { 10 memset(count , 0, sizeof(count)); 11 scanf("%d", &n); 12 for (int i = 1; i <= n; i++) { 13 scanf("%d", &x); 14 int right = x + i - 1; 15 int left = right - count[right - 1] - 1; 16 ans[i] = (right - left + 1) / 2; 17 count[right] = (left ? count[left - 1] : 0) + ans[i] * 2; 18 } 19 for (int i = 1; i < n; i++) { 20 printf("%d ", ans[i]); 21 } 22 printf("%d\n", ans[n]); 23 } 24 return 0; 25 }
poj1573 - Robot Motion
大意：从一个入口进入迷宫。按"NSEW"的指示走，直到走出迷宫外或进入死循环。输出相应信息。
题解：纯模拟，用一个值记录当前步数。走到迷宫外或走到走过的格子就结束了。
1 import java.util.*; 2 3 public class Main { 4 public static void main(String args[]) { 5 Scanner in = new Scanner(System.in); 6 while (true) { 7 int n = in.nextInt(); 8 int m = in.nextInt(); 9 int y = in.nextInt(); 10 if (n == 0) { 11 break; 12 } 13 String[] s = new String[n]; 14 int[][][] a = new int[n + 1][m + 1][2]; 15 int[][] f = new int[n + 1][m + 1]; 16 for (int i = 0; i < n; i++) { 17 s[i] = in.next(); 18 } 19 for (int i = 0; i < n; i++) 20 for (int j = 0; j < m; j++) { 21 char c = s[i].charAt(j); 22 if (c == ‘N‘) { 23 a[i + 1][j + 1][0] = -1; 24 a[i + 1][j + 1][1] = 0; 25 } else if (c == ‘S‘) { 26 a[i + 1][j + 1][0] = 1; 27 a[i + 1][j + 1][1] = 0; 28 } else if (c == ‘W‘) { 29 a[i + 1][j + 1][0] = 0; 30 a[i + 1][j + 1][1] = -1; 31 } else { 32 a[i + 1][j + 1][0] = 0; 33 a[i + 1][j + 1][1] = 1; 34 } 35 } 36 int x = 1; 37 int now = 1; 38 f[x][y] = 1; 39 while (true) { 40 int tx = x + a[x][y][0]; 41 int ty = y + a[x][y][1]; 42 x = tx; 43 y = ty; 44 now++; 45 if (x == 0 || y == 0 || x == n + 1 || y == m + 1) { 46 System.out.println(String.format("%d step(s) to exit", now - 1)); 47 break; 48 } 49 if (f[x][y] > 0) { 50 System.out.println(String.format("%d step(s) before a loop of %d step(s)", f[x][y] - 1, now - f[x][y])); 51 break; 52 } 53 f[x][y] = now; 54 } 55 } 56 } 57 }
原文：http://www.cnblogs.com/nilmo/p/3566760.html
