跳转至

CF 杂题

CF1977E Tensor

这是一道交互题。有一个包含 \(n\) 个节点的 DAG，保证：

  • 所有边都是从编号大的点连向编号小的点；
  • 图的最小链覆盖不超过 \(2\)；

你初始只知道图的点数 \(n\)。你需要向交互器提出不超过 \(2n\) 个询问，每次你可以询问图上 \(i,j\) 两个点，交互器会告诉你 \(j\) 能否到达 \(i\)。然后，你需要给出图的一种黑白染色方案，满足：颜色相同的点分布在同一条链上。

显然 DAG 形如两条链中间任意连了一些边。我开始 naive 了，以为只询问 \((i,i+1)\) 然后二分图染色就行。其实中间的边完全可以扰乱这个过程，使得你染出来的某一侧不能形成链。

考虑扫描 \(1\sim n\) 的点然后动态维护两条链的前缀。考虑加入一个新的点 \(i+1\)。如果加入的点始终只向其中一条链的链尾有连边，那么显然是容易的（上面那个算法也能过）。因为此时你可以保证两条链的链尾之间没有连边；根据题目限制，新加的点一定向两个链尾连至少一条边。

考虑如何处理同时向两个链尾连边的情况。发现如果不考虑后面的点是没法判断当前点应该加到哪条链后面的（第一种算法就假在这里）。因此考虑开第三条链维护这些不确定的点。

此时，再新加一个点，如果它向第三条链的链尾有连边，那么它的情况等价于同时向两个链尾连边，因此追加到第三条链末尾。否则，无论如何它不能合并到第三条链末尾，因此将它追加到原来的两条链之一，然后将第三条链直接拼接在另一条链后面。发现此时仍然满足两条链的末尾之间没有边相连。

发现可以将加入一个点的询问次数压缩在 \(2\) 次以内。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
using namespace std;
const int N = 110;

int T, n;
int ans[N];

int s2[N];
int t0, t1, t2;

bool query(int i, int j) {
    cout << "? " << i << ' ' << j << endl;
    cout.flush();
    string tmp;
    cin >> tmp;
    return tmp == "YES";
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        t0 = t1 = t2 = 0;
        t0 = 1;
        ans[1] = 0;
        for(int i = 2; i <= n; i++) {
            if(t2 && query(s2[t2], i)) s2[++t2] = i;
            else if(t0 && query(t0, i)) {
                if(!t2 && t1 && query(t1, i)) {
                    s2[++t2] = i;
                    continue;
                }
                t0 = i;
                ans[i] = 0;
                if(t2) t1 = s2[t2];
                while(t2) ans[s2[t2--]] = 1;
            } else {
                t1 = i;
                ans[i] = 1;
                if(t2) t0 = s2[t2];
                while(t2) ans[s2[t2--]] = 0;
            }
        }
        while(t2) { ans[s2[t2--]] = 0; }
        cout << "! ";
        for(int i = 1; i <= n; i++) cout << ans[i] << ' ';
        cout << endl;
        cout.flush();
    }

    return 0;
}

CF1834E MEX of LCM

给定一个长为 \(n\) 的序列 \(a_{1\sim n}\)，求 \(\operatorname{mex}\bigl(\{\operatorname{lcm}_{i=l}^{r}a_i\mid 1\le l\le r\le n\}\big)\)。

\(n\le 3\times 10^5\)

注意到固定右端点之后，区间 \(\operatorname{lcm}\) 只有本质不同的 \(\log V\) 个，因此集合大小不超过 \(n\log V\)。考虑如何求出这个集合。

考虑动态维护每个前缀的后缀 \(\operatorname{lcm}\) 集合。发现在加入一个数字之后，只需把原先集合中的数字都和当前数字取 \(\operatorname{lcm}\)，再把太大的部分砍掉，时间复杂度就是对的。用 set 维护即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
const int N = 3e5 + 10;
const int LIM = 1e7;

int T, n;
int a[N];

set<int> ans, tmp;
long long sta[N], top;

