Solution - Codeforces Round 1007 (Div. 2)

Posted on Edited on

Codeforces Round 1007 (Div. 2)

最难受的一集。

A The Play Never Ends

Solution

由于一个人两场必下，所以当一个人是spectator的时候，下一把对面一定会下（如果对面输了，下；如果对面赢了，连续两把，下）；而再下一把这个人一定会下（第二把不管输赢都得下）。故1,4,7,⋯1, 4, 7, \cdots这些局是spectator。

模33，O(1)O(1)。

Code

Show Code 
1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;
signed main(){
    int t; cin >> t;
    while (t--){
        int k; cin >> k;
        if (k % 3 == 1) puts("YES");
        else puts("NO");
    }
    return 0;
}

B Perfecto

Solution

打表发现只有n=1,8,49,288,1681,9800,57121,332928n=1, 8, 49, 288, 1681, 9800, 57121, 332928时总和是完全平方数，所以我们不妨先按照1,2,⋯ ,n1, 2, \cdots, n的顺序排，然后如果有以上88个数中的一个，就和后面的交换。可以发现这些平方数+1+1一定不是一个平方数，所以这就是一个合理的构造。

复杂度O(n)O(n)。

Code

Show 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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 5e5 + 1, FAIL[8] = {1, 8, 49, 288, 1681, 9800, 57121, 332928};
int n, A[N];
LL sq[N];
inline bool fail(int x){
    for (int i = 0; i < 8; ++i) if (x == FAIL[i]) return 1;
    return 0;
}
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    for (int i = 1; i < N; ++i) sq[i] = (LL)i * i;
    // LL now = 0;
    // for (int i = 1, j = 1; i < N; ++i){
    //     now += i;
    //     while (sq[j] < now) ++j;
    //     if (now == sq[j]) printf("i = %d, now = %lld\n",i, now);
    // }
    // return 0;
    int t; cin >> t;
    while (t--){
        cin >> n;
        LL now = 0;
        if (fail(n)) cout << -1 << endl;
        else if (n == 2) cout << "2 1" << endl;
        else{
            A[1] = 2;
            A[2] = 1;
            now = 2;
            for (int i = 3, j = 1; i <= n; ++i){
                now += A[i - 1];
                A[i] = i;
                while (sq[j] < now) ++j;
                if (now == sq[j]){
                    swap(A[i - 1], A[i]);
                    now -= A[i] - A[i - 1];
                    // assert(now - A[i - 1] + A[i] == sq[j - 1]);
                }
            }   
            for (int i = 1; i <= n; ++i){
                cout << A[i] << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

C Trapmigiano Reggiano

Solution

我们假设en\textrm{en}是根节点，从st\textrm{st}开始走，最终走到根节点就赢了。

我们先每次都往某个子节点走，每次都优先使用这个子节点的点来走，最终一定会停到某个节点，且这个节点以下部分全部用光了。

我们发现从这个节点网上一直到根节点都没有使用过，所以一定能使用这条路径上的点到达根节点。

每次用光之后回溯，优先使用比较劣的点，我们会重复这个过程，但是可以保证每次用光时都会有从这个点网上到根节点的路径上所有点都还没有使用。

所以一定有解，模拟这个过程即可。

具体来说，我们一直记录当前已经走了但还没有消耗节点的步数。先考虑往子节点走，如果某个子节点为根的树大小已经小于等于当前步数，则当前步数的一部分可以用这个子节点为根的子树来抵消；否则我们往那个子节点走。最终一定会停在某个节点，且步数为00。这个时候先原地走一步，再往根节点走，步数+1+1。重复这个过程就可以到达根节点，且用光所有步数。

复杂度O(n)O(n)。

看了下题解，有个更好的做法：

设最大深度为dd，发现当深度≥d\geq d的节点都用光之后，老鼠当前的深度≤d\leq d，此时再用完所有深度为d−1d-1的节点，老鼠深度≤d−1\leq d-1，如此往复老鼠一定会走到深度为00的点，及根节点。

时间复杂度O(n)O(n)，但实现起来方便很多。

Code

Show 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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, st, en;
vector<int> G[N];
int sz[N], tot, A[N], idx, fa[N], h[N];
bool vis[N];
void Dfs(int u){
    sz[u] = 1;
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if (!sz[v]) Dfs(v), sz[u] += sz[v];
        else fa[u] = v;
    }
}
void calc(int u){ // 把以某个点为根的子树所有节点都丢到答案序列中
    A[++idx] = u;
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if (v == fa[u]) continue;
        calc(v);
    }
}
void Dfs2(int u){
    
    // if (tot == sz[u]){
    //     A[++idx] = u;
    // }
    // for (int i = 0; i < G[u].size(); ++i){
    //     int v = G[u][i];
    //     if (v == fa[u]) continue;
    //     if (sz[v] <= tot) tot -= sz[v], calc(v);
    //     else ++tot, Dfs2(v);
    // }
    for (int i = 1; i <= n; ++i) vis[i] = 0;
    int nxt = u;
    while (true){
        int u = nxt; nxt = 0;
        vis[u] = 1;
        for (int& i = h[u]; i < G[u].size(); ++i){ // 手写回溯
            int v = G[u][i];
            if (v == fa[u] || vis[v]) continue;
            if (sz[v] <= tot) tot -= sz[v], calc(v); // 如果比当前步数小或刚好抵消当前步数
            else{
                ++tot, nxt = v; // 否则往下走一步
                break;
            }
        }
        if (!nxt){
            A[++idx] = u;
            if (fa[u] != -1) nxt = fa[u], tot = 1; // 回溯一步，tot一定已经用完，所以tot=1
            else break;
        }
    }
}
signed main(){
    // freopen("test-C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    int t; cin >> t;
    while (t--){
        cin >> n >> st >> en;
        for (int i = 1; i <= n; ++i) sz[i] = 0, h[i] = 0, G[i].clear();
        for (int i = 1; i < n; ++i){
            int u, v; cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        fa[en] = -1, Dfs(en);
        tot = idx = 0, Dfs2(st);
        // cout << "::::";
        for (int i = 1; i <= idx; ++i) cout << A[i] << " ";
        cout << endl;//return 0;
    }
    return 0;
}

D1 & D2 Infinite Sequence

Solution

D1

由ama_m的递推式可以得到a2k=a2k+1(2k>n)a_{2k} = a_{2k+1}(2k > n)。

不妨假设nn是奇数（如果nn是偶数，则递推一步）。设sum(i)=⨁j=1iajsum(i)=\bigoplus_{j = 1}^ia_j，则我们可以得到ama_m的简化递推式：

am={amifm≤n⨁i=1⌊m2⌋ai=sum(⌊m2⌋)ifm>n∧⌊m2⌋≤n⨁i=1⌊m2⌋ai=sum(n)⊕(an+1⊕an+2)⊕⋯=sum(n)if⌊m2⌋>n∧m是奇数⨁i=1⌊m2⌋ai=sum(n)⊕(an+1⊕an+2)⊕⋯=sum(n)⊕a⌊m2⌋if⌊m2⌋>n∧m是偶数a_m = \begin{cases} & a_m & \textrm{if} &m \leq n\\ & \bigoplus_{i=1}^{\lfloor\frac{m}{2}\rfloor} a_i = sum(\lfloor\frac{m}{2}\rfloor) & \textrm{if} & m>n\wedge \lfloor\frac{m}{2}\rfloor \leq n\\ & \bigoplus_{i=1}^{\lfloor\frac{m}{2}\rfloor} a_i = sum(n) \oplus (a_{n + 1}\oplus a_{n + 2})\oplus\cdots = sum(n) & \textrm{if} &\lfloor\frac{m}{2}\rfloor > n\wedge m\text{是奇数}\\ & \bigoplus_{i=1}^{\lfloor\frac{m}{2}\rfloor} a_i = sum(n) \oplus (a_{n + 1}\oplus a_{n + 2})\oplus\cdots = sum(n)\oplus a_{\lfloor\frac{m}{2}\rfloor} & \textrm{if} &\lfloor\frac{m}{2}\rfloor > n\wedge m\text{是偶数}\\ \end{cases}

通过递归可以O(log⁡r+n)O(\log r+n)时间内解决。

D2

观察D1的结论，发现当m>nm>n时，找到m>>1m>>1，m>>2m>>2，⋯\cdots中第一个为奇数或者小于等于nn的数xx，则答案是a2xa_{2x}与后缀0的个数−1后缀0的个数-1个sum(n)sum(n)作异或。而可以发现a2xa_{2x}大多数是sum(n)sum(n)（只有x<nx < n时才不是，而这种情况比较少，可以暴力处理），所以我们可以枚举后缀00的个数来进行计数。

时间复杂度 O(nlog⁡r)O(n\log r)。

Code(D2)

Show 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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, M = 63;
int A[N], sum[N];
int n;
// inline void calc(){
//     for (int i = 1; i <= 50; ++i){
//         sum[i] = sum[i - 1] ^ A[i];
//         if (i * 2 > n) A[i * 2] = sum[i];
//         if (i * 2 + 1 > n) A[i * 2 + 1] = sum[i];
//     }
//     for (int i = 1; i <= 101; ++i){
//         cout << A[i] << ' ';
//     }
//     cout << endl;
// }
int f(LL x){ // 用这个函数就足以搞定D1
    if (x <= n) return A[x];
    if ((x >> 1) <= n) return sum[x >> 1];
    if ((x >> 1) & 1) return sum[n];
    else return f(x >> 1) ^ sum[n];
}
signed main(){
    freopen("test.in", "r", stdin); // 这个记得删掉
    // freopen("D2.out", "w", stdout);
    int t; cin >> t;
    while (t--){
        LL l, r, ans = 0;
        cin >> n >> l >> r;
        // cout <<"?";
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            // for (int j = 1; j < M; ++j){
            //     A[i][j] = A[i - 1][j] ^ A[i][j - 1];
            // }
            sum[i] = sum[i - 1] ^ A[i];
        }
        if (n % 2 == 0) ++n, A[n] = sum[n / 2], sum[n] = sum[n - 1] ^ A[n]; // n为偶数，递推一次
        // cout << f(l) << endl;
        // calc();
        while (l <= n * 2 + 1 && l <= r){
            ans += f(l);
            ++l;
        } // 把比较小的部分处理掉
        if ((l & 1) && l <= r) ans += f(l++);
        if (!(r & 1) && l <= r) ans += f(r--);
        if (l > r){
            cout << ans << endl;
            continue;
        }
        l >>= 1, r >>= 1; // 由于a_2k = a_{2k+1}，统一处理，待会*2
        for (int y = 0; l <= r; y ^= sum[n]){ // 枚举0的个数
            // printf("n = %d, y = %d, l = %lld, r = %lld, ans = %lld\n", n, y, l, r, ans);
            ans += ((r - l + 1 + (l & 1)) / 2) * (sum[n] ^ y) * 2; // 处理大部分
            l = (l >> 1) + (l & 1);
            r = r >> 1;
            while (l <= r && l <= n) ans += (sum[l] ^ y ^ sum[n]) * 2, ++l; // 处理较小部分
        }
        // cout <<":::";
        cout << ans << endl;
    }
    return 0;
}

由于某个加号打成了减号，调了很久，附上对拍器和datamaker：

对拍器（Cpp，generated by ChatGPT）：

Show 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
#include <iostream>
#include <fstream>
#include <cstdlib> // 用于 system() 函数
#include <thread>  // 用于暂停
#include <chrono>  // 用于暂停

bool compareFiles(const std::string& file1, const std::string& file2) {
    std::ifstream f1(file1, std::ios::binary);
    std::ifstream f2(file2, std::ios::binary);
    
    if (!f1.is_open() || !f2.is_open()) {
        std::cerr << "Error opening files.\n";
        return false;
    }

    char c1, c2;
    while (f1.get(c1) && f2.get(c2)) {
        if (c1 != c2) {
            return false; // 文件内容不同
        }
    }

    std::cout << f1.get() << f2.get() << std::endl;

    // 检查文件是否同时结束
    return f1.eof() && f2.eof();
}

int main() {
    while (true) {
        // 第一步：运行 D-datamaker
        // std::cout << "Running D-datamaker...\n";
        int result = system("./D-datamaker");
        if (result != 0) {
            std::cerr << "Error running D-datamaker.\n";
            return 1;
        }

        // 第二步：运行 D2
        // std::cout << "Running D2...\n";
        result = system("./D2");
        if (result != 0) {
            std::cerr << "Error running D2.\n";
            return 1;
        }

        // 第三步：运行 D3
        // std::cout << "Running D3...\n";
        result = system("./D3");
        if (result != 0) {
            std::cerr << "Error running D3.\n";
            return 1;
        }

        // 比较 D2.out 和 D3.out
        // std::cout << "Comparing D2.out and D3.out...\n";
        if (compareFiles("D2.out", "D3.out")) {
            std::cout << "Files are identical. Restarting...\n";
        } else {
            std::cout << "Files are different. Exiting...\n";
            break;
        }

        // 暂停一段时间后重新开始 (可选)
        // std::this_thread::sleep_for(std::chrono::seconds(2));  // 2秒暂停
    }

    return 0;
}

对拍器2（python，generated by SJTU-DeepSeek，推荐使用）

Show 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
import subprocess
import sys
import os

def compare_files(file1, file2):
    with open(file1, 'r') as f1, open(file2, 'r') as f2:
        lines1 = [line.rstrip() for line in f1]
        lines2 = [line.rstrip() for line in f2]
    
    # 去除末尾空行
    while lines1 and lines1[-1] == '': lines1.pop()
    while lines2 and lines2[-1] == '': lines2.pop()
    
    return lines1 == lines2

try:
    # 获取脚本所在目录的绝对路径
    script_dir = os.path.dirname(os.path.abspath(__file__))
    
    for t in range(1, 10001):
        # 生成测试数据
        subprocess.run(
            [os.path.join(script_dir, 'D-datamaker')],
            check=True,
            cwd=script_dir,
            stdout=open(os.path.join(script_dir, 'test.in'), 'w')
        )
        
        # 运行两个解法程序
        subprocess.run(
            [os.path.join(script_dir, 'D2')],
            check=True,
            cwd=script_dir,
            stdin=open(os.path.join(script_dir, 'test.in'), 'r'),
            stdout=open(os.path.join(script_dir, 'sol1.out'), 'w')
        )
        subprocess.run(
            [os.path.join(script_dir, 'D3')],
            check=True,
            cwd=script_dir,
            stdin=open(os.path.join(script_dir, 'test.in'), 'r'),
            stdout=open(os.path.join(script_dir, 'sol2.out'), 'w')
        )
        
        # 比较输出
        if not compare_files(
            os.path.join(script_dir, 'sol1.out'),
            os.path.join(script_dir, 'sol2.out')
        ):
            print("Error: Outputs differ!")
            sys.exit(1)
        else:
            print(f"Test case {t} completed.")
            pass
        

except subprocess.CalledProcessError as e:
    print(f"Process error: {e}")
    sys.exit(1)
except KeyboardInterrupt:
    print("\nStopped by user")
    sys.exit(0)

datamaker：

Show Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int n = 3, MOD = 20;
signed main(){
    // freopen("test.in", "w", stdout);
    srand(time(0));
    cout << 1 << endl;
    LL l = (LL)rand() * rand() % MOD + 1;
    LL r = (LL)rand() * rand() % MOD + 1;
    if (l > r) l ^= r ^= l ^= r;
    cout << n << " " << l << " " << r << endl;
    for (int i = 1; i <= n; ++i){
        cout << rand() % 2 << " ";
    }
    cout << endl;
    return 0;
}

BruteForce：

Show 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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, M = 63;
int A[N], sum[N];
int n;
// inline void calc(){
//     for (int i = 1; i <= 50; ++i){
//         sum[i] = sum[i - 1] ^ A[i];
//         if (i * 2 > n) A[i * 2] = sum[i];
//         if (i * 2 + 1 > n) A[i * 2 + 1] = sum[i];
//     }
//     for (int i = 1; i <= 101; ++i){
//         cout << A[i] << ' ';
//     }
//     cout << endl;
// }
int f(LL x){
    if (x <= n) return A[x];
    if ((x >> 1) <= n) return sum[x >> 1];
    if ((x >> 1) & 1) return sum[n];
    else return f(x >> 1) ^ sum[n];
}
signed main(){
    // freopen("test.in", "r", stdin);
    // freopen("D3.out", "w", stdout);
    int t; cin >> t;
    while (t--){
        LL l, r, ans = 0;
        cin >> n >> l >> r;
        // cout <<"?";
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            // for (int j = 1; j < M; ++j){
            //     A[i][j] = A[i - 1][j] ^ A[i][j - 1];
            // }
            sum[i] = sum[i - 1] ^ A[i];
        }
        if (n % 2 == 0) ++n, A[n] = sum[n / 2], sum[n] = sum[n - 1] ^ A[n];
        // cout << f(l) << endl;
        // calc();
        for (LL i = l; i <= r; ++i) ans += f(i);
        cout << ans << endl;
    }
    return 0;
}

E LeaFall

Solution

最简单的思路，树形dp，对于每个点找到能和这个点配对的所有点的贡献，最后答案再除以二即可。

实现细节贼多。具体来讲，每个点uu的好朋友分为三类：

  1. 和uu相邻；
  2. 和uu距离为22；
  3. 和uu距离大于22。

1类点

为了处理1类点，我们需要计算以下几个参数：

  • p(u)p(u)表示uu存活的概率，p(u)=qu−puqup(u) = \frac{q_u - p_u}{q_u}；
  • isol(u)isol(u)表示uu被完全孤立的概率；
  • pend(u)pend(u)表示uu只连一个点的概率。

则uu的这部分贡献为：

∑v∈neighbors(u)p(u)⋅p(v)⋅isol(u)1−p(v)⋅isol(v)1−p(u)\sum_{v\in neighbors(u)} p(u)\cdot p(v)\cdot \frac{isol(u)}{1-p(v)}\cdot\frac{isol(v)}{1-p(u)}

其中isol(u)isol(u)和pend(u)pend(u)计算方法如下：

isol(u)=∏v∈neighbors(u)(1−p(v))pend(u)=∑v∈neighbors(u)(isol(u)⋅p(v)1−p(v))\begin{aligned} isol(u) =& \prod_{v \in neighbors(u)} (1 - p(v))\\ pend(u) =& \sum_{v \in neighbors(u)} (isol(u)\cdot\frac{p(v)}{1-p(v)}) \end{aligned}

2类点

2类点分为三类：

  1. 孙子；
  2. 爷爷；
  3. 兄弟。

对于孙子，分为用儿子相连，和不用儿子相连两种。计算如下参数：

  • sum_isol(u)sum\_isol(u)表示uu的某个儿子只跟uu相连且该儿子和uu都活着的概率之和；
  • sum_pend(u)sum\_pend(u)表示uu的某个儿子只跟一个非uu的相连且该儿子活着，uu死掉的概率只和。

有：

sum_isol(u)=∑v∈sons(u)isol(v)⋅p(u)1−p(u)⋅p(v)sum_pend(u)=∑v∈sons(u)(pend(v)−isol(v)⋅p(u)1−p(u))⋅p(v)\begin{aligned} sum\_isol(u) =& \sum_{v\in sons(u)} isol(v)\cdot\frac{p(u)}{1-p(u)}\cdot p(v)\\ sum\_pend(u) =& \sum_{v\in sons(u)} (pend(v)-isol(v)\cdot\frac{p(u)}{1-p(u)})\cdot p(v) \end{aligned}

那么uu的孙子的贡献就是：

∑v∈sons(u)sum_isol(v)⋅p(u)⋅isol(u)1−p(v)+∑v∈sons(u)sum_pend(v)⋅p(u)⋅pend(u)−isol(u)p(v)1−p(v)1−p(v)\begin{aligned} &\sum_{v\in sons(u)} sum\_isol(v)\cdot p(u)\cdot\frac{isol(u)}{1-p(v)}\\ +&\sum_{v\in sons(u)} sum\_pend(v)\cdot p(u)\cdot\frac{pend(u) - isol(u)\frac{p(v)}{1-p(v)}}{1-p(v)} \end{aligned}

对于爷爷，由于只有一个爷爷，直接分两种情况计算（设v=fa(u)）v=fa(u)）：

p(u)⋅p(v)⋅p(fa(v))⋅isol(u)1−p(v)⋅iso(fa(v))1−p(v)+p(u)⋅(1−p(v))⋅p(fa(v))⋅pend(u)−isol(u)p(v)1−p(v)1−p(v)⋅pend(fa(v))−isol(fa(v))p(v)1−p(v)1−p(v)\begin{aligned} &p(u)\cdot p(v)\cdot p(fa(v))\cdot\frac{isol(u)}{1-p(v)}\cdot\frac{iso(fa(v))}{1-p(v)}\\ +&p(u)\cdot(1-p(v))\cdot p(fa(v))\cdot\frac{pend(u)-isol(u)\frac{p(v)}{1-p(v)}}{1-p(v)}\cdot\frac{pend(fa(v))-isol(fa(v))\frac{p(v)}{1-p(v)}}{1-p(v)} \end{aligned}

对于兄弟，同样分两种情况计算：

p(u)⋅[sum_isol(fa(u))−isol(u)⋅p(fa(u))1−p(fa(u))⋅p(u)]⋅isol(u)1−p(fa(u))+p(u)⋅[sum_pend(fa(u))−(pend(u)−isol(u)⋅p(fa(u))1−p(fa(u)))⋅p(u)]⋅pend(u)−isol(u)p(fa(u))1−p(fa(u))1−p(fa(u))\begin{aligned} &p(u)\cdot [sum\_isol(fa(u))-isol(u)\cdot\frac{p(fa(u))}{1-p(fa(u))}\cdot p(u)]\cdot\frac{isol(u)}{1-p(fa(u))}\\ +&p(u)\cdot [sum\_pend(fa(u))-(pend(u)-isol(u)\cdot\frac{p(fa(u))}{1-p(fa(u))})\cdot p(u)]\cdot \frac{pend(u) - isol(u)\frac{p(fa(u))}{1-p(fa(u))}}{1-p(fa(u))} \end{aligned}

3类点

3类点与uu完全独立，所以我们计算：

  • exp_all(u)exp\_all(u)为uu的子树内（除根）的期望叶子个数；
  • exp_sons(u)exp\_sons(u)为uu的儿子的期望叶子个数。

exp_all(u)=∑v∈sons(u)(exp_all(v)+pend(v)⋅p(v))exp_sons(u)=∑v∈sons(u)pend(v)⋅p(v)\begin{aligned} exp\_all(u) &= \sum_{v\in sons(u)} (exp\_all(v) + pend(v)\cdot p(v))\\ exp\_sons(u) &= \sum_{v\in sons(u)} pend(v)\cdot p(v) \end{aligned}

对于子树内的三类点，我们枚举所有子节点，则贡献为：

∑v∈sons(u)[exp_all(v)−exp_sons(v)]⋅p(u)⋅pend(u)\sum_{v\in sons(u)} [exp\_all(v)-exp\_sons(v)]\cdot p(u)\cdot pend(u)

对于子树外的三类点，我们在DFS的时候维护一个prepre来表示外面的三类点总期望，则子树外贡献为：

pre⋅p(u)⋅pend(u)pre\cdot p(u)\cdot pend(u)

prepre在前往一个儿子的时候，每次会增加uu的兄弟、uu的爷爷和uu的其他儿子的子孙。

故prepre的增量为（从uu到uu的儿子vv）：

exp_sons(fa(u))−p(u)⋅pend(u)+p(fa(fa(u)))⋅pend(fa(fa(u)))+exp_all(u)−exp_all(v)−exp_sons(u)\begin{aligned} &exp\_sons(fa(u)) - p(u)\cdot pend(u)\\ +&p(fa(fa(u)))\cdot pend(fa(fa(u)))\\ +&exp\_all(u)-exp\_all(v)-exp\_sons(u) \end{aligned}

这样就可以做出来了，但我考试的时候怎么可能写出来呢？

时间复杂度O(nlog⁡MOD)O(n\log MOD)，常数爆炸。

肯定有好方法！

看了下题解，大体思路差不多，但是简单很多，啥时候研究一下。

Code

E.cpp

Shit Mountain 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MOD = 998244353, N = 1e5 + 1;
int n, p[N], ans, fa[N]
, isol[N]/*neighbor死光*/
, pend[N]/*只有一个neighbor*/
, exp_all[N]/*子树内（除根）的期望叶子个数*/
, exp_sons[N]/*儿子期望叶子个数*/
, sum_isol[N]/*儿子只跟爸爸相连且儿子和爸爸都活着的概率和*/
, sum_pend[N]/*儿子只跟除了爸爸的相连，且儿子活爸爸死的概率和*/;
vector<int> G[N];
inline int fpow(int a, int b){
    int x = 1;
    while (b){
        if (b & 1) x = (LL)x * a % MOD;
        a = (LL)a * a % MOD;
        b >>= 1;
    }
    return x;
}
inline int inv(int a){
    return fpow(a, MOD - 2);
}
void Dfs1(int u){
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        isol[u] = (LL)isol[u] * (MOD + 1 - p[v]) % MOD;
        if (v != fa[u]){
            fa[v] = u;
            Dfs1(v);
            exp_all[u] = ((LL)exp_all[u] + exp_all[v] + (LL)pend[v] * p[v] % MOD) % MOD;
            exp_sons[u] = (exp_sons[u] + (LL)pend[v] * p[v] % MOD) % MOD;
            sum_isol[u] = (sum_isol[u] 
                + (LL)isol[v] * p[v] % MOD * p[u] % MOD * inv(MOD + 1 - p[u]) % MOD) % MOD;
            sum_pend[u] = (sum_pend[u]
                + (LL)(pend[v] + MOD - (LL)isol[v] * p[u] % MOD * inv(MOD + 1 - p[u]) % MOD) % MOD
                * p[v] % MOD) % MOD;
        }
    }
    // printf(">>u = %d, sum_isol = %d\n", u, (LL)sum_isol[u]*32%MOD);
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        pend[u] = (pend[u] + (LL)isol[u] * inv(MOD + 1 - p[v]) % MOD * p[v]) % MOD;
    }
    // printf("u = %d, isol = %d, pend = %d\n", u, (LL)isol[u] * 8 % MOD, (LL)pend[u] * 8 % MOD);
}
void Dfs2(int u, int pre){
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        

        // 相邻点
        int del = ans;
        ans = (ans + (LL)p[u] * p[v] % MOD 
        * isol[u] % MOD * isol[v] % MOD
        * inv(MOD + 1 - p[u]) % MOD * inv(MOD + 1 - p[v]) % MOD) % MOD;
        
        // printf("u = %d, v = %d, del0 = %d\n",u,v,(LL)(ans + MOD - del) * 32 % MOD);


        if (v != fa[u]){
            del = ans;
            ans = (ans + (LL)sum_isol[v] * p[u] % MOD 
            * isol[u] % MOD * inv(MOD + 1 - p[v]) % MOD) % MOD;
            // printf("u = %d, v = %d, del1 = %d\n",u,v,(LL)(ans + MOD - del) * 32 % MOD);
            del = ans;
            // 孙子，儿子活
            ans = (ans + (LL)sum_pend[v] * p[u] % MOD
            * (pend[u] + MOD - (LL)isol[u] * inv(MOD + 1 - p[v]) % MOD * p[v] % MOD) % MOD * inv(MOD + 1 - p[v]) % MOD) % MOD;
            // 孙子，儿子死
            // printf("u = %d, v = %d, del2 = %d\n",u,v,(LL)(ans + MOD - del) * 32 % MOD);
            del = ans;
            ans = ((LL)ans + (LL)exp_all[v] * p[u] % MOD * pend[u] % MOD
            + MOD - (LL)exp_sons[v] * p[u] % MOD * pend[u] % MOD) % MOD;
            // printf("u = %d, v = %d, del3 = %d\n",u,v,(LL)(ans + MOD - del) * 32 % MOD);
            // 曾孙
        }else{ // 爷爷
            del = ans;
            ans = (ans + (LL)p[u] * p[fa[v]] % MOD * (
                (LL)p[v] * isol[fa[v]] % MOD * inv(MOD + 1 - p[v]) % MOD * isol[u] % MOD * inv(MOD + 1 - p[v]) % MOD 
                + 
                (LL)(MOD + 1 - p[v]) * (pend[u] + MOD - (LL)isol[u] * inv(MOD + 1 - p[v]) % MOD * p[v] % MOD) % MOD * inv(MOD + 1 - p[v]) % MOD
                * (pend[fa[v]] + MOD - (LL)isol[fa[v]] * inv(MOD + 1 - p[v]) % MOD * p[v] % MOD) % MOD * inv(MOD + 1 - p[v]) % MOD
                ) % MOD
            ) % MOD;
            // printf("u = %d, delfa = %d\n",u,(LL)(ans+MOD-del)*32%MOD);
        }

        
    }
    int del = ans;
    if (fa[u]) ans = (ans + (LL)(sum_isol[fa[u]] + MOD - (LL)isol[u] * p[u] % MOD * p[fa[u]] % MOD * inv(MOD + 1 - p[fa[u]]) % MOD) % MOD
     * p[u] % MOD * isol[u] % MOD * inv(MOD + 1 - p[fa[u]]) % MOD) % MOD;
    
    if (fa[u]) ans = (ans 
        + (LL)(sum_pend[fa[u]] + MOD - (LL)(pend[u] + MOD - (LL)isol[u] * p[fa[u]] % MOD * inv(MOD + 1 - p[fa[u]]) % MOD) % MOD
     * p[u] % MOD) % MOD
     * p[u] % MOD * (pend[u] + MOD - (LL)isol[u] * inv(MOD + 1 - p[fa[u]]) % MOD * p[fa[u]] % MOD) % MOD * inv(MOD + 1 - p[fa[u]]) % MOD) % MOD;
    // 兄弟
    // printf("u = %d, del5 = %d\n",u,(LL)(ans+MOD-del) * 8 % MOD);
    // 之前较远的节点
    del = ans;
    ans = (ans + (LL)pre * p[u] % MOD * pend[u] % MOD) % MOD;
    // printf("u = %d, del4 = %d\n",u,(LL)(ans + MOD - del) * 32 % MOD);
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if (v != fa[u]){
            int now = pre;
            // del = now;
            now = (now + (LL)pend[fa[fa[u]]] * p[fa[fa[u]]] % MOD) % MOD; // 爷爷
            // printf("u = %d, delnow = %d\n",u,(LL)(now + MOD - del) * 8 % MOD);
            if (fa[u]) now = ((LL)now + exp_sons[fa[u]] + MOD - (LL)pend[u] * p[u] % MOD) % MOD; // 兄弟
            
            now = ((LL)now + exp_all[u] + MOD - exp_sons[u] + MOD - exp_all[v]) % MOD; // 儿子
            
            Dfs2(v, now);
        }
    }
}
signed main(){
    // cout << "1/8 = " << inv(8) << endl;
    // cout << (LL)8 * inv(45) % MOD << endl;
    // freopen("test.in", "r", stdin);
    int t; cin >> t;
    while (t--){
        ans = 0;
        cin >> n;
        for (int i = 0; i <= n; ++i){
            fa[i] = 0, isol[i] = 1, pend[i] = 0, exp_sons[i] = 0;
            exp_all[i] = 0, sum_isol[i] = 0, sum_pend[i] = 0;
        }
        for (int i = 1; i <= n; ++i){
            int x, y;
            cin >> x >> y;
            p[i] = (LL)(y - x) * inv(y) % MOD;
            G[i].clear();
        }
        for (int i = 1; i < n; ++i){
            int u, v; cin >> u >> v;
            G[u].push_back(v), G[v].push_back(u);
        }
        Dfs1(1);
        Dfs2(1, 0);
        // cout <<":::";
        cout << (LL)ans * inv(2) % MOD << endl;
    }
    return 0;
}/*
1
4
1 2
1 2
1 2
1 2
1 2
1 3
1 4
*/

