Codeforces Round 781 div.2 CDE

C. Tree Infection

题意：给定一棵树，一开始所有节点都是未传染的状态，接下来每一秒，可以手动传染一个新节点，同时已经被传染的节点会传染它的一个兄弟节点。问最短多少秒能够传染所有节点。

首先容易发现，这个树并没有什么用，我们可以把连同一个父节点的点分成一组，组与组之间是无关的。

看起来是个简单题了，\(n\) 秒内一定能传染完，那么模拟即可。然而这个模拟还是有点恶心的，不要想 \(O(n)\) 解法了，搞个优先队列暴力搞，每次选取剩余最大的一组感染就行了。

int n, m;
int du[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) du[i] = 0;
    for(int i=2;i<=n;i++){
        int x;
        cin >> x;
        du[x]++;
    }
    du[0] = 1;
    sort(du, du+n+1, greater<int>() );
    int k = 0;
    for(int i=0;i<=n;i++){
        if(!du[i]) break;
        k++;
    }
    priority_queue<int> q;
    for(int i=0;i<=n;i++){
        if(!du[i]) break;
        int r = du[i] - (k - i);
        if(r > 0) q.push(r);
    }
    int ad = 0;
    while(!q.empty()){
        int p = q.top();
        q.pop();
        if(p <= ad) break;
        p--;
        ad++;
        q.push(p);
    }
    cout << k + ad << '\n';
}

D. GCD Guess

题意：交互题，需要去猜一个数字 \(x\)，每次交互可以输入两个不同的正整数 \(a,b\)，会得到 \(gcd(x+a,x+b)\) 的结果，需要在30次内猜出。

30次这个数字告诉我们，不是二分就是二进制...

解：按位考虑，假设我们已经知道 \(x\) 的前 \(i\) 位的值了（假设为 \(pre_i\)），现在猜第 \(i+1\) 位的情况，我们可以先让前面 \(i\) 位全部清零（在加 \(a,b\) 时处理掉前面的影响），然后取 \(a,b\) 分别为 \(2^{i}\) 和 \(2^i+2^{i+1}\)，这样如果 \(x\) 第 \(i\) 位为1，得到的结果即为 \(2^{i+1}\)

举例：

.....?0000
+    10000
+   110000
如果?为1，则gcd结果必为：
	100000
否则结果必为：
	 10000

构造方法应该不止这一种。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1000003;

int query(int x, int y){
    cout << "? " << x << ' ' << y << endl;
    cout.flush();
    int r; cin >> r;
	//int r = __gcd(1000000000+x, 1000000000+y);
    //交互题可以这样测试
    return r;
}

void solve(){
    int x = 0, xf = 0;
    for(int i=1;i<=30;i++){
        int s = query(xf + 1, xf + 1 + (1<<i));
        if(s == (1<<i)){
            x |= (1 << (i-1));
        }else{
            xf |= (1 << (i-1));
        }
    }
    cout << "! " << x << '\n';
}

E. MinimizOR

题意：给出一个数列，若干次询问，每次询问 \([l,r]\) 之间，两两或结果的最小值是多少。

结论：对于任意一个区间来说，只需要考虑最小的31个数两两或的结果即可（数字小于 \(2^{30}\)）。

思路：要算一个区间的两两或最小值，肯定是从高位到低位贪心地去考虑，高位能取0就取0，一定最优。

考虑当前最高位上1和0的个数：

• 全是1：这个高位对后续抉择没有影响，这一位必定是1
• 至少2个0：之后必定在这些高位为0的数字中选择，也就是选取较小的那一部分
• 有一个0：这个高位必定是1，继续考虑下一位。但需注意：下次遇到情况二时，高位为0的部分就不一定是最小值了，假设已经出现了 \(k\) 次情况3，那么可能出现 \(k\) 个比高位为0的还小的数。
• 显然，这个 \(k\) 至多为30，那么其实最终或最小的两个值一定出在前31小值内。

写一写感受一下，可选范围是不断缩小的，每枚举一位，下边界最多会移动1，那么最终结果就在前31小内。

结论证明完了，处理这个就很暴力了：线段树维护区间前31小值，每次询问的时候计算31*31种结果，复杂度两个log，能过。

int n, a[maxn];
struct SegTree{
    vector<int> mi[maxn << 2];
    void merge(vector<int> &res, vector<int> x, vector<int> y){
        res.clear();
        int l = 0, r = 0;
        while(l < x.size() && r < y.size() && res.size() < 31){
            if(x[l] < y[r]) res.push_back(x[l++]);
            else res.push_back(y[r++]);
        }
        while(l < x.size() && res.size() < 31) res.push_back(x[l++]);
        while(r < y.size() && res.size() < 31) res.push_back(y[r++]);
    }
    void build(int p, int l, int r){
        if(l == r){
            mi[p].clear();
            mi[p].push_back(a[l]);
            return;
        }
        int mid = (l + r) / 2;
        build(p*2, l, mid);
        build(p*2+1, mid+1, r);
        merge(mi[p], mi[p*2], mi[p*2+1]);
    }
    vector<int> query(int p, int l, int r, int L, int R){
        if(l > R || L > r) return {};
        if(L <= l && r <= R) return mi[p];
        int mid = (l + r) / 2;
        vector<int> res;
        merge(res, query(p*2, l, mid, L, R), query(p*2+1, mid+1, r, L, R));
        return res;
    }
}st;

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    st.build(1, 1, n);
    int Q;
    cin >> Q;
    while(Q--){
        int l, r;
        cin >> l >> r;
        auto res = st.query(1, 1, n, l, r);
        int ans = 2e9;
        for(int i=0;i<res.size();i++){
            for(int j=i+1;j<res.size();j++){
                ans = min(ans, res[i] | res[j]);
            }
        }
        cout << ans << '\n';
    }
}

解法二：

更加直观一些，建立可持久化字典树，复杂度同样也是两个log

查询的时候，也是根据左右儿子的数量：如果0有多个，无脑走0；如果0恰好有1个，那么就走1，同时把这个0号节点记录下来。至多记录31个，最后把这31个节点重新拿过来暴力一下即可。