【暑假集训】【模拟赛总结】lgjOI 7.14

· · 个人记录

68+100+35+0 = 203。 rk 10 左右吧。

第一题怒挂 32pts，像傻子。

T3

一道贪心。感觉考场上也推了和正解差不多的性质，但是总结出来的策略大大滴不对，没见过，我太菜。

如果把所有格子都用 x_0+y_0= k 的斜线划分，会发现机器人只能沿着当前斜线走，或者跳到 x_0+y_0=k+2。这个时候贪心来了：对于一个机器人 A，应该先吃同斜线的，吃不了的话就去另一条。可以大概理解一下：如果不吃，那么还需要至少一个机器人 B 处理斜线上的。但是如果机器人 A 走与 B 一样的路径，就可以省下来一段路了。

代码很简单：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
set<int>s[N];
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin>>T;
    while(T --) {
        int n,m; cin>>n>>m;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                char ch; cin>>ch;
                if(ch == '1') s[i+j].insert(i);
            }
        }
        int ans = 0;
        for(int i=1;i<=n+m;i++) {
            if(s[i+1].empty()) continue;
            int _i = i; ans++;
            for(int j=1;j<=n;j++) {
                s[_i+j].erase(j);
                if(!s[_i+j].empty() && *s[_i+j].rbegin() > j) _i--;
                else _i++;
            }
        }
        cout<<ans<<"\n";
    } 
    return 0;
}

T4 套路题。

参考联合省选 2024 D1T2。看到异或，想想 01trie。

以下的 dp 都是不考虑前缀的情况。比如数为 100111 时，考虑到第 4 个，就把数看成 000111。

假定节点 u 与他父亲节点连的边的权值放在了 u 上，即 u 代表了该位为 0/1。设 dp_u 为在 u 的子树内选的方案数，会发现做不了，因为两个子树都选的情况无法统计。

归根结底，不可做是因为不知道子树的子树的情况，那我们手动选择两个子树呢？

设 dp_{x,y} 要求在这两个子树表示的数来选（两个子树都强制取）的方案数。

当 X 在 x,y 的儿子这一位上为 0 的时候，显然不能选异侧的子树，答案即为 dp_{lx,ly} + dp_{rx,ry}。

当 X 在 x,y 的儿子这一位上为 1 的时候（以下设 x 随便选为 s(x)，根据题意也就是 2^{sz(x)}-1）：

如果 x,y 是一个节点，“两个子树”其实就是一个子树。同侧可以随便选，异侧的答案就是 dp_{lx,rx}。

如果不是。我们可以分成这三类：选 2,3,4 个子树进行统计（lx 表示 x 的左子树，其他同理）。

为什么能这么做？总而言之，是因为限制的情况只有 lx,ry，ly,rx。正是因为 相同值异或为 0 这一性质，才不会使复杂度爆炸。复杂度即为 01trie 的节点个数 n\log n。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10, mod = 998244353;
struct M{
    int sz,ch[2];
}t[N*22];
int n,a[N],T;
int mi(int x,int k) {int p; return k?p=mi(x,k>>1),p*p%mod*(k&1?x:1)%mod:1;}

int s(int x){
    return (mi(2,t[x].sz) - 1 + mod) % mod;
}
int idx,rt;
void ins(int &p,int x,int k) {
    if(p == 0) p = ++idx;
    t[p].sz ++;
    if(k < 0) return ;
    ins(t[p].ch[((x&(1<<k)) > 0)],x,k-1);
}
int dp(int x,int y,int k) {
    if(x == 0 || y == 0) {
        return 0;
    }
    if(k < 0) {
      //这个是叶子节点的情况：也就是说第 0 位 0/1
      //如果我们回到上一位的视角，你就会发现限制什么的其实不存在，所以这个随便选是对的
        if(x == y) return s(x);
        return s(x) * s(y) % mod;
    }
    #define xls t[x].ch[0]
    #define xrs t[x].ch[1]
    #define yls t[y].ch[0]
    #define yrs t[y].ch[1]

    if((T & (1 << k)) == 0) {
        return (dp(xls,yls,k-1) + dp(xrs,yrs,k-1)) % mod;
    }

    if(x == y) {
        return (dp(xls,xrs,k-1) + s(xls) + s(xrs)) % mod;
    }
    int ans = 0, k1 = dp(xls,yrs,k-1), k2 = dp(xrs,yls,k-1);
    ans += s(xls) * s(yls) % mod + s(xrs) * s(yrs) % mod; // 同左， 同右
    ans += k1 + k2;
    ans += s(xls) * k2 % mod + s(yrs) * k2 % mod + s(xrs) * k1 % mod + s(yls) * k1 % mod;
    ans += k1 * k2 % mod;
    return ans % mod;
}
signed main() {
    cin>>n>>T;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) ins(rt,a[i],30);
    cout<<dp(rt,rt,30);
    return 0;
}