第一届 Hello World 程序设计竞赛题解

Hello_World

A. 逃脱游戏

题意

给定三个数字，输出三个数中对 $3$ 取余最大的数字，如果有两个数字对 $3$ 的余数相等，输出靠前的数字。

数据范围

对于 $20\%$ 的数据，$0\leq a,b,c\leq10^5$
对于 $90\%$ 的数据，$0\leq a,b,c\leq2^{64}-1$
对于 $100\%$ 的数据，$0\leq a,b,c\leq10^{100}$

题解

本题作为全场最简单的题目，由于太简单了，所以我们增大了一些数据范围，使这个问题看起来更不容易拿满分一些。
对于 $20\%$ 的数据，几乎所有人都能通过，如果变量类型设为 long long，则可以得到 $50\%$ 的分数，如果变量类型设为 unsigned long long，则可以得到 $90\%$ 的分数（因为 $2^{64}-1$ 是 unsigned long long 的数据范围）。如果要拿满分，就要用字符串来读入了，因为 C/C++ 中没有任何基本数据类型可以直接读入 $10^{100}$ 大小的数字。
对于一个大整数，我们有两种方法求其对 $3$ 的余数，第一种是利用小学的能被 $3$ 整除的数字的性质：一个数若各个位上的数字的和是 $3$ 的倍数则这个数能够被 $3$ 整除，可以很容易证明：各个位上的数字的和对 $3$ 的余数，就是这个数字本身对 $3$ 的余数；第二种方法是利用公式 $(a+b)\%c=(a\%c+b\%c)\%c$，将 $n$ 位大整数拆分成 $\sum_{i=0}^{n-1}a_i\times10^i$，计算 $\sum_{i=0}^{n-1}a_i\times10^i\%3$，由于当 $n$ 很大时 $10^{n-1}$ 无法用基本数据类型储存，所以再用一个乘法分配律化简一下再进行计算，就能得到正确答案。

标程

