我喊，盼星星盼月亮等了半年了，终于恢复正常！热烈祝贺ing！以后有时间上去切切题...

在北大的ACM排名中即将冲进1000了！1001是个我喜欢的数字，虽然很垃圾，但还是在此特别截图纪念一下，希望2到3年后能冲进排名100。一天一点积累，慢慢进步，向大牛们看齐，争取某天自己也能不小心地成为一头小牛。

 

太简单以至于没什么好说的。费时0ms，内存48k，郁闷，不明白为什么要用到48k。

 

#include <stdio.h>

 

int main()
{
    char code[] = {0,1,2,3,0,1,2,0,0,2,2,4,5,5,0,1,2,6,2,3,0,1,0,2,0,2}, s[20], i, prev;

 

    while (EOF != scanf("%s", s))
    {
        prev = '\0';
        for (i = 0; s[i]; ++i)
        {
            if (code[s[i] - 'A'] != prev && code[s[i] - 'A'])
                printf("%d", code[s[i] - 'A']);
            prev = code[s[i] - 'A'];
        }
        printf("\n");
    }
}

只需要运用高中学的数列知识即可解决此题，公式如下：

 

等差数列通项公式：An = A1 + (n - 1)d

等比数列通项公式：An = A1 * q ^ (n - 1)

 

费时0ms，内存48k。

 

#include <stdio.h>

int main()
{
    int t, a[4];

 

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d%d%d", &a[0], &a[1], &a[2], &a[3]);
        printf("%d %d %d %d ", a[0], a[1], a[2], a[3]);
        if (0 == (a[0] + a[2]) % a[1] && 0 == (a[1] + a[3]) % a[2])
            printf("%d\n", a[3] + a[1] - a[0]);
        else
            printf("%d\n", a[3] * (a[1] / a[0]));
    }
}

这道题用暴力推导就行，不会超时的 :) 其实是偶数学不好，没推出公式来，别人的0ms肯定是用公式做出来的。

 

费时560ms，内存48k。

 

#include <stdio.h>

 

int main()
{
    int n, i, j, sum, count = 0;

 

    scanf("%d", &n);

 

    for (i = 1; i <= n; ++i)
    {
        sum = 0;
        for (j = i; j <= n; ++j)
        {
            sum += j;
            if (sum >= n)
            {
                if (sum == n)
                    ++count;
                break;
            }
        }
    }
    printf("%d\n", count);
}

这道题是著名的歌德巴赫猜想 :) 我的思路是自顶向下匹配素数，这样可以节省许多内存空间，但缺点是所需的时间会比较多。

 

费时578ms，内存56k。

 

#include <stdio.h>
#include <math.h>

 

int isprime(const int n)
{
    int i, j = sqrt(n);

 

    for (i = 2; i <= j; ++i)
        if (0 == n % i)
            return 0;
    return 1;
}

 

int main()
{
    int n, i;

 

    while (1)
    {
        scanf("%d", &n);
        if (0 == n)
            break;

 

        for (i = n - 3; i >= 3; i -= 2)
        {
            if (!isprime(i))
                continue;
            if (isprime(n - i))
            {
                printf("%d = %d + %d\n", n, n - i, i);
                break;
            }
        }
        if (i < 3)
            printf("Goldbach's conjecture is wrong.\n");
    }
}

旱，这道题其实很简单，但因为开始没读懂题意，连续WA了2次，第3次才AC。费时0ms，内存48k。

 

#include <stdio.h>

 

int main()
{
    int n, s, d;

 

    scanf("%d", &n);
    while (n--)
    {
        scanf("%d%d", &s, &d);
        if (s < d || (s + d) % 2)
        {
            printf("impossible\n");
            continue;
        }
        printf("%d %d\n", (s + d) / 2, (s - d) / 2);
    }
}

算银行的利率，容易题。费时15ms，内存56k，不太明白为什么要用到15ms，变态啊！

 

#include <stdio.h>

 

int main()
{
    int r, m, y, i;
    double result = 0;

 

    scanf("%d%d%d", &r, &m, &y);
    result = m;
    for (i = 0; i < y; ++i)
        result += (result * r) / 100;
    printf("%d\n", (int)result);
}

