20250715 --from alisa

E

知识点：形如 $x^{2} - y^{2}$ 的数字不能被 $4 k + 2$ 表示

给定两个数字 $a, b$ 判断 $n u m = (a + b) * (a - b)$ 的结果在所有这些数字的集合中的排名

打表找规律可以发现：

1 不能被表示，所有 $2 k + 1 (k > 0)$ 的数字都可以表示为 $(k + 1)^{2} - k^{2}$
4 不能被表示，所有 $4 k$ 可以表示为 $(k + 1)^{2} - (k - 1)^{2}$
所有形如 $4 k + 2$ 的数字都不能被表示

所以我们计算有多少个 $4 k + 2 < n u m$ 然后特别判断一下 1 和 4 即可 $n u m$ 的最小值是 $2^{2} - 1^{2} = 3$ 所以一定比1大

我们不妨这样理解：本来num在所有的正整数中就是排num名的但是有一些数字需要被剔除，那num减去这些被剔除的数字个数就是正确的排名

记录 $an s = n u m$ 由于 $n u m > 1$ 所以一开始就有 $an s - -$

满足 $4 k + 2 < n u m$ 的 $k_{min} = 0$ $k_{ma x}$ 可以通过计算 $k < (n u m - 2) /2$ 来求得他们一共有 $k_{ma x} - k_{min} + 1 = k_{ma x} + 1$ 个

因此， $an s - = \frac{n u m - 2}{2} + 1$

特别的如果 $n u m > 4,$ $an s - -$

ac code:

void solve()
{
    int a, b;
    cin >> a >> b;
    if (a < b)
    {
        swap(a, b);
    }
    int c = (a + b) * (a - b);
    /*
    本来应该是第c项 但是有一些要排除
    */
    int ans = c;
    // ans > 1
    ans--;
    if (c > 4)
    {
        ans--;
    }
    // 现在就可以看所有4k+2 k >= 0 的 式子
    int k = ((c - 2) >> 2) + 1;
    cout << ans - k;
}

G

一个模拟。

给定一个字符串S 给q次询问，每一次询问给一个字符串t和偏移量n 问：把t往右偏移n位，判断S和t相同的部分能构成多少个“对称区间”

e.g：

h e l l o w o r l d

f o l l o w

像这样对齐可以发现，1-based 的 3-6 部分这两个字符串是相同的可以构成 $[3, 3], [3, 4], [3, 5], [3, 6], [4, 4], [4, 5], [4, 6], [5, 5], [5, 6], [6, 6]$ 一共 $4 + 3 + 2 + 1 = \frac{( 首项 + 末项 ) * 项数}{2}$

令 $f (n) = \frac{( 1 + n ) * n}{2}$

那么问题就转化为找到每一个最大区间 $ma x n$ 答案就是 $\sum f (ma x n)$

ac code:

void solve()
{
    int n, q;
    string s;
    cin >> n >> q >> s;
 
    while (q--)
    {
        int ans = 0;
        int cur = 0;
        string ss;
        int idx;
        cin >> ss >> idx;
 
        vector<int> kk;
 
        for (int i = 0; i < min(n, (int)ss.size()); i++)
        {
            if (s[i + idx - 1] == ss[i])
            {
                cur++;
            }
            else
            {
                kk.emplace_back(cur);
                cur = 0;
            }
        }
 
        if (cur > 0)
        {
            kk.emplace_back(cur);
        }
 
        for (auto num : kk)
        {
            ans += (num) * (num + 1) / 2;
        }
 
        cout << ans << endl;
    }
}

L

给定n个数字，q次更新，每一次更新都会给出两个数字p和v，表示第p个数字增加v，每一次操作之后查询有多少个数字 $t o t$ 比 $\frac{n + 1}{2}$ 小

其实就是用数据结构来维护单点增加，区间查询，线段树和树状数组都可以做到这一点。

具体来说，每一次更新之后我们只需要对 $t o t$ 进行二分每次判断 $q u ery (1, t o t, 1, n, 1)$ 和 $\frac{n + 1}{2}$ 的关系即可。

如果想学习值域线段树的思想可以了解一下树状数组求逆序对的原理

想要构建值域线段树就势必要确定线段树的规模这里采取的做法是手动模拟一遍q次更新记录下所有出现的数字然后离散化处理。

值得一提的是，我在写这颗线段树的时候经历了答案错误 → 段错误 → 超时最后ac的时候内存基本上也占满了所以这里给出树状数组做法

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
 
