2020年中南大学研究生招生夏令营机试题
2020年中南大学研究生招生夏令营机试题
A题
题目描述
众所周知，彩虹有7种颜色，我们给定七个 字母和颜色 的映射，如下所示：
‘A’ -> “red”
‘B’ -> “orange”
‘C’ -> “yellow”
‘D’ -> “green”
‘E’ -> “cyan”
‘F’ -> “blue”
‘G’ -> “purple”
但是在某一天，彩虹的颜色少了几种，你能告诉PIPI哪些彩虹的颜色没有出现过吗?
输入
输入包含多组测试用例。
对于每组测试用例，输入n个合法的颜色字符串(0<=n<=100)，输出有多少种颜色没有出现过，并分别输出对应的字母。
输出
对于每一组测试样例，输出一个数字，代表缺失的颜色种数，然后按照升序输出缺失颜色对应的字母。
样例输入
3
red
orange
cyan
样例输出
4
C
D
F
G
题目思路
这题就是道签到题，直接暴力解决，用数组把七种颜色存储起来。每次输入颜色都与7种颜色相比，是否已经输入过此种颜色，如果没有则进行标记。同时记录已经输入了多少种颜色
上代码
#include<cstdio>
#include<cstring>
int main()
{
int n, cnt;
char s[10][10] = {"red", "orange", "yellow", "green", "cyan", "blue", "purple"};
int flag[7];
char s1[10];
while(~scanf("%d", &n))
{
cnt = 7;
memset(flag, 0, sizeof(flag));
for(int i = 0; i < n; i++)
{
scanf("%s", s1);
for(int j = 0; j < 7; j++)
{
if(flag[j]) continue;
if(!strcmp(s1, s[j]))
{
flag[j] = 1;
cnt--;
break;
}
}
}
printf("%d\n", cnt);
for(int i = 0; i < 7; i++)
{
if(flag[i]) continue;
printf("%c\n", 'A'+i);
}
}
return 0;
}
B题
题目描述
给定 n 个整数对(ai, bi) , 每个整数对的价值是(i-1)*ai + (n-i)*bi (下标从1开始， 这里的 ai 、bi 和输入不一定对应)，然后问所有整数对的最小价值总和。
输入
输入包含多组测试用例。
对于每组测试用例，首先输入数对的数量n(n<=1e5)
接下来输入n对数对 ai bi (0<=ai,bi<=1e9)
输出
对于每组测试用例，输出这些整数对的最小价值总和。
样例输入
3
3 2
2 4
6 1
样例输出
11
提示
0 * 6 + 2 * 1 + 1 * 3 + 1 * 2 + 2 * 2 + 0 * 4 = 11
题目思路
任取两个位置的对数P1,P2。（假设P1的位置为i在P2的位置j前面）(i < j)
则价值和为
value1 = (i - 1) * P1.a+ (n - i) * P1.b + (j - 1) * P2.a + (n - j) * P2.b
将P1和P2的位置对换一下
则价值和为
value2 = (i - 1) * P2.a+ (n - i) * P2.b + (j - 1) * P1.a + (n - j) * P1.b
value1 - value2 = (j - i) * ( (a2 - b2) - (a1 - b1) )
当a2 - b2 < a1 - b1时，value1 - value2 < 0
说明P1在i位置P2在j位置的价值和比P2在i位置P1在j位置的价值和小,不需要更换位置
通过上面的式子可以看出a-b大的放在前面,只需要用一个sort排序一下就可以了
上代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct dot
{
ll a;
ll b;
}dot;
dot p[100005];
int cmp(const dot &p1, const dot& p2)
{
return (p1.a - p1.b) > (p2.a - p2.b);
}
int main()
{
int n;
ll ans;
while(~scanf("%d", &n))
{
for(int i = 0; i < n; i++)
scanf("%lld %lld", &p[i].a, &p[i].b);
sort(p, p+n, cmp);
ans = 0;
for(int i = 0; i < n; i++)
ans += i * p[i].a + (n - i -1) * p[i].b;
printf("%lld\n", ans);
}
return 0;
}
C题
题目描述
PIPI每天早上都要从CSU的某个位置走到另一个位置。CSU可以抽象为一个n*m的方格。PIPI每天都要从(x1,y1)走到(x2,y2)，规定每次可以向下或者向右移动一格。总共有q次询问，每次询问从(x1,y1)走到(x2,y2)有多少条不同的路径，答案对1000000007取模。
输入
输入包含多组测试用例。
对于每组测试用例，首先输入三个整数n,m,q(1<=n,m,q<=5000),代表方格的大小和询问次数。
接下来q行，每行输入四个正整数 x1, y1 ,x2,y2(1<=x1<=x2<=n ,1<=y1<=y2<=m) 。意义如题所示。
输出
4 4 4
1 1 1 1
1 1 2 2
1 1 1 2
1 1 2 1
样例输入
1
2
1
1
题目思路
这题思路非常简单就是一个高中数学排列组合，从一个点(x1, y1)走到另外一个点(x2, y2)有多少条路径。
a = x2 - x1
b = y2 - y1
t = a + b
答案就为C_t^a
总共走t步，其中选a步向左走，其余的步数向下走。
问题在于数据太大会溢出要取模问题
有
(a*b)%mod = (a%mod * b%mod)%mod
但是没有
(a/b)%mod = (a%mod / b%mod )%mod
所以需要将除转化为逆元。在此处不讲述逆元的知识
inv(a) 表示为a的逆元
（a /b）%mod = (a * inv(b)) %mod
上代码
#include<cstdio>
#include<vector>
typedef long long ll;
using namespace std;
const ll mod = 1000000007;
ll p1[5005];
ll quick_pow(ll a, ll b)
{
ll ans = 1;
while(b)
{
if(b&1)
ans = ans * a % mod;
a = a * a % mod;
b>>=1;
}
return ans;
}
int main()
{
int n, m, p, x1, x2, y1, y2, a, b, tem1, tem2;
ll ans;
for(int i = 1; i <= 5000; i++)
p1[i] = quick_pow(i, mod-2);
while(~scanf("%d %d %d", &n, &m, &p))
{
for(int i = 0; i < p; i++)
{
ans = 1;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
a = x2 - x1 + y2 - y1;
if(x2 - x1 < y2 - y1)
b = x2 -x1;
else
b = y2 - y1;
tem1 = a;
tem2 = b;
for(int j = 0; j < b; j++)
{
ans = ans * tem1 % mod;
ans = ans * p1[tem2] % mod;
tem1--;
tem2--;
}
printf("%lld\n", ans);
}
}
return 0;
}
D题
题目描述
有 m 根木棍，m = n * k，n 个桶，每个桶由 k 块木板构成，桶的容量由最短的木板长度决定，桶的底面积为 1，现要求任意两个桶间的容量差小于等于 L，问 n 个桶的最大容量和。
如果无法满足组成n个桶，输出0.
输入
第一行输入三个整数 n,k, L(n _k <=1e5)。
第二行输入n_k根木板长度，a1,a2,a3…1 ≤ a**i ≤ 10^9
输出
输出n个木桶最大容量和。
样例输入
4 2 1
2 2 1 2 3 2 2 3
样例输出
7
提示
这四个桶可以是1 2, 2 2, 2 3, 2 3，那么答案就是1+2+2+2 = 7。
题目思路
先把木板从小到大排好序。如果要组成n个符合要求的桶子。则排好序后第n块木板的长度小于等于第一块木板的长度 + L。求出比第一块木板长度长L的总共有K块。如果K<n说明不可能组成n的符合要求的桶子,直接输出0。(长度小的木板能组成一个木桶，总容量才会大)
下面为找出的K个符合要求的n个木桶的最短木板（长度从小到大排序）
A（1） A（2） A（3） ... A（k）
先把A（1）作为第一个木桶的最短木板,因为要尽可能多的短木板组成一个木桶。又要有n个符合要求的最短木板，
所以挑选a = min（k-1， K-n）块长度小的木板和A(1)组成一个木桶。
再挑选A（1+min（K-1, K-n）+1）作为第二个木桶的最小木板,再挑选min(k-1, K-n-a)块长度小的木板和其组成木桶
一直挑选下去即可
上代码
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll board[100005];
int main()
{
int n, k, l, i, j, cnt;
ll ans;
while(~scanf("%d %d %d", &n, &k, &l))
{
for(int i = 0; i < n*k; i++)
scanf("%lld", &board[i]);
sort(board, board+n*k);
if(board[n-1] - board[0] > l)
printf("0\n");
else
{
j = cnt = ans = 0;
for(i = n-1; i < n*k; i++)
{
if(board[i] - board[0] <= l)
continue;
else
break;
}
i = i - n;
while(i > 0)
{
if(i >= k-1)
{
ans += board[j];
i -= k-1;
j += k;
cnt++;
}
else
{
ans += board[j];
j += i+1;
i = 0;
cnt++;
}
}
if(cnt < n)
{
for(i = j; i < n*k; i++)
{
if(cnt >= n)
break;
ans += board[i];
cnt++;
}
}
printf("%lld\n", ans);
}
}
return 0;
}
