华南师大 2017 年 ACM 程序设计竞赛新生初赛题解

华南师大 2017 年 ACM 程序设计竞赛新生初赛题解

华南师范大学第很多届 ACM 程序设计竞赛新生赛（初赛）在 2017 年 11 月 20 日 - 27 日成功举行，共有 146 名同学有效参赛（做出 1 题）。进入决赛的资格初定为完成并通过 5 题或以上，决赛时间是 12 月 3 日，地点未定。

题解

被你们虐了千百遍的题目和 OJ 也很累的，也想要休息，所以你们别想了，行行好放过它们，我们来看题解吧。。。

A. 诡异的计数法

Description

cgy 太喜欢质数了以至于他计数也需要用质数表示！在他看来，2（第一小质数）表示1，3（第二小质数）表示2……可正因为他的计数方法太奇葩，所以他的数学成绩非常差而且拖累了他的绩点。 lxy 得知 cgy 的绩点排名之后打算告诉他，可是必须以极度麻烦的 cgy 质数计数法的方式表示。 lxy 出重金 ¥(10000000 mod 10) 请你来为他解决这个诡异的计数。

Input

输入包括多组数据，每组数据各占一行，每一行有一个正整数 n ，表示 cgy 的绩点排名，输入到文件结尾结束（ \(n \leq 100000\) ，数据组数 \(t \leq 1000000\) ）。

Output

对应每组数据输出一个质数，为 cgy 绩点排名的质数计数法。

Sample Input

1

2

28

13

Sample Output

2

3

107

41

Hint

1. 本场比赛是网络初赛，除了不能抄袭其他选手代码外，对任何知识和资料的检索获取不作限制；
2. A 题并不是最简单的，题目难度不按顺序，请量力而为~
3. 如有其他疑问请看补充说明 https://d.wps.cn/v/8pBAU

题目大意

求第 \(K\) 个质数的值

参考思路

可以选用埃氏筛法（Sieve of Eratosthenes）、欧拉筛法（Sieve of Euler）来做预处理，之后就可以直接输出。

注意先计算出第 100000 个素数是 1299709 ，所以记录数组只要开到 MaxN ，但标记数组要开到 MaxP 。

时间复杂度 \(O(NloglogN)\) 或 \(O(N)\) 。

参考代码

标程使用了埃氏筛法：

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

int n,cnt;
int notprime[10000010];
int prime[5000010];

int main(void)
{
    for (int i=2;i<=sqrt(10000000)+1;++i)
        if (!notprime[i])
            for (int j=2*i;j<=10000000;j+=i)
                notprime[j]=1;
    for (int i=2;i<=10000000;++i)
        if (!notprime[i])
        {
            ++cnt;
            prime[cnt]=i;
        }
    while (~scanf("%d",&n))
        printf("%d\n",prime[n]);

    return 0;
}

ZYJ 的欧拉筛解：

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

const int MaxN = 1E5;
const int MaxP = 1299709;

int primes[MaxN + 1], cnt;
char isPrime[MaxP + 1];

void init() {
    memset(isPrime, 0xff, sizeof(isPrime));
    for (int i = 2; i <= MaxP; ++i) {
        if (isPrime[i]) {
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * primes[j] <= MaxP; ++j) {
            isPrime[i * primes[j]] = 0;
            if (!(i % primes[j])) {
                break;
            }
        }
    }
}

int main() {
    int N;
    init();
    while (~scanf("%d", &N)) {
        printf("%d\n", primes[N]);
    }
    return 0;
}

了解到计院方面教的是 cin/cout 的输入输出方法，由于某人出题事故导致 cin/cout 会被卡超时，公平起见放松了数据；进而导致优化的试除法可以险过（过滤偶数、循环外开方、懒计算），时间复杂度 \(O(N \sqrt{N})\) ：

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

const int MaxN = 1E5;

int cnt = 1, primes[MaxN + 1] = {-1, 2};

int isPrime(const int& n) {
    int q = (int)sqrt(n) + 1;
    for (int i = 2; i < q; ++i) {
        if (!(n % i)) {
            return 0;
        }
    }
    return 1;
}

int getPrime(const int& n) {
    if (cnt < n) {
        for (int i = primes[cnt] + 1; cnt < n; ++i) {
            if ((n & 1) && isPrime(i)) {
                primes[++cnt] = i;
            }
        }
    }
    return primes[n];
}

int main() {
    int N;
    while (~scanf("%d", &N)) {
        printf("%d\n", getPrime(N));
    }
    return 0;
}

B. 数发票

Description

cgy 组织了某外出活动准备到学院报销，学院给了他一定的差旅费报销金额。而 cgy 平时是一个十分注重收集公交车发票的人，他的手上有无数张不同面值的发票，现在他想计算最少要多少张发票可以恰好达到报销金额。 cgy 忙着整理这些发票，于是把这个任务交给了一起外出的你，你需要仔细计算否则就拿不到外出的车费了。

Input

输入第一行是一个正整数 T 表示数据组数。接下来是多组数据，每组数据第一行是正整数 n ，分别表示 cgy 有 n 种面值的发票（每种都有无数张），接下来一行有 n 个由空格隔开的正整数，表示这 n 种面值的大小，再下一行是一个正整数 x 表示报销金额(T,x<=1000; n<=100)。

Output

对于每一组数据，输出能凑齐报销金额的最少的发票张数，如果不能正好凑齐则输出 -1 。

Sample Input

2

3

1 3 5

11

2

3 5

7

Sample Output

3

-1

Hint

样例解释：

第一组数据中 11=5+5+1=5+3+3 ，最少要用 3 张

第二组数据中无论多少张都凑不齐 7 元，输出 -1

题目大意

有 \(N\) 种物品和一个容量为 \(X\) 的背包，每种物品都有无限件可以使用。若存在一种方案使得刚好放满背包，求这种方案中所使用物品的最小件数。

参考思路

动态规划，完全背包问题变种，时间复杂度 \(O(NX)\) 等。

参看《背包九讲》。

参考代码

标程：

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

int kase,n,x,c[1010];
int dp[1010];

int main(void)
{
    scanf("%d",&kase);
    while (kase--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for (int i=0;i<n;++i)
            scanf("%d",&c[i]);
        scanf("%d",&x);
        for (int i=0;i<=x;++i)
            for (int j=0;j<n;++j)
                if (i>c[j] && dp[i-c[j]])
                {
                    if (!dp[i])
                        dp[i]=dp[i-c[j]]+1;
                    else
                        dp[i]=dp[i-c[j]]+1<dp[i]?dp[i-c[j]]+1:dp[i];
                }
                else if (i==c[j])
                    dp[i]=1;
        if (dp[x])
            printf("%d\n",dp[x]);
        else
            printf("%d\n",-1);
    }

    return 0;
}