这道题果然改成KMP就AC了。思路是寻找最大的重复子串，然后用字符串的长度减去这个找到的位置，再一除就是结果了。费时140ms，内存2988k。值得一提的是改进版的KMP要比传统的KMP快31ms（试验所得），所以最后我用了改进版的KMP。

 

#include <stdio.h>
#include <string.h>

 

char s[1000001];
short next[1000000];

 

int main()
{
    int i, j, len;

 

    while (1)
    {
        scanf("%s", s);
        if ('.' == s[0] && '\0' == s[1])
            break;

 

        len = strlen(s);
        i = 0;
        j = -1;
        next[0] = -1;
        while (i < len)
        {
            if (-1 == j || s[i] == s[j])
            {
                ++i;
                ++j;
                if (s[i] != s[j])
                    next[i] = j;
                else
                    next[i] = next[j];
            }
            else
                j = next[j];
        }
        i -= j;
        if (0 == len % i)
            i = len / i;
        else
            i = 1;
        printf("%d\n", i);
    }
}

题目要求一个字符串由多少个重复的子串连接组成，例如ababab由3个ab连接而成，因此答案为3，又例如abcd由1个abcd连接而成，因此答案为1。

 

我的程序如下，无语中，超时，不过算法应该是对的。先贴上来，等我改成KMP看看行不行。

 

#include <stdio.h>
#include <memory.h>

 

#define MAXLEN 1000000

 

int main()
{
    char s[MAXLEN + 1];
    int i, j, n, maxn;

 

    while (1)
    {
        scanf("%s", s);
        if ('.' == s[0] && '\0' == s[1])
            break;

 

        maxn = 1;
        for (i = 1; s[i]; ++i)
        {
            n = 1;
            for (j = i; s[j]; j += i)
            {
                if (0 == memcmp(s, &s[j], i))
                    ++n;
                else
                {
                    n = 1;
                    break;
                }
            }
            if (maxn < n)
                maxn = n;
        }
        printf("%d\n", maxn);
    }
}

弱智题，先求出前1000个素数，然后根据题目要求输出即可。费时0ms，内存60k。

 

#include <stdio.h>
#include <math.h>

 

#define MAXN 1000

 

int isprime(const int n)
{
    int i, j = sqrt(n);

 

    for (i = 2; i <= j; ++i)
        if (0 == n % i)
            return 0;
    return 1;
}

 

int main()
{
    int i, j, prime[MAXN], n, c;

 

    for (i = 1, j = 0; j < MAXN; ++i)
        if (isprime(i))
            prime[j++] = i;

 

    while (EOF != scanf("%d%d", &n, &c))
    {
        printf("%d %d:", n, c);
        for (i = 0, j = 0; prime[i] <= n; ++i)
            ++j;
        i = j / 2 - c;
        c *= 2;
        if (0 != j % 2)
        {
            --c;
            ++i;
        }
        if (i < 0)
            i = 0;
        if (c > j)
            c = j;
        for (; c; --c)
            printf(" %d", prime[i++]);
        printf("\n\n");
    }
}

这道题要求算N!的尾部有多少个0，例如5!=120，尾部有1个0，答案应该为1。刚开始我条件反射地想用高精度乘法，后来想想其实没有必要，因为一个数的阶乘的结果有多少个0是由有多少个5参与运算来决定的，例如5!=1*2*3*4*5=120，尾部的那个0是由1个5参与运算而产生的，因此这道题的算法可以转变为求N有多少个5。

 

费时125ms，内存48k。

 

#include <stdio.h>

 

int main()
{
    int t, n, count;

 

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        count = 0;
        while (n)
        {
            n = n / 5;
            count += n;
        }
        printf("%d\n", count);
    }
}

tnnd可能以前做USACO多了，一看到这题的第一行是讲奶牛的就立刻联想到这是USACO的题，翻下去看source，果然是USACO 2003 March Orange！-_-b...

 

费时15ms，内存16k。感动啊！第一次做出了内存低于24k的成绩来，不过我实在不明白为何会占用那么低，再次-_-  另外费时也太多了，实在是匪夷所思！

 

#include <stdio.h>
#include <string.h>
#include <ctype.h>

 

int main()
{
    int i, len;
    char key[27], s[81], ch;

 

    gets(key);
    gets(s);
    len = strlen(s);

 

    for (i = 0; i < len; ++i)
    {
        ch = s[i];
        if (isalpha(ch))
        {
            if (isupper(ch))
                ch = toupper(key[tolower(s[i]) - 'a']);
            else
                ch = key[s[i] - 'a'];
        }
        printf("%c", ch);
    }
}

