〔补题〕2025 钉耙编程春季联赛（2）

（赛中 + 补题记录）

不是题解，更多是做题心得与评价。

• 时间卡的也太紧了，STD 两倍时限，STD 用数组我用 std::map 就 T 了。。

• PI 节没出个关于 PI 的题

1001 学位运算导致的

和同学聊天时口胡的思路，可能有点混乱

所求的$y$，直接看是若干个数 or and and or 这样从左至右算出来的，当然这些数可能重复。or and 运算满足分配律，所以表达式总是可以化简为若干个东西 or 起来再 and，或者若干个东西 and 起来再 or。选后者，比较符合直觉。

可以先从极端想，若干个东西 and 出来只有一位。枚举每一位，把 and 起来还有这一位的东西都 and 起来，尽量让其它位都变 0。当然如果没办法都变成 0，就形成了要有这一位，另一位就必须存在这种关系（注意这关系没有传递性）。比如原来是 10 和 11（二进制），包含最低位的那只能是 11。这些数有个特点，要么独立要么包含，两两 and 不可能更小，不会有 110 和 011 同时出现。这样处理将得到 64 个大数。

现在的问题就是，64 个数，选择一些数做 or，运算结果比$x$ 大且最小。

大概要枚举前缀，每次给$x$ 加个 lowbit，能不能用这些数或出一个这样的前缀。而后几位不用考虑，不加那肯定最小。比如当前前缀是 V，or 和是 sum，必须始终 sum&V=sum，逐个遍历那 64 个数加入 sum，看最终 sum 是不是等于 V，等于那就说明这个前缀可以构造出来。所有可能的结果取最小值就是答案。

但是复杂度是 log 方的，枚举前缀一个 log，再枚举又一个 log，过不去。

道理是对的，但是方案有问题，可能哪里浪费了。

确实浪费了。每次给$x$ 加个 lowbit 可以假加，因为这个步骤的本质是把某个 0 变成 1，后面忽略。sum&V=sum 也可以假判断，或者说这个判断完全没必要。$x$ 有 1 就必须把这个数加上，没得选，就算加上去更大了也没办法，得加，不加上就没法满足那个条件。所以其实是唯一的，没必要判断。这样省了个 log。

现在的方案是，从高位到地位枚举$x$ 的二进制位。如果是 1 就加到 sum 里，否则是 0，可能产生答案，把这一位 0 虚拟地变成 1 并把对应的数虚拟地加到 sum 计算结果。所有可能的结果取最小值就是答案。

时间复杂度$\operatorname{O}[(n+q)\log V]$。

注意：mod 不要写 1e16 + 1029，这是个 double，精度丢完了。

Bonus: 出题人说优雅集对应拓扑，sol 相当于找一组拓扑基。

int n, q;
cin >> n >> q;
vector<ull> dp(64, -1);  // -1 相当于 1111...1111
while (n--) {
    ull x;
    cin >> x;
    for (int bit = 63; bit >= 0; bit--) {
        if (x >> bit & 1) {
            dp[bit] &= x;
        }
    }
}
ull ans = 0;
while (q--) {
    ull x;
    cin >> x;
    ull sum = 0, res = -1;  // -1 相当于最大值 
    for (int bit = 63; bit >= 0; bit--) {
        if (x >> bit & 1) {
            sum |= dp[bit];
        } else {
            res = min(res, sum | dp[bit]);
        }
    }
    res = min(res, sum);
    ans ^= res % mod;
}
cout << ans << endl;

1002 学历史导致的

我真的是读入一个字符串后，先分离出天干、地支，然后再用 exCRT 算出年份的。

应该先预处理。

1003 学数数导致的

比较考验基本功。