BruteForce

Show 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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MOD = 998244353, N = 1e5 + 1;
int n, p[N], fa[N], ans, res, sum = 0; // u, u, fa; p是存活的概率
bool die[N], vis[N];
vector<int> G[N];
inline int fpow(int a, int b){
    int x = 1;
    while (b){
        if (b & 1) x = (LL)x * a % MOD;
        a = (LL)a * a % MOD;
        b >>= 1;
    }
    return x;
}
inline int inv(int a){
    return fpow(a, MOD - 2);
}
void Dfs(int u){
    vis[u] = 1;
    int deg = 0;
    for (int i = 0; i < G[u].size(); ++i){
        int v = G[u][i];
        if (!die[v]) ++deg;
        if (!vis[v] && !die[v]) Dfs(v);
    }
    if (deg == 1) ++res;
}
signed main(){
    // cout << "1/3 = " << inv(3) << endl;
    // cout << (LL)8 * inv(45) % MOD << endl;
    // freopen("test.in", "r", stdin);
    int t; cin >> t;
    while (t--){
        ans = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i){
            int x, y;
            cin >> x >> y;
            p[i] = (LL)(y - x) * inv(y) % MOD;
            G[i].clear(), fa[i] = 0;
        }
        for (int i = 1; i < n; ++i){
            int u, v; cin >> u >> v;
            G[u].push_back(v), G[v].push_back(u);
        }
        for (int i = 0; i < (1 << n); ++i){
            int x = i, pr = 1;
            for (int j = 1; j <= n; ++j, x >>= 1){
                die[j] = x & 1;
                if (die[j]) pr = (LL)pr * (MOD + 1 - p[j]) % MOD;
                else pr = (LL)pr * p[j] % MOD;
                vis[j] = 0;
            }
            res = 0;
            for (int j = 1; j <= n; ++j){
                if (!vis[j] && !die[j]){
                    Dfs(j);
                }
            }
            sum += res * (res - 1) / 2;
            ans = (ans + (LL)res * (res - 1) % MOD * inv(2) % MOD * pr % MOD) % MOD;
        }
        // cout <<":::";
        cout << ans << endl;
        // cout << "sum = " << sum << endl;
    }
    return 0;
}/*
1
4
1 2
1 2
1 2
1 2
1 2
1 3
1 4
*/

