Codeforces Round 772 div.2 A-F

A. Min Or Sum

题意：有一个数组 \(a\)，你可以进行任意次操作：取两个数 \(a_i,a_j\)，将这两个数分别改为 \(x,y\)，要求 \(a_i|a_j=x|y\) 问可能得到数组总和最小值。

我们显然可以把二进制中每一位上多余的部分全部删光，只留一个，答案即所有数或起来

ll n, m;
void solve(){
    cin >> n;
    ll ans = 0;
    for(int i=1;i<=n;i++){
        ll x; cin >> x;
        ans |= x;
    }
    cout << ans << '\n';
}

B. Avoid Local Maximums

题意：给一个数组 \(a\)，每次操作将任一个数修改为任意其他数，问至少操作几次，使得数组中不存在山峰（“山峰”即 \(a_i >a_{i-1}\) 且 \(a_i > a_{i+1}\) ）

我们可以把每个山峰都抹平，使之变成它两侧的较小值，但还有一种情况：两个山峰相邻（即下标相差2），那么可以把中间位置抬高到两山峰中的较大值，一次性消除两个山峰，模拟即可。

ll n, m;
int a[maxn];
 
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<int> f;
    for(int i=2;i<n;i++){
        if(a[i] > a[i-1] && a[i] > a[i+1]) f.push_back(i);
    }
    ll ans = 0;
    for(int i=0;i<f.size();i++){
        if(i != f.size()-1 && f[i] == f[i+1] - 2){
            a[f[i] + 1] = max(a[f[i]], a[f[i] + 2]);
            ans++, i++;
        }else{
            a[f[i]] = max(a[f[i]-1], a[f[i]+1]);
            ans++;
        }
    }
    cout << ans << '\n';
    for(int i=1;i<=n;i++) cout << a[i] << " \n"[i == n];
}

C. Differential Sorting

题意：给一个数组 \(a\)，每次操作可以选择三个位置 \(x,y,z(x<y<z)\)，使得 \(a_x\) 变为 \(a_y-a_z\)，要求构造一种操作方案，使得整个数组单调不降。

显然，最后两位是无法修改的，那么如果最后两位是递增的，一定不成立

排除这种情况后，此时 \(a_n\) 为最大值，如果 \(a_n<0\)，\(a_{n-2}\) 必然比 \(a_{n-1}\) 大，一定不行

现在有 \(a_n\ge0\)，我们向前枚举，后面的部分已经有序，那么直接拿 \(a_{i+1}-a_n\) 得到 \(a_i\)，就能使 \(a_i\) 越来越小。

ll n, m;
ll a[maxn];
void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    bool f = true;
    for(int i=1;i<n;i++){
        if(a[i] > a[i+1]){
            f = false;
            break;
        }
    }
    if(f){
        cout << "0\n";
        return;
    }
    if(max(a[n], a[n-1]) < 0 || a[n] < a[n-1]){
        cout << "-1\n";
        return;
    }
 
    cout << n-2 << '\n';
    for(int i=n-2;i>=1;i--){
        cout << i << ' ' << i+1 << ' ' << n << '\n';
    }
}

D. Infinite Set

题意：有一个集合 \(a\)，初始有一些数，如果 \(x\) 在集合中，那么 \(2x+1\) 和 \(4x\) 都在集合中，现在问集合中小于 \(2^p\) 的数共有多少个？（\(p\le2\times10^5\)）

首先我们把问题简化：\(2x+1\) 其实就是在 \(x\) 的二进制表示下添个1，\(4x\) 就是添两个0

对任一个 \(x\)​ 而言，我们不断的对它进行上面两种操作，产生的新数字是不会重复的。

设 \(f_i\) 表示二进制最高位为 \(i\) 的数的个数，那么有递推式 \(f_i = f_{i-1}+f_{i-2}\)

