Codeforces Round 973 (Div. 2) 题解

A. Zhan's Blender

搅拌机一秒最多能搅拌 \(min(x,c)\) 个水果，因此搅拌的总时间为 \(\lceil\frac{n}{min(x,c)}\rceil\)

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, x, y;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n >> x >> y;
        
        int t = min(x, y);
        cout << (n + t - 1) / t << endl;
    }

    return 0;
}

B. Battle for Survive

由于只能由高位战士淘汰低位战士，因此最后剩下的战士一定是第 \(n\) 个战士

为了使第 \(n\) 个战士保留评级最大，就要使 \([1,n-1]\) 中最后剩下的战士评级最小

\([1,n-1]\) 中剩下的战士一定是第 \(n - 1\) 个战士，为了使他保留的评级最小，可以用他来淘汰除 \(n\) 以外的所有战士

最终答案为 \(a[n]-(a[n-1]-\sum_{i}^{n-2}a[i])\)

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int res = a[n - 1] - a[n - 2];
        for (int i = 0; i < n - 2; i++) res += a[i];
        
        cout << res << endl;
    }

    return 0;
}

C. Password Cracking

交互题

每次询问在已知子串右边再拼接 \(0\) 或者 \(1\)，如果获得的回答都是 \(0\)，代表目前的字串是密码串的后缀，之后的每次询问在子串左边拼接即可

code:

#include <bits/stdc++.h>

#define int long long
#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        
        string s;
        
        bool flag = false;
        while (1)
        {
            if (flag)
            {
                string t = '1' + s;
                cout << "? " << t << endl;
                int x;
                cin >> x;
                if (x) s = '1' + s;
                else s = '0' + s;
            }
            else
            {
                string t = s + '1';
                cout << "? " << t << endl;
                int x;
                cin >> x;
                if (x) s += '1';
                else
                {
                    t = s + '0';
                    cout << "? " << t << endl;
                    cin >> x;
                    if (x) s += '0';
                    else flag = true;
                }
            }
            if (s.size() == n)
            {
                cout << "! " << s << endl;
                break;
            } 
        }
    }

    return 0;
}

D. Minimize the Difference

首先二分找到该序列能操作出的最大最小值 \(minv\)

接着把序列中的每个元素都处理成大于等于 \(minv\)，为了之后的可操作性更强

对于大于 \(minv\) 的部分，应尽量留在下标小的地方

最后对新序列进行二分，找到新序列最小的最大值

code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200010;

int T;
int n;
ll a[N];

bool check1(ll x)
{
    ll cnt = a[0];
    for (int i = 0; i < n; i++)
    {
        if (cnt < x) return false;
        cnt += a[i + 1] - x;
    }
    return true;
}

bool check2(ll x)
{
    ll cnt = a[0];
    for (int i = 0; i < n; i++)
    {
        if (cnt > x)
        {
            if (i == n - 1) return false;
            else cnt += a[i + 1] - x;
        }
        else cnt = a[i + 1];
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> T;
    while (T--)
    {
        cin >> n;
        for (ll i = 0; i < n; i++) cin >> a[i];
        
        ll l = 0, r = 1e12;
        while (l < r)
        {
            ll mid = l + r + 1 >> 1;
            if (!check1(mid)) r = mid - 1;
            else l = mid;
        }
        
        for (int i = n - 1; i >= 0; i--)
        {
            if (a[i] < l) a[i - 1] -= l - a[i], a[i] = 0;
            else a[i] -= l;
        }
        
        l = 0, r = 1e12;
        while (l < r)
        {
            ll mid = l + r >> 1;
            if (!check2(mid)) l = mid + 1;
            else r = mid;
        }
        
        cout << l << '\n';
    }

    return 0;
}

E. Prefix GCD

由于 \(gcd\) 每次缩小至少会除以 \(2\)，因此，从开始缩减到最小 \(gcd\) 只需要 \(log\) 次

显然，\(a[0]\) 一定要取数组最小值，接下来每一次取值，都要找剩下元素中能使当前 \(gcd\) 最小的，直到 \(gcd\) 缩小为最小 \(gcd\)，跳出循环

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long ll;

const int N = 200010;

int T;
int n;
int a[N];

int gcd(int a, int b)
{
    return b? gcd(b, a % b) : a;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        sort(a, a + n);
        
        int g = 0;
        map<int, int> p;
        for (int i = 0; i < n; i++) 
        {
            g = gcd(g, a[i]);
            if (i) p[i]++;
        }
        
        ll res = a[0], cnt = a[0];
        while (cnt > g)
        {
            int d = cnt, id = 0;
            for (auto it: p)
            {
                int t = gcd(d, a[it.x]);
                if (cnt > t) cnt = t, id = it.x;  
            }
            res += cnt;
            p.erase(id);
        }
        for (auto it: p) res += cnt;
        
        cout << res << endl;
    }

    return 0;
}