April 11th, 2010POJ 3080 —— Blue Jeans

多个串,找到最长的公共子串。
数据量较小,直接 kmp 或者 strstr。
Read the rest of this entry »



April 11th, 2010POJ 3461 —— Oulipo

KMP 算法的基本应用。求在一个串中模式串出现了多少次。
Read the rest of this entry »



也是判断假币问题。
还要判出是重还是轻。
Read the rest of this entry »



April 10th, 2010POJ 1029 —— False coin

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 »



April 10th, 2010POJ 1423 —— Big Number

题意:求数 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.




© 2008 - 2012 道阻且长 | iKon Wordpress Theme | Powered by Wordpress 3.3.2