CSP-J2025总结&思路&游记

Manacher · 2025-11-06 17:18:06 · 生活·游记

无聊的游记

训练常态

刷题刷题刷题
总结总结总结

day : -1

研究了一下学校的linux虚拟机
(我在本校考)
研究指 kill 掉主程序
然后没了
晚上11：00

day : 0

就在本校考好爽啊
考试前还能玩学习
灌上一瓶咖啡
出征！！！

number

虽然在看题目是没有想到有前导零的请况
但幸运的是题目保证了有至少一个1-9 的数
下次一定要注意审好题目

SEAT

这题是最糖的
我因为 n,m 看错挂到 35pts 了
下次要仔细读题虽然我在赛时感到 T2 会挂
但我看了下样例似乎是随机的
但样例的 n == m
然后就没看这题了

xor

这题是最遗憾的
思考了30min 终于有了 n^2 思路
写完之后才发现可用 桶优化
结果 没时间了

polygon

这题是最无波澜的想到了似乎是个 DP
但我没怎么做 正难则反 的题
于是打了一个 40pts 的 DFS

考试时的清况复现

8:15 进考场喽
右前竟然是机房模拟赛AK的大佬 %%%
8:27 公布压缩包密码了赶紧输
8:29 不是哥们怎么还错了
8:30 终于输对了，怎么有个保存密码的提示呀？有必要吗？不保存了
8:31 不是第二层怎么还要再输一遍
8:31 开 T1 每次选最小的一个应该可以n^2
但很好打
如果数据范围是 n <= 9000 应该可以
不对 n <= 1e6
emmm....
根据我 两年半 的编程经验
应该用桶
8:33 开打代码
8:38 测试样例，一遍过了
3:40 已完成今日保存代码大学习
8:48 T1 测完并保存
随便看了看题目，发现没什么好注意的
开下 T2
8:49 这题好像应该大概也许做过吧
我会直接分奇偶性模拟!
8:50 打代码
9:12 我嘞个豆，样例怎么炸了
不急，我会输出答案数组
列的顺序怎么反了

1	4	7
2	5	8
3	6	9

9:12 没事，我会调整循环顺序
9:13 去测别的样例喽！
都对了，✌
9:20 让我玩一下 check.exe
怎么没有找到？？？
哦,我的考号少了个0
终于200pts 了吗？（实际上是 135pts）
好紧张去上个厕所
切下一题
9:25 一眼 DP
9:37 Deepsleep 中
9:40 不会！！！
9:40 看 T4
也是一眼 DP
woc,又不会
还是正序开题吧
9:43 先看看特殊性质
那要相同的或是零
特性A 和 k = 0 的重复，没用
别的都看不出来 啊啊啊啊啊啊！ ::::info[n^2算法思考过程]
让我看一下样例
先求一下异或前缀是
2 , 1 , 1 , 2 k = 2
我们知道区间[L,R]的区间和是 pre[R] \oplus pre[L-1] 我们可以枚举 R , 然后从前往后检查 x[0]=0，x[1]=2，x[2]=3，x[3]=3，x[4]=0
（区间[l,r]异或和 = x[r]^x[l-1]）

考场写的比较乱~写个新的

遍历过程（i为右端点）由AI贡献

i=1：
单元素[1,1]：x[1] \oplus x[0] = 2 \oplus 0 = 2 = k → 标记位置1，ans=1。
i=2：
单元素[2,2]：x[2] \oplus x[1] = 3 \oplus 2 = 1 \neq k；向前找j，j=1已标记 → 无新区间，ans=1。
i=3：
单元素[3,3]：x[3] \oplus x[2] = 3 \oplus 3 = 0 \neq k；向前找j，j=1已标记 → 无新区间，ans=1。
i=4：
单元素[4,4]：x[4] \oplus x[3] = 0 \oplus 3 = 3 \neq k；j=2时，x[4] \oplus x[1] = 0 \oplus 2 = 2 = k → 标记[2,4]，ans=2。

结果

有效区间[1,1]和[2,4]，共2个。 ::::

10:30 终于过了大样例
考试时以为n^2一个都卡不过或是数据强
实际上可以得到 75pts
本来预估 48pts

实际因为数组够大到了 60pts
赢赢赢赢赢赢赢
这个故事告诉我们： :::epigraph[——李宁] anything is possible ::: :::epigraph[——Nike] JUST DO IT. ::: ::::info[xor code]

codeT3

传奇散装英语