ZYJ：

#include <stdio.h>

inline void getMin(int& a, const int b) {
    if (a > b) a = b;
}

const int INF = 0x3f3f3f3f;
const int MAXN = 101;
const int MAXX = 1010;

int N, amount;
int cost[MAXN];
int dp[MAXX];

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", cost + i);
    }
    scanf("%d", &amount);
}

void work() {
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        int tmp = INF;
        for (int j = 0; j < N; ++j) {
            if (cost[j] <= i) {
                getMin(tmp, dp[i - cost[j]]);
            }
        }
        dp[i] = tmp + 1;
    }
    printf("%d\n", dp[amount] >= INF ? -1 : dp[amount]);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

C. ljc 吃糖

Description

ljc 喜欢吃糖，每一颗糖能够给他提供一个单位的脑能量。对于每道题，他至少要有 m1 能量才会考虑去做，且 AC 这道题需要消耗 m2 能量（即 ljc 能量数大于等于 m1 时才能去 AC 这道题，AC 完成后 ljc 剩余(当前能量值-m2)能量）。

现在 ljc 的初始能量为 n，比赛题目数为 k，问若 ljc 想要 AK （All-Killed，即 AC 所有题目），则他至少要准备多少颗糖?

Input

第一行输入一个正整数 T 表示数据组数，每组第 1 行两个数 n, k，接下来 k 行为两个正整数 m1, m2。

保证所有数据 \(T, n, k, m1, m2 \leq 1000\)，且 \(m1 \geq m2\) 。

Output

每组数据占一行，输出 ljc 至少要准备的糖的数目。

Sample Input

1

0 8

4 2

6 4

8 6

10 8

12 10

14 12

16 14

18 16

Sample Output

74

Hint

ljc 做题的顺序可以任意排列，顺序不同， AK 所需要的糖数不一定相同。

如果要用到排序，你可以调用 C 语言的 qsort 函数或者 C++ 的 sort 函数。

题目大意

给定一系列若干个任务，每个任务都有一个先验条件 precondition 和完成消耗 cost ，现在拥有有限的不可再生资源数量 N ，问最少需要补充多少资源才能完成所有任务。

该问题是“给定不可补充资源，问最多能完成哪些任务”的变种，难度持平。

参考思路

贪心算法。时间复杂度 \(O(klogk)\) 。

假定当前最大可用能量为 N ，任务队列为 prob[] ，如果一个任务 \(prob_i\) 不能被完成，一定是它的先验需求 \(prob_i.m1 > N\) ，否则由于 \(m1 \leq m2\) 一定成立，任何一个任务都可以被选择完成。


再假定存在两个任务 a 和 b 能够按顺序完成，那么一定要 \(a.m2 + b.m1 < b.m2 + a.m1\) ，因为先完成的任务会先消耗能量，若前面任务消耗得太多，则会导致不满足后面任务的先验条件，进而需要不断地补充能量。如果一系列任务都能满足这一条件，就可以尽量少地补充能量，使得能量利用效率最大化。因此我们可以基于这一思想给任务排序。

进一步也可以转化为 \(a.m1 - a.m2 > b.m1 - b.m2\) 即对差值排序，思想也是类似的。

参考代码

没找到标程，以下由 ZYJ 提供：

#include <stdio.h>
#include <algorithm>

using std::sort;

const int MaxN = 1000;

struct Problem {
    int precond, cost;
    int priority;
    bool operator<(const Problem& cmp) const {
        return priority > cmp.priority;
    }
} prob[MaxN];

int n, k;

void read() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; ++i) {
        scanf("%d%d", &prob[i].precond, &prob[i].cost);
        prob[i].priority = prob[i].precond - prob[i].cost;
    }
}

void work() {
    sort(prob, prob + k);
    int res = 0;
    for (int i = 0; i < k; ++i) {
        if (n >= prob[i].precond) {
            n -= prob[i].cost;
        } else {
            res += prob[i].precond - n;
            n = prob[i].precond - prob[i].cost;
        }
    }
    printf("%d\n", res);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

D. 姓名字母排列

Description

自古以来，如果如何排列一份无序名单是一个具有争议性、颇为麻烦的问题。通常的做法是按照姓名拼音的英文字母排字典序。

某一天 Zyj 突发奇想，能不能把所有人的名字拼在一起成为一个串，并且这个串在所有拼接方案中字典序是最小的呢？比如有三个人的名字：zyh、zy、zyj，显然会有以下六种组合（加入空格是便于阅读，实际排列不应有空格）：

zyh zy zyj

zyh zyj zy

zy zyh zyj

zy zyj zyh

zyj zyh zy

zyj zy zyh

显然只有第二种 zyhzyjzy 是所有方案中字典序最小的。

现在给你一份名单，你能找出这个最小方案吗？

Input

第一行输入一个正整数 \(N < 10^6\) 代表名字数量。

接下来 \(N\) 行，每行输入一个只含小写字母的字符串（当然也不含空格），代表每个人的名字。

保证一个人的名字最大长度不超过 20 ，保证所有人名字长度的总和小于 \(10^6\) 。

Output

输出名字排列拼接方案，要在所有可行方案中满足字典序最小。

Sample Input

3

hello

world

zyj

Sample Output

helloworldzyj

Hint

如果要用到排序，你可以调用 C 语言的 qsort 函数或者 C++ 的 sort 函数。

题目大意

原原题：《最大数》，1998 年 NOIP 全国联赛提高组，codevs 1860；

原题：《ZLM 的扑克牌》，2015 年华南师范大学 ACM 新生赛（逃；

给定若干个小写的英文字母串，求一种方案使得所有串按该方案的顺序相邻首尾拼接后，得到的新串在所有方案中字典序最小。

参考思路

贪心算法，需要先严格弱序化（strict weak ordering）。

1. 单串字典序不决定拼接串字典序。如果就英文字母串的属性来说，显然每个串都有一个“A-Za-z”的“字典序”，既然有一个约定成俗的字典序，它们之间当然是可比的，也可以排序；但是并不能证明按照字典序排好的串拼接起来，得到的新串在所有拼接方案中，它也是按字典序的极小元或极大元。很容易找到反例： bacd 和 b 可以拼接成 bacdb 和 bbacd 两种， 虽然 b 是原串集合 {b, bacd} 中的极小元，但 bbacd 不是拼接串集合 {bacdb, bbacd} 的极小元，因此 b 不能排在 bacd 的前面。
2. 建立新关系。基于上面的思考，很容易想到将原串集合任意元素两两拼接比较。对于任意串 A 和 B ，大概有 3 种情况：
   • A 和 B 在开头处没有公共子串。直接按字典序排就好了，比如 AB < BA 显然能决定出 A < B ；
   • A 和 B 在开头处有一个短的公共子串。这时 A 可以分解为 PQ 而 B 可以分解为 PR ，对于 Q 和 R 的比较又回到了第一种情况；
   • A 是 B 在开头的子串，或反过来。假如是前者，则 B 可以分解为 AP ，对 AAP 和 APA 的比较实际上是第二种情况，对 A 和 P 的比较。但如果 A 和 P 又在开头处有公共子串，甚至是循环的呢？比如 A 和 B ，而 B = AA..AP 甚至 B = AA..AQR 且 A = QSQS..QS 呢？这时 A 比较短，先补齐到 B 的长度，有可能是 A/P 甚至是 S/Q 、 S/R 、 Q/R 的比较，取决于循环节的长度。

参考代码

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

const int MaxCount = 1E6 + 1;
const int MaxLength = 20 + 1;

int N;
char names[MaxCount][MaxLength] = {0};

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", names[i]);
    }
}

