2020 中南大学研究生招生夏令营机试题（回忆版）

说明：因为条件有限，所以没有办法做详细的记录（相关数据范围丢失），只能简单说明一下。可能存在部分疏漏，欢迎指正。
写这个的原因除了自己记录以外，也希望能对想参加中南计算机夏令营或者报考中南计算机研究生的同学们提供一些帮助。
如有侵权，请立即联系我删除。

A 第一题

给定七个 字母和颜色 的映射，如下：

'A' -> "red"

'B' -> "orange"

'C' -> "yellow"

'D' -> "green"

'E' -> "cyan"

'F' -> "blue"

'G' -> "purple"

然后输入给一些合法的颜色字符串，输出有多少种颜色没有出现过，分别输出对应的字母。

比如：

Input:
3
red
orange
cyan
Output:
4 
C
D
F
G

B 第二题

给定n个整数对$(a_i, b_i)$，每个整数对的价值是$(i - 1)*a_i + (n - i) * b_i$，然后问所有整数对的最小价值总和。

比如：

Input:
3 (n)
3 2 (ai, bi)
2 4
6 1
Output:
11

提示： 0 * 6 + 2 * 1 + 1 * 3 + 1 * 2 + 2 * 2 + 0 * 4 = 11 。

C 第三题

给定一个n*m的方格，然后规定每次可以向下或者向右移动一个方格，一共q次询问，每次问从坐标$(x_1, y_1)$到$(x_2, y_2)$有多少条不同的路径。$1<= n, m, q <= 5000$。输出对1000000007取模。

比如：

Input:
4 4 (n, m)
4 (q)
1 1 1 1 
1 1 2 2
1 1 1 2
1 1 2 1
Output:
1
2
1
1

D 第四题

有m根木棍，m = n * k，n个桶，每个桶由k块木棍构成，桶的容量由最短的木棍长度决定，桶的底面积为1，现要求每两个桶间的容量差小于等于l，问n个桶的最大容量和。

比如：

Input:
4 2 1 (n, k, l)
2 2 1 2 3 2 2 3 (m块木棍的长度)
Output:
7

提示：这四个桶可以是1 2, 2 2, 2 3, 2 3，那么答案就是1+2+2+2 = 7。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
typedef long long ll;

int a[maxn];

int main()
{
    int n, k, l, m;
    scanf("%d%d%d", &n, &k, &l);
    m = n * k;
    for (int i = 0; i < m; ++i)
        scanf("%d", &a[i]);
    sort(a, a + m);
    ll ans = 0;
    int pos = upper_bound(a, a + m, a[0] + l) - a;
    if (pos >= n)
    {
        int cnt = 0;
        for (cnt = 0; pos - cnt * k > n - cnt; ++cnt)
            ans += a[cnt * k];
        for (int i = pos - 1; i >= pos - (n - cnt); --i)
            ans += a[i];
    }
    printf("%lld\n", ans);
    return 0;
}

E 第五题

对于一个长度为n的数组A和一个整数c，A的特征值为前$\lfloor n / c \rfloor$个小的元素之外的元素的和。比如A={3, 1, 6, 5, 2}, c = 2，那么A的特征值就为3+5+6=14。

现要求将A划分为若干个序列，使得所有序列的特征值之和最小，输出最小的特征值之和。

比如：

Input:
7 2 (n, c)
2 3 6 4 5 7 1
Output:
17

提示：对于2 3 6 4 5 7 1可以划分为2 3，6 4 5 7，1，那么结果就是3 + 6 + 7 + 1 = 17。

补充

因为对CSUOJ很熟悉，所以最后看了下榜（当然是封榜之前的情况），4道题个位数，3道题及以上十几个，2道题及以上三十几个，1道题及以上七十几个，一共一百三十个人左右。后面听说有几位大佬AK了。

总之，一次很愉快的短期旅行，接触到的中南的老师感觉都很棒，很实在，也很接地气。

最后，感谢中南大学计算机学院以及老师和工作人员的付出，特别鸣谢中南大学三食堂。

The end.
2019年6月29日星期六