CSP J 2025

zengyukai2012 · 2025-11-09 22:15:43 · 个人记录

CSP J 2025

T1 拼数 / number

这道题是模拟题，由于 \left|S\right| \leq {10}^6，所以 n \log n < 2 \times 10^7，不会超时，直接暴力，考场代码如下：

#include <bits/stdc++.h>
using namespace std;
string s, s1;
bool cmp(char l, char r)
{
    return l > r;
}
int main()
{
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    for (size_t i = 0; i < s.size(); ++i)
        if ('0' <= s[i] && s[i] <= '9') // 判断是否是数字
            s1.push_back(s[i]);
    sort(s1.begin(), s1.end(), cmp); // 倒序排序
    cout << s1 << '\n';
    return 0;
}

T2 座位 / seat

这道题可以模拟，也可以当作数学题，对于这一列中是第几个，可以计算 \left(rnk - 1\right) \mod n + 1（rnk 表示排名），考场代码如下：

#include <bits/stdc++.h>
using namespace std;
int n, m, rnk = 1;
int a[101];
int t, tt;
int main()
{
    freopen("seat.in", "r", stdin);
    freopen("seat.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    cin >> a[1]; //输入小 R 成绩
    for (int i = 2; i <= n * m; ++i) // 输入其他人成绩
    {
        cin >> a[i];
        if (a[i] > a[1]) // 统计排名
            ++rnk;
    }
    t = (rnk + n - 1) / n; // 列
    tt = (rnk - 1) % n + 1; // 第几个
    if (t % 2 == 1)
        cout << t << ' ' << tt << '\n';
    else
        cout << t << ' ' << n - tt + 1 << '\n';
    return 0;
}

T3 异或和 / xor

这道题可以发现前缀异或和，即：

:::info[前缀异或和] 定义 qzh_i = qzh_{i-1} \oplus a_i，其中 qzh_0 = 0，则 {\large\oplus}_{i=l}^r a_i = qzh_r - qzh_{l-1} \left(l \leq r\right)（因为异或的逆运算是它本身）。 :::

所以可以想要在前面的所有前缀异或和中查找第一个 a_j = qzh_i \oplus k （lst < i < j，其中 lst 表示上一个区间的结尾），容易写出代码：

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[500001];
int qzh[500001];
int lst = 0; // 上一个区间结尾
int s = 0;
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i) // 计算前缀异或和
        qzh[i] = qzh[i - 1] ^ a[i];
    for (int i = 1; i <= n; ++i)
        for (int j = lst; j < i;++j) // 枚举每个区间 j + 1...i
            if ((qzh[j] ^ qzh[i]) == k) // 判断
            {
                ++s;
                lst = i;
                break;
            }
    cout << s << '\n';
    return 0;
}

但是实际测试中，只有 75 分（\colorbox{#052242}{\color{#FFFFFF}{\texttt{TLE}}} 5 \texttt{个点}）。

考虑优化，发现每次的“决策集合”都只会进行两种操作：

1. 插入一个数 qzh_i
2. 清空

所以考虑使用 set 和二分查找维护。

由此得到 \colorbox{#52C41A}{\color{#FFFFFF}{\texttt{AC}}} 代码：

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[500001];
int qzh[500001];
int ans, lst;
set<int> t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        qzh[i] = qzh[i - 1] ^ a[i];
    t.insert(0);
    for (int i = 1; i <= n; ++i)
    {
        set<int>::iterator fd = t.find(qzh[i] ^ k);
        if (fd != t.end())
        {
            t.clear();
            lst = i;
            ++ans;
        }
        t.insert(qzh[i]);
    }
    cout << ans << '\n';
    return 0;
}

然而我当时没想起来 find 方法，于是使用了 lower_bound 代替：

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[500001];
int qzh[500001];
int ans, lst;
set<int> t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        qzh[i] = qzh[i - 1] ^ a[i];
    t.insert(0);
    for (int i = 1; i <= n; ++i) // 浠?i 涓虹粨灏?
    {
        set<int>::iterator fd = t.lower_bound(qzh[i] ^ k);
        if (fd != t.end())
            if (*fd == (qzh[i] ^ k))
            {
                t.clear();
                lst = i;
                ++ans;
            }
        t.insert(qzh[i]);
    }
    cout << ans << '\n';
    return 0;
}

同样可以 \colorbox{#52C41A}{\color{#FFFFFF}{\texttt{AC}}}。

然而我考场时忘记判断 if (fd != t.end())，喜提 70 分。考场代码：

#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[500001];
int qzh[500001];
int ans, lst;
set<int> t;
int main()
{
    freopen("xor.in", "r", stdin);
    freopen("xor.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        qzh[i] = qzh[i - 1] ^ a[i];
    for (int i = 1; i <= n; ++i) // 以 i 为结尾
    {
        t.insert(qzh[i - 1]);
        set<int>::iterator fd = t.lower_bound(qzh[i] ^ k);
        if (*fd == (qzh[i] ^ k))
        {
            t.clear();
            lst = i;
            ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}

T4 多边形 / polygon

考场上这道题还剩越 1\rm{h}，没想出正解，写了暴力。考场代码：

#include <bits/stdc++.h>
using namespace std;
int n, ans;
int a[50001];
void dfs(int now, int lst, int s, int yx)
{
    if (now == n + 1)
    {
        if (yx >= 3)
            if (s > a[lst] * 2)
                ++ans;
        return;
    }
    dfs(now + 1, now, s + a[now], yx + 1);
    dfs(now + 1, lst, s, yx);
}
int main()
{
    freopen("polygon.in", "r", stdin);
    freopen("polygon.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    dfs(1, 0, 0, 0);
    cout << ans << '\n';
    return 0;
}