@Mars_Dingdang

绝处逢生

2020-11-05 17:46:03


这篇文章将作为 CSP-J/S2020期中考试 的游记。

11/4

考语文和物理。

刚考完语文觉得悬,时间其实也蛮紧张的。出来对答案发现有几个点争论不休,没有定论。不过语文作为主观科目,对答案也对不出什么东西。

结果物理就是当头一棒,尤其是计算题,两道全错,第一题漏解,第二题列式错误,完美避开正确答案。实验题其实也没有把握,不过据理力争地分析了最后一道实验题和作图题。

回家之后码了一道 广搜题目,学了康托展开+树状数组维护。然后刷了几套数学,看了几遍历史书。22:00睡觉了(作业要求21:30)。

11/5

数学和历史。

老师的话不可信。

我一直以为 HY 的老师诚实,结果……数学考试恶心至极,时间还紧,直接放弃了填空最后一题和大题最后一小问,答案对下来已经扣了至少 $10$ 分了。

历史也不怎么来得及,还有一题卡住了。

颓洛谷。用 unordered_map 水了一道哈希(oiwiki 上的例题),然后随机跳题跳了一道很水的贪心(区间覆盖),切了。最后用线段树 AC 了树状数组,算是复习,然后自学了 RMQ。

#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 做。连边方式想了一会儿,最后再计算取到的数和 这题 有点像。

打完发现大样例过了。再回来测样例一,结果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