「补档」CSP-S 2020 游记

坐标 HB，TG 选手。

作为初一 OIer，再加上八月份才开始接触 OI，我本打算今年只考普及，但是华一高那边的意思是让我考提高，结果就参加了 CSP-S。

总的来说，今年算是考垮了。

早上 8 点多起床，然后刷了华一高信息组那边上周 CSP-S Day1 模拟考的题，另外看了一下 Tarjan，我因为学校文化课，10 月月考之后工作日就没参加华一高的集训，结果 Tarjan、数论、线代都没学，少考了几场试，CSP-S 之前想着能多补一点是一点。

下午 1 点 20 从家里出发前往华一高考试，有意思的是华一高学长 CSP-S 复赛是在华科考，而我却跑到了华一高来参考。

一号考场是真的拉垮，键盘空格要用力敲才打得进去，而且 Dev C++ 的调试功能也是完全没法用，必须要在桌面上新建项目才能调试，而且还会随机闪退，我 tm 直接当场裂开，代码又得放在 D 盘（怕电脑出问题后重启，所以不能放桌面），我考试的时候就只能频繁的把 D 盘里的代码复制到桌面上调试，然后调完后再复制回 D 盘。我跟监考老师说这个调试有问题，他说能用就行。

考试开始，输解压密码输了半天，0 和 O 分不清楚。

T1

一看是大模拟直接傻掉，搞了一个多小时，勉强把大样例过掉也就不想调了，大样例要跑 0.8s。

#include<bits/stdc++.h>
#define F(name) freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);
using namespace std;
typedef long long ll;

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int y, m, d, t;
int q, r;

inline ll readint(){
    ll f = 1, n = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f *= -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        n = n * 10 + (ch - '0');
        ch = getchar();
    }
    return f * n;
}

inline bool isrunnian(int n){
    if(n >= 1582)
        return n % 400 == 0 || n % 4 == 0 && n % 100 != 0;
    if(n < 0){
        n++;
        return n % 4 == 0;
    }
    return n % 4 == 0;
}
inline int get10000(int y){
    if(y == -4713) return 3652463;
    return 3652425;
}
inline int get100(int y){
    if(y < 1488) return 36525;
    if(y == 1488) return 36515;
    if((y - 88) % 400 == 300) return 36525;
    return 36524;
}
inline int getday(int y){
    if(y == 1582) return 355;
    if(isrunnian(y)) return 366;
    return 365;
}
inline int getday(int y, int m){
    if(y == 1582 && m == 10) return 21;
    if(isrunnian(y) && m == 2) return 29;
    return days[m];
}

int main(){
    F("julian")
    q = readint();
    while(q--){
        r = readint();
        y = -4713, m = 1, d = 1;
        while((t = get10000(y)) <= r){
            r -= t;
            if(y == -4713) y = 5288;
            else y += 10000;
        }
        while((t = get100(y)) <= r){
            r -= t;
            if(y == -13) y = 88;
            else y += 100;
        }
        while((t = getday(y)) <= r){
            r -= t;
            y++;
            if(y == 0) y++;
        }
        while((t = getday(y, m)) <= r){
            r -= t;
            m++;
        }
        d += r;
        printf("%d %d %d ", d, m, abs(y));
        if(y < 0) printf("BC");
        printf("\n");
    }
    return 0;
}

能拿 40pts，还过得去。

那么问题来了，考完试我交上去的代码并不是这么写的，而是长这样：

inline get10000(int y){

内联函数没写类型，CE，完了。

应该是我调试的时候，改完代码忘了复制回 D 盘。测民间数据时哭死在桌上，过于下饭。

T2

T2 是整场考试最水的一道题？？？

我考试的时候想了半天，然后位运算又调了半天，代码长这样：

#include<bits/stdc++.h>
#define F(name) freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);
using namespace std;
typedef long long ll;

struct node{
    int p, q;
    node(): p(0), q(0) {}
    node(int p, int q): p(p), q(q) {}
};
int n, m, c, k, p, q, t, b, ans;
bool digit[70];
vector<node>si;
vector<int>used;

inline ll readint(){
    ll f = 1, n = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f *= -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        n = n * 10 + (ch - '0');
        ch = getchar();
    }
    return f * n;
}

bool cmp(node n1, node n2){
    return n1.q < n2.q;
}

int main(){
    F("zoo")
    n = readint(), m = readint(), c = readint(), k = readint();
    for(register int i = 0; i < n; i++){
        t = readint();
        int j = 0;
        while(t){
            if((t & 1) == 1 && ((b >> j) & 1) == 0) b += 1 << j;
            t >>= 1, j++;
        }
    }
    for(register int i = 0; i < m; i++){
        p = readint(), q = readint();
        if(((b >> p) & 1) == 0) si.insert(lower_bound(si.begin(), si.end(), node(p, q), cmp), node(p, q));
        else used.insert(lower_bound(used.begin(), used.end(), q), q);
    }
    int i = 0, j = 0;
    while(i < si.size()){
        while(j < used.size() && used[j] < si[i].q) j++;
        if(used[j] != si[i].q) digit[si[i].p] = true;
        i++;
    }
    for(register int i = 0; i < k; i++)
        if(!digit[i]) ans++;
    printf("%d", (int)pow(2, ans) - n);
    return 0;
}

没开 unsigned long long，数据范围没看清楚，而且我这个算法好像也不行，还是菜。

而且，

while(t){
    if((t & 1) == 1 && ((b >> j) & 1) == 0) b += 1 << j;
    t >>= 1, j++;
}

这一段我居然手写，明明可以用 |=？？？位运算我好像只有与和位移用的比较熟。

60pts。

T3

暴力都没打好，爆零了。

其实硬着模拟也可以拿点分，我考试的时候却想着能不能用一个 $k$ 存倍数，然后每次单点添加时只添加 $\frac{V_i}{k}$，这样两种操作复杂度都只有 $O(1)$，但显然精度差的太远，我都不知道我考试的时候怎么会想到这么写。

也想到了线段树，但是打得不熟，可能要调很长时间，剩的时间已经不多了。

T4

没时间写 T4，其实有个贪心的思路，应该可以混点分的。

$k=3$ 的那 20pts 都没拿到……

Ending

洛谷 0 + 60 + 0 + 0 = 60，华一高信息组垫底预定。

不知道 HB 这边能不能混个 3=。

还是练的太少了，虽然机器上有些问题，可能在一定程度上影响了发挥以及效率，但是说到底还是自己能力太弱，怪什么都没用。

马上要参加华一高一个月的封闭集训，高一的学长备战 NOIp，我应该是打不了的，但也要跟着好好练，不能再下滑了，再滑就滑没了。

（初一硬是过上了高一的生活，不容易不容易）

总结经验，不能信 CCF 的样例，样例实在是太水了。

考试要会分配时间，要学会打暴力，不要随便用乱搞算法，这样可能连暴力分也拿不到。

平时要好好对待模拟考和洛谷月赛，多做题。

毕竟是第一次参加 CSP，明年 CSP-S 再战。

---

2020.11.14

有道小图灵查分：60pts

预计获奖级别：2=

---

2020.11.17

CCF 初评成绩：0 + 60 + 10 + 0 = 70pts，华一高 rk34，2020 级 rk7。

居然比预期高了 10pts，好像这次 CCF 的数据比民间数据水，学长分数普遍比估分高了 10～20pts。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。