2019年湘潭大学程序设计竞赛（重现赛）-题解A-E
A-Who’s better?
ICPC比赛中，谁通过的题数多，谁排名靠前；在通过题数相同的情况下，谁的罚时少，谁排名靠前；如果前两者都相同，就看最后正确提交的时间，谁早最排名靠前。 现在给你两个队伍的正确通过的题数、罚时和最后正确提交时间，请判断一下，谁的排名更靠前？
输入描述:
只有一组测试样例，两行，每行三个整数n(0≤n≤13),p(1≤p≤1000),s(1≤s≤300)
n(0≤n≤13),p(1≤p≤1000),s(1≤s≤300)
，依次表示两个队的正确通过的题数、罚时和最后正确提交时间。
输出描述:
输出一行（末尾要换行符）。
如果是第1个队排名靠前，输出1；如果是2队，输出2；如果无法分辨，输出"God"。
输入
1 10 10
1 22 2
输出1
输入
1 10 10
2 42 20
输出
2
输入
1 10 10
1 10 10
输出
God
题解：水题 if判断过去就好
#include<stdio.h>
int main()
{
int a,b,c;
int x,y,z;
scanf("%d%d%d%d%d%d",&a,&b,&c,&x,&y,&z);
if(a>x)
{
printf("1\n");
}
else if(x>a)
{
printf("2\n");
}
else
{
if(b+c>y+z)
printf("2\n");
else if(b+c<y+z)
printf("1\n");
else
printf("God\n");
}
return 0;
}
B-Number
Bonnie得到了一个数字n。
现在她想对这个数字不断的做一种操作：
如果n的最后一位数码是0，那么她就把n除以10；
否则她把这个数加上1；
直到n变为一个不大于1的数。
给定n，请问Bonnie需要做多少次操作？
输入描述:
第一行一个数字T(1≤T≤300000)
T(1≤T≤300000)
–样例个数。
每个样例仅一行一个数字n(1≤n≤109)
n(1≤n≤109)
。
输出描述:
每个样例输出一行一个数字—Bonnie需要做的操作次数。
输入
6
9
99
2
11032
1000000000
62
输出2 3 9 44 9 13
说明
第一个样例: 9→10→1
9→10→1
第二个样例: 99→100→10→1
99→100→10→1
题解:
模拟
Code：
#include<stdio.h>
int main()
{
int n,m,count;
scanf("%d",&n);
while(n--)
{
count=0;
scanf("%d",&m);
while(m>1)
{
if(m%10==0)
{
m=m/10;
count++;
}
else
{
m++;
count++;
}
}
printf("%d\n",count);
}
return 0;
}
C-Math Problem
题目描述
已知整数a,a3
a,a3
除192的余数是1。求区间[L,R]之间满足条件的a的累加和是多少？
输入描述:
第一行是一个整数T(1≤T≤10000)
T(1≤T≤10000)
，表示样例的个数。
每个样例包含两个整数L,R,1≤L≤R≤109
L,R,1≤L≤R≤109
。
输出描述:
每行输出一个样例的结果。
输入
1
1 10
输出
1
题解:
还有一个求和公式 首项加尾项乘个数处以2
Code:
#include<stdio.h>
int main()
{
long long n,e,f,count=0,q,p,sum;
scanf("%lld",&n);
while(n--)
{
sum=0;
scanf("%lld%lld",&e,&f);
q=e,p=f;
while(q%192!=1)
{
q++;
}
while(p%192!=1)
{
p--;
}
sum=(q+p)*((p-1)/192-(q-1)/192+1)/2;
printf("%lld\n",sum);
}
return 0;
}
D-Stone
题目描述
有n堆石子排成一排，第i堆石子有ai
ai
个石子。
每次，你可以选择任意相邻的两堆石子进行合并，合并后的石子数量为两堆石子的和，消耗的体力等价于两堆石子中石子数少的那个。
请问，将所有的石子合并成一堆，你所消耗的体力最小是多少？
输入描述:
第一行是一个整数T(1≤T≤20)
T(1≤T≤20)
，表示样例的个数。
每个样例的第一行是一个整数n(1≤n≤10000)
n(1≤n≤10000)
,表示石子堆的数量。
第二行是n个整数ai(1≤ai≤109)
ai(1≤ai≤109)
输出描述:
每行输出一个样例的结果。
输入：
2
2
1 2
1
1
输出
1
0
题解：
全部相加减去最大值
Code：
#include<stdio.h>
int main()
{
long long count,k,max;
int n,number;
scanf("%d",&n);
while(n--)
{
max=-1;
count=0;
scanf("%d",&number);
while(number--)
{
scanf("%lld",&k);
if(k>max)
max=k;
count=count+k;
}
printf("%lld\n",count-max);
}
return 0;
}
E-Watermelon
题目描述
在ACM队暑假集训的某一天，实验室里有 n
n
个人。因为天气很热，大家都很想吃西瓜。
于是Eric买了 m
m
个西瓜拿到了实验室。
Eric把这 n
n
个人分别编号为 1,2,3…n
1,2,3…n
,他希望这 n
n
个人循环轮流来吃西瓜。
也就是说从 1
1
号开始，然后 2
2
号， 3
3
号… n
n
号依次吃西瓜， n
n
号吃完后又轮到 1
1
号来吃，直到这 m
m
个西瓜被吃完。
而这 n
n
个人每个人有一个肚量值，第i个人的肚量值为 ai
ai
。
lililalala是这 n
n
个人肚量值最大的人，不仅如此，他还非常贪吃，每次轮到他吃西瓜时，都会直接吃掉等同于他的度量值数量的西瓜。如果剩余的西瓜已经不够吃了，那么他会把所有西瓜直接吃完。(是的他很能吃)
除了lililalala以外的其他人,对于第 i
i
号每次吃西瓜可以选择吃掉 [1,ai]
[1,ai]
中任意整数数量个西瓜。当然，不能超过当前剩余的西瓜数量。
为了使吃西瓜更有意思一些，Eric规定如果在轮到某个人吃西瓜时没有西瓜了，那么由他来打扫一次实验室。(是的大家都很能吃)
其他人都觉得lililalala吃的太多了应该由他来打扫卫生。请问在其他人串通好的情况下能否合理安排每个人的行动使得吃完西瓜后由lililalala来打扫卫生?
输入描述:
第一行一个数字T(1≤T≤50)
T(1≤T≤50)
–样例个数。
每个样例包含两行。
第一行两个数字n,m(1≤n≤105,0≤m≤106)
n,m(1≤n≤105,0≤m≤106)
。
第二行 n
n
个数字a1,a2…an(1≤ai≤107)
a1,a2…an(1≤ai≤107)
，以空格分隔。
保证所有样例中肚量最大的人只有一个。这个人是lililalala。
保证所有样例中 ∑n
∑n
不超过 3×106
3×106
。
保证所有样例中 ∑m
∑m
不超过 107
107
。
输出描述:
每个样例输出一行，输出”YES”如果合理安排可以使得最后由lililalala来打扫卫生，否则输出“NO”。
输入：
2
4 3
1 2 3 2
5 8
1 2 3 2 1
输出YES NO
说明
第一个样例中lililalala是3号:
一种可行的方案:
1号吃掉1个西瓜
2号吃掉2个西瓜
第一次到3号吃西瓜时就没有西瓜可以吃了，所以3号需要打扫卫生。
第二个样例无论怎样安排各个人在每一次吃西瓜的数量，也不能达成目标。
题解：
区间【L，R】的一个问题，
当i为吃的最多的那个人时，若L<=0，则说明他以及没有西瓜了，他需要扫地输出YES，否则L-a[i],R-a[i].
当i不是吃最多的那个人时，因为他可以吃[1,a[i]]个西瓜，因此只要 r>0就还有西瓜可以吃，若 r<=0,则输出NO,否则 L-=a[i]，R-=1。
原理就是在R<=0之前L如果L<=0了那么他就可以轮到吃西瓜最多的那个人扫地。
Code：
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int T,n,m;
int a[100005];
scanf("%d",&T);
while(T--)
{
int p=0;
scanf("%d %d",&n,&m);
for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
if(a[p]<a[i])
p=i;
}
if(n==1)
{
printf("YES\n");
continue;
}
int L=m,R=m;
int k=0;
while(1)
{
if(k==p)
{
if(L<=0)
{
printf("YES\n");
break;
}
L-=a[k];
R-=a[k];
}
else
{
if(R<=0)
{
printf("NO\n");
break;
}
L-=a[k];
R-=1;
}
k=(k+1)%n;
}
}
return 0;
}
F-Black & White
题目描述
你有一个长度为 n 的 01 串S，你可以执行最多 m 次操作。
对于每次操作，你可以选择一个位置 i 满足 1≤i≤n
1≤i≤n
，翻转这一位的值，0变成1，1变成0。
定义一个 01 串的价值为其中最长连续0的个数和最长连续1的个数的较大值，求S在经过最多m次操作后的最大价值。
输入描述:
- 第一行一个整数 T ，表示接下来有 T 个样例。
- 首先输入n,m，表示S串的长度n和操作次数m，其中1≤n≤100000
1≤n≤100000
，0≤m≤1000
0≤m≤1000
； - 接下来输入一个长度为n的字符串S。
输出描述:
一个整数，表示题面上描述的最大价值。
输入2 5 1 00101 2 1 01
输出
4
2
说明
第一个串翻转第三个位置，00001的价值为4；第二个串翻转第一个位置，11的价值为2。
题解：第一次循环得到1的最大串，第二次循环得到0的最大串，i-j+1巧妙的计算出了连续的0或1的连续个数。
Code：
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int T,n,m;
char x[100005];
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&m);
getchar();
gets(x);
int cnt0=0,cnt1=0;
int j=0,ans=0;
for(int i=0; i<n; i++)
{
if(x[i]=='1')
{
cnt1++;
if(cnt1>m)
{
while(x[j++]!='1');
ans=max(ans,i-j+1);
}
}
ans=max(ans,i-j+1);
}
j=0;
for(int i=0; i<n; i++)
{
if(x[i]=='0')
{
cnt0++;
if(cnt0>m)
{
while(x[j++]!='0');
ans=max(ans,i-j+1);
}
}
ans=max(ans,i-j+1);
}
printf("%d\n",ans);
}
return 0;
}