int namesCmp(const void* a, const void* b) {
    static char p[MaxLength << 1], q[MaxLength << 1];
    strcat(strcpy(p, (char*)a), (char*)b);
    strcat(strcpy(q, (char*)b), (char*)a);
    return strcmp(p, q);
}

void work() {
    qsort(names, N, MaxLength, namesCmp);
    for (int i = 0; i < N; ++i) {
        printf("%s", names[i]);
    }
    putchar('\n');
}

int main() {
    read();
    work();
    return 0;
}

E. Substring

Description

一个字符串的子串表示原字符串中一段连续的部分。例如，字符串"121"的子串总共有六个，它们分别是"1"(前一个),"2","1"(后一个),"12","21"和"121"。但"11"不是"121"的子串，因为两个'1'在原串中不连续。我们认为空串也不是子串。

现给你一个只含有'0'和'1'两种字符的字符串，问它含有相同'0'和'1'的子串有几个。例如，字符串"0101"中符合条件的子串有4个。它们分别是"01"(前一个),"10","01"(后一个),"0101"。

Input

输⼊只有一行，为给定的字符串。字符串长度不超过100，且只包含'0'和'1'两种字符。

Output

输出为一个数，表示符合条件的子串的个数。注意最后有一个换行符。

Sample Input

00110011

Sample Output

10

Hint

字符串"00110011"中符合条件的子串分别为"01"(前一个),"10","01"(后一个),"0011" (前一个),"0110","1100","1001","0011"(后一个),"011001","00110011"，共10个。

题目大意

给定任意 01 串，求含有相同数量的 '0' 和 '1' 的连续子串有多少个。

参考思路

遍历计数。时间复杂度 \(O(L^2)\) 或 \(O(L^3)\) ，其中 \(L = |S|\) 即字符串的长度。

从左到右扫一遍字符串，统计中间扫过的 '0' 和 '1' 的数量，若数量相等则扫过的子串符合条件，进行累加。

由于一个字符串的子串有 \(L + (L - 1) + \ldots + 2 + 1 = \frac{L(L + 1)}{2}\) 个，所以可能要遍历 \(L\) 次起点， \(1 \ldots (L - i)\) 次终点。

参考代码

\(O(L^3)\) 复杂度的解法：

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

char str[101];

void read() {
    scanf("%s", str);
}

