2025 杭电多校 2 补题

数上的图

最多两次操作，如果两个数相同为 0，如果两个数 1 的数量或最后一位 1 的位置相同为 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


#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, x, y;
    cin >> n >> x >> y;
    int cnta = 0, cntb = 0;
    int lsta = -1, lstb = -1;
    for (int i = 61; i >= 0; i--) {
        if (x & (1LL << i)) cnta++, lsta = i;
        if (y & (1LL << i)) cntb++, lstb = i;
    }
    if (x == y) {
        cout << "0" << endl;
        return;
    }
    if (cnta == cntb) {
        cout << "1" << endl;
        return;
    } 
    if (lsta == lstb) {
        cout << "1" << endl;
    } else {
        cout << "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;
}

井

翻到 0 ，就能排除当前这行这这列了，翻到 1，需要在行和列中确定一个。

最优操作策略即为：先一直翻不同行不同列的，接着通过一次操作确定是行还是列，然后翻完。

易想到，每次操作都是翻 (i, i), 翻到 0 的贡献是次数乘以概率，翻到 1 之后，可能翻错一次，也可能直接翻到结束，可得 $\frac{1 + \dots + n}{n} + \frac{1}{2}(n + (n - 1)) = \frac{3n}{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


#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=7e5+7,M=1e7+7,mod=1e10+7;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);

void solve()
{
    ll n;
    cin>>n;
    db ans=(db)3*n/2;
    printf("%.4lf\n",ans);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

半

显然对于每个选手，答案即为，两场比赛他前面的人加合再减去两场都在他前面的人

构成一个二维偏序 $ \sum_{i=1}^{n} [p_j < p_i \land q_j < q_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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


#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=2e6+7,M=1e7+7,mod=1e10+7;
const ll inf=1e18+7;
const db eps=1e-8,PI=acos(-1.0);
pii a[N];
struct bit_tree {
    int tr[N],n;
    void init(int _n)
    {
        n=_n;
        rep(i,1,n)  tr[i]=0;
    }
    void add(int x,int v)
    {
        for(;x<=n;x+=x&-x) {
            tr[x]+=v;
        }
    }
    int ask(int x)
    {
        int res=0;
        for(;x;x-=x&-x) {
            res+=tr[x];
        }
        return res;
    }
}tr;
int ans[N];
void solve()
{
    vector<pair<pii,int>> b;
    int n,x;
    cin>>n;
    tr.init(n);
    rep(i,1,n)  cin>>x,a[x].first=n-i+1;
    rep(i,1,n)  cin>>x,a[x].second=n-i+1;
    rep(i,1,n) {
        b.push_back({a[i],i});
    }
    sort(b.begin(),b.end());
    for(auto [x,id]:b) {
        int tmp=tr.ask(x.second);
        ans[id]=n-1-tmp;
        tr.add(x.second,1);
    }
    rep(i,1,n) {
        printf("%d ",ans[i]);
    }
    printf("\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}

苹果树

重链剖分，每次修改只需要对父亲 $Fa_x$ 与重儿子 $son_x$ 进行单点修改。所有非链顶节点都可以正确更新，对链顶节点额外单点查询即可。

  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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207


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

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

// --- 全局变量 ---
vector<int> nx[N]; // 邻接表存树
int a[N];          // 存储每个节点的“基础”权值
int d[N];          // 存储操作2中对节点x的增量y，这个增量会影响其轻儿子的真实权值
int dep[N];        // dep[i]: 节点i的深度
int fa[N];         // fa[i]: 节点i的父节点
int sz[N];         // sz[i]: 以节点i为根的子树大小
int son[N];        // son[i]: 节点i的重儿子（子树大小最大的儿子）
int pos[N];        // pos[i]: 节点i在线段树中的位置（DFS序）
int top[N];        // top[i]: 节点i所在重链的顶端节点
int rev[N];        // rev[i]: DFS序i对应的原始节点编号
int tot = 0;       // DFS序的计数器

// 线段树结构体
struct tr {
    int tr[N << 2]; // 线段树数组，存储区间最大值

    // 构建线段树
    void build(int now, int l, int r) {
        if (l == r) {
            // 叶子节点，其值为DFS序l对应的原始节点的a值
            tr[now] = a[rev[l]];
            return;
        }
        int mid = (l + r) >> 1;
        build(now << 1, l, mid);
        build(now << 1 | 1, mid + 1, r);
        // 从下往上更新，当前节点的值等于左右子节点的最大值
        tr[now] = max(tr[now << 1], tr[now << 1 | 1]);
    }

    // 单点更新
    // now: 当前线段树节点, [l,r]: 当前节点表示的区间, x: 要更新的点的DFS序, v: 增加的值
    void update(int now, int l, int r, int x, int v) {
        if (l == r) {
            // 找到目标叶子节点，更新权值
            tr[now] += v;
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            update(now << 1, l, mid, x, v);
        } else {
            update(now << 1 | 1, mid + 1, r, x, v);
        }
        // 从下往上更新路径上的最大值
        tr[now] = max(tr[now << 1], tr[now << 1 | 1]);
    }

    // 区间查询
    // now: 当前节点, [l,r]: 当前表示的区间, [x,y]: 要查询的区间
    int query(int now, int l, int r, int x, int y) {
        // 如果查询区间完全覆盖当前区间，直接返回当前节点的值
        if (l >= x && r <= y) {
            return tr[now];
        }
        int mid = (l + r) >> 1;
        int res = 0; // 注意：这里假设权值非负，否则应初始化为负无穷
        // 如果查询区间与左子区间有交集，递归查询左子树
        if (x <= mid) {
            res = query(now << 1, l, mid, x, y);
        } 
        // 如果查询区间与右子区间有交集，递归查询右子树，并取最大值
        if (y > mid) {
            res = max(res, query(now << 1 | 1, mid + 1, r, x, y));
        }
        return res;
    }
};

// 第一次DFS：计算 fa, dep, sz, son
void dfs1(int x, int f) {
    fa[x] = f;           // 记录父节点
    dep[x] = dep[f] + 1; // 计算深度
    sz[x] = 1;           // 初始化子树大小为1（自身）
    for (auto v : nx[x]) {
        if (v == f) continue; // 避免向上遍历
        dfs1(v, x);        
        // 寻找重儿子：如果v的子树比当前记录的重儿子的子树还大，则更新重儿子
        son[x] = (sz[v] > sz[son[x]]) ? v : son[x];
        sz[x] += sz[v];    // 更新子树大小
    }
}

// 第二次DFS：计算 top, pos, rev，进行重链剖分
void dfs2(int x, int t) {
    pos[x] = ++tot; // 分配DFS序
    top[x] = t;     // 记录所在重链的顶点
    rev[tot] = x;   // 记录DFS序对应的节点
    if (son[x]) {
        // 优先遍历重儿子，保证重链上的DFS序连续
        dfs2(son[x], t);
    } else return; // 如果是叶子节点，返回
    // 遍历轻儿子
    for (auto v : nx[x]) {
        if (v == fa[x] || v == son[x]) continue;
        // 轻儿子会开启一条新的重链，其顶点就是它自己
        dfs2(v, v);
    }
}

// 路径查询函数
int ask(int x, int y, tr &t) {
    int res = 0; // 同样，假设权值非负
    // 当x和y不在同一条重链上时，循环向上跳
    while (top[x] != top[y]) {
        // 让x成为所在重链深度较深的那个节点
        if (dep[top[x]] < dep[top[y]]) {
            swap(x, y);
        }
        // 查询x所在重链从top[x]到x这一段的最大值
        res = max(res, t.query(1, 1, tot, pos[top[x]], pos[x]));
        // 关键：top[x]是它父亲的轻儿子，需要计算它的真实权值
        res = max(res, a[top[x]] + d[fa[top[x]]]);
        // x跳到其所在重链顶点的父节点，进入上一条链
        x = fa[top[x]];
    }
    // 循环结束后，x和y在同一条重链上
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    // 查询同一条重链上，从x到y的最大值
    res = max(res, t.query(1, 1, tot, pos[x], pos[y]));
    // 关键：如果x不是根，且x是它父亲的轻儿子，也需要计算它的真实权值
    // (这种情况发生在x,y一开始就在同一条链，且x不是链顶)
    if (fa[x] != 0 && son[fa[x]] != x) res = max(res, a[x] + d[fa[x]]);
    return res;
}

// 更新辅助函数
void add(int x, int v, tr &t) {
    if (x == 0) return; // 安全检查，根的父节点为0，叶子的重儿子为0
    // 在线段树中对节点x的DFS序位置进行更新
    t.update(1, 1, tot, pos[x], v);
    // 同时更新基础权值数组a
    a[x] += v;
}

// 每个测试用例的主函数
void solve() {
    int n, m;
    cin >> n >> m;
    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);
    }

    tr t;
    // 1. 树链剖分预处理
    dfs1(1, 0);
    dfs2(1, 1);
    // 2. 构建线段树
    t.build(1, 1, n);

    // 3. 处理m个操作
    while(m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            // 查询操作
            cout << ask(x, y, t) << endl;
        } else {
            // 更新操作
            d[x] += y;
            add(fa[x], y, t);
            add(son[x], y, t);
        }
    }

    // --- 多组测试数据，清空全局变量 ---
    tot = 0;
    for (int i = 1; i <= n; i++) {
        nx[i].clear();
        a[i] = 0;
        d[i] = 0;
        dep[i] = 0;
        fa[i] = 0;
        sz[i] = 0;
        son[i] = 0;
        pos[i] = 0;
        top[i] = 0;
        rev[i] = 0;
    }
}

int main() {
    // 快速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t; // 读取测试用例数量
    while (t--) solve();
    return 0;
}

子集

沙吊卡内存题

异或和，易想到线性基来解决，同时数组极小，考虑暴力处理每种可能下的线性基。

同时注意到选取元素时，元素之间要么间隔只能为 1 或 2，因为大于 2 时，中间的元素进入线性基一定更优。

注意到过程中产生的线性基个数为 $g_i = g_{i-2} + g_{i-3}$，$g_50 + g_49$ 也仅仅 1221537，足够完成。

 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


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

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

struct Basis {
    vector<ll> b;
    
    Basis() {
        b.assign(64, 0);
    }

    void add(ll x) {
        for (int i = 63; i >= 0; i--) {
            if ((x >> i) & 1) {
                if (!b[i]) {
                    b[i] = x;
                    return;
                }
                x ^= b[i];
            }
        }
    }

    ll query() {
        ll res = 0;
        for (int i = 63; i >= 0; i--) {
            res = max(res, res ^ b[i]);
        }
        return res;
    }

};

ll ans, a[51];
int n;

void dfs(int x, Basis t) {
    if (x > n) return;
    t.add(a[x]);
    ans = max(ans, t.query());
    dfs(x + 2, t);
    dfs(x + 3, t);
}

void solve() {    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    ans = 0;
    Basis t1, t2;
    dfs(1, t1);
    dfs(2, t2);
    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;
}