Skip to content

紫禁城

子衿的居宫

Archive

Category: POJ

During his last sabbatical, professor M. A. Ya made a surprising discovery about the old Maya calendar. From an old knotted message, professor discovered that the Maya civilization used a 365 day long year, called Haab, which had 19 months. Each of the first 18 months was 20 days long, and the names of the months were pop, no, zip, zotz, tzec, xul, yoxkin, mol, chen, yax, zac, ceh, mac, kankin, muan, pax, koyab, cumhu. Instead of having names, the days of the months were denoted by numbers starting from 0 to 19. The last month of Haab was called uayet and had 5 days denoted by numbers 0, 1, 2, 3, 4. The Maya believed that this month was unlucky, the court of justice was not in session, the trade stopped, people did not even sweep the floor.

For religious purposes, the Maya used another calendar in which the year was called Tzolkin (holly year). The year was divided into thirteen periods, each 20 days long. Each day was denoted by a pair consisting of a number and the name of the day. They used 20 names: imix, ik, akbal, kan, chicchan, cimi, manik, lamat, muluk, ok, chuen, eb, ben, ix, mem, cib, caban, eznab, canac, ahau and 13 numbers; both in cycles.

Notice that each day has an unambiguous description. For example, at the beginning of the year the days were described as follows:

1 imix, 2 ik, 3 akbal, 4 kan, 5 chicchan, 6 cimi, 7 manik, 8 lamat, 9 muluk, 10 ok, 11 chuen, 12 eb, 13 ben, 1 ix, 2 mem, 3 cib, 4 caban, 5 eznab, 6 canac, 7 ahau, and again in the next period 8 imix, 9 ik, 10 akbal . . .

Years (both Haab and Tzolkin) were denoted by numbers 0, 1, : : : , where the number 0 was the beginning of the world. Thus, the first day was:

Haab: 0. pop 0

Tzolkin: 1 imix 0
Help professor M. A. Ya and write a program for him to convert the dates from the Haab calendar to the Tzolkin calendar.

题意:
告诉你2种历法的计算方法,给你一种,求另一种……
直接看
参考代码:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* 
 * Problem: pku_1008
 * Author: 子衿
 * Date: 2010/7/13
 * Site: http://zi-jin.com
*/
#include <stdio.h>
#include <string.h>
 
int main()
{
    const char HaabMonths[19][10] =
    {
        "pop",
        "no",
        "zip",
        "zotz",
        "tzec",
        "xul",
        "yoxkin",
        "mol",
        "chen",
        "yax",
        "zac",
        "ceh",
        "mac",
        "kankin",
        "muan",
        "pax",
        "koyab",
        "cumhu",
        "uayet"
    },Tzolkin[20][10] =
    {
        "imix",
        "ik",
        "akbal",
        "kan",
        "chicchan",
        "cimi",
        "manik",
        "lamat",
        "muluk",
        "ok",
        "chuen",
        "eb",
        "ben",        
        "ix",
        "mem",
        "cib",
        "caban",
        "eznab",
        "canac",
        "ahau"
    };
    //有人问:day为什么要用float?
    //答:因为它输入格式给得怪,后面有个'.'
    float day;
    int n, month, year, t, i;
    char chMonth[10];
    scanf("%d", &n);
    printf("%d\n", n);
    while (scanf("%d%s%d", &day, chMonth, &year))
    {
        for (i = 0; i < 19; ++i)
            if (!strcmp(chMonth, HaabMonths[i]))
            {
                month = i;
                break;
            }
        t = year * 365 + month * 20 + day;
        printf("%d %s %d\n", t % 13 + 1, Tzolkin[t % 20], t / 260);
    }
}

One measure of “unsortedness” in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence “DAABEC”, this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence “AACEDGG” has only one inversion (E and D)—it is nearly sorted—while the sequence “ZWQM” has 6 inversions (it is as unsorted as can be—exactly the reverse of sorted).

You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of “sortedness”, from “most sorted” to “least sorted”. All the strings are of the same length.

题意就是给出一些DNA密码子的序列
对于序列里每一个A
设它排在了a[i]个C或G或T的后面
对于每一个C
设它排在了b[i]个G或T的后面
对于每一个G
设它排在了c[i]个T的后面

