April 11th, 2010POJ 3080 —— Blue Jeans
多个串,找到最长的公共子串。
数据量较小,直接 kmp 或者 strstr。
Read the rest of this entry »
多个串,找到最长的公共子串。
数据量较小,直接 kmp 或者 strstr。
Read the rest of this entry »
KMP 算法的基本应用。求在一个串中模式串出现了多少次。
Read the rest of this entry »
也是判断假币问题。
还要判出是重还是轻。
Read the rest of this entry »
http://blog.sina.com.cn/s/blog_5c95cb070100cvtd.html
有多个硬币,其中一个是假的,根据输入的天平两边的等式或不等式,找出其中的块假币。
出现在等式两边的硬币无疑都是真硬币,假硬币必定出现在不等式中。有多少个不等式,假硬币肯定也出现多少次。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> using namespace std; const int MAXN = 1001; #define clr(x) memset(x, 0, sizeof(x)) int main() { char ch; int ans, count; int i, j, n, m, cnt = 0; int a[MAXN], val[MAXN], real[MAXN]; cin >> n >> m; clr(val); clr(real); while(m --) { cin >> a[0]; for(i = 1; i <= 2 * a[0]; i++) cin >> a[i]; cin >> ch; if(ch == '=') { for(j = 1; j <= 2 * a[0]; j++) real[a[j]] = 1; }else if(ch == '>') { cnt ++; for(j = 1; j <= a[0]; j++) val[a[j]] ++; for(j = a[0] + 1; j <= 2 * a[0]; j++) val[a[j]] --; }else { cnt ++; for(j = 1; j <= a[0]; j++) val[a[j]] --; for(j = a[0] + 1; j <= 2 * a[0]; j++) val[a[j]] ++; } } count = 0, ans = 0; for(i = 1; i <= n; i++) { if(real[i]) continue; if(val[i] == cnt || val[i] == -cnt) { count ++; ans = i; } } if(count != 1) printf("0\n"); else printf("%d\n", ans); return(0); } |
连连看,直接 bfs 搜索。
Read the rest of this entry »
题目:给定一个 N (10 < = N <= 10^9), 求满足以下条件的所有数对 (x,y):
y 为 x 去掉某个 10 进制位后形成的新数,比如可以从 1234 中去掉 3 得到 124;
y 总是比 x 少一位并可以以 0 开头, 如去掉 1002 的千位后得到 002。
x+y = N。
Read the rest of this entry »
http://blog.sina.com.cn/s/blog_5c95cb070100cy7z.html
从上到下逐层递推。
4 种操作,栈的基本使用。
一个 X 轴一侧有数个点,应该在 X 轴上放置几个圆,使得可以覆盖所有的点。点到 X 轴的垂直距离最大为圆半径。
Read the rest of this entry »
强烈推荐这种题目。
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n'th ugly number.
类似题目还有 POJ 2247。
Read the rest of this entry »
题意:求数 n 的阶乘有多少位数。
http://blog.sina.com.cn/s/blog_5c95cb070100czhu.html
大数加法,顺便要非常熟悉减法和乘除法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include<iostream> using namespace std; const int MAXN = 111; int main() { char s[MAXN]; int i, j, c[MAXN]; memset(c, 0, sizeof(c)); while(cin >> s) { if(strcmp(s, "0") == 0) break; int rear = MAXN - 1; for(i = strlen(s) - 1; i >= 0; i --) { c[rear] += s[i] - '0'; c[rear - 1] += c[rear] / 10; c[rear] %= 10; rear --; } } i = 0; while(c[i] == 0) i ++; for(j = i; j < MAXN; j ++) printf("%d", c[j]); printf("\n"); return(0); } |
直接计算,枚举,有些显而易见不满足的就直接跳过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <iostream> using namespace std; const int MAXN = 101; int main() { int i, j, k, n, cube, pw[MAXN]; scanf("%d", &n); for(i = 1; i < MAXN; i ++) pw[i] = i * i * i; for(cube = 3; cube <= n; cube ++) for(i = 2; i < cube; i ++) { if(pw[i] + pw[i + 1] + pw[i + 2] > cube * cube * cube) break; for(j = i + 1; j < cube; j ++) { if(pw[i] + pw[j] + pw[i + 2] > cube * cube * cube) break; for(k = j + 1; k < cube; k ++) { if(pw[i] + pw[j] + pw[k] > cube * cube * cube) break; if(pw[i] + pw[j] + pw[k] == cube * cube * cube) printf("Cube = %d, Triple = (%d,%d,%d)\n", cube, i, j, k); } } } return(0); } |
给定一批关键字,再给定一批句子,求出哪些句子包括尽可能多的关键字。
注意输入格式即可。
王、后、车、象的走子规则如下:
王:横、直、斜都可以走,但每步限走一格。
后:横、直、斜都可以走,每步格数不受限制。
车:横、竖均可以走,不能斜走,格数不限。
象:只能斜走,格数不限。
思路:设起点为(bx, by)终点为(ex, ey)。
(1)当起点和终点位置相同时,输出0 0 0 0.
(2)当起点和终点不同时:
1.王的最短步数为max(abs(bx - ex), abs(by, ey)).
原因:将起点与终点的连线进行直角坐标分解,得到一个直角三角形(bx, by) (ex, ey) 另一个点且假设为(bx, ey)(有四种情况)。则王的最短路径必是在这个三角形的范围内,不管可行的路径如何,最终路径的长度总反应在x轴和y轴的投影上,王最终最短路径的长度为king_step = max(abs(bx - ex),abs(by - ey));
2.后
对于后,当起点和终点在同行,或同列,或abs(bx - ex) == abs(by - ey)时,queen_step = 1;否则queen_step = 2;
3.车
对于车,当起点和终点在同行,或同列时,rook_step = 1;否则rook_step = 2;
4.象
对于象,当abs(bx, ex) 与abs(by, ey)奇偶相异时,不可能相互到达。否则,当abs(bx, ex) == abs(by, ey)时,最短步数为1,否则,最短步数为2.