策划部第一届水题赛题解
Keller出的水题赛QAQ
T1. Keller的欧皇之路!
Keller是一个抽卡游戏的爱好者，但是众所周知，抽卡游戏需要运气的加持，而Keller老非酋了，总是抽出一些低星卡。这天，忍无可忍的Keller的想知道自己有没有可能成为欧皇。
Keller首先注册了一个新的账号，初始的运气值为零。已知每天都会不同事物中获取运气值。得到这些运气值之后，Keller 可以去抽卡。但是如果Keller积攒的运气值太低，那么他就会抽到低星卡，把积攒起来的运气值消耗掉。如果运气值足够，那么他就会抽到六星卡，当然这些运气值就消耗掉了。一天之后，积攒下来的运气值会因为睡了一觉而少了一半（当然大魔王会把小数部分悄悄取走），留到第二天。因为Keller还是比较理智的，所以每天最多抽一次卡。
给出每天获取的运气值，求出最后Keller最多能获得多少张六星卡，剩下多少运气值。
输入格式
输入的第一行为一个整数T,表示有T组数据。
对于每组数据，第一行为两个整数 n, m ，表示一共有 n 天，抽六星卡需要消耗 m 运气值。
第二行 n 个整数 a_i， 表示每天获得的运气值。
输出格式
对于每组数据，输出一行包含一个整数为能获得的六星卡数量。
样例输入
1
7 40
30 29 45 36 38 50 10
样例输出
4
19
数据范围及要求
0＜T≤10 , 0＜n≤1000000 , 0<=a_i<=2000
题解思路
模拟，每天如果幸运度够的话就抽卡，不够就不抽。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int main(){
int T;cin>>T;
while(T--){
cin>>n>>m;
int sum=0,ans=0;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum=(sum>>1)+x;
if(sum>=m){
sum-=m;
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
T2.Keller与丢手绢的神!
这天Keller在去上课的路上忽然遇到一个奇奇怪怪的人，那个人自称自己是丢手绢的神！QAQ
丢手绢的神告诉Keller，在桌面上有一排共N枚硬币，每一枚硬币均为正面朝上。现在要把所有的硬币翻转成反面朝上，规则是每次可翻转任意 N-1 枚硬币（正面向上的被翻转为反面向上，反之亦然）。如果Keller可以告诉他最少需要的翻转次数，那么这些硬币就都可以送给Keller！
Keller十分心动，但还是上课要紧，所以Keller希望你能帮助他解决这个问题，当然大方的Keller会从得到的硬币中拿出一枚分给你！
输入格式
输入的第一行为一个整数T,表示有T组数据。
对于每组数据，第一行为一个偶数N,表示有N个硬币。
输出格式
对于每组数据，输出一行包含一个整数为能获得的六星卡数量。
样例输入
2
1
2
样例输出
1
2
数据范围及要求
0＜T≤10 , 1≤N≤10^9
题解思路
第1次除了第1个都翻过来，
第2次除了第2个都翻过来，
...
第n次除了第n个都翻过来。
这时所有的硬币都翻了n-1次，因为开始时所有硬币都朝下，所以此时所有硬币都朝上了。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int T;cin>>T;
while(T--){
int n;
cin>>n;
cout<<n<<endl;
}
return 0;
}
T3.Keller的RP提升计划！
这天成都难得出了太阳，Keller又决定去犀湖边转转，不过这次Keller看到了一群老人聚集在桥边。
Keller发现在桥的两边各有N个老人，他们都想要过桥，然后在桥的对岸休息一段时间后，再返回到桥原来的一边，但是由于老年人独自过桥时间很困难的事情，所以热心肠的Keller决定帮助这2*N个老人过桥。
现在已知最初Keller站在桥的一边，Keller自己或者Keller帮助老人过桥一次需要花费的时间为T，老人需要在桥的对岸休息的时间为X。但是Keller还想去邀请丢手绢的神一起爬山，所以Keller需要一个时间管理大师帮助他计算帮助完所有老人所需要的最短时间。
输入格式
输入的第一行为一个整数T表示有T组输入。
对于每组数据：输入一行=包含三个整数N、X、T 分别表示桥一侧老人的数量、休息时间、过桥时间。
输出格式
对于每组数据输出一行包含一个整数为所需的最短时间
样例输入
3
2 2 2
3 1 10
11 45 14
样例输出
16
120
616
提示
对于输入样例中的第一组数据，给出下面的示意图（x表示Keller的位置）
1 ≤ T≤ 10^4 1 ≤ N, X, T ≤ 10^9
题解思路
分类讨论。
代码
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int T;cin>>T;
while(T--){
long long n,x,t;
scanf("%lld%lld%lld",&n,&x,&t);
if((x+t)<=(2*n*t-t)){
cout<<4*t*n<<endl;
}
else if((x+t)>2*n*t-t &&(x+t)<=2*n*t){
cout<<x+t+t+2*n*t<<endl;
}
else if((x+t)>2*n*t&&(x+t)<=2*n*t+t){
cout<<t+(4*n)*t<<endl;
}
else if((x+t)>2*n*t+t){
cout<<(x+t)+2*n*t<<endl;
}
}
return 0;
}
T4.Keller带你爬山
Keller今天带大家去爬山，山顶有许多岩石排成一排，于是Keller决定举办一场跳石头大赛，他选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,策划部的小伙伴们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,Keller计划移走一些岩石,使得大家在比赛过程中的最短跳跃距离尽可能长。由于体力限制,Keller至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。
输入格式
输入的第一行表示包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及Keller至多移走的岩石数。
接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出格式
输出一行只包含一个整数,即最短跳跃距离的最大值。
样例输入
25 5 2
2
11
14
17
21
样例输出
4
数据范围及要求
输入输出样例 1 说明：将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。
对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。
题解思路
二分答案。
对最短跳跃距离进行二分，然后把这个跳跃距离“认为”是最短的跳跃距离，然后去以这个距离为标准移石头。使用一个judge判断这个解是不是可行解。如果这个解是可行解，那么有可能会有比这更优的解，那么我们就去它的右边二分。为什么去右边？答案是，这个区间是递增的 ，而我们求的是最短跳跃距离的最大值，显然再右边的值肯定比左边大，那么我们就有可能找到比这更优的解，直到找不到，那么最后找到的解就有理由认为是区间内最优解。反过来，如果二分到的这个解是一个非法解，我们就不可能再去右边找了。因为性质，右边的解一定全都是非法解。那么我们就应该去左边找解。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
int d,n,m;
int a[maxn];
int l,r,mid,ans;
bool judge(int x){//judge函数，x代表当前二分出来的答案
int tot = 0;//tot代表计数器，记录以当前答案需要移走的实际石头数
int i = 0;//i代表下一块石头的编号
int now = 0;//now代表模拟跳石头的人当前在什么位置
while (i < n+1){//千万注意不是n，n不是终点，n+1才是
i++;
if (a[i] - a[now] < x)//判断距离，看二者之间的距离算差值就好
tot++;//判定成功，把这块石头拿走，继续考虑下一块石头
else
now = i;//判定失败，这块石头不用拿走，我们就跳过去，再考虑下一块
}
if (tot > m)
return false;
else
return true;
}
int main(){
cin>>d>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
a[n+1]=d;
l=1;//l和r分别代表二分的左边界和右边界
r=d;
while(l<=r){
mid=(l+r)/2;
if(judge(mid)){//带入judge函数判断当前解是不是可行解
ans=mid;
l=mid+1;//走到这里，看来是可行解，我们尝试看看是不是有更好的可行解
}
else
r=mid-1;//噫，你找了个非法解，赶紧回到左半边看看有没有可行解
}
cout << ans << endl;
return 0;
}