则每一个序列都有一个权值w[i] = sigma(a) + sigma(b) + sigma(c)
按权值将这些序列从小到大排序后输出

方法:写一个归排,对每一个序列求出逆序对数

参考代码:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/* 
 * Problem: pku_1007
 * Author: 子衿
 * Date: 2010/7/12
 * Site: http://zi-jin.com
*/
#include <stdio.h>
#include <string.h>
 
#define MAXM 100
#define MAXN 51
 
int n, m
char t[MAXN], c[MAXN];
 
struct Seq
{
    char ch[MAXN];
    int w;
    inline Seq() :w(0) {}
 
    void GetW()
    {
        strcpy(c, ch);
        MergeSort_GetW(0, n - 1);
    }
    void MergeSort_GetW(int left, int right)
    {
        int mid = (left + right) >> 1;
        left < mid ? MergeSort_GetW(left, mid) : 0;
        mid + 1 < right ? MergeSort_GetW(mid + 1, right) : 0;
        int i = left, j = mid + 1, k = left;
        while (i <= mid || j <= right)
        {
            if (j > right || (i <= mid && c[i] <= c[j]))
                t[k++] = c[i++];
            else
            {
                t[k++] = c[j++];
                w += mid - i + 1;
            }
        }
        for (i = left; i <= right; ++i)
            c[i] = t[i];
    }
}R[MAXM], tR[MAXM];
 
void MergeSort(Seq a[], int left, int right)
{
    int mid = (left + right) >> 1;
    left < mid ? MergeSort(a, left, mid) : 0;
    mid + 1 < right ? MergeSort(a, mid + 1, right) : 0;
    int i = left, j = mid + 1, k = left;
    while (i <= mid || j <= right)
    {
        if (j > right || (i <= mid && a[i].w <= a[j].w))
            tR[k++] = a[i++];
        else
        {
            tR[k++] = a[j++];
        }
    }
    for (i = left; i <= right; ++i)
        a[i] = tR[i];
}
 
int main()
{
    int i;
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; ++i)
    {
        scanf("%s", R[i].ch);
        R[i].GetW();
    }
    MergeSort(R, 0, m - 1);
    for (i = 0; i < m; ++i)
    {
        puts(R[i].ch);
    }
}

典型的模线性方程问题
复习一下数论中的中国剩余定理(CRT):
定理用来解一次同余式组的,比如:有一个数,除以3余2,除以5余3,除以7余2,问这个数最小是多少?
(《孙子算法》:“今有物不知其数,三三数之余二 ,五五数之余三 ,七七数之余二,问物几何?”)

答案是23:x≡2×70+3×21+2×15≡233≡23(mod105)

1.能被5和7 整除而被3除余1:5×7×2 =70,则被3除余2的数:70×2
2.能被3和7 整除而被5除余1:3×7 = 21,则被5除余3 的数: 21×3
3.能被3和5 整除而被7除余1:3×5 = 15,则被7 除余2 的数:15×2

推广:若m_1到m_k为两两互素的正整数,M = m_1 * m_2 * … * m_k = m_1*M_1 = m_2*M_2 = … = m_k*M_k,

则同余式组:

W≡r_1(mod m_1)
W≡r_2(mod m_2)
……
W≡r_k(mod m_k)

有且只有解
W≡ M_1*r_1+M_2*r_2+ … + M_k*r_k (mod M)

参考代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/* 
 * Problem: pku_1006
 * Author: 子衿
 * Date: 2010/7/11
 * Site: http://zi-jin.com
*/
#include <stdio.h>
 
const int m[3] = {23, 28, 33};
 
//最大公约数,并且gcd == a * x + b * y;
/*
int _gcd, t;
void gcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        _gcd = a;
        return;
    }
    gcd(b, a % b, x, y);
    t = x;
    x = y;
    y = t - a / b * y;
}
*/
 
//这里我给出利用CRT完整的实现,有一些这题用不到的,
//但其他题目可能要注意到的问题也一一列出
 