这题的描述有点问题，不小心的话会理解错。费时0ms，内存24k。

 

#include <stdio.h>

 

int f(const int n)
{
    int i, j = 0;

 

    for (i = 1; i <= n; ++i)
        if (0 == n % i)
            ++j;

 

    return j;
}

 

int main()
{
    int n, nn, i, j;

 

    scanf("%d", &nn);
    while (nn--)
    {
        scanf("%d", &n);
        j = 0;
        for (i = 1; i <= n; ++i)
            if (f(i) % 2)
                ++j;
        printf("%d\n", j);
    }
}

弱智题，费时0ms，内存56k。

 

#include <stdio.h>

 

#define MAXN 10000

 

int main()
{
    int i, a[MAXN] = { 0 }, b, c;

 

    for (i = 1; i <= MAXN; ++i)
    {
        b = i;
        c = b;
        while (b)
        {
            c += b % 10;
            b /= 10;
        }
        if (0 <= c - 1 && c - 1 < MAXN)
            a[c - 1] = 1;
    }
    for (i = 0; i < MAXN; ++i)
        if (0 == a[i])
            printf("%d\n", i + 1);
}

又是一道高精度运算，加法。可能一次算完Fib数列保存好的话费时会少点，不过我偷懒了，让它每次都运算吧，反正数据量不大，肯定不会TLE的。

 

费时109ms，内存48k。

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

 

#define MAXLEN 101

 

void add(const int len_a, const char a[], const int len_b, const char b[], int *len_c, char c[])
{
    int i, j, temp, carry = 0;

 

    *len_c = 0;
    j = MAXLEN - max(len_a, len_b);
    for (i = MAXLEN - 1; i >= j; --i)
    {
        temp = a[i] + b[i] + carry;
        c[i] = temp % 10;
        carry = temp / 10;
        ++(*len_c);
    }
    if (carry)
    {
        c[i] = carry;
        ++(*len_c);
    }
}

 

void init(const len, char a[], int is_char)
{
    int i, j = MAXLEN - 1;

 

    for (i = len - 1; i >= 0; --i)
        a[j--] = a[i] - (is_char ? '0' : 0);
}

 

int compare(const int len_a, const char a[], const int len_b, const char b[])
{
    int i;

 

    if (len_a < len_b)
        return -1;
    else if (len_a > len_b)
        return 1;

 

    for (i = MAXLEN - len_a; i < MAXLEN; ++i)
    {
        if (a[i] < b[i])
            return -1;
        else if (a[i] > b[i])
            return 1;
    }

 

    return 0;
}

 

int main()
{
    char a[MAXLEN], b[MAXLEN], fn1[MAXLEN], fn2[MAXLEN], fib[MAXLEN];
    int len_fn1, len_fn2, len_fib, len_a, len_b, result1, result2, count;

 

    while (1)
    {
        scanf("%s %s", a, b);
        if ('0' == a[0] && '\0' == a[1] && '0' == b[0] && '\0' == b[1])
            break;

 

        len_a = strlen(a);
        len_b = strlen(b);
        init(len_a, a, 1);
        init(len_b, b, 1);

 

        count = 0;
        memset(fn1, 0, MAXLEN);
        memset(fn2, 0, MAXLEN);
        fn1[0] = 0;
        fn2[0] = 1;
        len_fn1 = 1;
        len_fn2 = 1;
        init(len_fn1, fn1, 0);
        init(len_fn2, fn2, 0);
        memset(fib, 0, MAXLEN);

 

        while (1)
        {
            add(len_fn1, fn1, len_fn2, fn2, &len_fib, fib);
            result1 = compare(len_fib, fib, len_a, a);
            result2 = compare(len_fib, fib, len_b, b);
            if (result2 > 0)
                break;
            if (0 <= result1 && result2 <= 0)   // a <= fib <= b
                ++count;

 

            len_fn1 = len_fn2;
            memcpy(fn1, fn2, MAXLEN);
            len_fn2 = len_fib;
            memcpy(fn2, fib, MAXLEN);
        }
        printf("%d\n", count);
    }
}