inline long long lcm(int a, int b) {
    return (long long)a / __gcd(a, b) * b;
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        ans.clear(); tmp.clear();
        for(int i = 1; i <= n; i++) cin >> a[i];
        tmp.insert(a[1]); ans.insert(a[1]);
        for(int i = 2; i <= n; i++) {
            for(int j : tmp) sta[++top] = lcm(j, a[i]);
            tmp.clear();
            while(top) {
                if(sta[top] <= LIM) { tmp.insert(sta[top]); ans.insert(sta[top]); }
                --top;
            }
            tmp.insert(a[i]); ans.insert(a[i]);
        }
        for(int i = 1; i <= LIM; i++) {
            if(!ans.count(i)) { cout << i << '\n'; break; }
        }
    }

    return 0;
}

CF1699E Three Days Grace

给定一个正整数集合 \(A\)，你每次可以选择集合中一个数字 \(k\)，将它分解为 \(k=xy\)，然后将 \(k\) 删掉，\(x,y\) 加入集合。问经过若干次操作，集合的极差最小是多少。

\(n\le 10^6,~a_i\le 5\times 10^6\)

考虑双指针进行枚举，外层枚举集合的下界，然后不断缩紧集合的上界（外层枚举集合的上界显然是没有前途的）。设集合当前的范围为 \([l+1,r]\)，考虑 \(l+1\) 转移到 \(l\) 时的情况，那么一些数字可以分解成 \(l\) 和一些别的，情况增加，因此更优。

设 \(f_x\) 表示在当前下界 \(l\) 下，将数字 \(x\) 分解成若干数字，最大值最小是多少。在加入一个 \(l\) 时，我们枚举 \(x=kl,~(k\ge l)\)，并进行转移：

\[ f_{kl}=\min(f_{kl},f_{k}) \]

记得更新边界 \(f_l=l\)。这样复杂度形如一个调和级数。过程中动态维护 \(f(a_i)\) 的桶，更新边界之后，根据桶来缩紧上界即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int V = 5e6 + 10;
const int INF = 0x3f3f3f3f;

int T;
int n, m, k;
int a[V], f[V], cnt[V];
int ans;

void clear() {
    ans = INF;
    for(int i = 0; i <= m + 5; i++) a[i] = cnt[i] = 0;
    for(int i = 0; i <= m + 5; i++) f[i] = INF;
    st.clear();
    k = 0;
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while(T--) {
        cin >> n >> m;
        clear();
        for(int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if(!a[x]) ++k;
            a[x] = 1;
        }
        for(int i = m, r = m, c = 0; i >= 1; i--) {
            f[i] = i;
            if(a[i]) ++cnt[i], ++c;
            for(int j = i; j * i <= m; j++) {
                if(f[j] < f[j * i]) {
                    if(a[j * i]) --cnt[f[j * i]];
                    f[j * i] = f[j];
                    if(a[j * i]) ++cnt[f[j * i]];
                }
            }
            while(r > i && !cnt[r]) --r;
            if(c == k) ans = min(ans, r - i);
        }
        cout << ans << '\n';
    }

    return 0;
}

CF1935E Distance Learning Courses in MAC

给定一个长为 \(n\) 的有序二元组序列 \((l_i,r_i),~(i\in [1,n],~l_i\le r_i)\)。考虑一个序列 \(a_{1\sim n}\) 满足 \(a_i\in [l_i,r_i]\)。现在有 \(q\) 次询问，每次询问给定 \([x,y]\)，询问 \(\operatorname{OR}_{i=x}^{y}a_i\)（按位或）的最大值。

\(n,q\le 2\times 10^5\)

考察 \(a_i\) 和 \(r_i\) 的最长公共前缀，记其长度为 \(k\)。那么 \(a_i\) 从高往低数的第 \(k+1\) 位为 \(0\)，\(r_i\) 从高往低数的第 \(k+1\) 位是 \(1\)。然后从第 \(k+2\) 位往后就都可以取 \(1\) 了。

