一、题目报告
比赛中第一题AC,第二题0分（时间超限），第三题AC,第四题0分，比赛后全部AC。
二、赛中概况
首先做得第一题，第一题特别简单，用了3分钟左右；
然后是第二题，
三、题目正解
T1 挑选苹果(apple)
时间限制：1秒 内存限制：128M
题目描述
小可手里有n个苹果，大小为a1,a2,⋯,an。小可希望留给爸爸妈妈最大的k个苹果，剩下的自己吃掉。
请问，小可自己吃掉的苹果的大小总和是多少？
输入描述
第一行两个正整数n,k，代表苹果个数和希望留给爸爸妈妈的苹果个数。
第二行nn个正整数a1,a2,⋯,an，代表苹果的大小。
第三行一个正整数k，代表小可希望留给爸爸妈妈的苹果个数。
输出描述
输出一个正整数，代表小可自己吃掉的苹果的大小总和。
样例输入
5 31 2 3 4 5
样例输出
3
数据范围
对于30%的数据，1≤k<n≤100,1≤ai≤100
对于60%的数据，1≤k<n≤10^5,1≤ai≤1000
对于100%的数据，1≤k<n≤10^9,1≤ai≤10^9
思路解析
无其他知识点，排序即可。
正解代码
#include<iostream>
#include<algorithm>
using namespace std;
long long n,k,sum;
int main(){
cin>>n>>k;
long long a[n+1];
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
sort(a+1,a+n+1);
for(int i=1;i<=n-k;i++){
sum+=a[i];
}
printf("%lld",sum);
return 0;
}T2 谁是胜者(winner)
时间限制：1秒 内存限制：128M
题目描述
现在有n个人进行决战！他们每个人都有一个战斗力，他们排成一排，战斗力分别为a1,a2,⋯,an。
保证n一定是2的幂。每轮战斗，都会把所有人分成人数相同的两部分，然后进行战斗。也就是说，假设现在有x人，左侧x/2个人是左侧团队，右侧x/2个人是右侧团队。然后这两个团队进行决斗，
决斗的规则是：一个团队的战斗力是这个团队所有人的战斗力的总和。如果两个团队的战斗力相同，那么如果是第奇数轮战斗，那么左侧的团队胜利。如果是第偶数轮战斗，那么右侧的团队胜利。否则战斗力大的团队获胜，战斗力小的团队会失败。失败的团队的所有人都会退场。如果最后只剩一个人，那么这个人就是冠军。
请你得出最后胜利的人的战斗力。
输入描述
第一行一个整数n，表示有n个人。保证n一定是2的幂。
第二行n个整数a1,a2,⋯,an，表示每个人的战斗力。
输出描述
输出一个整数，表示最后胜利的人的战斗力。
样例输入1
47 1 5 4
样例输出1
5
样例输入2
43 2 1 4
样例输出2
3
数据范围
对于40%的数据，1≤n≤1000。
对于100%的数据，1≤n≤10^5，1≤ai≤10^9。
思路分析
利用前缀和求和，配合双指针进行二分比较。
正解代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[100005];
ll sum[100005];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {//输入的同时求出前n项前缀和
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int L=1,R=n,cnt=0;
while(L<R) {//二分
cnt++;//统计轮数，题目相等时判断的要求
int mid=(L+R)/2;//取中点，因为n是2的幂，所以肯定能等分
ll left=sum[mid]-sum[L-1],right=sum[R]-sum[mid];//左边的区域L~mid 右边的区域mid+1~R
if(left<right) L=mid+1;//右边获胜，则继续看右边的情况
else if(left>right) R=mid;//左边获胜，则继续看左边的情况
else {//相等
if(cnt%2==0) L=mid+1;//偶数轮右边获胜
else R=mid;//奇数轮左边获胜
}
}
printf("%d",a[R]);//输出最后获胜的人的编号
return 0;
}
T3 合并序列(merge)
时间限制：1秒 内存限制：128M
题目描述
小可有一个长度为n的序列a1,a2,⋯,an，序列的所有元素的值要么是0，要么是1。
规定，一个区间内的众数是区间内出现次数最多的元素。如果0和1的出现次数相同，那么众数是0。
现在我们有一种操作：选择一个区间[l,r]，将区间内的所有数字全部删除，然后在这个区间原本所在位置插入这个区间的众数。例如，对于序列[0,1,1,0,1,1,0]，选择区间[2,5]进行操作，那么这个序列会变成[0,1,1,0]。
请问，经过若干轮操作后，序列有没有可能只剩一个数字11？
输入描述
第一行一个正整数T，表示测试数据组数。
接下来T组测试数据，每组测试数据第一行一个正整数n，表示序列的长度。
接下来一行nn个整数，第ii个整数表示ai(0≤ai≤1)。这n个数字之间没有空格。
输出描述
对于每组测试数据，输出一行一个字符串，如果可能只剩一个数字1，输出Yes，否则输出No。
样例输入
5101120191000000019000011000
样例输出
NoYesNoYesNo
数据范围
有20%的数据，T=1,1≤n≤10.
对于100%的数据，1≤T≤4×10^4,1≤n≤2×105^5，对于同一组数据的T组n的总和不超过2×10^5.
思路解析
尽可能为1，如果用比0多的1和比1少的0换成1，那么没有好处 （1），如样例：
000011000
如果用2个1换1个0，那么是没有作用的
因为一串数字0少化0，所以可以先去掉连续的，多余的0
000011000 变成
0110
这时可以发现无论如何都无法变成1，因为1不比0多，又因为（1）得出的结论，所以本题可以化简为：给定字符串，将一串连续的0简化为1个0，最后比较1是否比0多。
正解代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int T,n;
char s[N];
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d%s",&n,s+1);//下标从1开始存储，否则需要考虑越界情况
int cnt0=0,cnt1=0;
for(int i=1; i<=n; i++) {
if(s[i]=='1') cnt1++;
//把连续的0只认为是一个0，因为要尽可能的减少0的出现次数
//连续的0可以通过操作变为一个0，判断是否是一个开端
if(s[i]=='0'&&s[i-1]!='0') cnt0++;
}
if(cnt1>cnt0) printf("Yes\n");//总1的数量多，则可以整体变为众数1
else printf("No\n");//否则则不可以
}
return 0;
}T4 邪恶大马猴
时间限制：1秒 内存限制：128M
题目描述
小可最近总是睡不着觉。在经历了若干天长时间的学习之后，小可终于感受到困意，打算睡一个好觉。
但是有一只邪恶的大马猴不想小可睡觉！
小可现在的睡意值是m，大马猴设置了n个闹钟即将响起。第ii个闹钟的吵闹值是ai。吵闹值会影响小可的睡眠，如果小可的睡意值减少到0或者负数，那么小可就会醒过来。
现在，你可以帮助小可，在闹钟响起之前关闭一些闹钟。你可以选择一个区间[L,R]，关掉这个区间内的所有的闹钟。这样，区间[1,L−1]和[R+1,n]的闹钟依旧会响起，但是这两个区间之间就有了一个空白时间，这两个区间并不连续。
对于一个连续的区间[L,R]，如果这个区间的闹钟全部响起，第一个闹钟会让小可的睡意值减少aL，第二个闹钟会让小可的睡意值减少2×aL+1，第三个闹钟会让小可的睡意值减少3×aL+2，以此类推。这样，小可的睡意值减少的总量就是1×aL+2×aL+1+3×aL+2+⋯+(R−L+1)×aR。
现在，请你选择一个最短的区间[L,R]，关掉其中的闹钟，并且能让小可不被吵醒。请输出这个区间的长度。区间长度最小是1。
输入描述
第一行两个正整数。n,m
第二行n个正整数a1,a2,⋯,an
输出描述
输出一个正整数，表示最短的区间长度。这个结果最小是1，即使不关闹钟小可也能不被吵醒。
样例输入
4 101 2 3 4
样例输出
1
提示
样例中，关掉3这个闹钟，总的吵闹值为1+2×2+4=9
对于20%的数据，1≤n≤100
对于另外40%的数据，1≤n≤5000
对于100%的数据，1≤n≤10^5,1≤m≤10^9,1≤ai≤10^9
思路解析
本题的题目描述中提到连续的问题，如果直接循环肯定会超限，先来分析一下求和公式：
-------------------------------------------------------------------------------
0 L R n
假设要求一段区间的吵闹值，起点为L,终点为R.
设i为L到R间的所有下标
" 这样，小可的睡意值减少的总量就是1×aL+2×aL+1+3×aL+2+⋯+(R−L+1)×aR。" 根据题目要求，如果一段区间连续，则每个数为(i−L+1)×a[i],一直到（(R−L+1)×aR），然后求和。
把式子进行拆分，就等于：
i*a[i]的和-L*a[i]的和+1*a[i]
进行合并，原式=i*a[i]的和-（L-1)*a[i]的和
推到这里，公式就出来了，因为i代表L-R的所有下标，又提到不同数组值的和，所以用前缀和来解决。
可以定义两个前缀和数组，分别对应i*a[i]的前缀和与a[i]的前缀和。
然后二分最小化答案，因为求最短区间。
正解代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m,a[N];
ll sum1[N],sum2[N];
ll getsum(int L,int R) {//求一个区间的吵闹值，套公式
if(L>R) return 0;
return (sum2[R]-sum2[L-1])-(L-1ll)*(sum1[R]-sum1[L-1]);
//1ll等价于把1转换成Long long类型防止数据溢出
}
bool check(int x) {
for(int i=1;i+x-1<=n;i++){//关闭的是i~j长度为x的区域
int j=i+x-1;
if(getsum(1,i-1)+getsum(j+1,n)<m){
return true;
}
}
return false;
}
int main() {
scanf("%d%d",&n,&m);
for(ll i=1; i<=n; i++) {
//对于区间L~R上的闹钟造成的总吵闹值
//1*a[L]+2*a[L+1]+....(R-L+1)*a[R]
//公式：i-(L~R) (i-L+1)*a[i]求和
// i-(L~R)-> i*a[i]-(L-1)*a[i]
scanf("%d",&a[i]);
sum1[i]=sum1[i-1]+a[i];//普通的前缀和
sum2[i]=sum2[i-1]+i*a[i];//i*a[i]的前缀和
}
int L=1,R=n;//二分答案 满足条件的最小值，最小化答案
while(L<R) {
int mid=L+R>>1;
if(check(mid)) R=mid;//如果mid这个区间长度可以，则尝试更短
else L=mid+1;//否则加大长度
}
printf("%d",R);//输出答案
return 0;
}
总结
可以发现，几套模拟题频繁出现前缀和，说明非常重要！！！二分答案也要掌握，可以降低不必要的循环。
标签：小可,报告,int,样例,long,补题,闹钟,区间,模拟 From： https://blog.csdn.net/rxyxxxxxxx/article/details/142961840