4.23模拟赛总结

写在前面

不用说了, 狗屎

虽然没有爆零, 但是和爆零也没啥区别了

赛后发现题目一个赛一个简单, 看完题解只能感叹自己是唐氏

~~不过T1真的不考虑升一下等级吗啊喂~~

让我们祝贺StarLinkOvO还是没能打破自己模拟赛切不了题的诅咒
~~其实就是菜不要找借口~~

不过说到底还是收获了一些经验的

那就是:

不要轻易的认为越靠前的题越简单更不要死磕一道题

~~其实已经因为这个吃了好几回亏了, 不过一直吃一堑吃一堑又吃一堑~~

好了不发牢骚了我们进入正题

T1 : P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了

题目点这里

T1题意简述

定义 f(x) = x \oplus (x + 2 ^ k) , 其中 \oplus 为二进制下的异或运算

给出 n, k 求出 f(0) + f(1) + f(2) + ... + f(n) 的值

本题有多组数据

T1解题思路

作者还没学会, 所以只好抄一遍题解先凑合看着, 我会回来填坑的

原题解 click

观察到增加一个 2 ^ k 变化的位数有限，而异或统计答案只关注于变化的这些位，于是考虑按位统计答案.

注意到 2 ^ k 的贡献次数为 n+1 , 先算掉。

注意到第 i 位产生贡献时，必然满足从第 k 位到 i−1 位必须全部为 1 。

于是不妨 n←n+2 ^ k那么此时我们只需要统计第 i 位是 1 而从 k 到 i−1 位全为 0 的出现次数，这是好做的。

然后贡献大小就是 2_{i + 1} - 2_{k + 1} .

T1 : AC代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T, n, k;

void solve() {
    int ans = (1 << k) * (n + 1);
    n += (1 << k);

    for (int i = 1 << (k + 1); i <= n; i *= 2) {
        int f = n / (i << 1);
        int c = min(1ll << k, n % i + 1);
        int sum = f * (1 << k);
        ans += sum * i * 2 - sum * (1 << (k + 1));
        if (n & i) ans += i * c * 2 - c * (1 << (k + 1));
    }
    cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> T;
    while (T--) {
        cin >> n >> k;
        solve();
    }
	return 0;
}

T2 : P12148 【MX-X11-T2】「蓬莱人形 Round 1」所以我放弃了音乐

题目在这里

T2题意简述

在无限大的棋盘上有 n 个互不相同的棋子 (x_i, y_i) , 有如下操作:

选择一个格子 (x, y)
若该位置上有棋子则将其删除, 否则结束该操作
依次检查 (x + 1, y),\;(x + 1, y),\;(x + 1, y - 1) .
若检查到第一个有棋子的格子时, 删除该棋子, 停止检查, 将 (x, y) 的坐标更新为该格子并返回第二步.
若三个格子里都没有棋子, 终止操作

计算需要多少次操作才能删掉所有的棋子

T2解题思路

看到这个题我们一般会首先想到模拟解题, 即通过当前选定棋子去删掉更多的棋子, 从而达到目的

但是写代码时我们就会遇到各种问题

我不敢说这样一定就是错的, 但是在考场上是很难写对的

那怎么办?

—将思维逆转过来吧! 成步堂龙一!—

~~好燃啊但是不知道在燃什么~~

我们设想一下, 当你面对一个给小孩子玩的做迷宫的题, 那你会怎样尽量快的找到路线

没错就是从出口往回走

也就是说对一个棋子, 我们不考虑它能转移到哪些点, 而是考虑它能否从其它点转移过来

将不能被其他点转移回来的点的个数统计起来就是我们想要的答案

怎么样是不是炒鸡煎蛋

T2 : AC代码

#include <bits/stdc++.h>
using namespace std;

map < int , bool > mp[1000003];
vector < int > ve[1000003];
int n, ans;