std1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 100 + 100
char str[3][maxn];
int MOD(char *str) {
    int ret = 0, i;
    for(i = 0; str[i]; ++i) {
        ret = ret * 10 + str[i] - '0';
        ret %= 3;
    }
    return ret;
}
int main(int argc, char *argv[]) {
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    int mod = -1, ans, i;
    for(i = 0; i < 3; ++i) {
        scanf("%s", str[i]);
        int mtmp = MOD(str[i]);
        if(mod < mtmp) {
            ans = i;
            mod = mtmp;
        }
    }
    printf("%s\n", str[ans]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

std2.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 100 + 100
char str[3][maxn];
int MOD(char *str) {
    int ret = 0, i;
    for(i = 0; str[i]; ++i) {
        ret += str[i] - '0';
    }
    return ret % 3;
}
int main(int argc, char *argv[]) {
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    int mod = -1, ans, i;
    for(i = 0; i < 3; ++i) {
        scanf("%s", str[i]);
        int mtmp = MOD(str[i]);
        if(mod < mtmp) {
            ans = i;
            mod = mtmp;
        }
    }
    printf("%s\n", str[ans]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

B. 卖火柴的小女孩（节选）

题意

给两个正整数 $l,r$，如果在区间 $[l,r]$ 内能找到三个互不相等的整数构成一个三角形的三边，则输出 $YES$，并输出三条边的长度，否则输出一个 $NO$。

数据范围

$1\leq l\leq r\leq10^5$

题解

本题作为全场第二简单的题目，可能通过率比第一题还要多一些，唯一的坑就是区间 $[1,3]$，除了这种情况，当 $r-l\geq2$ 时，总能找到满足题意的答案，三边长度 $r-2,r-1,r$ 为其中一个可行解。

特殊判定

特殊判定程序逻辑：

1. 忽略 $YES$ 与 $NO$ 大小写进行比对；
2. 若选手输出第一行字符串与标准输出第一行字符串不同，则返回程序错误；
3. 若标准输出为 $NO$，则返回程序正确；
4. 读入选手输出第二行的 $3$ 个数字，若选手输出不足 $3$ 个数字，或者输出的数字不在区间 $[l,r]$ 内，则返回程序错误；
5. 若选手输出小数或其他字符，则会由于读入错误判定为选手输出的数字在 $[l,r]$ 外，返回程序错误，若选手输出的数字多于 $3$ 个，则对多余的数字不做判定；
6. 若选手输出的三个数字存在重复，则返回程序错误；
7. 若选手输出的数字不能构成三角形的三边（即 $a,b<c$ 且 $a+b\leq c$），则返回程序错误；
8. 返回程序正确。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
int main(int argc, char *argv[]) {
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
    int l, r;
    int a, b, c;
    scanf("%d%d", &l, &r);
    if(r - l >= 2) {
        a = r - 2;
        b = r - 1;
        c = r;
        if(a + b > c) {
            printf("YES\n%d %d %d\n", a, b, c);
        } else {
            printf("NO\n");
        }
    } else {
        printf("NO\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

C. 深井中的蜗牛

题意

一只蜗牛从深为 $x$ 米的井底往井口爬，白天往上爬 $a$ 米，晚上往下滑 $b$ 米，输出蜗牛第几天爬出枯井。

数据范围

$1\leq x,a,b\leq100$

题解

本题作为全场第三简单的题目，看上去可能要特判很多种情况，比较好判断的有：$a\leq b$，这种情况只要它第一天爬不到井口，就永远都爬不到了，还有到哪一天正好爬到井口，晚上就不再下滑了，这些细节上的处理可能就比较烦了。
其实看到这题的数据范围就可以发现：如果蜗牛能够爬到井口，它最多只需要 $100$ 天（$a,b$ 都为整数，在 $a>b$ 的情况中，$\min(a-b)=1$，所以 $day_{max}=\max(\frac{x}{a-b})=\frac{\max(x)}{min(a,b)}=100$），所以直接按题意模拟，最多模拟 $100$ 次就可以知道蜗牛第几天能爬出枯井，或者永远不能爬出枯井（超出 $100$ 次还没有爬到枯井就说明蜗牛永远都爬不出枯井）。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
int main(int argc, char *argv[]) {
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
    int a, b, x;
    int ans, top;
    top = ans = 0;
    scanf("%d%d%d", &x, &a, &b);
    while(top < x) {
        ++ans;
        top += a;
        if(top >= x) {
            break;
        }
        top -= b;
        if(ans > 200) {
            break;
        }
    }
    if(ans > 200) {
        printf("impossible\n");
    } else {
        printf("%d\n", ans);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

D. 修路工程

题意

在一张 $n$ 个节点的完全图（任意两个节点之间都有一条连边的简单图，$n$ 个节点的完全图上有 $\frac{n\times(n-1)}{2}$ 条边）上，求其最小生成树的边权和，第 $i$ 个节点的点权为 $w_ i$，则点 $u$ 与点 $v$ 之间的边权为 $w_u+w_v$。

数据范围

对于 $20\%$ 的数据，$2\leq n\leq200$
对于 $70\%$ 的数据，$2\leq n\leq1000$
对于 $100\%$ 的数据，$2\leq n\leq10^6,1\leq w_i\leq10^5$

题解

作为全场的中等难度中最简单的题目，为了让题目看上去不显得那么 $low$，我们特地为大家设计了一个图论背景，还考了最小生成树算法（不管你们看不看得出来，反正它是一个最小生成树），我们又懒得解释“完全图”和“最小生成树”这些要用一大段专业术语来解释的名词，就给出了这样的以“修路”为背景的题面……

---

好，废话到此为止
如果有同学会 $prim$（普里姆求最小生成树）算法的话，恭喜你，可以通过 $70\%$ 的数据，可以先构造出 $\frac{n\times(n-1)}{2}$ 条边的一张完全图，然后在图上跑一遍 $prim$，由于 $prim$ 算法的时间复杂度为 $O(n^2)$，其中 $n$ 为节点数，所以对于最后 $3$ 组数据（$5\times10^5\leq n\leq10^6$），要构造出所有的边，计算机最少的计算次数为 $(5\times10^5)^2=2.5\times10^{11}$，远远超过 $10^8$，程序超时是必然的。

---

好，上面的都是废话，下面的才是真正的题解。
我们知道，最小生成树除了 $prim$ 算法还有一个名字更长的 $kruskal$（克鲁斯卡尔）算法，这种算法的做法是将所有边的长度按照从小到大的顺序排序，依次取边，如果取到的边的两个端点之间没有路径可以互相到达，就选择这条边连接两个端点，作为生成树上的一条边，否则忽略这条边继续往后取边。
在这题当中我们不必处理出所有的边，因为我们可以发现所有按照以上方法取出的边必然是点权最小的点 $u$ 与其他所有节点的连边，所以最后最小生成树上的每条边一定与点 $u$ 相连，所以最小生成树的权值和就是 $\sum_{i=1}^nw_u+w_i(u\in\{u|w_u\leq w_v,\forall v\in[1,n]\})$。这种做法的时间复杂度为 $O(n)$，对于最大的一组数据，其计算次数仅为 $10^6$，小于 $10^8$，可以在 $1s$ 内运行出结果。
所以说了那么多，这题的代码其实只有一个 for 循环就完事了，或许不需要会什么 $kruskal$，不需要知道最小生成树，猜结论都可以猜出来，由于这题的代码太简单了，所以实际上并没有什么难度，想到了就能写出来。
最后，由于后 $3$ 组数据比较大，所以直接用 cin cout 会导致程序读入还没结束就已经超时，本题的读入已经在选手须知的“友情提示”中提醒大家了。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 1000000 + 100
int n;
long long sum, Min;
long long num[maxn];
long long min(long long a, long long b) {
    return a < b? a: b;
}
int main(int argc, char *argv[]) {
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
    int i;
    Min = maxn;
    scanf("%d", &n);
    for(i = 0; i < n; ++i) {
        scanf("%lld", &num[i]);
        Min = min(Min, num[i]);
        sum += num[i];
    }
    sum += Min * (n - 2);
    printf("%lld\n", sum);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

E. 算积分

题意

计算以下积分：

$$\int_{a}^{b}(e^{-x^2}+\frac{\sin{x}}{x}+\frac{1}{\ln{x}})\text{d}x$$
输出保留两位小数。

数据范围

$T\leq100$
$2<a<b<12$ 且 $b-a<2$

题解

$\because\int_0^\infty e^{-x^2}\,{\rm d}x=\frac{\sqrt\pi}{2}~~~~ \int_0^\infty\frac{\sin x}{x}\,{\rm d}x=\frac{\pi}{2}$
且 $\int_0^\infty\frac{1}{\ln x}\,{\rm d}x$ 的原函数不是初等函数
又 $\because$ 题给积分上下限是 $[a,b]$，而不是 $[0,\infty)$
$\therefore$ 又说了四行废话
这题最重要的是数据范围，$b-a<2$，所以可以用积分的定义 $\int_a^bf(x)\,{\rm d}x\approx\sum_{x=a}^bf(x)\times\Delta x$，$\Delta x$ 越小，则结果越精确，而且输出只要保留两位小数，所以只要设置好 $\Delta x$ 的范围使得 $\frac{2}{\Delta x}\times T\leq10^8$，就能通过程序。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
double getf(double x) {
    return exp(-x * x) + sin(x) / x + 1 / log(x);
}
int main(int argc, char *argv[]) {
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
    int T, i;
    double ii;
    scanf("%d", &T);
    for(i = 0; i < T; ++i) {
        double a, b, S = 0;
        scanf("%lf%lf", &a, &b);
        for(ii = a; ii < b; ii += 0.0001) {
            S += getf(ii) * 0.0001;
        }
        printf("%.2lf\n", S);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

F. 解密

题意

输出将 $n$ 个数全排列按字典序排序后，排列 $s$ 往后数 $k$ 个的排列。

数据范围

$0<n\leq10^4,0\leq k\leq1000$

题解

这题想说废话也没得说了，直接按题意先暴力跑到排列 $s$，接着往后面跑 $k$ 个排列，每往后跑一个排列则 --k，如果所有排列都已经跑完而 $k\neq0$，则输出 "impossible"。递归大暴力是最好想但不是最好写的方法。
这题思维上没什么难度，主要就是一个递归函数要花一些时间写一下，比较考递归函数的代码实现能力。当然如果会调用 C++ 的函数 next_permutation，或者找到类似字典序法生成下一个全排列的规律，那这题一个 while 循环就解决了。
这题如果 $k$ 的值设置得更大一些（例如 $k\geq10^6$），而 $n$ 的值小一些，就需要用到康拓展开及其逆运算的知识了，学习理解康托展开之前建议先理解 $n!$ 进制这种数的表示方法，本题由于 $n$ 太大，康拓展开需要进行大数运算，所以无法用康拓展开，但建议了解一下。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 10000 + 100
int n, k;
int num[maxn];
int vis[maxn], ans[maxn];
void dfs(int depth, int limit) {
    if(depth == n + 1) {
        --k;
        return ;
    }
    int i, low;
    if(limit == 0) {
        low = 1;
    } else {
        low = num[depth];
    }
    for(i = low; i <= n; ++i) {
        if(vis[i] == 0) {
            vis[i] = 1;
            ans[depth] = i;
            dfs(depth + 1, limit && i == low);
            vis[i] = 0;
            if(k == 0) {
                return ;
            }
        }
    }
}
int main(int argc, char *argv[]) {
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
    int i;
    scanf("%d%d", &n, &k);
    ++k;
    for(i = 1; i <= n; ++i) {
        vis[i] = 0;
        scanf("%d", &num[i]);
    }
    dfs(1, 1);
    if(k == 0) {
        for(i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        } 
        printf("\n");
    } else {
        printf("impossible\n");
    } 
    fclose(stdin);
    fclose(stdout);
    return 0;
}

G. 一键复制粘贴

题意

有一个空字符串，对于这个空字符串有两种操作，第一种操作是往串尾添加一个字符，第二种操作是按下 Ctrl 键进行一键全选复制粘贴，且第一种操作可以进行无限次而第二种操作只能进行一次，要求用最少的操作次数得到字符串 $s$，输出最少的操作次数。

数据范围

对于 $20\%$ 的数据，$1\leq\left|s\right|\leq100$
对于 $50\%$ 的数据，$1\leq\left|s\right|\leq1000$
对于 $100\%$ 的数据，$1\leq\left|s\right|\leq10^6$

题解

啊……三道基础题和三道假算法题之后，终于来到了算法题部分，这题并不是由于它是高分题中最简单的而被放在第一题，实际上“香槟酒”更简单，只是因为，如果想不出“香槟酒”的正解，基本上拿不到分数，而这题就算只想出纯暴力的方法，也能拿到 $50\%$ 的分数，所以这题的数据相比于后面一题，更加友好一些。
实际上我们第一次出的 $20$ 组数据，由于没考虑到另一种优美的暴力写法，导致优美的暴力能够通过所有的数据，所以我们加强了第 $11$ 组到第 $20$ 组的数据，不论多优美的暴力都会超时的数据（flag 先立在这了，出数据的我坐等打脸）。

---

稍微往后面想两步就可以发现，这题要求的是：将字符串 $s$ 拆分成 $aab$ 这种形式的字符串，且要使字符串 $a$ 的长度最大，能通过 $50\%$ 的暴力解法，就是从 $1$ 到 $\lfloor\frac{n}{2}\rfloor$ 枚举字符串 $a$ 的长度 $l$，判断 $s$ 的子串 $s_1s_2s_3\cdots s_l$ 是否等于 $s_{l+1}s_{l+2}s_{l+3}\cdots s_{2l}$，取满足条件的最长的 $l$。因为这种做法要枚举 $l\in[1,\lfloor\frac{n}{2}\rfloor]$，且对于每个 $l$，都需要进行 $l$ 次比较，所以总的程序执行次数为：$\sum_{l=1}^{\lfloor\frac{n}{2}\rfloor}l=\frac{(1+\lfloor\frac{n}{2}\rfloor)\times\lfloor\frac{n}{2}\rfloor}{2}$（如果数据足够随机，这个比较次数将会是很小的数字，所以我们人为地设计了数据），对于 $50\%$ 的数据，计算次数最多为 $125250<10^8$，足以通过 $50\%$ 的数据，而对 $100\%$ 的数据 $9\times10^5\leq|s|\leq10^6$，最少计算次数约为 $1.01\times10^{11}>10^8$，超时稳的。

---

那现在来说一下正解吧，本题的正解有两种，会用其中任意一种就可以过题，这题的数据没什么坑，只要写出来过了样例基本上就能得满分。一种是字符串匹配 $KMP$ 算法，另一种是字符串哈希。
在看题解之前先了解一下 $KMP$ 吧：字符串练习题解。

---

好，理解了 $KMP$，我们就可以用第一种解法来解决这个问题了。
$KMP$ 的 $Next$ 数组的第 $i$ 位存的是第 $i$ 个字符及前面所有字符所组成的字符串的最长相同前后缀对应的前缀下标。我们可以发现，在 $i-Next_i\geq\frac{i}{2}$ 的情况下，$i$ 所代表的前缀就是一个最小周期长度为 $i-Next_i$ 的周期为 $T$ 的周期串，因为最小周期长度为 $len$ 的字符串同时也是一个周期长度为 $len\times t~(T\%t=0)$ 的周期串，因此只要 $i-Next_i$ 能整除 $\frac{i}{2}$，那么 $i$ 对应的前缀字符串就可以拆分成两个完全相同的字符串。于是就可以在字符串 $s$ 上 $O(n)$ 跑出 $Next$ 数组后，检查满足条件 $\frac{i}{2}\%(i-Next_i)=0$ 的所有 $i$ 中，最大的 $i$ 值，答案就是 $1+|s|-\frac{i}{2}$。
下面的 std1.c 代码就是用 $KMP$ 算法解决的，也是代码长度最短的解法。

---

另一种字符串哈希的方法，实际上相比于纯暴力解法，就是加快了比较两个字符串是否相等的速度，在暴力解法中，比较两个长度为 $l$ 的字符串是否相等的比较次数最大为 $l$ 次，通过字符串哈希可以只通过一次比较就判断出两个字符串是否相等。
那再来简单解释一下字符串哈希吧，字符串哈希就是相当于把一个字符串看作一个 $26$ 进制的数字（看字符集的大小，如果既有大写字母又有小写字母，且区分大小写的话，字符集大小就是 $52$，要哈希这个字符串就要用 $52$ 进制），第 $0$ 位的位权为 $26^0$，第 $1$ 位的位权为 $26^1$，以此类推，第 $i$ 位的位权为 $26^i$。由于基本数据类型无法存下 $26^{1000000}$ 大小的数字，所以我们可以用 A 题中的方法，取一个大质数，将字符串哈希后的值对这个大质数取余（大质数一般取 $10^7+9$ 或 $10^9+7$ 或 $10^9+9$），这样在能保证按照一定规则对字符串进行处理后，得到一个唯一确定的值，相同的字符串哈希后的值就是相等的，不同字符串哈希后的值相等的概率极小，发生冲突的概率为 $prime^{-1}$，$prime$ 为哈希字符串所选择的质数。为了减小哈希的冲突概率，我们可以用双哈希的方法，也就是用两个大质数来对同一个字符串进行哈希，只有当两个哈希值都相等的时候，才认为两个字符串相等，这样哈希冲突的概率就可以降到 $(prime_1\times prime_2)^{-1}$ 本题的 std2.c 与 std3.c 用的都是双哈希。
这里以十进制为例，说明如何用哈希的方式比较两个字符串是否相等。例如对于数字：$1231234$（假设字符集为 $0-9$，将第 $i$ 个字符的位权设为 $10^{i-1}$，那么哈希后的字符串在形式上与对应的十进制数是相反的），我们用一个 $Hash$ 数组来记录每一位的 $Hash$ 值，于是就有以下数组（数组下标从 $0$ 开始，而字符串下标从 $1$ 开始）：

0	1	2	3	4	5	6
0	1	21	321	1321	21321	321321

从这个数组中截取原串的第 $i$ 位到第 $j$ 位子串对应的哈希值的计算方式为：$\frac{Hash_j-Hash_{i-1}}{10^{i-1}}$（可以很容易证明 $Hash_j-Hash_{i-1}$ 一定是 $10^{i-1}$ 的整数倍）。
这个字符串中出现了两次 $123$ 子串，我们可以取出这个字符串的第 $4$ 到第 $6$ 位子串对应的哈希值，取法：$\frac{Hash_6-Hash_{4-1}}{10^{4-1}}=\frac{321321-321}{10^3}=321$，将得到的数字与第 $1$ 到第 $3$ 位子串对应的哈希值（$\frac{Hash_3-Hash_{1-1}}{10^{1-1}}=\frac{321-0}{10^0}=321$）进行比较，发现 $321=321$，因此原字符串内的子串 $s_1s_2s_3=s_4s_5s_6$。
现在将十进制转化到 $26$ 进制，则获取子串 $s_ls_{l+1}s_{l+2}\cdots s_r$的哈希值方式为：$\frac{Hash_r-Hash_{l-1}}{26^{l-1}}$，由于哈希值的获取涉及取模运算，所以不能直接对数字进行除法操作，需要求出除数相对于模数的逆元（详见 $exgcd$ 求逆元），这也是哈希模数取质数的原因。
在取模运算中运用除法，是标程 std3.c 中的做法，而 std2.c 中的做法，则不运用除法，而是直接将低位的数字乘上 $26^{l-1}$ 次方后与高位的数字进行对比，即判断 $Hash_{l,r}$ 是否等于 $Hash_{1,l-1}\times26^{l-1}$，在取模运算中涉及到乘法，可以直接运用与加法类似的公式：$(a\times b)\%c=(a\%c\times b\%c)\%c$，进行求解，而不需要用到逆元的知识。

标程

std1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 1000000 + 100
int ans, len;
int Next[maxn];
char str[maxn];
int min(int a, int b) {
    return a < b? a: b;
}
void get_Next(char *str) {
    int j = 0, i;
    len = strlen(str + 1);
    Next[1] = 0;
    for(i = 2; i <= len; ++i) {
        while(j != 0 && str[j + 1] != str[i]) {
            j = Next[j];
        }
        if(str[j + 1] == str[i]) {
            ++j;
        }
        Next[i] = j;
    }
}
int main(int argc, char *argv[]) {
    freopen("G.in", "r", stdin);
    freopen("G.out", "w", stdout);
    int i;
    scanf("%s", str + 1);
    get_Next(str);
    ans = len;
    for(i = 2; i <= len; i += 2) {
        if((i / 2) % (i - Next[i]) == 0) {
            ans = min(ans, i / 2 + 1 + len - i);
        }
    }
    printf("%d\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

std2.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 1000000 + 100
int len, ans;
char str[maxn];
long long Pow[2][maxn];
long long Sum[2][maxn];
long long MOD[2] = {1000000007, 10000009};
void Init() {
    int i, j;
    Pow[0][0] = Pow[1][0] = 1;
    for(i = 0; i < 2; ++i) {
        for(j = 1; j < maxn; ++j) {
            Pow[i][j] = Pow[i][j - 1] * 26 % MOD[i];
        }
    }
}
void get(char *str) {
    int i, j;
    for(i = 0; i < 2; ++i) {
        Sum[i][0] = 0;
        for(j = 1; str[j]; ++j) {
            Sum[i][j] = (Sum[i][j - 1] + (str[j] - 'a' + 1) * Pow[i][j] % MOD[i]) % MOD[i];
        }
    }
}
int judge(int Index) {
    int i;
    for(i = 0; i < 2; ++i) {
        long long num1 = ((Sum[i][Index] - Sum[i][Index / 2]) % MOD[i] + MOD[i]) % MOD[i];
        long long num2 = Sum[i][Index / 2] * Pow[i][Index / 2] % MOD[i];
        if(num1 != num2) {
            return 0;
        }
    }
    return 1;
}
int min(int a, int b) {
    return a < b? a: b;
}
int main(int argc, char *argv[]) {
    freopen("G.in", "r", stdin);
    freopen("G.out", "w", stdout);
    int i;
    Init();
    scanf("%s", str + 1);
    get(str);
    ans = len = strlen(str + 1);
    for(i = 2; i <= len; i += 2) {
        if(judge(i)) {
            ans = min(ans, i / 2 + 1 + len - i);
        }
    }
    printf("%d\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

std3.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 1000000 + 100
char s[maxn];
long long inv[2];
long long sum[2][maxn];
long long Pow[2][maxn];
long long invpow[2][maxn];
long long mod[2] = {1000000007, 1000000009};
void exgcd(long long a, long long b, long long *x, long long *y) {
    if(b == 0) {
        *x = 1;
        *y = 0;
        return ;
    }
    exgcd(b, a % b, y, x);
    *y -= *x * (a / b);
}
long long ch(char u) {
    return u - 'a' + 1;
}
long long getInv(long long num, long long mod) {
    long long x, y;
    exgcd(num, mod, &x, &y);
    return (x % mod + mod) % mod;
}
void Init(char *str, int len) {
    int i, j;
    long long x, y;
    for(i = 0; i < 2; ++i) {
        Pow[i][0] = 1;
        inv[i] = getInv(26, mod[i]);
        invpow[i][0] = 1;
        sum[i][0] = 1;
    }
    for(i = 0; i < 2; ++i) {
        for(j = 1; j < maxn; ++j) {
            Pow[i][j] = Pow[i][j - 1] * 26 % mod[i];
            invpow[i][j] = (invpow[i][j - 1] * inv[i]) % mod[i];
        }
    }
    for(i = 0; i < 2; ++i) {
        for(j = 1; j <= len; ++j) {
            sum[i][j] = (sum[i][j - 1] * 26 + ch(str[j])) % mod[i];
        }
    }
}
long long get(char *str, int l, int r, int Index) {
    return (((sum[Index][r] - sum[Index][l - 1]) % mod[Index]) + mod[Index]) % mod[Index] * invpow[Index][l] % mod[Index];
}
int min(int a, int b) {
    return a < b? a: b;
}
int main(int argc, char *argv[]) {
    freopen("G.in", "r", stdin);
    freopen("G.out", "w", stdout);
    int i, len, ans, Len;
    scanf("%s", s + 1);
    len = strlen(s + 1);
    Init(s, len);
    ans = len;
    for(i = 1; i <= len; ++i) {
        Len = i;
        if(i + Len <= len) {
            if((get(s, 1, i, 0) == get(s, i + 1, i + Len, 0)) && get(s, 1, i, 1) == get(s, i + 1, i + Len, 1)) {
                ans = min(ans, 1 + len - Len);
            }
        }
    }
    printf("%d\n", ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

H. 香槟酒

题意

给一种香槟酒的倒酒规则，问要把第 $a$ 行的第 $b$ 个酒杯装满，至少要倒多少单位体积的香槟酒。

数据范围

$1\leq b\leq a\leq30$

题解

这题数据范围本来出 $100$ 的，后来我们我们发现要倒满第 $100$ 层的酒杯的答案大小远远超出了 double 能够表示的范围，就改成了 $30$ 了。
我们稍微往第三层第四层画下去几层可以发现，在同一层内，要装满两端的两个酒杯所需要的香槟酒是最多的，由于两端的情况比较好推，所以我们先从这里入手来看看有什么规律。通过找规律或者简单证明一下可以发现：装满第 $i$ 层两端的酒杯需要的香槟酒为 $2^i-1$，所以如果把数据范围设为 $100$，那 $(100,100)$ 的答案就是 $2^{100}-1$，显然 double 是无法存在下这么大的答案的，所以我们将数据范围减小到了 $30$。我们再将这个思路推到更普遍的情况可以发现，这很难推，所以这段话只是说明了我们改数据范围的原因。

---

我们很容易可以发现，如果我已经知道要倒多少香槟酒到顶端的酒杯，可以 $O(n^2)$ 地计算出酒杯 $(i,j)$ 最终含有的香槟酒的体积（用一个二维数组保存对应位置酒杯的酒的体积，模拟一遍倒酒的过程即可）。
并且：往顶端的酒杯倒越多的香槟酒，酒杯 $(i,j)$ 内香槟酒的体积就越大，如果把香槟酒的总体积作为自变量，酒杯 $(i,j)$ 内的香槟酒体积作为函数值，就是一个单调递增的函数，因此我们可以用高中学过的二分法求零点的方式来求函数值等于 $1$ 的自变量的值。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 100 + 100
int a, b;
double num[maxn][maxn];
int judge(double x) {
    int i, j;
    num[1][1] = x;
    for(i = 2; i <= a; ++i) {
        for(j = 1; j <= i; ++j) {
            num[i][j] = 0;
            if(num[i - 1][j - 1] >= 1) {
                num[i][j] += (num[i - 1][j - 1] - 1) / 2;
            }
            if(num[i - 1][j] >= 1) {
                num[i][j] += (num[i - 1][j] - 1) / 2;
            }
        }
    }
    return num[a][b] >= 1;
}
int main(int argc, char *argv[]) {
    freopen("H.in", "r", stdin);
    freopen("H.out", "w", stdout);
    int i;
    double high = 1e18;
    double low = 0;
    double mid;
    scanf("%d%d", &a, &b);
    for(i = 0; i < 1000; ++i) {
        mid = (low + high) / 2;
        if(judge(mid) == 1) {
            high = mid;
        } else {
            low = mid;
        }
    }
    printf("%.10f\n", high);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

I. 送分题 A+B

题意

输入 $A~B$，输出 $A+B$ 及 $A-B$ 的结果。

数据范围

对于 $10\%$ 的数据，$-18\times10^{18}\leq A,B\leq18\times10^{18}$
对于 $50\%$ 的数据，$A\times B>0$
对于 $100\%$ 的数据，$-10^{100000}\leq A,B\leq10^{100000}$

题解

这场比赛原本是 $8$ 选 $5$ 而不是 $9$ 选 $6$ ，但是我们赛前两周的一次讨论即将结束的时候，许子涵学长提了一个问题，我们给的这些标程代码长度最长的有多长？我看了一下，空行头文件都算进去的话大概五六十行吧……才五六十行啊……我们害怕由于代码太短有大佬很早就结束了比赛提前离场（抱歉，代码短不代表题目就简单），所以打算出一道每个人都知道怎么写，但是写起来代码量大一些的题目，本来打算出高精度整数乘法的，但是其实高精度整数就算加上正负号也就五六十行，两个 for 循环就完事了，所以我和孙昊哲又讨论了怎么出这道题，于是“送分题 A+B” 就这样诞生了——这题本人在有实现高精度整数加减乘除法经验的前提下完成代码，大概写了一个小时的标程，总代码长度 $184$ 行（当然为了程序逻辑清晰更容易看懂，在前面写了许多函数声明导致代码长度增加，但是只要你的代码风格是正常的，不刻意压行的话，$100$ 行代码是少不了的）。算上这道题，本人可能三小时也很难做出分数最高的六题。
这题就是一个高精度整数的加减法，不论输入用的是什么基本数据类型，提交得分都是 $0$，即使是第一组数据……第一组数据的数据范围其实是用来迷惑你们的，虽然 unsigned long long 的数据范围大约是 $[0,18\times10^{18}]$，但是两个 $18\times10^{18}$ 相加就会溢出，为了让你们认真写高精度整数加减法，第一组数据就是两个 $18\times10^{18}$。（嘿嘿嘿……）
如果只会写加法不会写减法，也可以获得 $50\%$ 的分数，因为那部分数据是 $A~B$ 同号的。
同号加法就不说怎么写了，这里主要说一下关于减法与负号如何处理，处理同号加法不是这题的难点，这题的精髓在于处理不同号数据的加减法，这里简单说明一下这部分程序的逻辑：

1. 首先实现四个基本函数：取相反数，绝对值比较函数，同号加法函数，同号减法函数（在 $A>B$ 的情况下）
2. 在 $A+B$ 的情况下
   
   1. 若 $B$ 为负号，则对 $B$ 取相反数后调用 $A-B$
   2. 若 $A$ 为负号，则对 $A$ 取相反数后调用 $B-A$
   3. 直接执行 $A+B$
3. 在 $A-B$ 的情况下：
   
   1. 若 $B$ 为负号，则对 $B$ 取相反数后调用 $A+B$
   2. 若 $A$ 为负号，则对 $A$ 取相反数后调用 $B+A$，再对计算结果取反
   3. 若 $A<B$，则调用 $B-A$，再对计算结果取反
   4. 直接执行 $A-B$

在 $A+B$ 与 $A-B$ 两种情况下的每一个判断，前面的判断优先级大于后面的判断，也就是如果先满足了前面的判断，就不必执行后面的判断，例如：要进行 $3.3$ 的判断，应该先不满足条件 $3.1$ 与 $3.2$，也就是 $A~B$ 都大于等于 $0$ 的情况下才会判断 $A<B$ 是否为真，因此这里的比较一定是绝对值比较，在执行 $3.4$ 时，应该先不满足前面三个条件，也就是在调用 $A-B$ 时，已经满足了 $A~B$ 非负数且 $A\geq B$，得到的结果必然是一个正数。
这题十分考代码能力与程序的结构化能力，如果对正负号与加减号进行组合判断的话，总共就要写 $8$ 种情况的运算，代码量将会远远超过 $200$ 行，且不易 $debug$。

标程

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */ 
#define maxn 100000 + 100
typedef struct BigInteger {
    int sign;
    int len; 
    int num[maxn];
} BigInteger;
int max(int a, int b);
void Init(BigInteger *x);
void str2num(char *str, BigInteger *x);
void Copy(BigInteger *from, BigInteger *to);
void CutLeadingZeros(BigInteger *x);
void Get_neg(BigInteger *x);
int smaller(BigInteger *a, BigInteger *b);
void add(BigInteger *a, BigInteger *b, BigInteger *ans);
void sub(BigInteger *a, BigInteger *b, BigInteger *ans);
void Print(BigInteger *x);
char str[maxn];
BigInteger num[2];
BigInteger tmp[2];
BigInteger ans;
int main(int argc, char *argv[]) {
    freopen("I.in", "r", stdin);
    freopen("I.out", "w", stdout);
    int i, j;
    for(i = 0; i < 2; ++i) {
        scanf("%s", str);
        Init(num + i);
        str2num(str, num + i);
    }
    for(i = 0; i < 2; ++i) {
        Copy(num + i, tmp + i);
    }
    Init(&ans);
    add(tmp + 0, tmp + 1, &ans);
    Print(&ans);
    Init(&ans);
    sub(num + 0, num + 1, &ans);
    Print(&ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
int max(int a, int b) {
    return a > b? a: b;
}
void Init(BigInteger *x) {
    x->len = 1;
    x->sign = 1;
    int i;
    for(i = 0; i < maxn; ++i) {
        x->num[i] = 0;
    }
}
void str2num(char *str, BigInteger *x) {
    int i;
    int Left = 0;
    int len = strlen(str);
    if(str[0] == '-') {
        x->sign = 0;
        Left = 1;
    }
    x->len = len - Left;
    for(i = len - 1; i >= Left; --i) {
        x->num[len - 1 - i] = str[i] - '0';
    }
}
void Copy(BigInteger *from, BigInteger *to) {
    int i;
    to->len = from->len;
    to->sign = from->sign;
    for(i = 0; i < maxn; ++i) {
        to->num[i] = from->num[i];
    }
}
void CutLeadingZeros(BigInteger *x) {
    int i;
    for(i = maxn - 1; i >= 0; --i) {
        if(x->num[i] != 0) {
            x->len = i + 1;
            return ;
        }
    }
    x->len = 1;
    x->sign = 1;
}
void Get_neg(BigInteger *x) {
    x->sign = 1 - x->sign;
}
int smaller(BigInteger *a, BigInteger *b) {
    if(a->len != b->len) {
        return a->len < b->len;
    }
    int i;
    for(i = a->len - 1; i >= 0; --i) {
        if(a->num[i] != b->num[i]) {
            return a->num[i] < b->num[i];
        }
    }
    return 0;
}
void add(BigInteger *a, BigInteger *b, BigInteger *ans) {
    if(b->sign == 0) {
        Get_neg(b);
        sub(a, b, ans);
        return ;
    }
    if(a->sign == 0) {
        Get_neg(a);
        sub(b, a, ans);
        return ;
    }
    int i, c = 0;
    int len = max(a->len, b->len);
    for(i = 0; i < len; ++i) {
        ans->num[i] = (c + a->num[i] + b->num[i]) % 10;
        c = (c + a->num[i] + b->num[i]) / 10;
    }
    ans->num[len] = c;
    ans->sign = 1;
    CutLeadingZeros(ans);
}
void sub(BigInteger *a, BigInteger *b, BigInteger *ans) {
    if(b->sign == 0) {
        Get_neg(b);
        add(a, b, ans);
        return ;
    }
    if(a->sign == 0) {
        Get_neg(a);
        add(a, b, ans);
        Get_neg(ans);
        return ;
    }
    if(smaller(a, b)) {
        sub(b, a, ans);
        Get_neg(ans);
        return ;
    }
    int i, c = 0;
    for(i = 0; i < a->len; ++i) {
        if(a->num[i] - c < b->num[i]) {
            ans->num[i] = a->num[i] - c + 10 - b->num[i];
            c = 1;
        } else {
            ans->num[i] = a->num[i] - c - b->num[i];
            c = 0;
        }
    }
    ans->sign = 1;
    CutLeadingZeros(ans);
}
void Print(BigInteger *x) {
    if(x->sign == 0) {
        printf("-");
    }
    int i; 
    for(i = x->len - 1; i >= 0; --i) {
        printf("%d", x->num[i]);
    }
    printf("\n");
}