绝处逢生
Mars_Dingdang
2020-11-05 17:46:03
这篇文章将作为 **CSP-J/S2020** 和 **期中考试** 的游记。
## 11/4
考语文和物理。
刚考完语文觉得悬，时间其实也蛮紧张的。出来对答案发现有几个点争论不休，没有定论。不过语文作为主观科目，对答案也对不出什么东西。
结果物理就是当头一棒，尤其是计算题，两道全错，第一题漏解，第二题列式错误，完美避开正确答案。实验题其实也没有把握，不过据理力争地分析了最后一道实验题和作图题。
回家之后码了一道 [广搜题目](https://www.luogu.com.cn/problem/P2730)，学了康托展开+树状数组维护。然后刷了几套数学，看了几遍历史书。22：00睡觉了（作业要求21：30）。
## 11/5
数学和历史。
>老师的话不可信。
我一直以为 HY 的老师诚实，结果……数学考试恶心至极，时间还紧，直接放弃了填空最后一题和大题最后一小问，答案对下来已经扣了至少 $10$ 分了。
历史也不怎么来得及，还有一题卡住了。
颓洛谷。用 `unordered_map` 水了一道哈希（oiwiki 上的例题），然后随机跳题跳了一道很水的贪心（区间覆盖），切了。最后用线段树 AC 了树状数组，算是复习，然后自学了 RMQ。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int maxn=1e5+5,maxl=20;
int a[maxn],n,m;
//<------------head------------->
#define re register
#define gg (getchar())
inline int read(){
register int x=0,f=1;
re char c=gg;
while(!isdigit(c)){
if(c=='-') f=-1;
c=gg;
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=gg;
}
return x*f;
}
//<----------FastIO----------->
class ST{
public:
inline void init(){
n=read(),m=read();
rep(i,1,n) a[i]=read();
l[0]=-1;
rep(i,1,n)
{
f[i][0]=a[i];
l[i]=l[i>>1]+1;
}
rep(j,1,maxl)
{
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);//Time: O(NlogN)
}
}
inline int query(int x,int y){
int k=l[y-x+1];
return max(f[x][k],f[y-(1<<k)+1][k]);// Time: O(1)
}
private:
int l[maxn],f[maxn][maxl+5];//Memory: O(NlogN)
};
ST s;
//<---------RMQ------------>
int main(){
s.init();
while(m--){
int x=read(),y=read();
printf("%d\n",s.query(x,y));
}
return 0;
}
```
明天英语和道法，不算强项，仔细点吧，加油 rp++！
考完后准备复习图论和基础算法，再练几道动态规划吧。
## 11/6
英语自认为还好，道法也还行。英语出来对答案发现基础好像错了挺多，首字母还好。据收卷同学说我道法写得是全组最少的。
本打算复习 OI 的，结果STEM课题小组要去写论文，于是荒废了半天的时光。晚上有课，因此备战的时间只剩下一个小时，顿时慌的一批。
没有再去看新的算法，自己列了一个提纲，过了几眼高精、逆序对、快速幂、Dijkstra、线段树的板子，公交上还复习了一下MST。晚上回来开始研究 dp 背包和 LCS $O(n\log n)$。
## 11/7
>CSP RP++！
一直以为上午提高组，紧张至极。到考场发现上午普及，安全。
准时开考，有点不适应环境，T1 卡了一会儿，觉得比去年麻烦，想到转二进制，还开了个辅助数组做出来的。T2 一开始没想到正解，用 `sort` and `nth_element` 暴力都失败了，毕竟复杂度是 $O(n^2\log n)$。考虑二分加插排，瞄到数据 $n$ 的上面一行，限制 $score\le 600$，发现 $O(600n)$ 能过，于是码了一个桶排碰运气。
T3 一开始以为是简单的表达式求值，用栈模拟，结果写着写着发现有些复杂，跳到了 T4。“方格取数”第一眼先暴力 dfs，结果还调了好久，拿了 20 分。再看发现跟洛谷某一次月赛的“雷雨”有点像，并且 $|w|\le 10^4$，于是找了个办法化掉了负边权用 Dijkstra 做。连边方式想了一会儿，最后再计算取到的数和 [这题](https://www.luogu.com.cn/problem/P2384) 有点像。
打完发现大样例过了。再回来测样例一，结果SPFA了，原来没法走环。
没思路，跑回 T3，打了一个暴力保佑。
考试出来才知道：T2 好多人没想到桶排；T4 是动态规划；T3 全输出 0 可以拿很多分……
>提高组要抱灵了qaq
就这样担惊害怕的进了考场。密码输了好久不对，拿到 T1 就慌了。听到旁边两位同学都在飞速 typing，于是决定果断放弃，来看T2。发现这题很简单，随便码了一段居然大样例也过了。检查数据范围：$k\le 64$ 用 `unsigned long long`，又试了几组极限数据，判断了一下边界，觉得切了一题。
T3 T4 明显不会，只能骗分，暴力拿了45回去看T1了。
T1 只好硬着头皮慢慢做，还列了一个提纲式的东西，用九十行的代码过了前两个样例，觉得有 $50\sim 60$ 分，收工了。
## 11/8
代码公开了，开始自测。
发现结果让我大跌眼镜。普及 100+100+5+35=240，提高 10+60+25+20=115，彻底炸了。很好奇提高 T1T2 到底错哪里了。不管了。
正解：普及
- T1 二进制模拟，特判奇数
- T2 桶排（强制在线很讨厌）
- T3 表达式树
- T4 dp $O(nm)$
提高
- T1 大模拟（我旁边那位码出来了，结果调试行没注释抱灵了）
- T2 跟我的思路差不多，可能有几个细节
- T3 拓扑
- T4 贪心
1= 无望了。
## 11/9
>还能不能见到明天的太阳？
出期中考试成绩，满分460，我语数外集体翻车，还好有物理历史道法救我。
因数学太不符合水准被蔡帝叫去谈话，给我分析卷子：“这题解三角形找特殊角……这题图都对了还错……这几题都是看错……”说着说着我就100了。
一个礼拜总算结束了qaq