chen_zhe 的博客

chen_zhe 的博客

CSP-S2 2020 游记

posted on 2020-11-08 11:26:48 | under 未分类 |

考点七宝中学。

先吐槽一下交通出行。选了一条最不适合人走的路(,中间全是外环边上的防护林绿道或者单车道小马路。然后考场附近没有任何小卖部。

然后在考场外面和我校(紫竹)各位神仙互膜同时讨论起了期中考试……期中考试果然不止我一个人炸(((

然后就进考场了。七宝的电脑其实配置还行,4 代 i5,但是(至少是我的)电脑上的软件非常可怕,chrome+QQ 浏览器+360 极速浏览器+忘了什么浏览器,然后后台一直有进程把 cpu 跑到 50%,使得用起来有点一卡一卡的。键盘的话还可以,就是 del 键比较大。考试之前先看了一眼压缩包里面的文件名,call julian snakes zoo,感觉不太好惹。

密码具体细节忘了,其实看到 Ke Yi 的时候我还以为是科艺,然后看到后面 Gong Yu 还以为科艺开了公寓。然后想了想是可以攻玉。那上午密码应该是他山之石?

然后就看了个题。其实一开始只看了 T1 T2。T2 第一眼没看懂就先开始干 T1 了。其实 T1 的话刚开始读题确实感觉不难,然后越写越恶心。比如说我看错了 1582 年之前和之后的闰月判断,如何快速获取 1582 年之后的日期之类的。大概想法就是在 1584 年之前的日子按 4 跳(4 年=1461 天),然后再一个一个跳,最后 O(1) 判断出月份日期(枚举 1-12 月一个一个对着剩余日期减)。这样做是单次 O(1) 的。然后再考虑对 1584 年之后的日子按 400 跳(400 年=146097 天),然后再按 4 跳,同时补齐多减的 100 倍数。对于 1582 年各种特判。然后这么整了两个半小时之后过了大样例……代码非常恶心。

然后的话就光速写完 T3 T4 暴力。T3 的话大概拿了暴力去硬算分和只有乘法操作的分,因为我感觉我考场上打不出线段树 2。然后 T4 20 分 n=3 写挂了。

(人间迷惑行为)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

int a[3000050];

int main()
{
    //freopen("snakes.in","r",stdin);
    //freopen("snakes.out","w",stdout);
    int T;
    scanf("%d",&T);
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    if (a[3]>a[1]+a[2])
        printf("1\n");
    else
        printf("3\n");
    T--;
    while (T--)
    {
        int k;
        scanf("%d",&k);
        for (int i=1;i<=k;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            a[x]=y;
        }
        sort(a+1,a+n+1);
        if (a[3]>a[1]+a[2])
            printf("1\n");
        else
            printf("3\n");
    }
    return 0;
}

(怎么挂的懂的都懂)

然后去看 T2。本来也就是先打了个暴力。打完暴力对着题目再看了两眼,发现其实本质水题。目前有的饲料的二进制位是可以选的,目前没的饲料的二进制位不出现在饲料清单上的也是可以选的,那么设可以选的位数是 $cnt$,那么答案就是 $2^{cnt}-n$。然后就这么写了几分钟过掉了大样例就没管。

然后出了考场一看群,发现对于 $100 \%$ 的数据,$0 \le n, m \le 10^6$,$0 \le k \le 64$,$1 \le c \le 10^8$。

那么 $2^{64}$ 喜提爆炸。而且我开的是 ll 不是 ull。而且我开了个 map 去存。那 $O(n \log n)$ 喜提爆炸。反正民间数据只测了 60 分。

最后考场估分:100+100+10+20=230。民间估分:40+60+25+15=140。

一天考的和我去年两天差不多多,也是迷惑。

反正之后就专心搞一个月的 OI,退役之前打个漂亮战吧。