int solve(int m[], int r[], int k, int &M)
{
    //m[i]同文中的m_i
    //k同文中的k,本题是定值3,但其他题目中可能是变量
    int i, M_i, x, y, a = 0;
    for (i = 0, M = 1; i < k; M *= m[i++]);
    for (i = 0; i < k; ++i)
    {
        M_i = M / m[i];
 
        a = (a + M_i * r[i]) % M;
 
        //以下2步解决m[i]不两两互质的情况
        //gcd(m[i], M_i, x, y);
        //a = (a + y * M_i * r[i]) % M;
    }
    return (a + M) % M; //保证a非负
}
int main()
{
    int r[3], d, c = 1, ans, M;
    while (scanf("%d%d%d%d", &r[0], &r[1], &r[2], d) && r[0] != -1)
    {
        r[0] %= m[0];
        r[1] %= m[1];
        r[2] %= m[2];
        ans = solve(m, r, 3, M);
        while (ans < d)
            ans += M;
        printf("Case %d: the next triple peak occurs in %d days.\n", c, ans - d);
        ++c;
    }
}

求半圆的面积

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * Problem: pku_1005
 * Author: 子衿
 * Date: 2010/7/11
 * Site: http://zi-jin.com
*/
#include <stdio.h>
 
#define PI 3.14159
 
int main()
{
    int T, ans;
    float x, y;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++i)
    {
        scanf("%f%f", &x, &y);
        ans = PI * (x * x + y * y) / 100 + 1;
        printf("Property %d: This property will begin eroding in year %d.\n", i, ans);
    }
    puts("END OF OUTPUT.");
}

求12个数的平均数

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 
 * Problem: pku_1004
 * Author: 子衿
 * Date: 2010/7/11
 * Site: http://zi-jin.com
*/
#include <stdio.h>
 
int main()
{
    float f, s = 0.;
    while (scanf("%f", &f) != EOF)
        s += f;
    printf("$%.2f\n", s / 12);
}

题目就是给定一个浮点数f,问s = 1 + 1/2 + 1/3 + … + 1/n使得s > f, s – 1/n < f的n是多少

不用说题解了吧?
参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 
 * Problem: pku_1003
 * Author: 子衿
 * Date: 2010/7/11
 * Site: http://zi-jin.com
*/
#include <stdio.h>
 
int main()
{
    float f, t, i;
    while (scanf("%f", &f) && f > 0.00)
    {
        t = 0.;
        i = 1.;
        while (t < f)
        {
            ++i;
            t += (1 / i);
        }
        printf("%d card(s)\n", int(i - 1));
    }
}

Description
Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino’s by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their “three tens” number 3-10-10-10.

The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:

A, B, and C map to 2
D, E, and F map to 3
G, H, and I map to 4
J, K, and L map to 5
M, N, and O map to 6
P, R, and S map to 7
T, U, and V map to 8
W, X, and Y map to 9

There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.

Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.

电话号码有很多种格式,你要判断所有读入的信息中,全部转换为标准格式后每个电话号码是否有重复的,将所有不止出现一次的电话号码标准格式按字典序输出并在每一个的后面加上重复次数

题解:
首先当然是将所有的都转换成标准格式
然后把它们排序
排序后找相同的个数就容易了,而且也是字典序

参考代码:

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
44
45
46
47
48
49
50
51
52
53
54
/* 
 * Problem: pku_1002
 * Author: 子衿
 * Date: 2010/7/11
 * Site: http://zi-jin.com
*/
#include <stdio.h>
#include <stdlib.H>
#include <string.h>
 
#define MAXN 100001
 
inline int vcmp(const void *a, const void *b)
{
    return strcmp((char*)a, (char*)b);
}
 
int main()
{
    const char map[] = "2223334445556667777888999";
    int n, l, i, j, k;
    char Numbers[MAXN][9], Number[100];
    bool flag = true;
    scanf("%d", &n);
    k = 0;
    while (scanf("%s", Number) != EOF)
    {
        l = strlen(Number);
        j = 0;
        Numbers[k][3] = '-';
        for (i = 0; i < l; ++i)
        {
            if (Number[i] == '-')
                continue;
            j == 3 ? ++j : 0;
            Numbers[k][j] = (Number[i] >= 'A' && Number[i] < 'Z') ? map[Number[i] - 'A'] : Number[i];
            ++j;
        }
        Numbers[k][j] = '\0';
        ++k;
    }
    qsort(Numbers, n, 9, vcmp);
    for (i = 0; i < n;)
    {
        j = i;
        strcpy(Numbers[n], Numbers[j]);
        ++i;
        while (!strcmp(Numbers[i], Numbers[j]))
            ++i;
        i - j > 1 ? printf("%s %d\n", Numbers[j], i - j), flag = false : 0;
    }
    if (flag)
        puts("No duplicates.");
}

