- gf25030 的博客
2026年10月31日csp-j复盘
-
gf25030
LV 9
@
2026-10-31 18:43:12
本文仅分享我考场上的想法
T1旅游/travel
居然没发现座位号是ABCDF(没有e)，应该要扣15分
考场代码(模仿)
#include<bits/stdc++.h>
using namespace std;
int a, c;
string b, d;
int main(){
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> a >> b >> c >> d;
string aa = b.substr(0, 2), bb = d.substr(0, 2);
if (a == c)
{
cout << 1;
if (aa == bb)
{
cout << 1;
if ((b[2] > 'C' && d[2] > 'C') || (b[2] <= 'C' && d[2] <= 'C'))
{
cout << 1;
int x = abs(b[2] - d[2]);
if (x == 1)
{
cout << 1;
}
else
{
cout << 0;
}
}
else
{
cout << "00";
return 0;
}
}
else
{
cout << "000";
return 0;
}
}
else
{
cout << "0000";
}
return 0;
}
T2回文串 / string
考场上想到一种思路(虽然很垃圾，后面回文串判断方法不做赘述)，可以发现让串的每一个a[i]除以题目的最大公约数，最后再输出压缩后的答案*最大公约数(数据太阴就过不了，以至于ans6.in过了ans5.in没过)
考场代码(模仿)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int a[N], n, t, cnt;
char c[N];
string s;
signed main(){
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i] >> c[i];
if (i == 1)t = a[i];
else t = __gcd(t, a[i]);
}
for (int i = 1; i <= n; i++)
{
a[i] /= t;
for (int j = 1; j <= a[i]; j++)
{
s += c[i];
}
}
for (int i = 0; i < s.size() / 2; i++)
{
if (s[i] != s[s.size() - i - 1])cnt++;
}
cout << cnt * t;
return 0;
}
T3按位与 / and
考场上第一眼以为是dp，写了一会发现不是，思考了很久但是想不到是什么解法，于是使用了骗分 + dfs(除了特殊性质B其他特殊情况全出)。回看考场上的非正解但可以骗大量分数的思路，我很好奇是当时是怎么想到的，大抵是我鬼脑发动了吧。。。
数据范围：
① 当n <= 20时，dfs
② 当m = 1 时，代表只能选一个，for寻找最大值
③当m = n 时，全选，直接for跑一遍
④当m = 2 时，要选2个，注意到双层for循环未超时直接跑
⑤ 特殊性质A ： 所以数字 + 1都是2的正整数次幂，代表化成2进制一定全是1，可以直接输出第m大的数
为什么？
如
3 2
3 8 15
不难看出都是2的正整数次幂，换成2进制为：
0011
0111
1111
聪明的都懂了吧？这些数字都是以若干个1为后缀组成的，这里面选m个数得到&最大，直接把最大的m个拼起来，不过不需要再循环m次， 这个序列直接输出a[m]和从&a[1] ~ a[m]答案是一样的
否则继续使用dfs(万一对了呢)
考场代码(模仿)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, a[N], ans;
bool flag, vis[N];
bool check_A(int x)
{
if (int(sqrt(x)) * int(sqrt(x)) == x)return 1;
return 0;
}
void dfs(int x, int cnt, int p)
{
if (cnt > m)
{
ans = max(ans, p);
return;
}
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
vis[i] = 1;
if (p == 0)dfs(i, cnt + 1, a[i]);
else dfs(i, cnt + 1, (p & a[i]));
vis[i] = 0;
}
}
}
signed main(){
freopen("and.in", "r", stdin);
freopen("and.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (!check_A(a[i] + 1))flag = 1;
}
sort(a + 1, a + 1 + n, greater<int>());
if (flag == 0)//满足特殊性质A
{
cout << a[m];
return 0;
}
if (m == 1)//仅选1个
{
cout << a[1];
return 0;
}
if (m == n)//全选
{
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (i == 1)ans = a[i];
else ans = ans & a[i];
}
cout << ans;
return 0;
}
if (m == 2)//选2个
{
int ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i == j)continue;
ans = max(ans, (a[i] & a[j]));
}
}
cout << ans;
return 0;
}
dfs(1, 1, 0);
cout << ans;
return 0;
}
纸牌游戏 / card
最后一题忘记咋做的了（其实是考场上写得太屎山了模仿不出来，样例1过了样例2没过）
后记
这次感觉比以往难了很多，第一题80-90，第二题应该60-70，第三题50-60，最后一题应该没分，正常应该有200+(在bcoi做了前3题刚好200分)