为了方便处理，首先把本质相同的 \(a_i\) 去掉（只保留一个），即如果 \(a_j\) 的二进制可以表示为 \(a_i+00100..\) 则 \(a_j\) 和 \(a_i\) 本质相同，后面的 \(00100\) 要求是由 \(1\) 和 \(00\) 组成的串，判重可以用01字典树完成。

这样我们把本质不同的数先加入 \(f\) 数组，就得到了初值，随后dp即可。

int n, m;
int a[maxn], cnt[maxn];
ll f[maxn];

struct tire{
    int ch[2];
    bool end;
}t[maxn << 5];
int tcnt = 0;
 
int mxk(int x){
    int mxk = 0;
    while(x > 0){
        x /= 2;
        mxk++;
    }
    return mxk;
}
 
bool add(int x){
    int p = 0;
    vector<int> vp;
    for(int i=mxk(x);i>=1;i--){
        int v = (x >> (i-1)) & 1;
        if(!t[p].ch[v]) t[p].ch[v] = ++tcnt;
        p = t[p].ch[v];
        vp.push_back(p);
    }
    if(t[p].end) return false;
    t[p].end = true;
    if(vp.empty()) return true;
    for(int i=vp.size()-1;i>=0;i--){
        if(i != vp.size()-1 && t[vp[i]].end) return false;
        int v = x % 2;
        x /= 2;
        if(v) continue;
        else{
            if(x > 0 && x % 2 == 0) x /= 2, i--;
            else return true;
        }
    }
    return true;
}
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int i=1;i<=n;i++){
        if(add(a[i])){
            cnt[mxk(a[i])]++;
        }
    }
    ll tot = 0;
    for(int i=1;i<=m;i++){
        if(i > 1) f[i] = (f[i-1] + f[i-2]) % mode;
        (f[i] += cnt[i]) %= mode;
        tot = (tot + f[i]) % mode;
//        cout << f[i] << '\n';
    }
    cout << tot << '\n';
}

E. Cars

题意：\(x\) 轴上有 \(n\) 辆车，每辆车有位置和朝向，不知道他们的具体情况，但知道 \(m\) 条信息：

• \(i,j\) 两辆车方向相反，接下来会撞上
• \(i,j\) 两辆车方向相反，但是会越来越远

要输出所有车的情况，或者输出-1表示不存在这种情况

方向和位置信息一起考虑比较复杂，我们分开考虑：

首先任意一对关系，都说明他们的方向相反，我们在 \(i,j\) 之间连一条边，得到一张图之后染色，判断方向是否存在冲突。

因为左右对称性，第一辆车的方向是无所谓的，我们假设第一辆车的方向是 \(L\)，然后再跑一次这张图，这次可以根据两个相邻点的方向和它们之间的关系，判断谁在谁左边。假设 \(i\) 在 \(j\) 左边，那么在一个新的图中让 \(i\) 向 \(j\) 连一条有向边。

构成的这个新图中，如果存在环即不存在答案。

随后按照拓扑序给每个节点分配位置即可。

int n, m;
vector<pair<int, int>> vp[maxn];
vector<int> vp2[maxn];
int col[maxn];
 
bool dfs(int p, int c){
    col[p] = c;
    for(auto v:vp[p]){
        if(col[v.first]){
            if(col[v.first] == 3 - c) continue;
            else return false;
        }
        if(!dfs(v.first, 3 - c)) return false;
    }
    return true;
}
 
bool vis[maxn];
int du[maxn], dir[maxn], pos[maxn];
void dfs2(int p, int d){
    if(vis[p]) return;
    dir[p] = d;
    vis[p] = true;
    for(auto v:vp[p]){
        if(v.second == 1){
            if(d == 1) vp2[v.first].push_back(p), du[p]++;
            else vp2[p].push_back(v.first), du[v.first]++;
        }else{
            if(d == 0) vp2[v.first].push_back(p), du[p]++;
            else vp2[p].push_back(v.first), du[v.first]++;
        }
        dfs2(v.first, d ^ 1);
    }
}
 