datamaker

Show Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
const int n = 6;
signed main(){
    srand(time(0));
    cout << 1 << endl;
    cout << n << endl;
    for (int i = 1; i <= n; ++i){
        cout << "1 2" << endl;
    }
    for (int i = 1; i < n; ++i){
        cout << (rand() % i) + 1 << " " << i + 1 << endl;
    }
    return 0;
}

F Towering Arrays

Solution

对于一个数列，它的pp可以表示为

max⁡i{min⁡j(aj+∣i−j∣)}\max_i\{\min_j(a_j + \left| i - j\right|)\}

首先，求最小值的最大值，发现没什么思路，考虑二分pp，然后求最小要删去几个数，看看会不会比kk大。

我们假设确定了ii，这个时候我们发现要删去的数的个数是确定的。对于一个数aja_j，如果p>aj+1p > a_j + 1，那么这个数就在某些ii的时候不能存在，且它不能存在的范围是一个区间，所以我们可以考虑从左往右遍历所有的ii，动态维护左边和右边的不能存在的jj。

我们维护两个线段树，分别存左右两边对应坐标的数还有多久会离开/进入不能存在范围。具体见代码。线段树只需实现区间加，单点修改和区间最小值。

时间复杂度O(nlog⁡nlog⁡max⁡ai)O(n\log n\log\max{a_i})。

