CSP-J 2022 游记（BJ）

liyuanchen2021 · 2022-10-30 15:07:57 · 个人记录

2022.10.27 测试回收系统

我用 NOI Linux 在程序回收系统中提交了一道题的代码并发给 dls，dls 说程序没有问题。

而我在赛后发现有些人注释 freopen 了（而且每年都有不少人这样做），希望大家在提交至回收系统的时候，别忘了把 freopen 的注释去掉。

//freopen("pow.in","r",stdin);
//freopen("pow.out","w",stdout);

应改为：

freopen("pow.in","r",stdin);
freopen("pow.out","w",stdout);

我趁考试之前的最后一天，抓紧时间复习算法，调整好心态，做好考试的准备。

这道题我用了 cmath 头文件下的 pow() 函数（没用快速幂），并且开了 long long。当结果超过 10^9 的时候，输出 -1，否则输出 a^b 的结果。

预期分数：100 | 洛谷估分：100 | 实际分数：100

这道题我直接用了暴力，时间复杂度为 O(k\times\sqrt{n})，测样例的时候 T 在了 #4 上。

我在赛后才发现可以采用更优的算法来拿到更高分数（如二分）。

预期分数：60 | 洛谷估分：60（TLE #7~10）| 实际分数：60

这道题的目的是求中缀表达式的值。大家一定要知道，按位与的优先级要比按位或的优先级更高。

这道题我用了我学过的求中缀表达式的方法——递归求值法，时间复杂度为 O(n^2)，不如先把中缀表达式转换为后缀表达式，再把后缀表达式进行求值，这样的时间复杂度优化为 O(n)。测试大样例时也是 T 在了 #4 上。

预期分数：50 | 洛谷估分：70（评测结果如下图所示）| 实际分数：50

这虽然是一道 DP 题，但是我没有时间去做这道题，因为此时还有 30 分钟考试就要结束了，这主要是因为被 T3 磨得没时间写，希望大家在做题的时候提升速度。

预期分数：100+60+50+0=210 分

洛谷：100+60+70+0=230 分

实际分数：100+60+50+0=210 分

预计奖项：二等奖（5 级勾）