茶7.8-7.12

茶7.8-7.12

Mon

Find the Different Ones!_923D

输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5，q 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤1e6)，下标从 1 开始。
然后输入 q(1≤q≤2e5) 和 q 个询问，每个询问输入两个数 L R(1≤L<R≤n)。

对于每个询问，输出在 [L,R] 内的两个下标 i 和 j，满足 a[i] ≠ a[j]。
如果不存在，输出 “-1 -1”。

样例太长，请在原题查看。

Sol:

定义 left[i] 表示在 a[i] 左侧的不等于 a[i] 的最近元素下标。

递推：如果 a[i] = a[i-1] 则 left[i] = left[i-1]，否则 left[i] = i-1。

回答询问时，如果 left[R] < L 则输出 -1 -1，否则输出 left[R] 和 R。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve()
{
    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++) cin>>a[i];
    vi nxt(n);
    nxt[n-1]=n;
    for(int i=n-2;i>=0;i--){
        nxt[i] = a[i] == a[i+1] ? nxt[i+1] : i+1;
    }
    int q;
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        l--;
        if(nxt[l]<r){
            cout<<l+1<<" "<<nxt[l]+1<<"\n";
        }else{
            cout<<-1<<" "<<-1<<'\n';
        }
    }   
}

Tue

https://codeforces.com/problemset/problem/1670/C

输入 T(≤1e5) 表示 T 组数据。所有数据的 n 之和 ≤5e5。
每组数据输入 n(1≤n≤1e5) 和两个 1~n 的排列 a 和 b，
然后输入数组 d，保证 d[i] 是 {0,a[i],b[i]} 中的一个。

构造一个 1~n 的排列 c，满足：
如果 d[i]>0，那么 c[i] 必须是 d[i]，否则 c[i] 可以是 a[i]，也可以是 b[i]。

你能构造出多少个不同的排列 c？模 1e9+7。
保证至少能构造一个排列 c。

样例太长，请在原题查看。

Sol:

从 a[i] 向 b[i] 连边，我们会得到若干个环（没有树枝，因为 a 和 b 都是排列）。

对于长度大于 1 的环，如果不包含 d[i] > 0 的点，那么有两种选法。

比如 1-2-3-1 这个环，每条边可以分别选 1,2,3 也可以分别选 2,3,1。

所以答案就是 2^m，其中 m 是长度大于 1 的不含 d[i]>0 的环的个数。

Code:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int j = 0; j < n; j++){
      cin >> a[j];
      a[j]--;
    }
    vector<int> b(n);
    for (int j = 0; j < n; j++){
      cin >> b[j];
      b[j]--;
    }
    vector<int> d(n);
    for (int j = 0; j < n; j++){
      cin >> d[j];
      d[j]--;
    }
    vector<bool> used(n, false);
    bool ok = true;
    for (int j = 0; j < n; j++){
      if (d[j] != -1){
        if (used[d[j]]){
          ok = false;
        }
        used[d[j]] = true;
      }
    }
    if (!ok){
      cout << 0 << "\n";
    } else {
      vector<vector<int>> E(n);
      for (int j = 0; j < n; j++){
        E[a[j]].push_back(b[j]);
        E[b[j]].push_back(a[j]);
      }
      long long ans = 1;
      vector<bool> used2(n, false);
      for (int j = 0; j < n; j++){
        if (!used2[j]){
          used2[j] = true;
          queue<int> Q;
          Q.push(j);
          int cnt = 0;
          bool ok2 = true;
          while (!Q.empty()){
            int v = Q.front();
            Q.pop();
            cnt++;
            if (used[v]){
              ok2 = false;
            }
            for (int w : E[v]){
              if (!used2[w]){
                used2[w] = true;
                Q.push(w);
              }
            }
          }
          if (ok2 && cnt >= 2){
            ans *= 2;
            ans %= MOD;
          }
        }
      }
      cout << ans << "\n";
    }
}

Wed

Moving Both Hands