Code

Show 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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n;
bool working[N];
class SegTree{
private:
    int T[N << 2], lz[N << 2];
    inline void change(int k, int v){
        T[k] += v, lz[k] += v;
    }
    inline void pushup(int k){
        T[k] = min(T[k << 1], T[k << 1 | 1]);
    }
    inline void pushdown(int k){
        if (lz[k]){
            change(k << 1, lz[k]);
            change(k << 1 | 1, lz[k]);
            lz[k] = 0;
        }
    }
    void add(int k, int l, int r, int le, int ri, int v){
        if (l >= le && r <= ri) return change(k, v);
        int mid = l + r >> 1;
        pushdown(k);
        if (mid >= le) add(k << 1, l, mid, le, ri, v);
        if (mid < ri) add(k << 1 | 1, mid + 1, r, le, ri, v);
        pushup(k);
    }
    void set(int k, int l, int r, int p, int v){
        if (l == r) return T[k] = v, void();
        int mid = l + r >> 1;
        pushdown(k);
        if (mid >= p) set(k << 1, l, mid, p, v);
        else set(k << 1 | 1, mid + 1, r, p, v);
        pushup(k);
    }
    int findzero(int k, int l, int r){
        if (T[k] > 0) return -1;
        if (l == r) return l;
        int mid = l + r >> 1;
        pushdown(k);
        // printf("k = %d, l = %d, r = %d, s1 = %d, s2 = %d\n",k,l,r,T[k << 1], T[k << 1 | 1]);
        if (T[k << 1] <= 0) return findzero(k << 1, l, mid);
        else return findzero(k << 1 | 1, mid + 1, r);
    }
public:
    inline void init(int x){
        for (int i = 0; i <= (x << 2); ++i) T[i] = 0x3f3f3f3f, lz[i] = 0;
    }
    void Add(int l, int r, int v){
        if (l > r || l > n || r < 1) return;
        add(1, 1, n, l, r, v);
    }
    int Findzero(){
        return findzero(1, 1, n);
    }
    void Set(int p, int v){
        set(1, 1, n, p, v);
    }
    void print(int k, int l, int r){
        if (l == r) return printf("x = %d, val = %d\n",l, T[k]), void();
        int mid = l + r >> 1;
        pushdown(k);
        print(k << 1, l, mid), print(k << 1 | 1, mid + 1, r);
    }
} Tl, Tr;
int A[N], k;
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n >> k;
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
        }
        int l = 1, r = 1e9;
        while (l < r){
            Tl.init(n), Tr.init(n);
            int mid = l + r + 1 >> 1;
            int ans = 0x3f3f3f3f, res = 0;
            for (int i = 1; i <= n; ++i){
                if (mid > A[i] + 1) Tr.Set(i, i - 1 - (mid - A[i] - 1));
                working[i] = 0;
            }
            for (int i = 1; i <= n; ++i){
                int now = Tr.Findzero();
                while (~now){
                    working[now] = 1;
                    res++;
                    Tr.Set(now, 0x3f3f3f3f);
                    Tr.Add(now + 1, n, -1);
                    now = Tr.Findzero();
                }
                now = Tl.Findzero();
                while (~now){
                    working[now] = 0;
                    res--;
                    Tl.Set(now, 0x3f3f3f3f);
                    Tl.Add(1, now - 1, -1);
                    now = Tl.Findzero();
                }
                // if (mid==3) printf("i = %d, res = %d\n",i,res);
                if (A[i] >= mid) ans = min(ans, res);
                if (working[i]){
                    Tl.Set(i, mid - A[i] - 1);
                }else Tl.Add(1, i, -1), Tr.Add(i + 1, n, -1);
            }
            if (ans <= k) l = mid;
            else r = mid - 1;
        }
        // cout << ":::::";
        cout << l << endl;
    }
    return 0;
}/*
1
3 1
1 1 3
*/