// 作用：维护一个频率数组 freq[1..n] 的前缀和，支持：
//  - add(i, delta): 单点加
//  - sumPrefix(i): 前缀和 [1..i]
//  - kth(k): 找到“最小的 idx，使得 sumPrefix(idx) >= k”
// 实现要点：t[i] 存的是某一段的和（最低位 1 的覆盖段），按位运算 i += i&-i / i -= i&-i 走树形结构。
// 注意：本实现使用 1-based 下标。
struct BIT
{
    int n;
    vector<int> t;
 
    void init(int _n)
    {
        n = _n;
        t.assign(n + 1, 0);
    }
 
    // 单点加：freq[i] += delta
    // 时间：O(log n)
    void add(int i, int delta)
    {
        // 每次跳到能覆盖 i 的更大区间的节点
        for (; i <= n; i += i & -i)
        {
            t[i] += delta;
        }
    }
 
    // 前缀和：sum_{j=1..i} freq[j]
    // 时间：O(log n)
    int sumPrefix(int i)
    {
        int s = 0;
        // 从 i 开始逐步跳到更小的区间节点累加
        for (; i > 0; i -= i & -i)
        {
            s += t[i];
        }
        return s;
    }
};
 
void solve()
{
    int n, q;
    cin >> n >> q;
 
    // 初始数组 a[1..n]
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
 
    // 读取所有操作，并为“值域离散化”收集可能出现的值
    vector<pair<int, int>> ops(q);
    vector<int> now = a; // 维护实时的值
    vector<int> coord;   // 离散化坐标表
    coord.reserve(n + q + 5);
 
    // 把初始值加入离散集合
    for (int i = 1; i <= n; ++i)
        coord.push_back(a[i]);
 
    // 每次操作为：位置 p 增加 v；把“更新后的值”加入离散集合，确保映射完备
    for (int i = 0; i < q; ++i)
    {
        int p, v;
        cin >> p >> v;
        ops[i] = {p, v};
        a[p] += v;             // a 临时承载“累加后的值”
        coord.push_back(a[p]); // 新值进入离散集合
    }
 
    // 离散化：排序 + 去重
    sort(all(coord));
    coord.erase(unique(all(coord)), coord.end());
    int nn = (int)coord.size(); // 离散值域大小
 
    // 将真实值 x 映射到 1-based 索引（树状数组的下标）
    auto getId = [&](int x) -> int
    {
        // lower_bound 返回的是 x 在升序 coord 中的位置（0-based）
        // 我们 +1 变成 1-based，便于与 BIT 配合
        return (int)(lower_bound(all(coord), x) - coord.begin()) + 1;
    };
 
    // 树状数组维护“每个离散值出现的次数”
    BIT bit;
    bit.init(nn);
    for (int i = 1; i <= n; ++i)
        bit.add(getId(now[i]), 1); // 初始频率加入
 
    // 关键逻辑（题意等价转换）：
    // 定义：L = ceil((n-1)/2)。一个数“麻木”的充要条件是：它比自己大的数的个数 >= L。
    // 设 rank(x) = “<= x 的元素个数”。因为“比 x 大”的个数 = n - rank(x)。
    // 条件 n - rank(x) >= L  等价于  rank(x) <= n - L。
 
    // 进一步计算 n - L：
    // - n 为奇数 n=2m+1：L=ceil((2m)/2)=m，n-L = (2m+1)-m = m+1 = ceil(n/2)
    // - n 为偶数 n=2m：  L=ceil((2m-1)/2)=m，n-L = 2m-m = m   = n/2
 
    // 统一写成：n - L = floor(n/2) + (n%2!=0) = ceil(n/2)
    // 我们要数的是“rank(x) <= n-L”的元素个数，也就是“<= 第 (n-L) 小的值”的个数。
    // 为了写成“严格小于某个值”的形式，设 p = (n-L)+1 = ceil(n/2) + 1，
    // 令 pos = 第 p 小值所在的离散下标，则“严格小于该值”的个数 = rank <= p-1 = n-L，正好是答案。
 
    // 因此：
    //   p = ceil(n/2) + 1
    //   pos = bit.kth(p)
    //   ans = bit.sumPrefix(pos - 1)
    int p = (n + 1) / 2 + 1; // 等价于 ceil(n/2)+1
 
    // 处理每次更新
    for (auto [idx, add] : ops)
    {
        int cur = now[idx];
        int nxt = cur + add;
 
        // 从频率中删除旧值、加入新值（值域是离散下标）
        bit.add(getId(cur), -1);
        bit.add(getId(nxt), +1);
        now[idx] = nxt;
 
        // 目标 target = n - L = ceil(n/2)
        // 我们要找“最大的位置 last_le，使得 sumPrefix(last_le) <= target”
        // 这等价于“严格小于第 (target+1) 小的值”的数量。
        int target = (n + 1) / 2; // = ceil(n/2)
 
        int l = 1, r = nn, last_le = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            // f(mid) = 前缀和，单调不降
            if (bit.sumPrefix(mid) <= target)
            {
                last_le = mid; // mid 可行，尽量往右找更大的
                l = mid + 1;
            }
            else
            {
                r = mid - 1; // mid 不可行，收缩到左边
            }
        }
 
        // 答案 = 严格小于第 (target+1) 小值的个数
        // 即“前缀和 <= target”的最大位置的前缀和
        int ans = bit.sumPrefix(last_le);
 
        cout << ans << endl;
    }
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