刚开始把问题想复杂了，甚至是理解错题意了。费时0ms，内存48k。

 

#include <stdio.h>
#include <string.h>

 

int main()
{
    int i, count, len;
    char line[257];

 

    while (EOF != scanf("%s", line))
    {
        count = 0;
        len = strlen(line);
        for (i = len - 1; i >= 0; --i)
        {
            if ('p' <= line[i] && line[i] <= 'z')
                ++count;
            else if ('N' == line[i])
            {
                if (0 == count)
                    break;
            }
            else if ('C' == line[i] || 'D' == line[i] || 'E' == line[i] || 'I' == line[i])
            {
                if (count >= 2)
                    --count;
                else
                {
                    count = 0;
                    break;
                }
            }
            else
            {
                count = 0;
                break;
            }
        }
        printf(1 == count ? "YES\n" : "NO\n");
    }
}

一定要把DP入门！现在做题的时候碰到DP就立刻跳过去，因为一直对DP都没有什么感觉，打算最近集中精力从最弱智的题开始尽量都过一次，一定要入门！

 

另外，有人批评我最近不写流水帐，实际上我贴的代码就是流水帐了。他们没搞明白“流水帐”这三个字的真正含义，特此鄙视之。

昨晚那个垃圾程序，偶晚上没关机跑了6个小时，总共才算出190个幻方来。今天向BSCH学习了一下，加入了一种剪枝的方法，立刻使速度提高无数倍，6分钟左右就能把7040种情况全部输出完，恐怖ing。注意，实际上只有880种，因为每一个幻方都会顺时针旋转4次，左右对称翻转1次，上下对称翻转1次，两条对角线翻转2次，总共重复了8次，880*8=7040。

 

这里还要讲讲全排列的生成。我们要运用高中学过的排列组合知识：n个数的全排列，实际上就是把第n个数往前n-1个数的中间插。比如说1、2、3的全排列，前两个数1、2的全排列是[1 2]和[2 1]，那么，把3往它们中间插：先把3插入[1 2]，就是[1 2 3]、[1 3 2]、[3 1 2]；往[2 1]插，就是[2 1 3]、[2 3 1]、[3 2 1]。如此可以用递归来推广到n。

 

然后再讲讲剪枝。如果要全排列出16个数字的所有情况来，一共有 16!=20922789888000 种可能性，然而大部分的可能性都是不能构成4阶幻方的，因此，我们的剪枝思路是尽可能早地cancel掉没有用的枚举。我们知道，4阶幻方每行只有4个数字，因而每当已经出枚举的个数为4的倍数时，也就是4、8、12，就可以看看该行的数字和是不是34（4阶幻方每行的和），如果不是的话，后面的枚举就没有必要继续了，这样每次最多能节省 (16-4)!=12!=479001600 次循环和判断！（大部分情况下都能节省，搜索到的幻方只占可能性总数的极小部分）

 

废话说完了，肯定还能优化的，以后有空再说。

 

#include <stdio.h>

 

#define MAGIC_NUM 34

 

int caseid = 0;
int magic[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};

 

int check()
{
    if (MAGIC_NUM != magic[0] + magic[1] + magic[2] + magic[3])
        return 0;
    // already compared:
    /*
    if (MAGIC_NUM != magic[4] + magic[5] + magic[6] + magic[7])
        return 0;
    if (MAGIC_NUM != magic[8] + magic[9] + magic[10] + magic[11])
        return 0;
    if (MAGIC_NUM != magic[12] + magic[13] + magic[14] + magic[15])
        return 0;
    */
    if (MAGIC_NUM != magic[0] + magic[4] + magic[8] + magic[12])
        return 0;
    if (MAGIC_NUM != magic[1] + magic[5] + magic[9] + magic[13])
        return 0;
    if (MAGIC_NUM != magic[2] + magic[6] + magic[10] + magic[14])
        return 0;
    if (MAGIC_NUM != magic[3] + magic[7] + magic[11] + magic[15])
        return 0;
    if (MAGIC_NUM != magic[0] + magic[5] + magic[10] + magic[15])
        return 0;
    if (MAGIC_NUM != magic[3] + magic[6] + magic[9] + magic[12])
        return 0;
    return 1;
}

 