bool cmp(int a, int b) {
    return a > b;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        ve[x].push_back(y);
        mp[x][y] = 1;
    }

    for (int i = 1; i <= 1000000; i++) {
        if (ve[i].size() == 0) continue;

        sort(ve[i].begin(), ve[i].end(), cmp);
        for (auto j : ve[i]) {
            if (mp[i + 1][j + 1]) mp[i + 1][j + 1] = 0;
            else if (mp[i + 1][j]) mp[i + 1][j] = 0;
            else if (mp[i + 1][j - 1]) mp[i + 1][j - 1] = 0;
            else ans++;
        }
    }

    cout << ans << endl;

    return 0;
}

T3 : [JOIG 2025] 修学旅行 / School Trip

题目在这里

T3题目简述

不简述了没法简述自己看吧 (语文不好的作者如是说)

JOIG 高中有 3^N 名学生，编号从 1 到 3^N。

JOIG 高中决定举行一场学校旅行，有两个可能的旅行目的地：阿拉斯加（记为“方案 \texttt{A}”）和玻利维亚（记为“方案 \texttt{B}”）。学生们决定使用以下的流程确定最终的旅行方案：

考虑一个长度为 3^N 的字符串 S：如果学生 i\left(1\le i\le 3^N\right) 选择方案 \texttt{A}，那么 S_i 为 \texttt{A}，否则为 \texttt{B}；
执行以下操作 N 次：
- 假设当前 S 的长度为 X，考虑一个长度为 \frac{X}{3} 的字符串 S'，满足 S'_j\left(1\le j\le\frac{X}{3}\right) 为 S_{3j-2},S_{3j-1},S_{3j} 中出现次数较多的字符（\texttt{A} 或 \texttt{B}）；接着将 S 替换为 S'；
所有操作结束之后，S 将成为一个长度为 1 的字符串（要么为 \texttt{A} 要么为 \texttt{B}）；如果 S 为 \texttt{A}，那么学校最终选取方案 \texttt{A}，否则选取方案 \texttt{B}。

初始时，我们使用一个字符串 T 表示每名学生选择哪个方案：如果学生 i\left(1\le i\le 3^N\right) 选择方案 \texttt{A}，那么 T_i 为 \texttt{A}，否则为 \texttt{B}。

之后依次发生了 Q 次事件，第 k(1\le k\le Q) 次事件中，学生 p_k\left(1\le p_k\le 3^N\right) 改变了其选择的方案，即若原来他 / 她选择方案 \texttt{A}，那么现在他 / 她选择的方案变为 \texttt{B}，反之亦然。

对于 k=1,2,\ldots,Q，求出第 k 次事件发生后，按照上述流程，学校会选择哪个旅行方案。

T3解题思路

其实这个题并不难, 但是它就坑在大家都没有写过甚至见过多叉线段树

考虑维护三叉线段树, 用 0 表示 A , 1 表示 B , 若一个节点的左右中儿子的值相加大于 2 , 那么该节点就是 0 , 反之则为 1

修改也没啥难点, 普通单点修改即可

只需要注意我们求的 mid 和向下递归操作的范围不同, 即 mid = (r - l + 1) / 3 , 递归的边界是 l ~ l + mid - 1 , l + mid ~ l + 2 * mid - 1 和 l + 2 * mid ~ r , 其余的直接套板子即可

最终的答案就是 char(tree[1] + 'A')

T3 : AC代码

#include <bits/stdc++.h>
#define int long long
#define lc k * 3 - 1
#define mc k * 3
#define rc k * 3 + 1
using namespace std;

const int MN = 6e5 + 3;
int N, n = 1, m;
string s;
int tree[MN << 2]; //0: A; 1: B

void build(int l, int r, int k) {
    if (l == r) {
        tree[k] = s[l] - 'A';
        return ;
    }

    int mid = (r - l + 1) / 3;
    build(l, l + mid - 1, lc);
    build(l + mid, l + mid * 2 - 1, mc);
    build(l + mid * 2, r, rc);

    tree[k] = (tree[lc] + tree[mc] + tree[rc] >= 2);
}
void update(int l, int r, int k, int x) {
    if (l == r) {
        tree[k] ^= 1;
        return ;
    }

    int mid = (r - l + 1) / 3;
    if (x <= l + mid - 1) update(l, l + mid - 1, lc, x);
    else if (l + mid * 2 <= x) update(l + mid * 2, r, rc, x);
    else update(l + mid, l + mid * 2 - 1, mc, x);

    tree[k] = (tree[lc] + tree[mc] + tree[rc] >= 2);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N >> m;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= N; i++) n *= 3;

    build(1, n, 1);

    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        update(1, n, 1, x);
        cout << char(tree[1] + 'A') << endl;
    }

    return 0;
}