void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int t, x, y;
        cin >> t >> x >> y;
        vp[x].emplace_back(y, t);
        vp[y].emplace_back(x, t);
    }
    for(int i=1;i<=n;i++){
        if(!col[i] && !dfs(i, 1)){
            cout << "NO\n";
            return;
        }
    }
    for(int i=1;i<=n;i++) dfs2(i, 1);
 
    queue<int> q;
    int tot = 0;
    for(int i=1;i<=n;i++) if(!du[i]) q.push(i);
    while(!q.empty()){
        int p = q.front(); q.pop();
        pos[p] = ++tot;
        for(int v:vp2[p]){
            du[v]--;
            if(du[v] == 0) q.push(v);
        }
    }
    for(int i=1;i<=n;i++){
        if(!pos[i]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    for(int i=1;i<=n;i++){
        cout << "LR"[dir[i]] << ' ' << pos[i] << '\n';
    }
}

F. Closest Pair

题意：有 \(n\) 个点，每个点有坐标 \(x_i\)（\(x_i\) 保证有序） 和权值 \(w_i\)，接下来有一堆询问，每次问 \([l, r]\) 这段点中，点对 \(i,j\) 的 \(|x_ i-x_j|\times(w_i+w_j)\) 的最小值。

这道题的思维比较巧妙

在一段区间中，如果 \(i,j\) 这个点对是值最小的点对，那么 \(i,j\) 之间一定不存在另一个 \(w_k\) 介于 \(w_i, w_j\) 之间（不然最小值就是 \(i,k\) 了）

所以对于每个点 \(i\)，取它左右两端第一个 \(w_j<w_i\) 的 \(j\)，答案一定在这 \(2n\) 个点对当中。

这样问题就转换为了：有 \(2n\) 条带权的线段，每次询问一个区间，问这个区间包含的线段的最大值是多少。

离线+线段树维护最小值即可

struct SegTree{
    ll mi[maxn << 2];
    inline void push_up(int p){
        mi[p] = min(mi[p*2], mi[p*2+1]);
    }
    void modify(int p, int l, int r, int pos, ll to){
        if(l == r){
            mi[p] = min(mi[p], to);
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) modify(p*2, l, mid, pos, to);
        else modify(p*2+1, mid+1, r, pos, to);
        push_up(p);
    }
    ll query(int p, int l, int r, int L, int R){
        if(R < l || r < L) return 4e18;
        if(L <= l && r <= R) return mi[p];
        int mid = (l + r) / 2;
        return min(query(p*2, l, mid, L, R), query(p*2+1, mid+1, r, L, R));
    }
}segt;
 
vector<pair<int, ll>> seg[maxn];
vector<pair<int, int>> qr[maxn];
void solve(){
    int n, q;
    cin >> n >> q;
    vector<ll> x(n+1), w(n+1);
    for(int i=1;i<=n;i++){
        cin >> x[i] >> w[i];
    }
    fill(segt.mi, segt.mi + (maxn << 2), 4e18);
    stack<int> st;
    for(int i=1;i<=n;i++){
        while(!st.empty() && w[i] <= w[st.top()]){
            seg[i].emplace_back(st.top(), (w[i] + w[st.top()]) * (x[i] - x[st.top()]));
//            cout << i << ' ' << st.top() << '\n';
            st.pop();
        }
        if(!st.empty()){
            seg[i].emplace_back(st.top(), (w[i] + w[st.top()]) * (x[i] - x[st.top()]));
//            cout << i << ' ' << st.top() << '\n';
        }
        st.push(i);
    }
 
    vector<ll> ans(q+1);
    for(int i=1;i<=q;i++){
        int l, r; cin >> l >> r;
        qr[r].emplace_back(l, i);
    }
    for(int i=1;i<=n;i++){
        for(auto v:seg[i])
            segt.modify(1, 1, n, v.first, v.second);
        for(auto v:qr[i]){
            ans[v.second] = segt.query(1, 1, n, v.first, n);
        }
    }
    for(int i=1;i<=q;i++) cout << ans[i] << '\n';
}