2020中南大学研究生招生夏令营机试题
2020中南大学研究生招生夏令营机试题
-
- 1.缺失的彩虹
- 2.最小价值和
- 3.PIPI上学路
1.缺失的彩虹
题目描述
众所周知，彩虹有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
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
map<string,char>hash;//value==1则表示有出现过了
hash["red"]='A';hash["orange"]='B';hash["yellow"]='C';hash["green"]='D';
hash["cyan"]='E';hash["blue"]='F';hash["purple"]='G';
bool vis[7];
while(scanf("%d",&n)!=EOF)
{
memset(vis,false,sizeof vis);
string s;
int cnt=0;
for(int i=0;i<n;i++)
{
cin>>s;
//cout<<s<<endl;
if(!vis[hash[s]-'A'])
vis[hash[s]-'A']=true,cnt++;
}
printf("%d\n",7-cnt);
for(int i=0;i<7;i++)
{
if(!vis[i]) printf("%c\n",i+'A');
}
}
return 0;
}
2.最小价值和
题目描述
给定 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
#include<bits/stdc++.h>
using namespace std;
//贪心算法，根据整数对差的大小进行从大到小排序
const int maxn=1e5+5;
struct node
{
int a,b;
node():a(0),b(0){}
bool operator< (const node& p) const{
return a-b>p.a-p.b;
}
};
node arr[maxn];
int n;
int main()
{
while(scanf("%d",&n)!=EOF)
{
long long res=0;
for(int i=1;i<=n;i++) scanf("%d%d",&arr[i].a,&arr[i].b);
sort(arr+1,arr+1+n);
for(int i=1;i<=n;i++)
res+=(i-1)*(long long)arr[i].a+(n-i)*(long long)arr[i].b;
cout<<res<<endl;
}
return 0;
}
3.PIPI上学路
题目描述
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
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,q,a,b,c,d;
int dp[5005][5005];
int main()
{
for(int i=1;i<=5000;i++)
for(int j=1;j<=5000;j++)
{
if(i==1||j==1) dp[i][j]=1;
else dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
}
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
while(q--)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",dp[c-a+1][d-b+1]);
}
}
return 0;
}