void work() {
    int len = strlen(str);
    int res = 0;
    for (int i = 0; i < len; ++i) {
        for (int j = i; j < len; ++j) {
            int zeroCnt = 0, oneCnt = 0;
            for (int k = i; k <= j; ++k) {
                str[k] == '0' ? ++zeroCnt : ++oneCnt;
            }
            if (zeroCnt == oneCnt) {
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

int main() {
    read();
    work();
    return 0;
}

\(O(L^2)\) 复杂度的解法只在一念之间，只要你愿意想：

void work() {
    int len = strlen(str);
    int res = 0;
    for (int i = 0; i < len; ++i) {
        int zeroCnt = 0, oneCnt = 0;
        for (int j = i; j < len; ++j) {
            str[j] == '0' ? ++zeroCnt : ++oneCnt;
            if (zeroCnt == oneCnt) {
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

F. 法特狗

Description

众所周知， cgq 因为脸黑而没有去玩法特狗这一款游戏，不过他老板 gou4shi1 经常问他某个英灵厉不厉害，为了一劳永逸， cgq 决定写个程序给所有英灵打个分。

在法特狗里，每张卡牌都对应着一个英灵。设 \(n\) 为卡池里所有卡牌的数目， \(m\) 为卡池里有多少张卡牌 y 使得，英灵 x 的所有属性都大于等于英灵 y 的对应属性（注意， y 可以是 x 本身），则英灵x的评分为 \(\frac{m}{n}\) 。

现在认为每个英灵只有四个属性（耐久、敏捷、魔力、幸运），每个属性只有四个等级（ABCD ， A 最强， D 最弱）。给出一个卡池所有英灵的属性，要求给所有英灵评分。

Input

输入第一行是一个整数 n （ \(1 \le n \le 100000\) ），代表卡池里所有卡牌的数目。

接下来是 n 行，每行四个大写字母，分别代表每个英灵的耐久、敏捷、魔力、幸运。

Output

输出 n 行，每行一个浮点数（小数点后保留两位），代表每个英灵的评分。

Sample Input

4

AAAA

AAAD

CBCD

DDDD

Sample Output

1.00

0.75

0.50

0.25

Hint

1.00 = 4/4

0.75 = 3/4

0.50 = 2/4

0.25 = 1/4

题目大意

给定若干个物品，每个物品含有四个属性，每个属性又有四种值，当且仅当一个物品所有属性的值都小于等于另一个物品，才可以说这个物品比另一个物品弱。求对于任意一个物品，比它弱的物品数。

参考思路

四维偏序关系（partial ordering relation）计数。

虽然有四个维度，但由于每一个维度的范围较小，所以状态数有限，只有 \(4^4 = 256\) 个，完全可以用标记数组记录一下：先预处理出同一种状态的卡牌有多少张，对于每种卡牌，找出比它弱的卡牌数量，最后根据卡牌的输入顺序直接计算输出答案。时间复杂度 \(O(256 \times 256 + N)\) 或 \(O(256N)\) 。

L2M 说可以将每个状态加起来，时间复杂度 \(O(4 \times 256 + N)\) 。

标记数组可以是 'D' - 'A' 变基映射成 0 - 3 的四维属性数组，这样大概会有 5 或 8 个 for 循环；也可以是存储哈希（hash）成四进制数的一维状态数组；当然某些同学直接打表算状态也可以，就是有点奇怪hhh。

易错点解析

1. 偏序关系不可比：由于 C/C++ 函数库里的排序方法要求严格弱序，而这里是四维偏序，即任意两个物品 \(X\) 和 \(Y\) ，当且仅当 \(X.p1 \leq Y.p1\) 且 \(X.p2 \leq Y.p2\) 且 \(X.p3 \leq Y.p3\) 且 \(X.p4 \leq Y.p4\) 都满足时才有 \(X \preccurlyeq Y\) ，比如 \(ABCD \preccurlyeq AABB\) ，但 \(ABCD\) 和 \(BACD\) 不可比较。你可以根据偏序关系的定义来自己证明一下，总之是不可以直接进行比较排序（comparison sort）的，即使 hash 成四进制数也不行（数字本身也是严格序）；
2. 数据漂移：由于要计算并输出浮点数，部分用 float 的同学有可能会遇到浮点数数据漂移问题；
3. 卡牌可重复：一张卡牌只可能是有限的 256 种状态，卡池里 \(N\) 张牌肯定有重复的；但最后却要根据卡牌的输入顺序来输出（即相等可重复但不相同）；
4. 反向映射：因为原来的属性值是 'A' - 'D' ，如果按这个顺序映射成 0 - 3 的话，大概就是 'D' < 'A' 等价于 3 > 0 ，这样要小心，对属性值的关系比较要反着来；如果 0 - 3 代表 'D' - 'A' 就不用费这脑细胞了。

参考代码

标程 1 （\(O(256N)\)）:

#include <stdio.h>

const int N = 1e5 + 10;
const int M = 4;
int a0[N], a1[N], a2[N], a3[N];
int b[M][M][M][M];

int main() {
    int n;
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%c%c%c%c\n", &a0[i], &a1[i], &a2[i], &a3[i]);
        a0[i] = 'D' - a0[i]; a1[i] = 'D' - a1[i]; a2[i] = 'D' - a2[i]; a3[i] = 'D' - a3[i];
        b[a0[i]][a1[i]][a2[i]][a3[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        int ans = 0;
        for (int j0 = 0; j0 <= a0[i]; ++j0)
            for (int j1 = 0; j1 <= a1[i]; ++j1)
                for (int j2 = 0; j2 <= a2[i]; ++j2)
                    for (int j3 = 0; j3 <= a3[i]; ++j3)
                        ans += b[j0][j1][j2][j3];
        printf("%.2f\n", (double)ans/n);
    }
    return 0;
}

标程 2 （\(O(256 \times 256 + N)\)）：

#include <stdio.h>

const int N = 1e5 + 10;
const int M = 4;
int a0[N], a1[N], a2[N], a3[N];
int b[M][M][M][M], c[M][M][M][M];

int main() {
    int n;
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%c%c%c%c\n", &a0[i], &a1[i], &a2[i], &a3[i]);
        a0[i] = 'D' - a0[i]; a1[i] = 'D' - a1[i]; a2[i] = 'D' - a2[i]; a3[i] = 'D' - a3[i];
        b[a0[i]][a1[i]][a2[i]][a3[i]]++;
    }
    for (int i0 = 0; i0 < M; ++i0)
        for (int i1 = 0; i1 < M; ++i1)
            for (int i2 = 0; i2 < M; ++i2)
                for (int i3 = 0; i3 < M; ++i3)
                    for (int j0 = 0; j0 <= i0; ++j0)
                        for (int j1 = 0; j1 <= i1; ++j1)
                            for (int j2 = 0; j2 <= i2; ++j2)
                                for (int j3 = 0; j3 <= i3; ++j3)
                                    c[i0][i1][i2][i3] += b[j0][j1][j2][j3];
    for (int i = 0; i < n; ++i)
        printf("%.2f\n", (double)c[a0[i]][a1[i]][a2[i]][a3[i]]/n);
    return 0;
}

ZYJ 的四进制标记解法（O\((4 \times 256 \times 256 + N)\)，虽然多了个常数 4 但就是自豪地比标程快(骄傲.jpg)）：

#include <stdio.h>

int N;
int cardSet[100100];
int cardMap[256];
int leqCount[256];

void addCard(int idx, const char* card) {
    int val = 0;
    for (const char *p = card + 3; p >= card; --p) {
        val <<= 2;
        val |= 'D' - *p;
    }
    cardSet[idx] = val;
    ++cardMap[val];
}

void read() {
    char card[5];
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", card);
        addCard(i, card);
    }
}

int leqCard(int a, int b) {
    for (int i = 4; i > 0; --i) {
        if ((a & 3) > (b & 3)) {
            return 0;
        }
        a >>= 2;
        b >>= 2;
    }
    return 1;
}

void work() {
    for (int i = 0; i < 256; ++i) {
        if (cardMap[i]) for (int j = 0; j < 256; ++j) {
            if (cardMap[j] && leqCard(j, i)) {
                leqCount[i] += cardMap[j];
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        printf("%.2lf\n", (double)leqCount[cardSet[i]] / N);
    }
}

int main() {
    read();
    work();
    return 0;
}

G. zyj 打印奖状

Description

zyj 又被叫去打印奖状啦！但是学院办公室的打印机实在太辣鸡，经常把奖状文字打歪。为了让学院更换打印机， zyj 把自己在学院得的所有奖状都拿出来，用以展示这打印机打出来的奖状到底歪成什么样子。为了方便表示， zyj 决定把每一张奖状的文字范围中心和奖状纸张中心的几何距离列举出来，用以表观地显示打印机的误差。 zyj 天天都要打印奖状，日理万机，所以他请求你帮他完成这个任务。

Input

zyj 得的奖状数不胜数，所以输入文件包括若干组奖状数据。每组奖状数据包含两行，第一行是两个浮点数 a, b(a, b > 0) ，表示奖状的大小；第二行是四个浮点数 x, y, l, w(x, y >= 0; l, w > 0) ，表示奖状上文字范围左上角的坐标和文字范围的长和宽。输入数据保证文字范围一定完全在奖状面积内。输入到文件结尾结束。

Output

对应每一组奖状数据输出奖状中心和文字区域中心的几何距离，保留 3 位小数。

Sample Input

3.0 4.0

1.0 1.0 1.0 1.0

2.0 2.0

1.0 1.0 1.0 1.0

3.0 3.0

0.0 0.0 3.0 3.0

Sample Output

0.500

0.707

0.000

Hint

double 类型的输入输出格式： scanf("%lf") / printf("%f")

本题数据量大，请使用 scanf/printf ，使用 cin/cout 会导致超时

题目大意

给定两个矩形，其中小矩形一定被套在大矩形之中。给出大矩形的长宽，小矩形的左上角顶点坐标和长宽，求出两个矩形中心的几何距离。

参考思路

签到题，公式乱搞就行。

易错点解析

1. 这题没有说清楚长是平行于 x 轴的长，宽是平行于 y 轴的宽，举报出题人；
2. 这题没有说清楚 a / x / l 一定对应以及 b / y / w 一定对应，举报出题人；
3. 输入输出：如果用 scanf / printf 作输入输出，前者要指定具体是 %f / %lf / %Lf 的哪个，而后者的 float / double 都是用 %f 输出，当然 long double 还是用 %Lf ；
4. 数据漂移：由于要计算并输出浮点数，部分用 float 的同学有可能会遇到浮点数数据漂移问题；

参考代码

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

double a, b;
double x, y, width, height;

inline double dist(double x1, double y1, double x2, double y2) {
    return sqrt(pow(x1 - x2, 2.f) + pow(y1 - y2, 2.f));
}

int main() {
    while (~scanf("%lf%lf", &a, &b)) {
        scanf("%lf%lf%lf%lf", &x, &y, &width, &height);
        double res = dist(a / 2.f, b / 2.f, x + width / 2.f, y + height / 2.f);
        printf("%.3f\n", res);
    }
    return 0;
}

H. CG 之争

Description

众所周知， cgq 和 cgy 名字中只差一个字。为了保住 CG 这个名号， cgq 作为擂主给 cgy 出了个难题：要是 cgy 能在 1s 内答出 \(\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}\) ，就能获得一次正式挑战 cgq 的机会。 cgy 好菜啊，而且他的 1s 十分宝贵，于是求助于你，请你帮他求出这个数。

Input

多组数据，每一组一行是 cgq 给出的一个正整数 n ，输入到文件结尾结束（\(n \leq 80\)）。

Output

对应于每一组 n 求出 \(\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}\) ，保留 3 位小数。

Sample Input

1

2

Sample Output

1.000

1.000

Hint

double 和 long double 精度都有限，求 80 次方会存不下。

题目大意

求斐波那契数列的第 \(k\) 项值。

参考思路

打表 or 记忆化递推。递推的时间复杂度 \(O(80)\) ，还有 \(O(N)\) 的输入输出。

因为浮点数类型存不下 80 次方这么大的数（存储位数不够 or 表示精度不够），可以搜索一下题目给出的公式，容易知道是斐波那契数列的通项公式；也可以搜索一下 C/C++ 语言是怎么处理大数计算、高精度科学计算的，用高精算法求 80 次方也可以。

易错点解析

1. 保留 3 位小数是骗你的。因为斐波那契是个整数数列，就算用公式算，考虑上精度损失等问题后得到的还是个整数；
2. 不作记忆化处理的递归是会超时的。递归空间是一棵二叉树，不作记忆化处理的话最大有 80 层，复杂度高达 O(2^N) 指数爆炸算到地老天荒；
3. 不作记忆化处理的递推是可能会超时的。因为有多组输入数据呀，你的复杂度是 O(80T) 哦；
4. 用浮点数类型递推到最后精度不够是会 WA 的。有些同学就做了优化，从奇怪的地方拿到了第 79 、 80 项直接用字符串输出， emmm... 也是可以的。

参考代码

#include <stdio.h>

#define LL long long
#define lld "%lld"

const int MaxN = 80;

LL fib[MaxN + 1] = {0, 1};

inline void init() {
    for (int i = 2; i <= MaxN; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

int main() {
    int N;
    init();
    while (~scanf("%d", &N)) {
        printf(lld".000\n", fib[N]);
    }
    return 0;
}

I. 人形质量单位

Description

每个人的质量或许相同，或许不同。于是乎，如果以人们的体重作为一个计量单位，那么可以有多少种不同的组合呢？

设有 n(\(1 \leq n \leq 10\)) 种不同的质量，第 i 种质量大小为 w[i](\(w[i] \leq 300\))，第 i 个质量有 x[i](\(1 \leq x[i] \leq 100\)) 个人（其总重量不超过 300000kg ），要求编程输出这些人形能称出不同质量的种数，但不包括一个人也不用的情况。

Input

第一行输入质量的种数 n

第二行输入每种质量的质量

第三行输入每种质量的人的人数

Output

输出可以称量的质量种数

Sample Input

3

1 2 3

2 1 2

Sample Output

10

Hint

无

题目大意

有 \(N\) 种物品，每种物品有 \(X_i\) 个且价值为 \(W_i\) 。可以任意选取物品，求使得所取物品总价值不同的方案数。

参考思路

动态规划，或记忆化搜索。

如果限定了人数，求最大总质量，那就是多重背包问题，参看《背包九讲》。

这里只是要求方案数，拿个标记数组记录一下就好了，时间复杂度 \(O(N\sum{W_iX_i})\) 等。

易错点解析

1. 可能会有同学想到枚举的方法，即假设总共有 P 个人，从选 1 个人到选 P 个人不断组合出来，看有多少种不同的总质量不就好了吗？但要注意，最坏情况下可选方案数是小于等于 \(C^1_P + C^2_P + \ldots + C^P_P = 2^P - 1\) 的（当且仅当所有种类质量值 \(W_i\) 互质，且不存在 \(p \leq X_j \land q \leq X_i\) 使得 \(W_i = p \land W_j = q\) 时取等号），考虑到有 10 种质量且每种质量有 100 个人，总人数最多高达 1000 这是要算到地老天荒的节奏；

参考代码

标程（\(O(N\sum{X_i\sum{W_iX_i}})\)）：

#include<iostream>

using namespace std;
int main()
{
    int max=0;
    int n,w[305],x[105];
    bool p[300*100*10+5];
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        max+=x[i]*w[i];
    }
    for(int i=1;i<=max;i++) p[i]=false;
    p[0]=true;

    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=x[k];i++)
            for(int j=max;j>=w[k];j--)
            {
                if(p[j]==false && p[j-w[k]]==true) p[j]=true;
            }
    }
    int ans=0;
    for(int i=1;i<=max;i++)
    {
        if(p[i]) {ans++; }
    }
    cout<<ans;
}

\(O(N\sum{W_iX_i})\) ：

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

const int MaxN = 10, MaxW = 301, MaxX = 101;
const int MaxM = MaxN * MaxW * MaxX;

int N, maxWeight;
int W[MaxW], X[MaxX], flag[MaxM];

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", W + i);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", X + i);
        maxWeight += W[i] * X[i];
    }
}

int curr[MaxM];

void work() {
    int res = 0;
    flag[0] = 1;
    for (int i = 0; i < N; ++i) {
        memset(curr, 0, sizeof(curr));
        for (int j = W[i]; j <= maxWeight; ++j) {
            if (!flag[j] && flag[j - W[i]] && curr[j - W[i]] < X[i]) {
                flag[j] = 1;
                curr[j] = curr[j - W[i]] + 1;
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

int main() {
    read();
    work();
    return 0;
}

J. 训练 ZetaGo

Description

L2M 未来科技开发公司研制了一款新的智能机器人 ZetaGo ，它可以把任何事物都计算出一个特征值，在经过重排后可以据此做出一系列的决策。

为了检验 ZetaGo 的重排能力，需要人工进行监督学习(supervised learning)训练。 LLM 作为 L2M 手下的一名实验员，就要每天进行这样的苦差事。

今天的重排规则是这样的：已知一组特征值 A ，要求重新排列后的组合 B 可以满足任意两个相邻元素的乘积（\(B_i * B_{i+1}\)）为 4 的倍数。 ZetaGo 经过决策运算后会给出是否存在这样一种重排方案， LLM 要根据决策结果告诉它对不对，以便纠正学习模型。

今天 LLM 实在太累啦，想拜托你帮帮忙。

Input

第一行输入一个正整数 \(T \leq 10\) 代表着训练组数。

接下来 \(3T\) 行，每 \(3\) 行首先是一个正整数 \(2 \leq N \leq 1000\) 代表着特征值的个数，接下来一行是用空格隔开的特征值 \(A_i\) （其中 \(1 \leq A_i \leq 10^9\) 且 \(0 \leq i < N\) ），最后一行 ZetaGo 会给出它的判定结果 "yes" 或者 "no" 。

Output

请你告诉 ZetaGo 它的判定结果对不对，输出 "AC" 或者 "WA" 表示对或错（不包括引号）。

Sample Input

3

2

4 4

no

3

1 2 4

yes

4

1 2 2 4

yes

Sample Output

WA

AC

AC

Hint

样例 2 解释：1 4 2

样例 3 解释：1 4 2 2

题目大意

给定一组数据，问是否存在这样一种排列，使得重排后的数据，任意相邻元素两两相乘的值是 4 的倍数，再跟机器人输入的“它的判断结果”作比较。

参考思路

规律题，统计数量关系。时间复杂度 \(\theta(N)\) 。

分类讨论，可以将数字分为三类： 4 的倍数、是 2 的倍数但不是 4 的倍数、奇数。

1. 显然，任何数和 4 的倍数相乘，其结果仍然是 4 的倍数，因此是万能搭配；
2. 显然，任意 2 的倍数只有一个因子 2 ，因此它们只能两两间相乘才能得到 4 的倍数，必须相邻地放一起；
3. 对于任意奇数，和 2 的倍数相乘不符合题意，只能和 4 的倍数相间搭配。

因此可以先排列所有 cnt1 个奇数，每两个奇数之间插入一个 4 的倍数，需要 \(cnt1 - 1\) 个 4 的倍数；若存在 2 的倍数，需要拿出一个 4 来连接它们，这样需要 \(cnt1\) 个 4 的倍数。判断一下 4 的倍数有多少个，是否满足条件，并将判断结果跟机器人的相比较，得出答案。

易错点解析

1. 有些同学规律找对了，可惜忘记每次都要初始化；
2. 有些同学规律找对了，可惜跟机器人结果的对比反了；
3. 有些同学规律找对了，可惜统计 4 的倍数时也顺带算进 2 的倍数了；
4. 有些同学规律找对了，可惜忘记是倍数；

参考代码

#include <stdio.h>

int T, N;
int cnt1, cnt2, cnt4;
char ans[4] = "yes";

void init() {
    cnt1 = cnt2 = cnt4 = 0;
}

void read() {
    int rd;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &rd);
        if (rd & 3) {
            (rd & 1) ? ++cnt1 : ++cnt2;
        } else {
            ++cnt4;
        }
    }
    scanf("%s", ans);
}

void work() {
    puts(ans[0] == "ny"[cnt4 >= cnt1 - !cnt2] ? "AC" : "WA");
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        read();
        work();
    }
}

K. 强迫症患者

Description

cgy是一个很有强迫症的人，他一看到小数就浑身难受。然而有一天，他碰到了这么一条只有整数和除号构成的式子：1/2/4/16 ，他的强迫症又来了，加上了括号让式子变成了 （1/2）/（4/16）=2 把它变成了整数。但是走着走着，他又碰到了一个墙上写满了这个风格的式子，cgy突然发现有些式子可以通过加括号来让结果变为整数，有些却不行。但是他手边没有纸和笔，于是就没有把这个想法写下来，现在你能通过这一系列数字来判断他们是否可以通过加括号变成整数么

Input

一个整数 n(n<=100) 表示有几组数据

接下来输入 m(m<=1000) 表示有 m 个数字，再下去一行输入 m 个正整数（每个数字不大于 1000 ），表示式子中的数字。

Output

对于每一行输入，如果可以通过加括号变成整数就输出 Yes ，否则输出 No 。

Sample Input

3

3

1 2 4

4

1 5 6 9

4

1 4 2 2

Sample Output

Yes

No

Yes

Hint

无

题目大意

给定一串除法式子 a / b / c / ... ，可以对该式子任意加括号以改变其中某些运算符（除号变乘号），问是否存在这样一种加括号方案，使得整个式子的分子可以整除分母。

参考思路

贪心 + 最大公约数，时间复杂度 \(O(N)\) 。

因为括号可以任意加，一定存在一种最优方案，使得除了第二个数只能作为除数外，其他数字的乘积为被除数，若它们的乘积跟第二个数的最大公约数为 1 ，则说明所有的数乘起来都不能整除第二个数，否则第二个数除以这个最大公约数后其值为 1 （被除掉了，也可以理解为被约分了）。

贪心策略证明：假如从最优方案中删去某一个括号，使得还有另外一组数跟第二个数相乘作为除数，若其他剩余的数的乘积不能整除第二个数，当然也不能整除这个新的更大的除数；若剩余的数的乘积能整除这个新除数，根据乘法结合律，它们也能整除单独的第二个数，因此得证。

易错点解析

1. 乘法溢出：因为 int 乘法有可能溢出，为了避免高精计算，干脆每次都让第二个数除以某个数跟它的最大公约数，只要到最后时第二个数变为 1 ，说明它在这个过程中被除掉啦；
2. 约分：整个过程其实就相当于约分，我们在约分时就是在找分子和分母的最大公约数并同除，这个应该非常好理解；
3. 运算结合性：现代人类设计出来的算术乘法、算术除法符号是左结合的，也就是一定是从左往右算的，这点应该没问题吧，所以 a / b / c 一定等价于 ((a / b) / c) 也没问题吧....

参考代码

#include <stdio.h>

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void work() {
    int M, a, b;
    scanf("%d%d%d", &M, &a, &b);
    b /= gcd(a, b);
    for (int i = 2; i < M; ++i) {
        scanf("%d", &a);
        b /= gcd(a, b);
    }
    puts(b == 1 ? "Yes" : "No");
}

int main() {
    int N;
    scanf("%d", &N);
    while (N--) {
        work();
    }
    return 0;
}

L. Oyk 捏泡泡纸

Description

著名的剪纸大师 Oyk 今年不剪纸了，最近工作压力大，他改为捏泡泡纸来放松心情。由于 Czj 每天上班摸鱼，他被抓过来陪 Oyk 捏泡泡纸。

已知一张完好的泡泡纸上会有 \(N\) 个泡泡，他们约定每次每个人都可以 paji 掉 2 的幂次（1，2，4，8，16，...，\(2^k\)）个泡泡，并且总是由 Oyk 先捏，轮流下去直到捏完。他们都想由自己来捏完整张泡泡纸，且他们都足够聪明，总会试图选择最有利于自己的策略。

看他们捏泡泡太无聊了，我想预先知道他们谁能够刚好在最后捏完整张泡泡纸。

Input

可能会有多行输入，请你一直处理到文件尾。

每行会输入一个正整数 \(N \leq 10^6\) 。

Output

对于每张泡泡纸，请你告诉我故事的结局。

如果是 Oyk 最后捏完，输出 "Oyk Oyk!" （不包括引号，下同）。

如果是 Czj 最后捏完，输出 "diu,Czj!" 。

Sample Input

4

5

6

Sample Output

Oyk Oyk!

Oyk Oyk!

diu,Czj!

Hint

对于样例 3 ，无论 Oyk 先捏 1 / 2 / 4 个都改变不了泡泡纸最后被 Czj 捏完。

题目大意

原题：与 hdu 1847 几乎一样。

只有一堆若干数量的物品，规定每人每次可以取 \(2^{\mathbb{k}}\) 个，取完者胜，问先手是否能赢。

参考思路

巴什博弈变种，找出先手必败态，发现 \(N = 3\mathbb{k}\) 先手必败。时间复杂度 \(O(1)\) 。

可以先枚举出前几个数比如 1 ~ 10 观察先手的胜负情况，发现 \(N = 3\) 是第一个先手必败态，想办法将必败态转移给对方就能获得胜利。发现任何数总能加 1 或 2 成为 3 的倍数，而任何 \(3\mathbb{k}\) 都不能整除 \(2^{\mathbb{p}}\) ，剩下的数总会是 \(3\mathbb{m} + 1\) 或 \(3\mathbb{m} + 2\) ，这样只需要拿走 1 个或 2 个就能将 \(3\mathbb{m}\) 的状态转移给对方，直到 \(N = 3\) ，因此我们可以确定 \(N = 3\mathbb{k}\) 是本游戏的先手必败态。

由于数据较小，也允许递推的做法，复杂度 \(o(NlogN)\) 。原理是这样的，假设当前有 \(N\) 个，如果取走 \(2^{\mathbb{p}}\) 个后对手是必败态，说明这一局先手是必胜的，遍历一遍所有的取法即可。这一思想其实类似于 SG 函数，各位可以自行去了解 SG 函数的原理，把这个题当作 SG 的入门题hhh。

易错点解析

1. 不知道有没有同学把 Oyk 看成了 Qyk ...（逃；

参考代码

标程：

#include <stdio.h>

int main() {
    int N;
    while (~scanf("%d", &N)) {
        puts(N % 3 ? "Oyk Oyk!" : "diu,Czj!");
    }
    return 0;
}

递推解法（改自一个同学的提交）：

#include <stdio.h>

const int MAXN = 1E6;
int win[MAXN + 1];

void init() {
    for (int i = 1; i <= MAXN; ++i) {
        for (int j = 1; j <= i; j <<= 1) {
            if (!win[i - j]) {
                win[i] = 1;
                break;
            }
        }
    }
}

int main() {
    init();
    int N;
    while (~scanf("%d", &N)) {
        puts(win[N] ? "Oyk Oyk!" : "diu,Czj!");
    }
    return 0;
}

M. 光棍节活动

Description

一年一度的光棍节活动中，cgy 的班级想搞一个别出心裁的活动，要求将班上的男生和女生完美分组，规则如下：

1. 每个组之间男生数要相同，女生数也要相同；
2. 同一个组中的男生数不能等于女生数；
3. 每组中男生和女生分别要有 2 名或以上；
4. 必须要分成 2 个或以上的组，组数也要尽可能的多才好玩；

如果不能完美分组，将随机抽出一名男生和一名女生组成一队进行假扮情侣活动，重复进行（尽量少的次数）抽人直到剩下的男女生人数恰好可以完美分组。

如果始终不存在完美分组，那么除了成功组队进行假扮情侣的外，可能会多出若干男生或者女生没有组队哦（同性才是真爱！）。

cgy 安排 lxy 实施这个方案，但 lxy 脸红心跳，想请你帮帮忙。

Input

第一行输入正整数 \(T \leq 100\) 代表总共有 \(T\) 种情况。

接下来 \(T\) 行，每行包含两个正整数 \(N < 10^5\) 和 \(M < 10^5\) 代表着该种情况中有 \(N\) 名男生和 \(M\) 名女生。

Output

对于每种情况，请你帮忙计算出完美分组数和假扮情侣数，在一行中输出，用空格隔开。

如果存在没有组队的幸运儿，你可以再为 ta 们输出且只输出一行 "happy single dog!" （不包括引号）聊表庆祝。

Sample Input

3

18 24

19 25

18 19

Sample Output

6 0

6 1

0 18

happy single dog!

Hint

样例解释：

对于样例 1 ，可以完美分组为最多 6 组，每组有 3 名男生 4 名女生，不需要再抽人进行假扮情侣活动。

对于样例 2 ，先抽出一对送给 FFF 团，之后就跟样例 1 一样啦。

对于样例 3 ，只能抽出 18 对玩假扮情侣活动，然后下一行为剩下的可怜妹纸输出 happy single dog! 。

题目大意

有两堆数量不等的物品，要求对其进行分组，且做到组数最大化；

不能只分一个组，否则不叫分组；

不能任意分组，每个组的情况要相同；

加入规则 2 ，一个组中不同种类物品数量不同；

加入规则 3 ，一个组中任意一种物品数量不为 1 。

（由于我原来的程序忘记考虑规则 3 ，所以比赛中临时删掉了，后来发现数据也没卡掉，改不改都是对的）

参考思路

数量关系规律题，枚举到能求最大公约数为止。

如果两个数量相等则直接全部算作假扮情侣。

如果两个数量相差 1 则一定不能求 gcd 。

如果枚举过程中最大数可以整除最小数，则不满足规则 3 。

如果枚举失败，那就不能完美分组了。

参考代码

下面的代码已经考虑了规则 3 ：

#include <stdio.h>

int N, M;

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

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void read() {
    scanf("%d %d", &N, &M);
}

void work() {
    int perfect = 0, fake = 0;
    bool hasSingle = false;
    if (N > M) {
        swap(N, M);
    }
    if (N == M) {
        fake = N;
    } else if (N + 1 == M) {
        hasSingle = true;
        fake = N;
    } else {
        int groupCnt = 1;
        while (N && (1 == (groupCnt = gcd(M, N)) || N == groupCnt)) {
            ++fake;
            --N;
            --M;
        }
        if (!N) {
            hasSingle = true;
        } else {
            perfect = groupCnt;
        }
    }
    printf("%d %d\n", perfect, fake);
    if (hasSingle) {
        puts("happy single dog!");
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

初赛复盘

一开始我是没想过要把题目排成这个顺序的，我们的背锅侠忘记调啦！于是只好在 7 分钟发了条@全员说难度不按顺序，然而大家还是喜欢按顺序做（摊手.jpg）。于是就又有了一堆被打击信心的爆零啦 qwq

接着就由于没有充分验题，陆续发现了卡 cin 之类的奇怪问题，改了两次数据重判了若干次，又把原来 AC 的给重判成 TLE 了“咦重判完 AC 反而变少了”（药丸.jpg）。

然后安利一下 qu 老师家的可能还算好用的金山 WPS 写得；借助这个奇怪的写作(?)工具临时对发现的一些问题，一些没说清楚的事项作了个补充（虽然感觉并没有人看），于是像 system("pause") 之类的到后期似乎没在选手们的提交中出现过了。

整体区分度良好，从最终排名来看，做对题目数呈阶段性分布；除了 A 题是个看起来简单其实大家都没学过的大坑外，对 H 题《CG 之争》难度估算错误，显然大家都没听说过斐波那契的通项公式；对 M 题《光棍节活动》难度估算错误，虽然与 K 题《强迫症患者》一样是要用到求最大公约数的算法，但题面明显较复杂，陈述有待优化，甚至出现出题人自己都漏考虑其中一个条件的情况；对 L 题《Oyk 捏泡泡纸》难度估算错误，显然大家找规律的能力还是挺强的，之前是认为这个博弈题比较难证明，然而大家敢交题。。

整体题目质量良好，除了个别题目题意有待加强、条件描述不准确或其他小问题外，涉及的知识点较全，没有重复出题；除了个别选手在 F 题用到批处理生成长段代码，正解解答代码量适中，涉及的少数程序语言知识大致符合教xue学xi进度。

出题总结

题号	题目	ZYJ 预xia估cai难度	正确率（正确/提交）	通过率（正确人数/有效人数）	出题人
A	诡异的计数法	2.8	9.88%(100/1012)	61.64%(90/146)	Cgy
B	数发票	4.0	11.43%(28/245)	13.01%(19/146)	Cgy
C	Ljc 吃糖	2.5	8.82%(30/340)	14.38%(21/146)	Ljc
D	姓名字母排列	2.5	9.59%(21/219)	8.22%(12/146)	Zyj
E	Substring	2.0	51.08%(118/231)	74.66%(109/146)	Zlm
F	法特狗	3.0	7.29%(25/343)	12.33%(18/146)	Cgq
G	Zyj 打印奖状	1.0	26.97%(140/519)	88.36%(129/146)	Cgy
H	Cg 之争	1.8	21.55%(86/399)	53.42%(78/146)	Cgy
I	人形质量单位	4.0	20.00%(16/80)	6.85%(10/146)	Lxy
J	训练 ZetaGo	3.0	21.02%(78/371)	47.95%(70/146)	Zyj
K	强迫症患者	2.5	21.26%(44/207)	27.40%(40/146)	Lxy
L	Oyk 捏泡泡纸	3.0	59.90%(118/197)	74.66%(109/146)	Zyj
M	光棍节活动	2.2	11.35%(43/379)	26.03%(38/146)	Zyj

呃，文字性的东西辣么烦，怎么可能会有出题总结这种东西嘛。

最后

初赛并不是为了刁难大家，而是让大家体验 ACM 程序设计竞赛是怎样的，算法和数据结构是个什么东西，对于一个已知的问题，如何抽象出它的模型并找到合适的方法，在较好的性能内解决它。

今年应该也是第一年允许转专业的同学参加，一开始还挺担心他们多学了半学期《数据结构》会不会太强了的（逃）。可能对于多数同学来说，参加 ACM 新生赛或许是第一次这么高密度地思考和解决问题，但不论是萌新也好，还是转专业的同学也好，希望我们这次比赛可以是你踏上专业成长路线的第一步，相信也只是各位的许多生活历程的一小段，未来的生活还很长，可能你会像我一样莫名其妙地转了前端开发，可能你会做一些更有趣的东西，可能你以后会做一名教师，也可能你会继续深入计算机科学的研究中，甚至可能爱上算法竞赛以及算法研究与设计，往小了说后面还有 CTF 竞赛（逃）。

不管怎样，希望这次比赛能够让你感受到计算机科学的艺术与程序设计的魅力，让你的编程能力有所锻炼和提高，让你的思考空间和知识面有所扩充，而不仅仅是停留在表面上的“这个太难了”“这个有什么用嘛”“我以后总会学到的”，谢谢！

本文基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，欢迎引用、转载或演绎，但是必须保留本文的署名BlackStorm以及本文链接http://www.cnblogs.com/BlackStorm/p/SCNUCPCFF-2017-Solutions.html，且未经许可不能用于商业目的。如有疑问或授权协商请与我联系。