2025牛客暑期多校训练营4 补题

For the Treasury!

假设我们决定将原数组中位于（从1开始的）下标 $x_1, x_2, \dots, x_k$ (这里假定 $x_1 < x_2 < \dots < x_k$) 的 $k$ 个元素，移动到新数组的 $1, 2, \dots, k$ 位置，同时保持它们的相对顺序。将位于 $x_1$ 的元素移到位置 $1$，需要 $x_1 - 1$ 次交换。将位于 $x_2$ 的元素移到位置 $2$，需要 $x_2 - 2$ 次交换。 … 将位于 $x_i$ 的元素移到位置 $i$，需要 $x_i - i$ 次交换。因此，总的最小交换次数 $\text{num}$ 为： $\text{num} = \sum_{i=1}^{k} (x_i - i) = \left(\sum_{i=1}^{k} x_i\right) - \left(\sum_{i=1}^{k} i\right)$ 我们的目标函数变为最大化： $\left(\sum_{i=1}^{k} a_{x_i}\right) - c \cdot \left( \left(\sum_{i=1}^{k} x_i\right) - \left(\sum_{i=1}^{k} i\right) \right)$ 整理一下这个式子： $\left(\sum_{i=1}^{k} a_{x_i} - c \cdot x_i\right) + c \cdot \left(\sum_{i=1}^{k} i\right)$ $= \left(\sum_{i=1}^{k} (a_{x_i} - c \cdot x_i)\right) + c \cdot \frac{k(k+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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    ll n, k, c;
    cin >> n >> k >> c;
    vector<ll> a(n);
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= c * (i + 1);
    }
    sort(a.begin(), a.end(), greater<ll>());
    ll ans = 0;
    for (ll i = 0; i < k; i++) {
        ans += a[i];
    }
    cout << ans + c * (k * (k + 1) / 2) << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

首先找到起点和终点可达的地点。

接着从最右侧开始寻找死局的点。

这种顺序保证了，处理第 j 列时，右侧的死局都已经被标记过了。

我们以当前列中所有 0 为起点，逆向行走，标记所有可达点，同时标记已来过，对于可达点，同时计算他视野能看到的最右侧是否小于当前列，如果小于，那么这个点就是死局。

  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


#include <bits/stdc++.h>
#define rep(x,l,r) for(int x=l;x<=r;++x)
#define per(x,r,l) for(int x=r;x>=l;--x)
#define mk(x,y) make_pair(x,y)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define max(x,y) ((x)<(y)?(y):(x))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const ll N=3e5+7,M=1e7+7,mod=998244353;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);
vector<vector<int>> a,vis1,vis2,dis;
int dx[5]={-1,0,1,0},dy[5]={0,-1,0,1},n,m,k,flag,ans=0;
bool check(int x,int y)
{
    if(x<1 || x>n || y<1 || y>m || a[x][y]==1) return false;
    return true;
}
void dfs(int x,int y)
{
    vis1[x][y]=1;
    rep(i,0,2) {
        int xx=x+dx[i],yy=y+dy[i];
        if(check(xx,yy) && !vis1[xx][yy]) {
            dfs(xx,yy);
        }
    }
}
void dfs2(int x,int y)
{
    if(ans)  return;
    dis[x][y]=flag;
    rep(i,0,2) {
        int xx=x+dx[i],yy=y+dy[i];
        if(check(xx,yy) && vis2[xx][yy]) {
            int mx=min(m,yy+k);
            if(mx<=flag)  ans=1;
        }
        if(check(xx,yy) && vis2[xx][yy] && !vis1[xx][yy] && dis[xx][yy]==0) {
            dfs2(xx,yy);
        }
    }
}
void dfs3(int x,int y)
{
    vis2[x][y]=1;
    rep(i,0,3) {
        if(i==1)  continue;
        int xx=x+dx[i],yy=y+dy[i];
        if(check(xx,yy) && !vis2[xx][yy]) {
            dfs3(xx,yy);
        }
    }
}
void solve()
{
    ans=0;
    string s;
    cin>>n>>m>>k;
    a.resize(n+1,vector<int>(m+1,0));
    vis1.resize(n+1,vector<int>(m+1,0));
    vis2.resize(n+1,vector<int>(m+1,0));
    dis.resize(n+1,vector<int>(m+1,0));
    rep(i,1,n) {
        cin>>s;
        rep(j,1,m) {
            a[i][j] = s[j-1] - '0';
        }
    }
    dfs(1,m);
    dfs3(1,1);
    per(j,m,1) {
        flag=j;
        if(j==m)  --flag;
        rep(i,1,n) {
            if(a[i][j]==1 || vis2[i][j]==0 || dis[i][j] || vis1[i][j])  continue;
            dfs2(i,j);
            if(ans)  break;
        }
        if(ans)  break;
    }
    if(ans)  printf("Yes\n");
    else printf("No\n");
    a.clear();
    vis1.clear();
    vis2.clear();
    dis.clear();
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

Ghost in the Parentheses

下列讲解由哈基米呈现：

我们的目标是计算一个给定的合法括号序列 $s$ (长度为 $N$)，在每个字符有 $1/2$ 概率变成 ? 后，能够被唯一还原的概率。

1. 基本定义与公式

令 $s$ 为原始的合法括号序列。
令 $s_q$ 为随机化后带有 ? 的字符串。
总共可能产生的 $s_q$ 有 $2^N$ 种，每种的概率都是 $(1/2)^N$。
令 $C(\text{unique})$ 为可以被唯一还原成 $s$ 的 $s_q$ 的数量。
所求概率 $P(\text{unique}) = \frac{C(\text{unique})}{2^N}$。

我们的核心任务是计算 $C(\text{unique})$。

2. “非唯一性”的根源

还原不唯一，当且仅当存在另一个合法的括号序列 $s’ (s’ \neq s)$，它与 $s$ 的差异点能被 $s_q$ 中的 ? 完全覆盖。

我们来分析最简单的导致非唯一性的情况：交换一对括号。

令 $v(c)$ 为字符的数值：$v(’(’) = +1$, $v(’)’) = -1$。
令 $S[k] = \sum_{l=1}^{k} v(s[l])$ 为 $s$ 的前缀和。因为 $s$ 合法，我们有 $S[k] \ge 0$ 对所有 $k$ 成立，且 $S[N]=0$。
假设我们选择一个 $s[i] = ‘(’$ 和一个 $s[j] = ‘)’$ (其中 $i < j$)，将它们交换，得到新序列 $s’$。
$s’$ 的前缀和 $S’[k]$ 与 $S[k]$ 的关系如下：
- $k < i \implies S’[k] = S[k]$
- $i \le k < j \implies S’[k] = S[k] - 2$ (因为位置 $i$ 的 $+1$ 变成了 $-1$)
- $k \ge j \implies S’[k] = S[k]$ (因为位置 $i$ 的变动和位置 $j$ 的变动抵消了)
为了使 $s’$ 也成为一个合法的括号序列，必须满足 $S’[k] \ge 0$ 对所有 $k$ 成立。这等价于： $$ \min_{k=i}^{j-1} S[k] - 2 \ge 0 \implies \min_{k=i}^{j-1} S[k] \ge 2 $$
结论：如果存在一对 $(i, j)$ 满足 $s[i] = ‘(’, s[j] = ‘)’, i < j$ 且 $\min_{k=i}^{j-1} S[k] \ge 2$，那么只要 $s[i]$ 和 $s[j]$ 同时变成 ?，还原就至少有两种可能性 ($s$ 和 $s’$)，从而导致非唯一性。

3. 构造性计数法 (Constructive Counting)

直接计算 $C(\text{unique})$ 很困难。代码采用了一种精妙的构造方法，将所有可唯一还原的配置（即 $s_q$）划分为若干个互不相交的集合，然后将它们的数量相加。

令 $I_L = {k \mid s[k] = ‘(’}$ 为所有左括号的位置集合。令 $I_R = {k \mid s[k] = ‘)’}$ 为所有右括号的位置集合。

集合 A：单侧 ? 的情况

$U_L$: 只有左括号变成 ? 的配置（不含空集）。
- 任何一个 ? 只能还原成 (，否则总和 $S[N]$ 将不为0。因此还原是唯一的。
- 数量为 $|U_L| = 2^{|I_L|} - 1$。
$U_R$: 只有右括号变成 ? 的配置（不含空集）。
- 同理，还原是唯一的。
- 数量为 $|U_R| = 2^{|I_R|} - 1$。
$U_\emptyset$: 全都不变的配置。
- 数量为 $|U_\emptyset|=1$。

这三部分的总和为 $(2^{|I_L|} - 1) + (2^{|I_R|} - 1) + 1 = 2^{|I_L|} + 2^{|I_R|} - 1$。这对应代码中 ans 的初始值。

集合 B：精心构造的混合 ? 情况 为了处理同时有 ( 和 ) 变成 ? 的情况，我们为每一个左括号 $s[i]$ ($i \in I_L$) 构造一个专属的、可唯一还原的配置集合 $V_i$。

定义“弱点”: 令 $j_i = \min {k \mid k > i \text{ and } S[k] \le 1}$。这是位置 $i$ 之后第一个前缀和“脆弱”的位置。它的存在意味着对于区间 $[i, j_i-1]$ 内的所有位置 $k$，都有 $S[k] \ge 2$。
构造集合 $V_i$: 对于一个固定的 $i \in I_L$，集合 $V_i$ 中的配置 $s_q$ 必须满足以下所有条件：
1. $s[i]$ 必须变成 ?。
2. $i$ 是所有变成 ? 的左括号中，位置最小的那个。
3. 在 $s[j_i+1 \dots N]$ 中的右括号，至少有一个要变成 ?。
$V_i$ 的唯一性证明:
- 根据条件2，所有在 $i$ 之前的左括号都不能是 ?。
- 根据条件1，$s[i]$ 是 ?。如果试图将其错误地还原成 )，那么对于所有 $k \in [i, j_i-1]$，前缀和都会变为 $S[k]-2$。因为我们知道在这个区间内 $S[k] \ge 2$，所以 $S[k]-2 \ge 0$，前缀和仍然合法。
- 但是，到了弱点 $j_i$，前缀和会变成 $S[j_i]-2$。因为 $S[j_i] \le 1$，所以 $S[j_i]-2 < 0$，导致非法。
- 因此，$s[i]$ 处的 ? 只能被唯一地还原成 (。一旦它被确定，其他 ? 的还原方式也随之确定。
$V_i$ 的数量计算:
- 条件1和2固定了 $s[1 \dots i]$ 中哪些左括号是 ? (只有 $s[i]$ 是)。
- $s[1 \dots i-1]$ 中的右括号都不能是 ?。
- $s[i+1 \dots j_i]$ 中的所有字符都不能是 ?。
- $s[1 \dots i-1]$ 中的左括号可以任意变成 ?。数量：$2^{\text{count of ‘(’ in } [1, i-1]} = 2^{\text{pre}[i-1]}$。
- $s[j_i+1 \dots N]$ 中的右括号至少一个变成 ?。数量：$2^{\text{count of ‘)’ in } [j_i+1, N]} - 1 = 2^{\text{suf}[j_i+1]} - 1$。
- 因此，$|V_i| = 2^{\text{pre}[i-1]} \times (2^{\text{suf}[j_i+1]} - 1)$。
集合的互斥性:
- $V_i$ 和 $V_k$ ($i \neq k$) 是互斥的，因为它们“最小的?化左括号”的位置不同。
- $V_i$ 与 $U_L, U_R, U_\emptyset$ 也是互斥的，因为 $V_i$ 中必然同时包含变自 ( 和 ) 的 ?。

4. 最终公式

将所有互不相交的集合数量相加，得到 $C(\text{unique})$：

$$ C(\text{unique}) = \left( 2^{|I_L|} + 2^{|I_R|} - 1 \right) + \sum_{i \in I_L} \left( 2^{\text{pre}[i-1]} \times (2^{\text{suf}[j_i+1]} - 1) \right) $$

其中，pre[i-1][0] 是 $s[1 \dots i-1]$ 中左括号的数量，suf[j_i+1][1] 是 $s[j_i+1 \dots N]$ 中右括号的数量。

最后，将总数除以 $2^N$ 得到概率：

$$ P(\text{unique}) = \frac{C(\text{unique})}{2^N} = C(\text{unique}) \cdot (2^N)^{-1} \pmod{998244353} $$

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e6 + 7, mod = 998244353;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll a) {
    return qpow(a, mod - 2);
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    s = ' ' + s;
    vector<vector<int>> pre(n + 1, vector<int>(2, 0)), suf(n + 2, vector<int>(2, 0));
    vector<int> sum(n + 1, 0);
    deque<int> q;

    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1]; 
        if (s[i] == '(') {
            pre[i][0]++;
            sum[i] = sum[i - 1] + 1;
        } else {
            pre[i][1]++;
            sum[i] = sum[i - 1] - 1;
        }
        if (sum[i] <= 1) {
            q.push_back(i);
        }
    }


    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1];
        if (s[i] == ')') {
            suf[i][1]++;
        } else {
            suf[i][0]++;
        }
    }

    ll ans = (qpow(2, pre[n][0]) + qpow(2, pre[n][1]) - 1 + mod) % mod;
    for (int i = 1; i <= n; i++) {
        if (s[i] == ')') continue;
        while (!q.empty() && q.front() < i) {
            q.pop_front();
        }
        if (q.empty()) break;
        int j = q.front();
        ll tmp = (qpow(2, suf[j + 1][1]) - 1 + mod) % mod * qpow(2, pre[i - 1][0]) % mod;
        ans = (ans + tmp) % mod;
    }
    ans = ans * inv(qpow(2, n)) % mod;
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

