CSP2020游记 + 半退役感想

今年 $\text{ln}$ 省初赛分数线极低， $\text{S}$ 和 $\text{J}$ 都很低，然后像我一样的蒟蒻就纷纷莫名其妙进了复赛给 $\text{dalao}$ 们送菜， $\text{mqy}$ 最开始 $\text{J}$ 组进了但是 $\text{S}$ 没进，结果因为有人没报名结果多余名额自由报名了，于是 $\text{mqy}$ 又进了复赛，我突然感觉我相对于 $\text{mqy}$ 初赛成绩的优势已经没有了，有点气啊。 ~~但反正我们俩都是炮灰~~，本是同根生，相煎何太急啊！ ------------ 早上是 $\text{J}$ 组，复赛的题还好，第一题难度有点像 $\text{14}$ 年的题目第一题，但是我分析了一下数据， $1 \le n \le 1 \times 10^7$ ， $\text{Soga}$ ！果断打表！ ```cpp #include <bits/stdc++.h> using namespace std; int n; long long pow2[24] = {0, 8388608, 4194304, 2097152, 1048576, 524288, 262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2}; int main() { cin >> n; if(n % 2 == 1) { cout << -1 << endl; return 0; } for(int i = 1; i <= 23; i = i + 1) if(n >= pow2[i]) { n = n - pow2[i]; cout << pow2[i] << " "; } return 0; } // freopen我比赛写了，但是这里我就懒得写了，别打我 // 滑稽滑稽 ``` 这一波在洛谷评测了一下，满分过了，非常好啊，很有精神！  -------------- 写完了之后去看了一眼第二题，第二题看起来很厉害的样子，但是其实一般，仔细分析了一下条件，然后就把代码写好了： ```cpp #include <bits/stdc++.h> using namespace std; int n, w; int a[100010]; bool cmp(int p, int q) { return p > q; } int main() { cin >> n >> w; for(int i = 1; i <= n; i = i + 1) { cin >> a[i]; sort(a + 1, a + 1 + i, cmp); if(i == 1) cout << a[1] << " "; else cout << a[i * w / 100] << " "; } return 0; } // 按照上题“惯例”我又不写freopen了 ``` 然后测了一下，样例一过了，样例二输出了一串0，我心态一点不乱，心态一乱，这个题就绝对搞不出来了。 查了一下，发现在 $i == 1$ 的特判的地方出现问题了。 首先我得弄明白为什么要特判，因为有的时候向下取整可能会取 $0$ ，所以这个时候就要取第一位。 然而，不一定是只有一位的时候向下取整取到 $0$ ，所以只要向下取整取到 $0$ ，直接输出第一名就完事了。 ```cpp #include <bits/stdc++.h> using namespace std; int n, w; int a[100010]; bool cmp(int p, int q) { return p > q; } int main() { cin >> n >> w; for(int i = 1; i <= n; i = i + 1) { cin >> a[i]; sort(a + 1, a + 1 + i, cmp); int u = i * w / 100; if(u == 0) cout << a[1] << " "; else cout << a[u] << " "; } return 0; } ``` 然后本来想去测试样例三的，但是那个东西太长了， $\text{NOI Linux}$ 系统的 $\text{Guide}$ 我不会复制（ $\text{mqy}$ ：那你还写 $\text{freopen}$ 你怎么不会用啊！），那么一大长串一个一个敲不太容易，所以自己去分析了一下数据和我的代码的复杂度： $\text{sort}$ 是 $\text{STL}$ 函数库自带的排序函数，本质好像是堆排序，复杂度是 $O(n \log n)$ ，如果乘上输入的 $n$ 的话我的算法时间复杂度是 $O(n^2 \log n)$ ，前 $50\%$ 的数据没什么问题，但是后面的 $50\% $大概率是炸了，想用桶排序试一试，结果最后不知道哪里出问题了样例都没过，而且当时第四题心态有点炸了（当时是做完了第四题回来看的第二题分析的复杂度，第四题出了点状况，下面会提到），然后不得已放弃了桶排序，还是选择 $\text{sort}$ 排序，加上了一个玄学优化，刚才在你谷测评姬上测了一下，是前 $50\%$ 都对了，但是后面全炸掉了，玄学优化没起任何作用。 插一句不想干的题外话，上学之后 $\text{mqy}$ 来问我第二题的事情，结果他才发现他的复杂度也过不去，当场炸了…… ------------ 第三题……嗯……不会……再见…… 倒不是我懒得读题， $\text{mqy}$ 这个题是用栈做，其实我也想这么干的，结果临时想不起来怎么读取输入的一整行，我就记得是个 $\text{getline}$ ，但是具体怎么写不知道了，最后心态突然就乱了，然后，再见…… 但因为这个题要求输出 $\text{1}$ 和 $\text{0}$ ，所以我灵机一动玄学随机数想骗点分，然后写了个随机数，就保存了…… ------------ 说第四题之前，先插个题外话： 考试之前 $\text{mqy}$ 开玩笑地问我今年 $\text{CSP}$ 可能出什么题目，我也开玩笑的回答说：“今年可能出原题。” 我俩人一笑而过。 谁知一语成谶。 ------------ 第四题，方格取数，对于这个题我也是熟悉的不得了了，每天一看洛谷题库，放在第五题就叫方格取数，题意也差不多。 但很难受，我没做过。 盲猜是 $\text{DP}$ ，但是后来转移方程写错了，写完了才查出来，因为第三题的缘故，心态就已经炸掉了，于是草草了事，骗了点分。 洛谷自测貌似是 $\text{35}$ ？？？ ```cpp #include <bits/stdc++.h> #include <iomanip> using namespace std; int a[1005][1005], dp[1005][1005]; int n, m; int main() { cin >> n >> m; for(int i = 1; i <= n; i = i + 1) for(int j = 1; j <= m; j = j + 1) { cin >> a[i][j]; dp[i][j] = a[i][j]; } for(int i = 1; i <= n; i = i + 1) { for(int j = 1; j <= m; j = j + 1) { if(i != 1 && j != 1) dp[i][j] = max(dp[i][j] + dp[i - 1][j], dp[i][j] + dp[i][j - 1]); else if(i == 1) dp[i][j] = dp[i][j] + dp[i][j - 1]; else dp[i][j] = dp[i][j] + dp[i - 1][j]; } } cout << dp[n][m] << endl; return 0; } ``` 考场的时候也没给只向右或下走的情况，于是我也不知道具体多少分，当时洛谷自测是民间数据，所以真正分数我也不确定。 估分：$100$ + $50$ + $0$ + $35$ = $185$ 这个分在 $\text{LN}$ 是不低的分了，我还算满意了吧。 至少比去年好一点，大概估分只有 $155$ ，最后还因为没写 $\text{freopen}$ 爆 $0$ 了，那心态不就炸了吗。 算了，听天由命吧，我其实今后学不学都不一定了，桑…… 因为 $\text{CCF}$ 今年推迟比赛导致两个省竞赛生还未开始就出局这种情况，再加上一个物理竞赛的学长告诉我竞赛有很多黑幕，我最后被迫暂时退役。 如果初三的时候成绩够好能考上本地著名的的 $24$ 中学，还有机会继续学下去，但是就以我现在的语文成绩，我看有点悬。 也许三年之后，我彻底退役了，再不会有人记得我， $\text{JS}$ 小学（本人母校）也不会记得我的传说，以及 $\text{JS-OI}$ 初代（ $\text{JS}$ 小学首先参加信息学竞赛的四个人的组合，我， $\text{mqy}$ ， $\text{hjz}$ 和 $\text{yzh}$ 四个人，$\text{hjz}$ 和 $\text{yzh}$ 彻底退役，我半退役，仅有 $\text{mqy}$ 目前仍在役）当年大闹信息课的事件。 但我仍然希望，能够在退役前（或许是永远退役了），留下属于自己的荣耀。 $\text{mqy}$ 和 $\text{prdn}$ 还会坚持的，也许他们，能够继续走下去，带着我们的希望，和荣耀。 不知道为什么就偏题了，但是还是因为要退役了，所以很感慨，就多说了两句。（ $\text{mqy}$ ：你管这叫两句？？？） 好了朋友们，山高路远，我们江湖再见。