设 $L = \frac{n - 1}{2}$ 我们要找到尽可能大的数字使得起码还有 L个数字比它大也就是说有 n - L 个数字小于等于它

记 $p re [i]$ 为 i和i之前所有数字的数目和这一段和 + L 有可能会小于n 也有可能等于n 即： $p re [i] + L \leq n$ 二分找到最大的i 然后输出 $p re [i]$ 即可

在此基础上记录 $t a r g e t = n - L = \frac{n + 1}{2}$ 就有了上面的写法

K

对于一条路径 $[x, i d x]$ （其中x是当前节点，idx是到达当前节点的路径），必然有且只有一条路径可以走到下一个节点，进而可以发现，行走的路线一定在一个环上，这一定是一片环的森林。所以问题转化为：对于每一个 $[x, i d x]$ 对，求环的大小

可以考虑采用dfs来维护答案，这里给出代码：

void solve()
{
    int n;
    cin >> n;
    vector adj(n + 1, vector<int>());
    for (int i = 1; i <= n; i++)
    {
        int op;
        cin >> op;
        while (op--)
        {
            int x;
            cin >> x;
            adj[i].emplace_back(x);
        }
    }
 
    vector vis(n + 1, vector<int>(3));
    set<pair<int, int>> st;
    vector<int> ans(n + 1);
 
    function<int(int, int)> dfs = [&](int u, int idx) -> int // u从idx走进来 问有多少条不同路径
    {
        if (idx != -1)
        {
            // 判断是否进入环
            if (vis[u][idx])
            {
                return st.size();
            }
            vis[u][idx] = 1;
        }
 
        idx = (idx + 1) % adj[u].size();
        auto nxt = adj[u][idx];
        int res = 0;
        st.insert({min(nxt, u), max(nxt, u)});
 
        for (int i = 0; i < adj[nxt].size(); i++)
        {
            if (adj[nxt][i] == u)
            {
                res = dfs(nxt, i);
                break;
            }
        }
 
        if (idx == 0)
        {
            ans[u] = res;
        }
        return res;
    };
 
    for (int i = 1; i <= n; i++)
    {
        st.clear();
        if (!ans[i])
        {
            dfs(i, -1);
        }
        cout << ans[i] << endl;
    }
}

H

赛时有一半的做法都不是2s复杂度的正解，而错解其实跟abc的D(D - Substr Swap)非常像，算是比较有教育意义的一道题。

我们不妨先去看看上面的那道D，给出两个字符串每一次操作都给出 $[l, r]$ 要求对两个字符串的对应位置进行换位最后输出第一个字符串

我的想法Submission #68541210 - AtCoder Beginner Contest 419 个人认为是比较清晰的一个思路，可以很好的贯通到这道题上。

首先现在有两个字符串那么我们可以用一个新的辅助数组来表示字符串1的某个元素是否已经被替换，如果 $[l, r]$ 区间被替换就对这个辅助数组的 $[l, r]$ 区间统一增加1 最后输出的时候每个元素都对2取模来得到真实位置。

这样分析下来用一个支持区间更新单点查询的数据结构来维护辅助数组就行了，刚好可以用差分：

对每一次 $[l, r]$ ，把 v[l]++, v[r + 1]-- 这样一来我们只需要在最后对v做一次前缀和就能复原上述操作了。

搞定了这道D题，现在回过头来看看本场的H 会发现其实也可以很容易的构造第二个字符串：对字符串1 按位异或1 即可

现在，问题就跟上面的D题一模一样了别的照抄就行。

放一个首杀的代码，完全就是这个思路：代码查看

由于赛后修改了时间限制，现在这个思路已经不能ac了

Alisa的数字花园

探索

20250715

E

G

L

K

H

关系图谱

目录