I, Box

首先注意到范围极小，可以考虑大暴力。

判断是否有解很简单，每个联通块内的目标点和箱子数量必须相等，不然就是无解。

考虑遍历每个箱子，将该箱子通过最短路移动到任意一个目标点。

先不管路径上的其他箱子，将路径上的所有点赛入一个队列中。

从后往前遍历路径，如果当前该点上有箱子，就将其移动到上一个路径上。

  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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

char dir[4] = {'U', 'D', 'L', 'R'};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n + 1, vector<char>(m + 1));
    vector<vector<int>> vis(n + 1, vector<int>(m + 1, 0)), id(n + 1, vector<int>(m + 1, 0));
    vector<pair<int, int>> pos;
    pos.emplace_back(0, 0); 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '@' || a[i][j] == '!') {
                pos.emplace_back(i, j);
                id[i][j] = pos.size() - 1;
            }
        }
    }
    auto check = [&](int x, int y) {
        if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '#') return false;
        return true;
    };
    //联通块判断
    function<int(int, int)> com = [&](int x, int y) {
        vis[x][y] = 1;
        int res = 0;
        if (a[x][y] == '@') ++res;
        if (a[x][y] == '*') --res;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny) && !vis[nx][ny]) {
                res += com(nx, ny);
            }
        }
        return res;
    };
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check(i, j) && !vis[i][j]) {
                int res = com(i, j);
                if (res > 0) {
                    cout << "-1" << endl;
                    return;
                }
            }
        }
    }

    //开始构建移动过程
    deque<pair<int, int>> q;
    //从(x, y)到任意一个目标点
    function<bool(int, int)> dfs = [&](int x,int y) {
        vis[x][y] = 1;
        q.push_back({x, y});
        if(a[x][y] == '*') return 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny) && !vis[nx][ny]) {
                if (dfs(nx, ny)) return 1;
            }
        }
        q.pop_back();
        return 0;
    };
    //从 u 移动到 v 如何移动
    auto mov = [&](pair<int, int> u, pair<int, int> v) {
        for (int i = 0; i < 4; i++) {
            int nx = u.first + dx[i], ny = u.second + dy[i];
            if (nx == v.first && ny == v.second) {
                return make_pair(u, dir[i]);
            }
        }
        return make_pair(make_pair(-1, -1), ' ');
    };
    vector<pair<pair<int, int>, char>> ans, tmp;
    while(1) {
        int now = 0;
        for (int i = 1; i < pos.size(); i++) {
            auto [x, y] = pos[i]; 
            if (a[x][y] == '@') {
                now = i;
                break;
            }
        }
        if (now == 0) break; 
        auto [x, y] = pos[now];
        q.clear();
        fill(vis.begin(), vis.end(), vector<int>(m + 1, 0));
        dfs(x, y);
        int len = q.size();
        pair<int, int> lst = q.back();
        for (int i = len - 2; i >= 0; i--) {
            auto [nx, ny] = q[i];
            tmp.push_back(mov(q[i], q[i + 1]));
            if (a[nx][ny] == '@' || a[nx][ny] == '!') {
                auto [tx, ty] = lst;
                if (a[nx][ny] == '@') {
                    a[nx][ny] = '.';
                } else {
                    a[nx][ny] = '*';
                }
                if (a[tx][ty] == '.') {
                    a[tx][ty] = '@';
                } else {
                    a[tx][ty] = '!';
                }

                int blo = id[nx][ny];
                id[tx][ty] = blo;
                id[nx][ny] = 0;
                pos[blo] = make_pair(tx, ty);

                while(!tmp.empty()) {
                    ans.push_back(tmp.back());
                    tmp.pop_back();
                }
                lst = q[i];
            }            
        }
        while(!tmp.empty()) {
            ans.push_back(tmp.back());
            tmp.pop_back();
        }
    }
    cout << ans.size() << endl;
    for (auto &[p, d] : ans) {
        cout << p.first << " " << p.second << " " << d << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Determinantof01-Matrix

核心策略：先构造，后变换

算法的灵魂在于一个两步走的策略：首先，我们不直接构造最终的0-1矩阵，而是先构造一个更容易处理的整数矩阵 $A_{int}$，使其行列式为 $N$。然后，我们通过一系列保持行列式不变的行变换，将这个整数矩阵巧妙地“雕琢”成最终的0-1矩阵 $A_{final}$。

步骤一：构造“毛坯”矩阵 $A_{int}$

这一步的目标是建立一个结构简单且行列式为 $N$ 的基础矩阵。

1.1 矩阵结构

我们构造一个 $n \times n$ 的上三角矩阵 $A_{int}$ (代码中 $n=99$)。它的特点是：

主对角线元素几乎都为1：$a_{i,i} = 1$ for $i=1, \dots, n-1$。
主对角线最后一个元素为 $N$：$a_{n,n} = N$。
最后一列是一个特殊构造的整数序列 $c_1, c_2, \dots, c_n$。
所有其他元素均为0。

其形式如下：

$$ A_{int} = \begin{pmatrix} 1 & 0 & \cdots & 0 & c_1 \\ 0 & 1 & \cdots & 0 & c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & c_{n-1} \\ 0 & 0 & \cdots & 0 & N \end{pmatrix} $$

1.2 行列式计算

根据线性代数的基本性质，一个上三角矩阵的行列式等于其对角线元素的乘积。

$$ \det(A_{int}) = \underbrace{1 \times 1 \times \cdots \times 1}_{n-1 \text{ 个}} \times a_{n,n} = N $$

这样，我们就轻松地满足了 $\det(A) = N$ 的要求。

1.3 特殊序列 $c_i$ 的生成

最后一列的序列 $c$ 是算法的“秘密配方”，它是为了在第二步中被完美消解而设计的。我们定义一个辅助序列 $q_0, q_1, q_2, \dots$：

初始值: $q_0 = N$
递推关系: $$ q_{k+1} = \begin{cases} -q_k / 2 & \text{如果 } k \text{ 是偶数 (代码中 `tmp=0`)} \\ (-q_k + 1) / 2 & \text{如果 } k \text{ 是奇数 (代码中 `tmp=1`)} \end{cases} $$ 这里的除法是C++中的整数除法（向零取整）。

然后，用这个 $q$ 序列填充 $c$ 向量（即 $A_{int}$ 的最后一列）：

$c_n = q_0 = N$
$c_{n-1} = q_1$
$c_{n-2} = q_1$
$c_{n-3} = q_2$
$c_{n-4} = q_2$
…
通项公式: 对于 $i < n$, $c_i = q_{\lfloor(n-i)/2\rfloor+1}$。

步骤二：变换为最终0-1矩阵 $A_{final}$

这一步的目标是通过行变换，将 $A_{int}$ 改造为 $A_{final}$，同时保持行列式不变。

2.1 行变换规则

算法对 $A_{int}$ 的每一行 $R_i$ (从 $i=n$ 到 $1$) 应用一个变换，得到 $A_{final}$ 的对应行 $R’i$。 $$ R'_i \leftarrow R_i + R_{lst(i)-2} + R_{lst(i)-1} $$ 其中，$lst(i)$ 是小于或等于 $i$ 的最大奇数。这种行变换（将一行的倍数加到另一行）的行列式为1，因此 $\det(A{final}) = \det(A_{int}) = N$。

2.2 0-1化证明：魔法发生的地方

现在我们证明，为何经过上述变换后，矩阵的所有元素都变成了0或1。

前 $n-1$ 列： $A_{int}$ 的前 $n-1$ 列是单位矩阵的一部分，每行最多只有一个1。行变换本质上是将这些只包含0和1的行向量相加，结果自然也只可能是0或1。
最后一列：这是证明的核心。设 $d_i$ 是 $A_{final}$ 最后一列的元素。根据行变换规则：
$$ d_i = c_i + c_{lst(i)-2} + c_{lst(i)-1} $$
我们将 $c_i$ 的定义（用 $q$ 序列表示）代入。经过推导（如上一轮回答所示），可以得到一个统一的表达式：
$$ d_i \text{ 的值取决于 } q_j + 2q_{j+1} \text{ 这样的结构} $$
其中 $j$ 的取值与 $i$ 相关。现在我们来分析这个表达式的值：
- 当 $j$ 为偶数: $q_{j+1} = -q_j / 2$。 $q_j + 2q_{j+1} = q_j + 2(-q_j/2) = q_j - (q_j - (q_j \pmod{-2})) = q_j \pmod{-2}$。一个数对-2取模的结果只能是 $0$ 或 $-1$。由于我们是加行，符号可以被吸收，有效值为 $0$ 或 $1$。
- 当 $j$ 为奇数: $q_{j+1} = (-q_j+1)/2$。 $q_j + 2q_{j+1} = q_j + 2((-q_j+1)/2) = q_j + (-q_j+1) - ((-q_j+1) \pmod 2) = 1 - ((-q_j+1) \pmod 2)$。一个数对2取模的结果是 $0$ 或 $1$。所以表达式的值是 $1-0=1$ 或 $1-1=0$。

结论：在所有情况下，$d_i$ 的值都必然是 $0$ 或 $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
55
56
57


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    ll n;
    cin >> n;
    int siz = 99;
    vector<vector<ll>> a(siz + 1, vector<ll>(siz + 1, 0));
    for (int i = 1; i <= siz; i++) {
        a[i][i] = 1;
    }
    a[siz][siz] = n;
    ll now = n, tmp = 0;
    for (int i = siz; i >= 1; i--) {
        a[i][siz] = now;
        if (i & 1) {
            if (tmp == 0) {
                now = -now / 2;
            } else {
                now = (-now + 1) / 2;
            }
            tmp ^= 1;
        }
    }
    for (int i = siz; i >= 1; i--) {
        int lst = (i - 1) / 2 * 2 + 1;
        if (lst >= 2) {
            for (int j = lst - 2; j <= lst - 1; j++) {
                for (int k = 1; k <= siz; k++) {
                    a[i][k] += a[j][k];
                }
            }
        }
    }
    cout << siz << endl;
    for (int i = 1; i <= siz; i++) {
        for (int j = 1; j <= siz; j++) {
            cout << a[i][j];
            if (j < siz) cout << " ";
            else cout << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Ladder Challenge

注意到小明挑战第 $i$ 个选手时，最终他的得分 $x$ 会变为 $x_{new} = \lceil \frac{x_{old} + a_i}{2} \rceil$。

挑战顺序也固定，一定是从第一个分数严格大于他的选手开始，一直向后挑战。

最后的挑战次数即为最终得分和初始得分的差值。

离线所有查询后，统一操作显然更优。

将所有查询按初始分数大小排序，时刻更新挑战路径。

因为当前查询的初始分数 $x$ 是单调递增的，所以它所触发的挑战路径，相对于之前分数更低的查询所触发的路径，是一种“更强”的路径。这条更强的路径可以完全复用、甚至优化之前计算的结果。

为此，我们设计一个核心的辅助数组 p。p[i] 用来记忆化：在当前所有已处理的查询中，能够到达选手 $i$ 的最优分数（即最高分）。

我们首先用一个基准初始值（如0分）来初始化整个 p 数组。然后，在处理按 $x$ 排序后的每个查询时：

我们从该查询的初始分数 now = x 和起始挑战位置 st 开始模拟。
在模拟每一步挑战选手 i 时，我们计算出新的分数 now。
关键优化点：我们将新的 now 与 p[i] 比较。如果 now 与 p[i] 相等，说明我们这条从高分出发的“支线路径”已经完全汇入了之前计算出的“主干道路径” p。后续的演进将完全相同，因此可以立刻 break，停止模拟，极大地节省了时间。
如果 now 与 p[i] 不等（由于 $x$ 单调递增，now 只会更大），说明我们找到了一条更优的路径，于是更新 p[i] = now，并将这个更优的状态传递给下一步。

这个“路径合并”的思想是本算法能够高效运行的核心。

综上，完整算法流程如下：

离线与排序：读入所有查询 $(x, y)$，连同其原始编号，并按 $x$ 从小到大排序。
基准路径初始化：创建 p 数组，并模拟从0分开始挑战所有选手，填充 p 的初始值。
双指针与摊还计算： a. 使用一个指针 st 记录当前查询需要开始挑战的选手。由于查询已按 $x$ 排序，st 只会单向后移。 b. 遍历排好序的查询。首先根据 st 判断初始排名，若已满足目标则答案为0。 c. 否则，调用模拟函数，以当前查询的 $x$ 为初始值，从 st 开始更新 p 数组，直至路径合并 (p[i] == now)。 d. 根据目标排名 $y$ 计算出挑战终点为选手 $j = n - y + 1$。此时 p[j] 中已存有最优的最终分数。 e. 最终答案即为 p[j] - x。
输出：按原始查询顺序输出所有答案。

该算法的时间复杂度为 $O(Q \log Q + N)$。其中 $O(Q \log Q)$ 来自于查询排序，而后续所有的模拟和更新操作，由于路径合并的优化，其总计算量被摊还为线性的 $O(N)$。

 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 1e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n + 1), p(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = (p[i - 1] + a[i] + 1) / 2;
    }
    vector<pair<pair<ll, ll>, int>> que(q + 1);
    for (int i = 1; i <= q; i++){
        cin >> que[i].first.first >> que[i].first.second;
        que[i].second = i;
    }
    sort(que.begin() + 1, que.end());
    int st = 1;
    vector<ll> ans(q + 1, 0);
    auto func = [&](ll now, int x) {
        for (int i = x; i <= n; i++) {
            now = (now + a[i] + 1) / 2;
            if (p[i] == now) break;
            p[i] = now;
        }
    };
    for (int i = 1; i <= q; i++) {
        ll now = que[i].first.first;
        int t = que[i].first.second;
        int ori = que[i].second;
        while (st <= n && a[st] < now) st++;
        int rk = n - st + 1;
        if (st <= n && a[st] == now) rk++;
        if (rk < t) {
            ans[ori] = 0;
            continue;
        }
        func(now, st);
        int j = n - t + 1;
        ans[ori] = p[j] - now;
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Echoes of 24

好的，宗师将为你提炼最核心的思路。

核心策略：分类讨论

解法的灵魂在于根据路径长度进行分类讨论。设查询的路径为 $P(x, y)$，其节点数为 $|P(x, y)|$。我们以 24 为阈值，将问题一分为二：

长路径 ($|P(x, y)| \ge 24$): 路径过长，组合方式繁多，直接模拟不可行。此时问题被简化为一个启发式判断。
短路径 ($|P(x, y)| < 24$): 路径很短，节点数有限，可以直接暴力模拟所有可能的组合。

长路径策略：路径和近似

思路: 当路径足够长时，如果路径上所有大于1的数字之和都不大（例如，不超过24），那么通过加法和乘法也很难组合出24。这个观察是本策略的基石。
实现:
1. 忽略1: 在计算路径和时，我们只考虑权值大于1的节点。值为1的节点对求和没有贡献，对乘法也只是单位元。
2. 高效求和: 利用 DFS序 + 树状数组 的经典组合。将树上路径查询转化为线性序列上的区间查询，可以在 $O(\log N)$ 时间内求出路径上所有大于1的节点权值之和。
3. 判断: 若计算出的和 $S \le 24$，则认为可以组合出24；否则认为不可以。

短路径策略：位运算动态规划

思路: 路径短，节点数少于24个，我们可以精确计算出所有能组合出的数字。由于目标数字范围是0到24，这非常适合使用位运算动态规划 (Bitmask DP)。
实现:
1. 状态表示: 用一个long long整数 mask 作为位掩码。如果 mask 的第 $j$ 位是1，代表数字 $j$ 是可以被组合出来的。
2. 状态转移: 遍历路径上的每一个权值 $v$。对于当前的 mask，计算加入 $v$ 之后的新 mask'：
  - 加法: 新增的数字集合是原集合中每个数都加上 $v$。这等价于 mask << v。
  - 乘法: 新增的数字集合是原集合中每个数都乘以 $v$。这需要遍历 mask 的每一位。
  - 将加法和乘法得到的新集合（新的位掩码）合并，作为下一步的基础。
3. 判断: 走完路径后，检查最终 mask 的第24位是否为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
 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


#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;

const int N = 5e5 + 7, mod = 1e9 + 7;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> nx[n + 1], a(n + 1), fa(n + 1), dep(n + 1), dfn(n + 1), ed(n + 1), tr(n + 1), p(n * 2);
    vector<vector<int>> st(n + 1, vector<int>(21, 0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        nx[u].push_back(v);
        nx[v].push_back(u);
    }
    int tot = 0;
    function<void(int, int)> dfs = [&](int u, int f) {
        fa[u] = f;
        dep[u] = dep[f] + 1;
        dfn[u] = ++tot;
        for (int i = 1; i <= 20; i++) {
            st[u][i] = st[st[u][i - 1]][i - 1];
        }
        for (auto v : nx[u]) {
            if (v == f) continue;
            st[v][0] = u;
            dfs(v, u);
        }
        ed[u] = tot;
    };
    dfs(1, 0);
    auto add = [&](ll k, ll x) {
        for (int i = k; i <= n; i += i & -i) {
            tr[i] += x;
        }
    };
    auto query = [&](ll k) {
        ll res = 0;
        for (int i = k; i > 0; i -= i & -i) {
            res += tr[i];
        }
        return res;
    };
    auto lca = [&](int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i = 20; i >= 0; i--) {
            if (dep[st[u][i]] >= dep[v]) {
                u = st[u][i];
            }
        }
        if (u == v) return u;
        for (int i = 20; i >= 0; i--) {
            if (st[u][i] != st[v][i]) {
                u = st[u][i];
                v = st[v][i];
            }
        }
        return st[u][0];
    };
    auto update = [&](int u, ll val, int type) {
        if (val == 1) return;
        add(dfn[u], type * val);
        add(ed[u] + 1, -type * val);
    };
    for (int i = 1; i <= n; i++) {
        update(i, a[i], 1);
    }
    while (q--) {
        int op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            int z = lca(x, y);
            int len = dep[x] + dep[y] - 2 * dep[z] + 1;
            if (len >= 24) {
                ll sum = query(dfn[x]) + query(dfn[y]) - query(dfn[z]) - query(dfn[fa[z]]);
                if (sum <= 24) cout << "1\n";
                else cout << "0\n";
            } else {
                tot = 0;
                int now = x;
                while (now != z) {
                    p[++tot] = a[now];
                    now = fa[now];
                }
                p[++tot] = a[z];
                int siz = tot;
                now = y;
                while (now != z) {
                    p[++tot] = a[now];
                    now = fa[now];
                }
                reverse(p.begin() + siz + 1, p.begin() + tot + 1);
                ll sum = 0;
                if (p[1] <= 24) sum = (1ll << p[1]);
                for (int i = 2; i <= tot; i++) {
                    if (p[i] > 24 && p[i] != 1) {
                        sum = 0;
                        break;
                    }
                    ll tmp = 0;
                    if (p[i] <= 24) tmp = (sum << p[i]);
                    if (p[i] == 1) tmp |= sum;
                    else {
                        for (int j = 0; j * p[i] <= 24; j++) {
                            if ((sum >> j) & 1) tmp |= (1ll << (j * p[i]));
                        }
                    }
                    sum = tmp;
                    sum &= (1ll << 25) - 1; 
                }
                if ((sum >> 24) & 1) cout << "1\n";
                else cout << "0\n";
            }
        } else {
            update(x, a[x], -1);
            a[x] = y;
            update(x, a[x], 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}