codeforces round973 div2

A zhan's blender

问题：

思路：

模拟

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    cout << (n + min(x, y) - 1) / min(x, y) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

B Battle for survive

问题：

思路：注意到最后只会剩下最后一个战士$n$, 并且该战士的对手是战士$n - 1$, 因此如果让最后一个战士的rating最大，让倒数第二个战士的rating最小即可 即

代码：
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    if(n == 2) {
        cout << a[2] - a[1] << "\n";
        return;
    }
    vector<ll> s(n + 1);
    for(int i = 1; i <= n - 1; i ++ ) {
        s[i] = s[i - 1] + a[i];
    }
    
    cout << a[n] - (a[n - 1] - s[n - 2]) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

C password cracking

问题：

思路：
我们可以想象这样一种情况，如果我们一直向一个串的末尾加0或1字符，并且得到的反馈都是不是子串，那么是否说明我们现在找到的子串就是原串的一个后缀。答案是一定的，如果不是后缀的话那么至少会有一种情况得到的反馈是子串，同样的，在我们找到后缀后，按照同样的方法向前添加字符，就可以确定最后的串，由于我们每次拓展一位最多进行两次询问，因此我们的询问总数不会超过

代码：
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int ask(string s) {
    cout << "? " << s << endl;
    int re;
    cin >> re;
    //cout << re << endl;
    return re;
}

void solve() {
    int n;
    cin >> n;
    string ans;
    string a = "0";
    string b = "1";
    bool ok = true;
    for(int i = 1; i <= n - 1; i ++ ) {
        //cout << ans + a<<"LOJPJP" << endl;
        if(ok) {
            if(ask(ans + a)) {
                ans += a;
            } else if(ask(ans + b)) {
                ans += b;
            } else {
                ok = false;
                i --;
            }
        } else {
            if(ask(a + ans)) {
                ans = a + ans;
            } else if(ask(b + ans)) {
                ans = b + ans;
            }
        }
    }
    
    if(ok) {
        if(ask(ans + a)) {
            ans += a;
            cout << "! " << ans << endl;
        } else if(ask(ans + b)) {
            ans += b;
            cout << "! " << ans << endl;
        } else {
            if(ask(a + ans)) {
                ans = a + ans;
                cout << "! " << ans << endl;
            } else {
                ans = b + ans;
                cout << "! " << ans << endl;
            }
        }
    } else {
        if(ask(a + ans)) {
            ans = a + ans;
            cout << "! " << ans << endl;
        } else {
            ans = b + ans;
            cout << "! " << ans << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

E prifix gcd

思路：

对于一个数组，从前往后对这个数组进行gcd操作有这样一个性质：
即gcd的值最多变化次

这里进行一个简单的证明，倘若一个数组中的数足够多那么每次进行gcd操作gcd的值都会变成 如果存在其他的值只会让这种衰减衰减的更快

有了这个性质之后我们就可以执行一个循环，每次循环找出当前最小的gcd值，当我们发现本次循环的gcd与上一次循环的gcd的值一致时就可以break掉，由上述性质可知该循环是log级别的

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n + 1);
    for(ll i = 1; i <= n; i ++ ) cin >> a[i];
    //让式子的值最小，如果存在质数或互质的数, 输出min(互质的数) + n - 1 
      
    
    sort(a.begin() + 1, a.end());
    ll now = a[1];
    ll g = a[1];
    ll cnt = n - 1;
    ll ans = g;
    //cout << g << " ";
    while(true) {
        for(ll i = 1; i <= n; i ++ ) {
            now = min(now, gcd(g, a[i]));
        }
        //cout << now << " ";
        if(now == g) break;
        g = now;
        ans += now;
        cnt --;
    }
    //cout << now << " " << cnt << " ";
    cout << ans + now * max(0ll, cnt) << "\n";
}

int main() {
    ll t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

原文地址：https://blog.csdn.net/2201_75845839/article/details/142529913

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！