T4 : P2966 [USACO09DEC] Cow Toll Paths G

题目链接

T4题目简述

给一个 n 点 m 边的双向图, 第 i 条边连接 u_i 与 v_i , 点有点权, 边有边权

有 q 组询问, 每次询问求 s_i 到 t_i 的路径的边权值和与路径上点的点权的最大值的和的最小值
即求 ans = min{ 路径边权和 + max{路径上所有点的点权} }

T4解题思路

题目写的怪绕的, 我也是看了半天题解才看懂题目...

看懂了我们发现它就是要求路径上的边权和与路径上边权最大的点的边权尽量小, 这样他们的和也就越小

观察数据范围, 发现~~毒瘤的~~出题人只想让我们用 Floyd 算法 (不过好像有人用 dijkstra 也过了, 果然还是我太菜了)

我们需要对点权从小到大排序, 并保留输入的编号, 用一个结构体就可以解决

然后邻接表存图注意有重边记得判重 (当然在这之前记得预处理)

现在我们就要跑 Floyd 了, 但显然需要进行一些改动

先把 Floyd 的公式套一下

d_{i, j} = min ( d_{i, j}, d_{i, k} + d_{k, j} )

注意: 由于我们已经排过序了所以下标要用结构体里存的编号

然后 ans 就按照题目的要求写, 就像这样:

ans_{i, j} = min(ans_{i, j}, d_{i, j} + max (dot_i.val, dot_j.val, dot_k.val))

~~所以还是很简单~~

然后就是愉快的敲代码啦!

T4 : AC代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
int n, m, q;
struct node {
    int val, id;
}dot[255];
int d[1003][1003], ans[1003][1003];

bool cmp(node a, node b) {
    return a.val < b.val;
}

void fir() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;
            ans[i][j] = INF;
        }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> q;
    fir();

    for (int i = 1; i <= n; i++) {
        cin >> dot[i].val;
        dot[i].id = i;
    }
    sort(dot + 1, dot + n + 1, cmp);

    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        d[y][x] = min(d[y][x], z);
    }

    for (int k = 1; k <= n; k++) 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++){
                d[dot[i].id][dot[j].id] = min(d[dot[i].id][dot[k].id] + d[dot[k].id][dot[j].id], d[dot[i].id][dot[j].id]);
                ans[dot[i].id][dot[j].id] = min(ans[dot[i].id][dot[j].id], d[dot[i].id][dot[j].id] + max(dot[i].val, max(dot[j].val, dot[k].val)));
            }

    for (int i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        cout << ans[x][y] << endl;
    }

    return 0;
}

完结撒甲鱼! (OvO----)=3 E=(----OvO)

Menu

Share

4.23模拟赛总结

写在前面

T1 : P12147 【MX-X11-T1】「蓬莱人形 Round 1」仅此而已，就已经足够了

T1题意简述

T1解题思路

作者还没学会, 所以只好抄一遍题解先凑合看着, 我会回来填坑的

T1 : AC代码

T2 : P12148 【MX-X11-T2】「蓬莱人形 Round 1」所以我放弃了音乐

T2题意简述

T2解题思路

T2 : AC代码

T3 : [JOIG 2025] 修学旅行 / School Trip

T3题目简述

T3解题思路

T3 : AC代码

T4 : P2966 [USACO09DEC] Cow Toll Paths G

T4题目简述

T4解题思路

T4 : AC代码

Comment

数论学习笔记

16 ABC404 A ~ E 题解

模拟赛T2 hack

【模板】树链剖分

模拟赛T4 题解

4.23模拟赛总结

高精度模板

（勿入）帮一个大学生通过小测

梅深不见冬题解

2025 04 30 模拟赛题解