专栏文章

CSP J 2025

zzengyukai2012
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minawlud
此快照首次捕获于
2025/12/01 23:25
3 个月前
此快照最后确认于
2025/12/01 23:25
3 个月前
查看原文

CSP J 2025

T1 拼数 / number

这道题是模拟题，由于 ∣S∣≤106\left|S\right| \leq {10}^6，所以 nlog⁡n<2×107n \log n < 2 \times 10^7，不会超时，直接暴力，考场代码如下：
CPP
#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

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

这道题可以发现前缀异或和，即：
前缀异或和
定义 qzhi=qzhi−1⊕aiqzh_i = qzh_{i-1} \oplus a_i，其中 qzh0=0qzh_0 = 0，则 ⊕i=lrai=qzhr−qzhl−1(l≤r){\large\oplus}_{i=l}^r a_i = qzh_r - qzh_{l-1} \left(l \leq r\right)（因为异或的逆运算是它本身）。
所以可以想要在前面的所有前缀异或和中查找第一个 aj=qzhi⊕ka_j = qzh_i \oplus k （lst<i<jlst < i < j，其中 lstlst 表示上一个区间的结尾），容易写出代码：
CPP
#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;
}
但是实际测试中，只有 7575 分（TLE5个点\colorbox{#052242}{\color{#FFFFFF}{\texttt{TLE}}} 5 \texttt{个点}）。
考虑优化，发现每次的“决策集合”都只会进行两种操作：
  1. 插入一个数 qzhiqzh_i
  2. 清空
所以考虑使用 set 和二分查找维护。
由此得到 AC\colorbox{#52C41A}{\color{#FFFFFF}{\texttt{AC}}} 代码：
CPP
#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 代替：
CPP
#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;
}
同样可以 AC\colorbox{#52C41A}{\color{#FFFFFF}{\texttt{AC}}}。
然而我考场时忘记判断 if (fd != t.end())，喜提 7070 分。考场代码：
CPP
#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

考场上这道题还剩越 1h1\rm{h}，没想出正解，写了暴力。考场代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...