CF 893 (Div.2)

A. Buttons

签到题。两人会优先选择c中的按钮来，避免自己的按钮消耗同时减少对方可选择的按钮。所以c % 2 == 1等价于a的按钮数+1，c % 2 == 0时相当于c按钮不存在，比较a b 按钮的数量来得出答案即可。

#include<iostream>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 2e9;



void solve() {
    int a, b, c;
    cin >> a >> b >> c;
    if(c % 2 == 1){
        a++;
    }
    if(a > b){
        cout << "First" << endl;
    }
    else{
        cout << "Second" << endl;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

B. The Walkway

有n个位置，有m个小贩，m <= n。每个小贩都有一个位置(1 <= pos <= n)，任意两个小贩的位置不重合。Petya从1走到n，当满足以下条件时，他会在某个点吃饼干

• 如果这个点是一号点，他会吃一次饼干

• 否则，如果这个点上有小贩，他会吃一次饼干

• 否则，如果这个点和上个吃饼干的点之间的距离为d，他会吃一次饼干

现在给出n, m, d，2 <= d <= n <= 1e9, 2 <= m <= min(1e5, n)， 问如果可以并且必须移除一个小贩，那么Petya能吃到的最少的饼干数量是多少，并且有多少种移除小贩的方案。

首先会发现，任意两个小贩之间（把1号点，因为此时强制吃饼干，也视为一个小贩），那么从上一个小贩处（已经吃了饼干）到这个小贩处（此时需要吃饼干）吃掉饼干的数量为

 int cnt = (pos - pre) + 1;
 if((pos - pre) % d == 0){
     cnt--;
 }

我们可以记录下到每一个小贩时会再吃多少个饼干。

如果此时前面的小贩数量足够多（指到此时为止小贩的数量大于等于三），那么可以考虑移除前一个小贩会产生的变化：从上上个小贩处到此处新的消耗饼干的数量

 int dis = (vec[vec.size() - 1 - 1 - 1].first) - pos; //vec[i].fist -> 第i个小贩的位置， second -> 上述定义的饼干消耗
 int ncnt = (dis / d) + 1;
 if(dis % d == 0){
     cnt--;
 }

计算一下新的消耗比改变前的消耗少多少，对m个小贩不断更新即可。

最终退出循环时再相似的方法判断一下移除最后一个小贩的影响。

以及特判一下在第一个位置是否有小贩，以及此时饼干消耗的最大改变量是不是0即可。

#include<iostream>
#include<vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 2e9;



void solve() {
    int n, m, d;
    cin >> n >> m >> d;
    vector<pii> vec;
    int pre = 1;
    vec.push_back({1, 1});
    int maxminus = 0;
    int num = 0;
    vector<int> b;
    for(int i = 0; i < m; i++){
        int pos;
        cin >> pos;
        b.push_back(pos);
        if(pos == 1){
            continue;
        }
        int cnt = (pos - pre) / d + 1;
        if((pos - pre) % d == 0){
            cnt--;
        }
        //cout << "cnt: " << cnt << endl;
        vec.push_back({pos, cnt});
        int dis;
        if(vec.size() >= 3){
            dis = pos - vec[vec.size() - 1 - 1 - 1].first;
            int ncnt = dis / d + 1;
            if(dis % d == 0){
                ncnt--;
            }
            int change = ncnt - cnt - vec[vec.size() - 1 - 1].second;
            if(change == maxminus){
                num++;
            }
            else if(change < maxminus){
                maxminus = change;
                num = 1;
            }
        }
        //cout << "maxminus: " << maxminus << " num: " << num << endl;
        pre = pos;
    }
    if(vec.size() >= 2){
        int dis = n - vec[vec.size() - 1 - 1].first;
        int ncnt = dis / d;
        int change = ncnt - vec[vec.size() - 1].second - (n - vec[vec.size() - 1].first) / d;
        if(change == maxminus){
            num++;
        }
        else if(change < maxminus){
            maxminus = change;
            num = 1;
        }
    }

    if(b[0] == 1 && maxminus == 0){
        num++;
    }
    int sum = 0;
    for(int i = 0; i < vec.size(); i++){
        sum += vec[i].second;
    }
    int dis = n - vec[vec.size() - 1].first;
    int ncnt = dis / d;
    sum += ncnt;
    sum += maxminus;
    cout << sum << " " << num << endl;
    //cout << endl;

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C. Yet Another Permutation Problem

要求构造一个从1 到 n的permutation， 定义d_i = gcd(a_i， a_(i % mod + 1))， 要求构造的permutation中d_i的种类（不同的值）(distinct value)最多。

不难发现，对于一个数m，如果要使它和另一个比它小的数组合，求出最大公因数，那么这个数是 m / 2的时候(m % 2 == 0)，是它所能得到的最大公因数。由于数字从 1 到 n，所以对于m (m % 2 == 0)， 一定可以得到m / 2存在，而一个从1 到 n 的permutation，依题意所能得到的最多的d_i的数量，应该为n / 2，所以依照上述方法构造即可。

#include<iostream>
#include<vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 2e9;



void solve() {
    int n;
    cin >> n;
    vector<bool> vis(n + 1, 0);
    vector<int> ans;
    int ptr = n;
    int put = n;
    while(ptr > 0){
        if(!vis[put] && put % 2 == 0){
            while(!vis[put]){
                ans.push_back(put);
                vis[put] = true;
                put /= 2;
                if(put <= 0){
                    break;
                }
                if(put % 2 != 0){
                    if(!vis[put]){
                        ans.push_back(put);
                        vis[put] = true;
                    }
                    break;
                }
            }
        }
        else if(!vis[put]){
            ans.push_back(put);
            vis[put] = true;
        }
        else{
            while(vis[ptr]){
                ptr--;
            }
        }
        put = ptr;
    }

    for(auto e: ans){
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}