对于每个正整数，贪心找第一次出现的位置，下一个 0，下一个出现的位置，再加上后缀本质不同的数的数量。

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
    cin >> a[i];
}
auto all = a;
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for (int i = 0; i < n; i++) {
    a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
}
vector<vector<int>> mp(all.size());
for (int i = 0; i < n; i++) {
    mp[a[i]].push_back(i);
}
vector<int> suf(n + 1);  // 后缀本质不同的个数 
vector<int> cnt(all.size());
for (int i = n - 1; i >= 0; i--) {
    suf[i] = suf[i + 1];
    if (a[i] && !cnt[a[i]]) {
        cnt[a[i]]++;
        suf[i]++;
    }
}
ll res = 0;
auto& vec0 = mp[0];
for (int i = 1; i < mp.size(); i++) {
    auto& vec = mp[i];
    auto it = vec.begin();
    it = lower_bound(vec0.begin(), vec0.end(), *it);
    if (it == vec0.end()) continue;
    it = lower_bound(vec.begin(), vec.end(), *it);
    if (it == vec.end()) continue;
    res += suf[*it + 1];
}
cout << res << endl; 

可以优化为线性：

vector<int> fst(all.size());
vector<int> suf(n + 1);
for (int i = n - 1; i >= 0; i--) {
    suf[i] = suf[i + 1];
    if (a[i]) {
        suf[i] += (fst[a[i]] == 0);
        fst[a[i]] = i;
    }
}
ll res = 0;
int last0 = 0;
for (int i = 0; i < n; i++) {
    if (a[i] == 0) {
        last0 = i;
        continue;
    }
    if (fst[a[i]] < last0) {
        res += suf[i + 1];
        fst[a[i]] = inf;
    }
}
cout << res << endl;

不离散化打 map 会多个 log，TLE。

1004 学 DP 导致的

小 DP，按值按下标皆可。$k>26$ 时相当于 26，但需注意数据范围，$k$ 不能用 int 或 ll 存。

string s, t;
cin >> s >> t;
int k = (t.size() > 2) ? 26 : stoi(t);
array<int, 26> dp{};
while (k--) {
    for (auto c : s) {
        c -= 'a';
        dp[c] = max(dp[c], 1);
        for (int j = 0; j < c; j++) {
            dp[c] = max(dp[c], dp[j] + 1);
        }            
    }
}
cout << *max_element(dp.begin(), dp.end()) << endl;

1005 学几何导致的

不喜欢计算，小计算也不喜欢。

1006 学博弈论导致的

操作规则很复杂，而且是可打表（不可能无法结束，按照红蓝盒子的顺序能打表）的博弈题，无脑打表观察。

个人认为题解那种转化可操作性不强。除非一眼，有这时间表已经打出来了。

打表程序：

int dp[500][500][500];
dp[0][0][0] = 0;
for (int k = 0; k < 150; k++) {  // 盒子 
    for (int i = 0; i < 150; i++) {  // 蓝 
        for (int j = 0; j < 150; j++) {  // 红 
            int ans = 1;
            if (j >= 1) chmin(ans, dp[i][j - 1][k]);
            if (j >= 2) chmin(ans, dp[i][j - 2][k]);
            if (j >= 3) chmin(ans, dp[i][j - 3][k]);
            if (i >= 1) chmin(ans, dp[i - 1][j][k]);
            if (i >= 1 && j >= 1) chmin(ans, dp[i - 1][j - 1][k]);
            if (i >= 1) chmin(ans, dp[i - 1][j + 1][k]);
            if (i >= 2) chmin(ans, dp[i - 2][j + 1][k]);
            if (k >= 1) chmin(ans, dp[i][j + 1][k - 1]);
            if (k >= 1) chmin(ans, dp[i + 1][j][k - 1]);
            if (k >= 1) chmin(ans, dp[i + 1][j + 1][k - 1]);
            dp[i][j][k] = 1 - ans;
        }
    }
}

打出来长这样：

0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 
0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 

0 的位置也比较显然了。