输入 n(2≤n≤1e5) m(0≤m≤2e5)，表示一个 n 点 m 边的有向图。节点编号从 1 开始。保证图中无自环和重边。
然后输入 m 条边，每条边输入 x y w(1≤w≤1e9)，表示一条从 x 到 y 的边权为 w 的有向边。

定义 f(i) 为：有甲乙两人，分别从 1 和 i 出发，到达同一个点，两人用时之和的最小值。如果两人无法到达同一个点，则 f(i) = -1。
输出 f(2), f(3), …, f(n)。

输入
5 7
1 2 2
2 4 1
4 1 4
2 5 3
5 4 1
5 2 4
2 1 1
输出
1 -1 3 4

Sol:

分层图最短路。

建图：把每条有向边及其反向边加到图中，用一个额外变量 inv 表示这条边是否为反向边。

从 1 到 i 的路径分成两段：

从 1 到 x，走原图上的边。（记作状态 0）

从 x 到 i，走反向边。（记作状态 1）

由于到达每个节点时，都有两个状态，所以相当于在有 2n 个节点的图上跑 Dijkstra 算法。

Dijkstra 算法介绍

类似状态机 DP，在 Dijkstra 的优先队列中，额外记录一个状态 inv，如果 inv=0 表示当前在走原图上的边，如果 inv=1 表示当前在走反向边。

如果当前状态是 0，那么可以转移到 0 或者 1。

如果当前状态是 1，那么只能转移到 1。

