Codeforces Round #781 _C

Problem - A - Codeforces

签到题，找gcd(a,b)=lcm(c,d)且a+b+c+d=n，那么直接上代码

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using i64 = long long;


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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cout << n - 3 << " 1 1 1\n";
    }

    return 0;
}

Problem - B - Codeforces

题目有两种 *** 作，要么两个数互换，要么复制一遍这个数列，那么想要所有数相同且 *** 作次数最少，一定得先找个数最多的，然后其他的数一定得变，所以答案加上其他数的数量，然后每次复制数列，最多的数的数量是*2的，然后就循环需要几次复制就好了

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using i64 = long long;


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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        i64 cnt = 1;
        i64 maxx = 1;
        int ans = 0;
        for (int i = 1; i < n; i++) {
            if (a[i] != a[i - 1]) {
                maxx = max(maxx, cnt);
                cnt = 1;
            }
            else {
                cnt++;
                
                maxx = max(maxx, cnt);
            }
        }
        if (maxx == n) {
            cout << "0\n";
        }
        else {
            i64 c = n - maxx;
            ans += n - maxx;
            // cout << ans << "****\n";
            while (1) {
                if (c <= 0) {
                    break;
                }
                c -= maxx;
                maxx <<= 1;
                ans++;
            }

            cout << ans << '\n';
        }
    }

    return 0;
}

Problem - C - Codeforces

首先是给定一棵树，然后除了第一秒不会发生相同子节点间的传染，其他时间都会发生子节点之间的传染，每一秒都可以选择一个节点进行注射，注射次数其实是很珍贵的，能尽可能多的传染就传染，那么就先找每个节点有多少子节点，然后从大到小进行排序，有序数组可以考虑二分时间，时间是个左闭右开的区间，cnt记录的是比mid时间多用了多长时间

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
using namespace std;
using i64 = long long;


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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector b(n);
        for (int i = 1; i < n; i++) {
            int x;
            cin >> x;
            x--;
            b[x]++;
        }
        vector a { 1 };
        for (int i = 0; i < n; i++) {
            if (b[i]) {
                a.push_back(b[i]);
            }
        }
        sort(a.begin(), a.end(), greater());
        int l = a.size(), r = n;
        while (l < r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < a.size(); i++) {
                cnt += max(0, a[i] - mid + i);
            }
            if (a.size() + cnt <= mid) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        cout << l << '\n';
    }

    return 0;
}

Problem - D - Codeforces

交互题，又是交互题，用提问gcd(x+a,x+b)的答案来猜x是多少，看了眼题解，竟然还能这么做，确实没想到，x范围1到1e9确实30次一定能够猜出来，如果用x%mod，当mod大于x的时候，x%mod一定就是x，然而现在要考虑的是如何搞出gcd的模，题解的代数我感觉直观不好看出来，结合将x转换成二进制，然后从低到高去判断那一位是0还是1可能更好理解一点

附官方题解：

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
using namespace std;
using i64 = long long;
int ask (int a, int b) {
    cout << "? " << a << " " << a + b << endl;
    int ans;
    cin >> ans;
    return ans;
}
void solve() {
    int r = 0;
    for (int i = 1; i <= 30; i++) {
        int ans = ask((1 << (i - 1)) - r, (1 << i));
        if (ans == (1 << i)) {
            r += (1 << (i - 1));
        }
    }
    cout << "! " << r << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

官方题解还有另一种解答，最多23次就能判断出来x是多少（有机会再研究吧，大概也就能会第一种了QAQ：

官方标程：

#include 
using namespace std;
 
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
 
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
#define lc 1338557220
 
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll x, rs[maxn], p;
vector pw = {23, 19, 17, 13, 11, 9, 7, 5, 4};
 
ll ask(ll a, ll b) {
    cout << "?" _ a _ b << nf;
    ll x; cin >> x; return x;
}
 
void clm(ll x) {
    cout << "!" _ x << nf;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    /* #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif */
 
    // kudos for automatic wa
 
    cin >> t;
    while (t--) {
        for (i = 1; i <= 23; i++) {
            k = ask(x + i, lc + i);
            for (j = 0; j < 9; j++) {
                if (k % pw[j] == 0) rs[j] = i % pw[j];
            }
        }
 
        k = 1; p = 1;
        for (j = 0; j < 9; j++) {
            // cout << "p =" _ p << nf;
            while (p % pw[j] != rs[j]) p += k;
            k *= pw[j];
        }
 
        clm(lc - p);
    }
 
    return 0;
}

Problem - E - Codeforces

E题原理懂了但没完全懂，这个题就是考虑从高位到低位，如果少于两个0，那么这一位一定是1，否则一定是0，如果有一个是0，是0的那个数也不能丢掉，后面还有用处

这个题能用的数据结构比较多，可以线段树，字典树，哈希等等，方法不唯一

AC代码：

#include 
using namespace std;
using i64 = long long;
#define N 100010
int n, Q, a[N];
void solve() {
    unordered_map> mp[30];
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        int x = 0;
        for (int j = 29; j >= 0; j--) {
            x |= a[i] & (1 << j);
            mp[j][x].push_back(i);
        }
    }
    cin >> Q;
    while (Q--) {
        int l, r;
        cin >> l >> r;
        int u = 0;
        vector tmp;
        for (int i = 29; i >= 0; i--) {
            int cnt = upper_bound(mp[i][u].begin(), mp[i][u].end(), r) - lower_bound(mp[i][u].begin(), mp[i][u].end(), l);
            int zz = cnt;
            for (auto z : tmp) {
                cnt += !(z >> i & 1);
            }
            if (cnt >= 2) {
                vector _tmp;
                for (auto z : tmp) {
                    if (!(z >> i & 1)) {
                        _tmp.push_back(z);
                    }
                }
                tmp = _tmp;
            }
            else {
                if (zz) {
                    int p = *lower_bound(mp[i][u].begin(), mp[i][u].end(), l);
                    tmp.push_back(a[p]);
                }
                u |= 1 << i;
            }
        }
        cout << u << '\n';
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

附上E题官方题解，目前水平还不能完全理解明白，数学归纳法useful

官方AC代码：

#include

using namespace std;

const int MAXK = 31;
const int INF = (1 << 30);

vector> t;

pair get(int v, int vl, int vr, int l, int r) {
    if (vl >= l && vr <= r) return t[v];
    if (r <= vl || l >= vr) return make_pair(INF, INF);
    int vm = (vl + vr) / 2;
    return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r));
}

void mod(int v, int vl, int vr, int id, int val) {
    if (vr - vl == 1) {
        t[v] = make_pair(val, id);
        return;
    }
    int vm = (vl + vr) / 2;
    if (id < vm) mod(2 * v + 1, vl, vm, id, val);
    else mod(2 * v + 2, vm, vr, id, val);
    t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}

void solve() {
    int n;
    cin >> n;
    vector a(n);
    for (auto &c : a) cin >> c;
    t.resize(4 * n);
    for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        vector> b;
        for (int i = 0; i < min(r - l, MAXK); i++) {
            auto now = get(0, 0, n, l, r);
            b.push_back(now);
            mod(0, 0, n, now.second, INF);
        }
        int ans = (1LL << 31) - 1;
        for (int i = 0; i < (int)b.size(); i++) {
            for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first);
        }
        for (auto &c : b) mod(0, 0, n, c.second, c.first);
        cout << ans << "\n";
    }
}

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

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/607868.html

Codeforces Round #781

发表评论

评论列表（0条）