Description

Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.

This problem requires that you write a program to compute the exact value of Rn where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

计算R的n次方,R包含小数点最多有6位
输出的结果要求去掉最前最后所有0(包括0.5也要去掉0变成:.5)

题解:
将R读入到字符串
先处理掉小数点:
从字符串中删去小数点,记录小数点后的位数
将字符串中每个字符的值-48
则原本保存'1',现在保存1
进行n次高精度乘法后,将每个字符的值又+48
将小数点插到合适位置
删除前后多余的零

高精度乘法:
模拟手算乘法过程,双重循环一位一位乘,>9进位

参考代码:

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/* 
 * Problem: pku_1001
 * Author: 子衿
 * Date: 2010/7/10
 * Site: http://zi-jin.com
*/
#include <stdio.h>
#include <string.h>
 
int main()
{
    char R[7], ans[127];
    int t[125];
    int s, l, L, n, i, j, k;
    while (scanf("%s%d", R, &n) != EOF)
    {
        l = strlen(R);
        for (i = 0; i < l; ++i)
            if (R[i] == '.')
                break;
        s = l - i - 1;//R小数点后有s个数字
        for (; i < l; ++i)
            R[i] = R[i + 1];
        --l;
        for (i = 0; i < l; ++i)
            ans[i] = R[i] -= 48;
        L = l;
        for (i = 0; i < n - 1; ++i)
        {
            //高精度乘法
            memset(t, 0, sizeof(t));
            for (j = 0; j < L; ++j)
                for (k = 0; k < l; ++k)
                    t[j + k + 1] += ans[j] * R[k];
            for (j = L + l - 1; j > 0; --j)
            {
                t[j - 1] += t[j] / 10;
                ans[j] = t[j] % 10;
            }
            ans[0] = t[0];
            L +=l;
        }
        s *= n;//答案中小数点的位置
        for (i = 0; i < L - s; ++i)
            ans[i] += 48;
        for (j = L; j > L - s; --j)
            ans[j] = ans[j - 1] + 48;
        ans[i] = '.';
        j = -1, k = L + 1;//j,k分别记录最左最右不为0的数的位置
        while (ans[++j] == '0');
        while (ans[--k] == '0');
        ans[k] == '.' ? ans[k] = '\0' : ans[k + 1] = '\0';
        if (!j)
        {
            ans[0] = '\0';
            strcat(ans, ans + j);
        }
        puts(ans);
    }
}

Calculate a+b

计算并输出a+b
在这里我主要是想告诉大家输入输出时要注意的问题
那就是C++ 输入输出流中的cin效率非常低下
如果题目有大量输入输出,应该改用C中的scanf
而cout与scanf的效率差别就不那么大了,而且在不同的环境下,谁优谁劣还不一定,但在OJ中一般是printf效率高,可能本地cout效率又高一些

所以这里只给大家看看cout与scanf到底有多大差距

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
44
#include <stdio.h>
#include <iostream>
using std::cin;
using std::cout;
 
#define N 1000000
 
int main()
{
    freopen("~temp", "r", stdin);
    freopen("~temp", "w", stdout);
 
    clock_t t[2];
    int i, n;
 
    //由于先后顺序不同可能会造成不同的结果
    //(往往是放在前面的耗时长)所以我们将
    //效率高的放在前面,更能说明问题,但读
    //者仍应该尝试调换位置查看结果。
 
    for (i = 0; i < 2 * N; ++i)
    {
        printf("%d ", i);
    }
 
    fclose(stdout);
 
    t[0] = clock();
    for (i = 0; i < N; ++i)
    {
        scanf("%d", &n);
    }
    t[0] = clock() - t[0];
 
    t[1] = clock();
    for (i = 0; i < N; ++i)
    {
        cin >> n;
    }
    t[1] = clock() - t[1];
 
    freopen("result.txt", "w", stdout);
    printf("scanf:%ldms\ncin:%ldms\n", t[0], t[1]);
}

以下是我的测试结果:
scanf:653ms
cin:10926ms

怎么样?知道为什么自己TLE了吧?

Stats by WP SlimStat