void output()
{
    int i, j = 0;

 

    printf("Case %d\n-----------\n", ++caseid);
    for (i = 0; i < 16; ++i)
    {
        printf("%2d ", magic[i]);
        if (0 == (++j) % 4)
            printf("\n");
    }
    printf("\n");
}

 

void swap(int *a, int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

 

void arrange(const int n)
{
    int i;

 

    if (1 == n)
    {
        if (check())
            output();
    }
    else
    {
        if (0 == (n + 1) % 4)
        {
            switch (n)
            {
            case 3:
                if (MAGIC_NUM != magic[4] + magic[5] + magic[6] + magic[7])
                    return ;
                break;
            case 7:
                if (MAGIC_NUM != magic[8] + magic[9] + magic[10] + magic[11])
                    return ;
                break;
            case 11:
                if (MAGIC_NUM != magic[12] + magic[13] + magic[14] + magic[15])
                    return ;
                break;
            }
        }
        for (i = 0; i < n; ++i)
        {
            swap(&magic[i], &magic[n - 1]);
            arrange(n - 1);
            swap(&magic[i], &magic[n - 1]);
        }
    }
}

 

int main()
{
    arrange(16);
}

题目：请编程构造4阶幻方，所谓4阶幻方就是将1……4*4个连续整数，填入4*4的方格中，使横竖各行以及对角线上的数字的和等于常数。请列出所有可能的组合。

 

例如：

16  3  2 13

 5 10 11  8

 9  6   7 12

 4 15 14  1

 

它的每条横、竖、对角线上的数字的和都是34。

 

最直接、最垃圾的算法其实很简单：我们只要设置一个大小为16的数组，把数字1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16预存进去，然后对这个数组进行全排列（枚举），每排列一次，就判断一次这个数组的横、竖、对角线上数字的和是否相等，都相等的话表示这是一个4阶幻方，可以输出！

 

这个算法表面上看起来不难，但其实真正的难点在于：对4*4的矩阵进行全排列，总共有 16!=20922789888000 种可能性！这是一个相当大的数字，要全部枚举一次需要很长的时间！必须进行剪枝优化！

 

不过现在太晚了，凌晨1点多了，等以后有空再说吧。貌似4阶幻方总共只有880种，而且本质不同的4阶幻方只有4种，这意味着大部分的幻方都是基于某点对称的，一定能优化！

 

下面贴出我的未经优化的版本，有兴趣的话请编译一下并让它在后台运行，看看一天能不能跑完（不保证没bug，更不保证不会死循环）。

 

#include <stdio.h>

 

int caseid = 0;
int magic[] = {16, 3, 2, 13, 5, 10, 11, 8, 9, 6, 7, 12, 4, 15, 14, 1};

 

int check()
{
    int a = magic[0] + magic[1] + magic[2] + magic[3];

 

    if (a != magic[4] + magic[5] + magic[6] + magic[7])
        return 0;
    if (a != magic[8] + magic[9] + magic[10] + magic[11])
        return 0;
    if (a != magic[12] + magic[13] + magic[14] + magic[15])
        return 0;
    if (a != magic[0] + magic[4] + magic[8] + magic[12])
        return 0;
    if (a != magic[1] + magic[5] + magic[9] + magic[13])
        return 0;
    if (a != magic[2] + magic[6] + magic[10] + magic[14])
        return 0;
    if (a != magic[3] + magic[7] + magic[11] + magic[15])
        return 0;
    if (a != magic[0] + magic[5] + magic[10] + magic[15])
        return 0;
    if (a != magic[3] + magic[6] + magic[9] + magic[12])
        return 0;
    return 1;
}

 

void output()
{
    int i, j = 0;

 

    printf("Case %d\n-----------\n", ++caseid);
    for (i = 0; i < 16; ++i)
    {
        printf("%2d ", magic[i]);
        if (0 == (++j) % 4)
            printf("\n");
    }
    printf("\n");
}

 

void leftshift(const int m)
{
    int i, j = magic[0];

 

    for (i = 0; i < m; ++i)
        magic[i] = magic[i + 1];
    magic[i] = j;
}

 

void arrange(const int m, const int n)
{
    int i;

 

    if (m < n)
    {
        for (i = 0; i <= m; ++i)
        {
            arrange(m + 1, n);
            leftshift(m);
        }
    }
    else
    {
        if (check())
            output();
    }
}

 

int main()
{
    arrange(0, 16);
}