#include<iostream> 
using namespace std;
int x[100005] , n , k , ans = 0;
bool fg[100005];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
cin >> n >> k;
for(int i = 1;i <= n;i++)
{
    cin >> x[i];
    x[i] ^= x[i - 1];
}
int enf = 0;
for(int i = 1;i <= n;i++)
{
    if((x[i] ^ x[i - 1]) == k)
    {
        ans++;
        fg[i] = 1;
        continue ;
    }
    for(int j = i;j >= 1;j--)
    {
        if(fg[j])
            break;
        if((x[j - 1] ^ x[i]) == k)
        {
            for(int kk = j;kk <= i;kk++)
                fg[kk] = 1;
            ans++;  
            enf = i;
            break;      
        }
    }
}
cout << ans;
return 0;
}
/*
int int long long bis/stdc++.h iostream using namespace std std std main
return reureruueb retubnr reurb eurb e loce oi OIer 
OIwiki
I love CCF !
I AK IOI ! 
10:30 48pts!!!
big test is AC!!!

10:35 use ton is 100pts ? 10:40

include<iostream>

using namespace std; int x[100005] , n , k , ans = 0; bool fg[100005]; int chu[1048580][3]; int main() { ios::sync_with_stdio(0); cin.tie(0); freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); cin >> n >> k; for(int i = 1;i <= n;i++) { cin >> x[i]; x[i] ^= x[i - 1]; chu[x[i]][0] = i; chu[x[i]][0] = } bool zd = 0; int enf = 0; for(int i = 1;i <= n;i++) { zd = 0; if((x[i] ^ x[i - 1]) == k) { ans++; zd = 1, fg[i] = 1; continue ; } for(int j = i;j >= 1;j--) { if(fg[j]) break; if((x[j - 1] ^ x[i]) == k) { zd = 1; for(int kk = j;kk <= i;kk++) fg[kk] = 1; ans++;
enf = i; break;
} } } cout << ans; return 0; } make that will use lianbiao , it's a lots of xijie let's see T4 10:48 Why am I feel T3 can't get to 48 pts; RP++ I must see T4 now; 11:22 maybe I can use VECTOR it's easy; but now let me test in NOI linux2 OH , I can't open the out file it's too big for linux I check it in windows Oh I fell I have not full time to write T3 But get I can get pts is the first. Maybe I can't get YIDENG BUT I am 13 years old. It is a long way to me; my English is so bad. my luogu ID is Manacher I'm in the SSSY shool. I must go to chek now. 11:34 11:41 WHY I need to write my information? */

::::
- 10:40 尝试用桶优化 T3，定义了chu数组但思路不清晰，没写完就卡住了
- 10:48 担心 T3 拿不到 48 分，开始焦虑，决定先看 T4
- 10:58 觉得 T4 像 DP 但没思路，打算对小数据打表，预估能拿 12 分
- 11:01 想到 n≤20 时可以用 DFS，决定动手写，觉得说不定能对拍过
- 11:15 T4 的 DFS 通过了样例，觉得能拿 40 分，有点小激动
- 11:18 确认 T4 的第三个样例没问题，开始幻想能拿到一等奖
- 11:21 确定 T4 能拿 40 分后，打算回头继续写 T3
- 11:22 考虑用 vector 处理 T3 的细节，但不确定是否可行
- 11:34 尝试在 NOI Linux2 上测试程序，却打不开输出文件，可能是文件太大了
- 11:34 打算回 Windows 系统检查输出文件，感觉写 T3 的时间不够了
- 11:34 觉得能拿到能拿的分数最重要，开始怀疑自己能不能拿一等奖
- 11:34 安慰自己才 13 岁，未来还有很长的路
- 11:34 吐槽自己英语太差
- 自己的洛谷 ID 是 Manacher，来自 SSSY 学校
- 11:34 决定现在必须去检查程序了
- 11:41 疑惑监考老师为什么要让我写这些个人信息
::::info[polygon code]
#### codeT4
```cpp
#include<iostream> 
using namespace std;
long long n , a[5005] , ans = 0 ;
bool flag[5005];
void dfs(int cnt , long long maxai , long long sum ,int lasti)
{
    if(cnt >= 3 && maxai * 2 < sum){
        ans++;
    }
    for(int i = lasti + 1;i <= n;i++)
    {
        if(!flag[i]){
            flag[i] = 1;
            dfs(cnt + 1 , max(maxai , a[i]) , sum + a[i] , i);
            flag[i] = 0;
        }
    }
    return ;//666
}
int main()
{   
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    if(n <= 2)
    {
        cout << 0;
        return 0;
    }else if(n == 3)
    {
        cout << (((max(a[1],max(a[2],a[3])) * 2) < (a[1] + a[2] + a[3])) ? 1 : 0);
        return 0;
    }else if(n <= 21)
    {
        dfs(0 , 0, 0 , 0);
        cout << ans;
        return 0;
    }
    return 0;
}
/*
It look like DP;
but I have not mind
1~3 I can DA'BIAO !!!
can I use chinese ?
10:58
maybe I get 12pts.
It OK to 260 pts get CSP_J YIDENG ?
I hope my T2 & T1 is AC;
11:01 
when n <= 20 
I can dfs;
Just do it!
my be it can dui'pai
11:15
my dfs is ac the yang'li !!!
I will get 40 pts;
Let's check now;
11:18
polygon3 is OK !!!
Maybe I will get to YI'DENG ?
I LOVE CCf 
11:21
I can get T4 40 pts now;
let me write T3;
*/

::::

展望

加油吧！

满江红・记 CSP - J 考场事

晓色初分，考场静、心潮暗涌。
灌咖啡、振袂欲出征，情方纵。
抬眼望、右前大佬，屏光微动。
密令两番输未对，指尖汗透衣痕重。
T1 了，桶轻弄； T2 憾，n m 弄。
恨审题疏略，卅五分压。
异或思来阶平方，桶优化迟时不共。
转头看、T4DFS 忙，残分拥。
时渐暮，敲键冗；题未解，意难纵。
叹少年伏案，眉峰深锁。
曾惧分数如落叶，终凭寸志撑残梦。
待明朝、再向NOIP行，初心奉。