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题传送门

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题传送门

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;
}