Code:

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
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<array<int, 3> > > adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w, 0});
        adj[v].push_back({u, w, 1});
    }
    const int64_t inf = 1e18;
    vector<vector<int64_t>> dist(n + 1, vector<int64_t>(2, inf));
    vector<vector<int>> st(n + 1, vector<int>(2));
    priority_queue<tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<tuple<int64_t, int, int>>> hp;
    hp.emplace(0, 1, 0);
    dist[1][0] = 0;
    while (!hp.empty()) {
        auto [d, x, rev] = hp.top();
        hp.pop();
        if (st[x][rev]) {
            continue;
        }
        st[x][rev] = true;
        for (auto& [y, w, e] : adj[x]) {
            if (!rev) {
                if (dist[y][e] > dist[x][0] + w) {
                    dist[y][e] = dist[x][0] + w;
                    hp.emplace(dist[y][e], y, e);
                }
            } else {
                if (dist[y][1] > dist[x][1] + w && e == 1) {
                    dist[y][1] = dist[x][1] + w;
                    hp.emplace(dist[y][1], y, e);
                }               
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << (min(dist[i][0], dist[i][1]) == 1e18 ? -1 : min(dist[i][0], dist[i][1])) << " \n"[i == n];
    }
}

Thu

https://codeforces.com/problemset/problem/582/B

输入 n(1≤n≤100) t(1≤t≤1e7) 和长为 n 的数组 a(1≤a[i]≤300)。

把 t 个一样的数组 a 拼接在一起，得到长为 t*n 的数组 b，满足 b[i] = b[i+n]。
输出 b 的 LIS 长度。注意这里的 LIS 是非降的，允许元素相等。

输入
4 3
3 1 4 2
输出
5

Sol:

贪心+二分求 LIS

如果 t <= n，那么直接求长为 tn 的数组的 LIS。也就是对数组 a 循环 t 次。

如果 t > n，只需要循环 n 次。

设最后一轮循环（第 n 轮循环）二分的数组 f 的长度增加了 d，那么有如下结论：

接下来的 t-n 轮循环是不需要跑的，保证每轮循环 f 数组的长度都会增加 d。

例如 a=[2,3,1]，前三轮循环，找到的 LIS 为 [2,3] [1,2,3] [1,1,2,3]

后面每轮循环都只会让 f 的长度增加 1。 相当于每多一轮循环，中间就插入了一个 1。

猜想：只需要循环 sqrt(n) 左右次即可。

Code:

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

void solve()
{
    int n, t, d;
    cin >> n >> t;
    vi a(n);
    FOR(i, 0, n-1) cin >> a[i];
    vi f;
    for (int i = 0; i <= n && t > 0; i++) {
        int m = f.size();
        for (int x : a) {
            auto j = lower_bound(f.begin(), f.end(), x + 1);
            if (j != f.end()) {
                *j = x;
            } else {
                f.push_back(x);
            }
        }
        d = f.size() - m;
        t--;
    }
    //BUG(t);
    //BUG(d);
    cout << f.size()+t*d << endl;
}

Fri

Maximizing Root_848F

输入 T(≤5e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(2≤n≤1e5) k(0≤k≤n) 和长为 n 的数组 a(1≤a[i]≤1000)。
然后输入一棵无向树的 n-1 条边，节点编号从 1 开始。
根节点为 1。节点 i 的点权为 a[i]。

你可以执行如下操作至多 k 次：
选择一个没有操作过的节点 v 和一个整数 x，其中 x 必须满足 x 是子树 v 中所有点权的公约数。然后把子树 v 中的每个点权都乘上 x。

输出操作后，a[1] 最大是多少。

输入
2
5 2
24 12 24 6 12
1 2
1 3
2 4
2 5
5 3
24 12 24 6 12
1 2
1 3
2 4
2 5
输出
288
576

Sol:

提示 1：为了让答案尽量大，从上到下操作比较好，还是从下到上操作比较好？

提示 2：答案一定是 a[1] 乘以它的一个因子。枚举这个因子 d。

提示 3：DFS 这棵树，什么情况下，子树是不需要操作的？什么情况下，子树只需要操作一次？什么情况下，子树只需要操作两次？

灵神题解

Code:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
void solve()
{
    vector<vector<int> > divisors(mx+1,vector<int>());
    for (int i = mx; i > 0; i--) {
        for (int j = i; j <= mx; j+=i) {
            divisors[j].push_back(i);
        }
    }
    vi ceilSqrt(mx+1);
    for (int i = 1;i <= mx; i++) {
        ceilSqrt[i] = 1;
        int x = i;
        for (int p = 2; p*p <= x; p++) {
            for (int p2 = p*p; x%p2 == 0; x /= p2) {
                ceilSqrt[i] *= p;
            }
            if (x % p == 0) {
                ceilSqrt[i] *= p;
                x /= p;
            }
        }
        if (x > 1) {
            ceilSqrt[i] *= x;
        }
    }
    int n , t, k;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        vi a(n);
        FOR(i, 0, n-1) cin >> a[i];
        vector<vector<int> > g(n, vector<int>());
        for (int i = 1;i < n; i++) {
            int v,w;
            cin >> v >> w;
            v--;
            w--;
            g[v].push_back(w);
            g[w].push_back(v);
        }
        if (k == 0) {
            cout << a[0] << endl;
            continue;
        }
        vi subGcd(n);
        std::function<void(int, int)> dfs0;
        dfs0 = [&](int v, int fa) -> void{
            subGcd[v] = a[v];
            for (int w : g[v]) {
                if (w != fa) {
                    dfs0(w, v);
                    subGcd[v] = gcd(subGcd[v], subGcd[w]);
                }
            }
        };
        dfs0(0, -1);
        int cnt;
        std::function<void(int, int, int)> dfs;
        dfs = [&](int v, int fa, int d) -> void {
            if (subGcd[v] % d == 0) {
                return;
            }
            if (subGcd[v]*subGcd[v]%d == 0) {
                cnt++;
                return;
            }
            if (g[v].size() == 1 || a[v]*a[v]%d > 0) {
                cnt = 1e9;
                return;
            }
            for (auto w : g[v]) {
                if (w != fa) {
                    dfs(w, v, ceilSqrt[d]);
                }
            }
            cnt++;
        };
        for (auto d : divisors[a[0]]) {
            cnt = 0;
            for (auto v : g[0]) {
                dfs(v, 0, d);
            }
            if (cnt < k) {
                cout << a[0]*d << endl;
                break;
            }
        }
    }
}
codeforces
#数据结构 #图论 #广度优先搜索（BFS） #环检测 #模运算
茶7.8-7.12
https://www.polarishaw.top/2024/07/08/茶7.8-7.12/
作者
Polaris
发布于
2024年7月8日
许可协议