int j, i, k;
cin >> j >> i >> k;
j %= 4;
i %= 2;
if (j % 2 == 1) {
    cout << "Alice" << endl;
} else if (i == j / 2) {
    cout << "Bob" << endl;
} else {
    cout << "Alice" << endl;
}

1007 学计算导致的 （待补）

1008 学画画导致的

这题大概是区域赛铜，思路好想但不好写的那种。

拓扑排序删掉完美的某行，能全删掉就 ok。

int n, q;
cin >> n >> q;
vector<vector<int>> adj(3 * n);
bool ok = true;
while (q--) {
    int x, y, c;
    cin >> x >> y >> c;
    x--, y--, c--;
    int u[3] = {
        y / 2,   // 竖着的 
        2 * n - 1 - x,   // 横着的 
        x - (y + 1) / 2 + 2 * n  // 斜着的 
    };
    bool found = false;
    for (int o = 0; o < 3; o++) {
        if (c == u[o]) {
            found = true;
            adj[u[o]].push_back(u[(o + 1) % 3]);
            adj[u[o]].push_back(u[(o + 2) % 3]);
        }
    }
    if (!found) ok = false;  // 特判 
}
// 下面是拓扑排序模板 
vector<int> deg(3 * n);
for (int u = 0; u < (3 * n); u++) {
    for (auto v : adj[u]) deg[v]++;
}
vector<int> Q;
for (int u = 0; u < (3 * n); u++) {
    if (deg[u] == 0) Q.push_back(u);
}
for (int i = 0; i < Q.size(); i++) {
    auto u = Q[i];
    for (auto v : adj[u]) {
        if (--deg[v] == 0) Q.push_back(v);
    }
}
if (Q.size() != (3 * n)) ok = false;
cout << (ok ? "Yes" : "No") << endl;

1009 学高考第 19 题导致的

非常好的图论建模题，只是题面有点绕，真是学高考第 19 题导致的。

题目的意思是将$a$ 重排，新数组与原数组的那个关系$\prec$（Latex: \prec）相对不变，原来满足那新数组也要满足，反之亦然。

我的想法是，注意$i,j$ 满足那个关系，那么$i$ 与$i+1,\dots, j-1$ 都满足，可以找对于每个$i$，第一个不满足那个关系的$j$，给$i\to j$ 连边后会形成一棵树。但这样丢信息了，只给$i\to j$ 连边不行，没有保证中间的都串在一起。

题解说找$i$ 左边最大的$j$，使得$j,i$ 满足关系，这就对了。现在也构成一棵树，所有有关系的，在树上都有一条链，所有没关系的，在树上都是兄弟。因此，只能修改子树之间的顺序。

从叶子到根依次排序。排序方案是，如果根不同，小的在前（思考为什么字典序最大还要小的在前），如果根不同，按字典序排序。字典序缺位补$+\infty$。

用 std::list 实现，代码极短。

vector<int> a(n + 1);
vector<vector<int>> adj(n + 1);
a[0] = inf;
stack<int> stk;
stk.push(0);
for (int i = 1; i <= n; i++) {
    cin >> a[i];
    // 找左边最近的比自己大的数 
    while (a[stk.top()] <= a[i]) {
        stk.pop();
    }
    adj[stk.top()].push_back(i);
    stk.push(i);
}
vector<list<int>> list(n + 1);
for (int i = 0; i <= n; i++) {
    list[i].push_back(a[i]);
    list[i].push_back(inf);    // 缺位补 inf
}
for (int i = n; i >= 0; i--) {
    sort(adj[i].begin(), adj[i].end(), [&](int x, int y) {
        return a[x] == a[y] ? list[x] > list[y] : a[x] < a[y];
    });
    for (auto x : adj[i]) {
        list[i].pop_back();  // 把补的 inf 删了 
        list[i].splice(list[i].end(), list[x]);
    }
}
list[0].pop_front();
list[0].pop_back();
for (auto x : list[0]) {
    cout << x << " ";
}
cout << endl;

1010 学排列导致的 （待补）