因此预处理 \(f_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\)；\(g_{i,j,k}\) 表示区间 \([i,j]\) 中 \(r_i\) 的第 \(k\) 位有多少个 \(1\) 能变成 \(0\)（也就是在 \(l_i,r_i\) 的公共前缀后面并且值为 \(1\)，变成 \(0\) 之后可以把后面全填上 \(1\)）。对于每次询问，我们从高位往低位处理，考虑第 \(k\) 位，

  • 若 \(f_k=0\)，那么该位只可能是 \(0\)；
  • 若 \(f_k>0\)，那么必须优先保证当前位为 \(1\)，再去考虑后面的位；
    • 若 \(f_k\ge 2\wedge g_k\ge 1\)，那么选择一个 \(1\) 变成 \(0\)，后面的位都填 \(1\) 就行了，结束贪心；

\(f\) 和 \(g\) 容易在 \(O(n\log V)\) 的时间内预处理出来。因此总时间复杂度为 \(O\big((n+q)\log V\big)\)。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
using namespace std;
const int N = 2e5 + 10;

inline int lg(int x) {
    int res = -1;
    while(x) { ++res; x >>= 1; }
    return res;
}

int T, n, q;
int a[N], b[N];

int f[N][30], g[N][30];

void clear() {
    for(int i = 0; i <= n + 5; i++) {
        for(int j = 0; j < 30; j++) f[i][j] = g[i][j] = 0;
    }
}

int main() {

    cin >> T;
    while(T--) {
        cin >> n;
        clear();
        for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
        for(int i = 1; i <= n; i++) {
            int tmp = lg(a[i] ^ b[i]);
            for(int j = 0; j < 30; j++) {
                f[i][j] = f[i - 1][j] + ((b[i] >> j) & 1);
                g[i][j] = g[i - 1][j] + (((b[i] >> j) & 1) && (j <= tmp));
            }
        }
        cin >> q;
        while(q--) {
            int l, r, ans = 0;
            cin >> l >> r;
            for(int i = 29; i >= 0; i--) {
                if(f[r][i] - f[l - 1][i] == 0) continue;
                ans |= (1 << i);
                if(f[r][i] - f[l - 1][i] == 1) continue;
                if(g[r][i] - g[l - 1][i]) { ans += (1 << i) - 1; break; }
            }
            cout << ans << ' ';
        }
        cout << '\n';
    }

    return 0;
}

CF749E Inversions After Shuffle

给定一个长为 \(n\) 的排列，你等概率选择一段区间 \([l,r]\) 然后等概率重排这段区间内的数。问得到的新序列的逆序对的期望个数。

\[ n\le 10^5 \]

注意到横跨区间内外的逆序对不会被影响。并且等概率随机重排区间 \([l,r]\) 后，\([l,r]\) 内的期望逆序对数量就是长为 \(r-l+1\) 的随机排列的期望逆序对数。因此问题转化为选择一段区间 \([l,r]\)，\([l,r]\) 内的逆序对数量的期望是多少。期望可以转换为求和。

考虑从大到小扫描值域，发现一个数字 \(a_i\) 的贡献等于它左边已经被加进来的点的下标之和，乘以 \(n-i+1\)。于是直接做做完了。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<iomanip>
#define int long long
#define ld long double
using namespace std;
const int N = 1e5 + 10;

int n;
ld ans;
int a[N], ia[N];

namespace BIT {
    int sum[N];
    inline void clear() {
        for(int i = 0; i <= n + 5; i++) sum[i] = 0;
    }
    inline void add(int p, int v) {
        for(int i = p; i <= n; i += i & -i) sum[i] += v;
    }
    inline int query(int p) {
        int res = 0;
        for(int i = p; i > 0; i -= i & -i) res += sum[i];
        return res;
    }
}

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) ia[a[i]] = i;

    for(int i = 1; i <= n; i++) {
        ans += (ld)(i * (i - 1) / 2) * (n - i + 1) / 2;
    }

    for(int i = n; i >= 1; i--) {
        int p = ia[i];
        ans -= (ld)BIT::query(p) * (n - p + 1);
        BIT::add(p, p);
    }

    ans /= n * (n + 1) / 2;

    BIT::clear();
    for(int i = n; i >= 1; i--) {
        ans += BIT::query(a[i]);
        BIT::add(a[i], 1);
    }

    cout << fixed << setprecision(12) << ans << '\n';

    return 0;
}

CF1826E Walk the Runway

bitset 高维偏序板子。用扫描线可以做到 \(O(nm+\frac{n^2m}{\omega})\)。