2016 沈航 ACM 校赛题解

12 月 25 日, 沈航 ACM 校赛很开心的举办了,这次比赛有 55 个队伍参加,也邀请了沈阳一些兄弟院校来友谊参赛,最终圆满结束,在这里记录一下每道题的解法。


Problem A 说反话

Description

大神众屌丝膜拜 觉得自己最近年老智力衰退了,想锻炼一下自己的反映速度,作为 ACM 的老队长,ACM 队员表示很乐意帮助他。
方式很简单,队员们说一个英文句子(一行),然后 大神众屌丝膜拜 把句子中的每个单词反转后输出。

Input

输入只有一行,一个由多个单词组成的英文句子,两个单词之间由一个或多个空格隔开,单词中没有特殊符号。每个单词不超过 50 个字符,一共不超过 500 个单词,句子总长不超过 50000。

Output

输出每个单词反转之后的字符串,不要改变单词的大小写,空格与原文保持一致。

Sample Input

hello World

Sample Output

olleh dlroW

解析

我这里用栈解决这个问题,遇到非空格字符就入栈,遇到空格就把栈中所有的字符输出,并输出空格即可。

Code

#include <stdio.h>

int main()
{
    int word[50], ch, top = 0;

    while(~(ch = getchar())) {
        if(ch == ' ') {
            while(top) putchar(word[--top]);
            putchar(ch);
        } else {
            word[top++] = ch;
        }
    }
    while(top) putchar(word[--top]);

    return 0;
}

Problem B 优雅的阶乘

Description

一个正整数的阶乘是所有小于及等于该数的正整数的积,并且 0 的阶乘为 1 。自然数n的阶乘写作 n! 。
但是我们的任务稍微复杂一点,要计算 1! + 2! + ... + n! 。

Input

输入包含多组数据,每组数据只有一个整数 n ,并且 (0 < n < 11) 。

Output

对于每组输入的 n ,输出 1! + 2! + ... + n! 的结果。

Sample Input

3
5
7

Sample Output

9
153
5913

解析

本场签到题,没啥说的。

Code

#include <stdio.h>

int main()
{
    int n;

    while(~scanf("%d", &n)) {
        int sum = 0, m = 1;
        for(int i = 1; i <= n; i++)
            sum += m *= i;
        printf("%d\n", sum);
    }

    return 0;
}

Problem C 不优雅的阶乘

Description

一个正整数的阶乘是所有小于及等于该数的正整数的积,并且 0 的阶乘为 1 。自然数n的阶乘写作 n! 。
我们的任务更复杂了一点,计算 1! + 2! + ... + n! 。

Input

输入包含多组数据,每组数据只有一个整数 n ,并且 (0 < n < 1111) 。

Output

对于每组输入的 n ,输出 1! + 2! + ... + n! 的结果。

Sample Input

33
55
77

Sample Output

8954945705218228090637347680100940313
12931604174610554792808543145134839786142796265765134511963408920420940313
147093731191520017915111951726939395484863652896205980410648566245268270960253582401634937653402336528920420940313

解析

高精度啊,用 Java 也能水过,用 C/C++ 写才有意思,比较锻炼代码能力吧我觉得。

Code

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

void mul(int *n, int m)
{
    for(int i = 1; i <= n[0]; i++)
        n[i] *= m;
    for(int i = 1; i < n[0]; i++) {
        if(n[i] >= 10000) {
            n[i + 1] += n[i] / 10000;
            n[i] %= 10000;
        }
    }
    if(n[n[0]] >= 10000) {
        n[n[0] + 1] = n[n[0]] / 10000;
        n[n[0]++] %= 10000;
    }
}

void add(int *n, int *m)
{
    for(int i = 1; i <= m[0]; i++) {
        if(i <= n[0]) n[i] += m[i];
        else n[i] = m[i];
    }
    if(n[0] < m[0]) n[0] = m[0];
    for(int i = 1; i < n[0]; i++) {
        if(n[i] >= 10000) {
            n[i + 1] += n[i] / 10000;
            n[i] -= 10000;
        }
    }
    if(n[n[0]] >= 10000) {
        n[n[0] + 1] += n[n[0]] / 10000;
        n[n[0]++] -= 10000;
    }
}

void print(int *n)
{
    printf("%d", n[n[0]]);
    for(int i = n[0] - 1; i > 0; i--)
        printf("%04d", n[i]);
}

int sum[1111][1024], fac[1024];

int main()
{
    int n;

    fac[0] = fac[1] = 1;
    sum[0][0] = 1; sum[0][1] = 0;
    for(int i = 1; i < 1111; i++) {
        sum[i][0] = 1; sum[i][1] = 0;
        mul(fac, i);
        add(sum[i], sum[i - 1]);
        add(sum[i], fac);
    }
    while(~scanf("%d", &n)) {
        print(sum[n]);
        putchar('\n');
    }

    return 0;
}

Problem D 阿甘再一次想知道线段的总长

Description

有一部脍炙人口的电影叫《阿甘正传》。里面提到过一个段子:
“当甘在跑步时闪过一则电视新闻,讲里根总统遭遇暗杀。而之后不久,阿甘进入珍妮的住所时,发现珍妮家里装了空调说了句“You get an air-conditionor.”
空调(air-conditionor)的发明正是和里根总统被刺有密切联系。里根遇刺后紧急抢救,当时是炎炎夏日,需要将病房温度降低才能进行手术,当时还没发明空调,手术无法进行。后来有人出想办法,把压缩空气机发热,还原空气制冷的原理,于是使用空气压缩机,最终使病房温度降下来,里根总统得以脱险。第一部空调也产生了。”
阿甘说:
There are N points in a axis(数轴),any two of these can match a 线段,each point can be 起点 or 终点。
阿甘想知道线段的总长。

Input

第一行,一个整数N,表示点数。
接下来N行,每行一个整数X_i,表示点的坐标。

(N <= 5000000 , -2500 <= X_i <= 2500)

Output

一个整数,表示线段的总长。

Sample Input

5
1
5
3
2
4

Sample Output

40

解析

Code

标签: 算法, acm

仅有一条评论

  1. What, follow me.

添加新评论