Codeforces Round 893（div2）
[A题传送门](Problem - A - Codeforces)
A题意：
我们有a+b+c个瓶盖，选手1可以拿指定的a个或者c个里面的一个，选手2可以拿指定的b个或者c个里面的一个，可以拿完最后一个的即为获胜者，每个人都有最优策略。
A思路：
这个题一开始想错了，主要是没有读懂题意，理解清楚题意后也就简单了，最好的方法就是选手1和2都先拿c里面的，因为其他的全是他们各自专属的，只有c是公共的，所以我们只需要将c分出去即可，最后统计一下每个人拿到的个数，拿的多的就是获胜者，如果相同，因为选手1是先手，那么选手2获胜。
A代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
ll a,b,c;
cin>>a>>b>>c;
ll a1=c/2+(c%2);
ll b1=c/2;
a+=a1;
b+=b1;
if(a>b){
cout<<"First"<<endl;
}
else{
cout<<"Second"<<endl;
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
B题意：
有n个站牌，有m个饼干贩卖员，他们停在不同的站牌上，当一个人（本身有无限多饼干）通过一个站牌时，如果满足下，面一种情况，就会吃掉一块饼干，而你要做的就是移走一个贩卖员，使得这个人吃的饼干数目尽可能小，输出最小饼干数目以及可移动的贩卖员数目
1.遇到贩卖员他会立刻买一个饼干并吃掉
2.如果他还没吃饼干，他会拿出一块饼干并吃掉
3.距离吃上次饼干已经过去d分钟了，他会再次吃一块饼干
B思路：
我们可以先求一遍答案，再枚举要移除的贩卖员，退还他所做出的贡献，再加上没有他产生的贡献即可。
B代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
void solve(){
int n,m,d;
cin>>n>>m>>d;
std::vector<int> v(m+2);
for(int i=1;i<=m;i++){
cin>>v[i];
}
v[0]=1;
v[m+1]=n+1;
int cnt=1;//一开始要吃一个，cnt是我们一开始不移除要吃的
for(int i=1;i<=m+1;i++){
cnt+=(v[i]-v[i-1]-1)/d;
if(v[i]!=1&&v[i]!=n+1){
cnt++;
}
}
int ans=INF;
int num=0;
for(int i=1;i<=m;i++){
int t=cnt;
t-=(v[i]-v[i-1]-1)/d+(v[i+1]-v[i]-1)/d;
//这是第i个贩卖员被移除所移除的影响
if(v[i]!=1){
t-=1;
}
t+=(v[i+1]-v[i-1]-1)/d;//这是移除后所产生的影响
if(ans>t){
ans=t;
num=1;
}
else if(ans>=t){
num++;
}
}
cout<<ans<<" "<<num<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
C题意：
有一个名为GCD permutations的游戏，玩家有以下操作：
首先，选择一个长度为n的序列，大小为1-n
然后对于每一个从1到n的数字计算di=gcd(ai,a(i%n+1))
最后的得分就是ans=d1+...+dn
而我们要做的就是找到一个排列，使得得分最大
C思路：
看了网上大佬的思路，这个就是贪心的想法，贪心着想着i的后面放2i，4 * i，8i...
大概是明白了，如果我们要求的得分是两个数的最大公约数，那么事实上最大公约数的最优（最大）情况一定是两个数中比较小的那个。
C代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
void solve(){
int n;cin>>n;
vector<int> vis(n + 1);
for(int i = 2;i <= n; ++i){
if(vis[i])continue;
for(int j = i;j <= n;j = 2 * j){
cout<<j<<' ';
vis[j] = 1;
}
}
cout<<1<<'\n';
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}