首页 > 其他分享 >游记 CSP2023-S2

游记 CSP2023-S2

时间:2023-10-22 16:14:52浏览次数:33  
标签:off vars S2 CSP2023 back mpt nowt 游记 typ

游记 CSP2023-S2

今年根本没有报名 J 组。

听说有人要开盒,感觉差不多得了,oierdb 搜 cjh 第一个就是我啊,怎么藏?感觉真的有有心人在查我,我早就被打回去了啊。

9.16

初赛过了就是过了,游记弃之,作文素材 +1。

10.20

在 S 校进行集训,打模拟赛,怎么突然这么会打了,能过两个题了,感觉很厉害,然后 xzzduang 马上给我打爆了。

今天是星期五。中午的时候,xzzduang 来了。他从周四模拟赛(他组题)讲起,说代码能力,说南京卷王怎么卷,然后大概后面的时候 Robin 过来聊起高考分数。令我惊奇的是,南京的卷王,他们除了每天 NOI 模拟赛的三个题都写完,还有 ARC 全部做完,CF div1 全部做完,俄罗斯有个训练营也全做,ucup 还有的时候也全做。

我问

10.21

8:00

和 S 校同学讨论虚拟机问题。算是知道了共享文件夹怎么用。

  • zhangtx:为啥你们这群初中崽都没去考j啊
  • caijianhong:因为去年AK了
  • NobodyThere:是这样的
  • NobodyThere:总之就是没必要考吧
  • crxis:今年入门组新增1000人,但是ak人数却大大减少了,为什么呢?
  • crxis:……所以早上可以参加入门组,顺便试机吧

13:40

OK 啊这边也是在石门中学打卡,还在下雨,好冷,怎么又是科学楼五楼,考 NOIP2022 的地方,完了怎么这么熟悉,完了怎么环境是完全一样的,求求了不要重现 NOIP2022(我的辉煌战绩之 NOIP2022 挂掉整整两个题获得整整 87 分)

14:05

怎么没人认出我?

为什么矿泉水瓶要将标签撕掉?那么水杯呢?我的铁打水杯和纯透明矿泉水瓶怎么都进去了???

14:27

密码下发了,具体忘了(因为今年游记是赛后写的)

键盘抬起!

但是下发文件在哪里?我看看快速访问,D:\ 没有,E:\ 没有,C:\ 没有,C:\user\admin_\Desktop 都没有?然后考生注意事项,怎么查看 pdf 的文件所在路径呢?但是桌面有个虚拟机,先来点虚拟机启动。暂时先不要管下发文件了,先玩玩虚拟机。

虚拟机开机。我还是第一次用 NOI Linux 虚拟机(真的),然后发现了 ~/桌面/ 下面的 share_dir 和 share.sh。想必是共享文件夹,但是怎么用?运行 ./share.sh,问我 admin_ 的密码???傻掉了

14:30

老师您能不能帮我看一下这个虚拟机怎么用共享文件夹?

(同一时刻终于发现文件在 F:\ 下,吓死了,好慌)

老师:我去找个人帮你解决一下。

开题,先看一遍题目。

T1 是个什么题?\(5^{10}=9765625\)(算错了应该是 \(10^5\)),直接暴力能过吧。

T2 首先有一个明显的栈做法,类似括号匹配,可以做一下。

T3 什么模拟能放 T3 的?

T4 是个什么题?连通块 DP?

在等待的过程中,我发现 windows 下有 gvim(梁老师诈骗我说只有 dev-c++ ?)。直接启动 powershell 在 windows 下完成了 T1 的代码。看上去很好写,有个溢出和相邻的问题,调一下就过了。那么现在是

14:59

也就是平常 8:00 开始模拟赛对应的 8:30,我怎么这么厉害秒 T1 了?

老师过来了。指导了一下,首先离开虚拟机环境,打开设备,共享文件夹,其它路径,挂载,自动挂载,然后就能传文件了。

我问老师,最终代码提交到那里?老师说是 windows。好的。

心中的一块巨石落地,今天可以纯用虚拟机完成代码。正片开始。

我把共享文件夹扔到 F:\,重新挂载,试了一下虚拟机关机。根本关不掉虚拟机,只能挂起。然后再次阅读 T3,发现 T3 就是纯纯的模拟,发现 T4 的起始点是 1 号点,好像能做了?

15:30

好像是这个时间吧,写了暴力。大致思路是,枚举左端点,扫过去,用一个栈。加入新字符时,如果与栈顶元素相同,弹栈,否则入栈。在所有使得栈空的右端点统计答案。这是一个 \(O(n^2)\) 暴力。

为了优化暴力,首先就是想能不能利用前面的匹配信息。若从右往左扫,可以搞一个 \(to_i\) 表示他第一次能弹空栈的地方是哪里,或者是 \(to_i=n+1\),那么如果 \(to_i\leq n\) 则 \(f_i=f_{to_i+1}+1\),其中 \(f_i\) 是以 \(i\) 为右端点的答案。

进一步的我们发现可以写一个暴力,就形如初始令 \(j=i+1\),循环当 \(a_i\neq a_j\) 时,使得 \(j=to_{j}+1\)。当然 \(j\leq n\),否则报告 \(to_i=n+1,f_i=0\)。

考虑这个过程,因为字符集太小了,考虑 \(nxt_{i,r}\) 表示当 \(j=i\),\(a_i=r\) 时最终会跳到哪里。那么 \(to_i=nxt_{i+1,a_i}\)。如果合法,那么从 \(nxt_{to_i+1}\) 继承所有信息,同时 \(nxt_{i, a_i}=i\)。

复杂度 \(O(26n)\)。稍微调一下边界,过一下大样例,过了。这题的数据很难造强,不打算对拍。当我将代码提交到 windows 时已经是

16:00

也就是平常 9:30,一个小时过掉 T2。进度有点快了。因为 T4 暴力有点难写,不确定在树上贪心的想法是不是对的,打算写个 T3。

T3 分界线

T3 是个大模拟,C++ 是没有 eval 这种东西的,比较暴躁。这题的重点是怎么存储结构体和变量,以及计算 offset(偏移量)和 align(对齐)。

写一个 type_wrapper 表示一个结构体。

struct type_wrapper {
    vector<pair<string, string>> vars;
    LL Align, Size;
    vector<LL> offset;
};

vars 就是结构体变量,使用 vector<pair<string, string>> 存,first 是类型,second 是名称。Align 就是对齐规则,Size 就是真实大小,offset 是每个变量的偏移。话说想起来小周老师写的,会出技术类大模拟,果真如此。

使用 map<string, type_wrapper> mp 存储所有结构体信息。

操作 1

            int k;
            string name;
            cin >> name >> k;
            type_wrapper typ;
            typ.Align = 0;
            typ.offset = vector<LL>(k);
            for (int i = 0; i < k; i++) {
                string t, v;
                cin >> t >> v;
                auto &&mpt = mp[t];
                typ.Align = max(typ.Align, mpt.Align);
                if (i != 0) {
                    LL tmp = typ.offset[i - 1] + mp[typ.vars.back().first].Size;
                    typ.offset[i] = calcoff(tmp, mpt.Align);
                }
                typ.vars.emplace_back(t, v);
            }
            typ.Size = 
                calcoff(typ.offset.back() + mp[typ.vars.back().first].Size, typ.Align);
            mp[name] = typ;
            cout << typ.Size << " " << typ.Align << "\n";

就摁建,摁算就是了。

calcoff 就是算对齐的,是一个向上取整再乘回去的东西。

操作 2

全局的变量,存储方法有一点不同,其实可以再新建一个 root 类型。但是因为我一开始没有看到全局变量也要对齐(?)所以还是开在外面,用 f 前缀标志全局(final,不对啊反了,不管)。

            string t, v;
            cin >> t >> v;
            if (foffset.empty()) foffset.push_back(0);
            else foffset.push_back(calcoff(foffset.back() + mp[fvars.back().first].Size, mp[t].Align));
            fvars.emplace_back(t, v);
            cout << foffset.back() << "\n";

操作 3

访问就直接访问就是了啊,暴力啊。记录当前访问到的类型,然后去找变量。

string name;
            cin >> name;
            vector<string> vec = split(name, '.');
            LL off = 0;
            string nowt;
            for (size_t i = 0; i < fvars.size(); i++) {
                if (fvars[i].second == vec[0]) {
                    off = foffset[i];
                    nowt = fvars[i].first;
                    break;
                }
            }
            for (size_t d = 1; d < vec.size(); d++) {
                auto &&mpt = mp[nowt];
                for (int i = 0; i < mpt.vars.size(); i++) {
                    if (mpt.vars[i].second == vec[d]) {
                        off += mpt.offset[i];
                        nowt = mpt.vars[i].first;
                        break;
                    }
                }
            }
            cout << off << "\n";

操作 4

主要是特判边界和溢出的情况。

LL off;
            cin >> off;
            if (fvars.empty() || off > foffset.back() + mp[fvars.back().first].Size) {
                cout << "ERR" << endl;
                continue;
            }
            vector<string> ret = {};
            string nowt;
            bool flag = 1;
            for (size_t i = int(fvars.size()) - 1; i >= 0; i--) {
                if (off >= foffset[i]) {
                    off -= foffset[i];
                    nowt = fvars[i].first;
                    ret.push_back(fvars[i].second);
                    break;
                }
            }
            while (true) {
                auto &&mpt = mp[nowt];
                if (off >= mpt.Size) {
                    //overflowed
                    flag = 0;
                    break;
                }
                if (nowt == "byte" || nowt == "short" || nowt == "int" || nowt == "long")
                    break;
                for (size_t i = int(mpt.vars.size()) - 1; i >= 0; i--) {
                    if (off >= mpt.offset[i]) {
                        off -= mpt.offset[i];
                        nowt = mpt.vars[i].first;
                        ret.push_back(mpt.vars[i].second);
                        break;
                    }
                } 
            }
            if (!flag) {
                cout << "ERR" << "\n";
                continue;
            }
            for (size_t i = 0; i < ret.size(); i++) {
                cout << ret[i] << ".\n"[i + 1 == ret.size()];
            }

感觉挺自然的,其中有几次段错误和除以零,随便调一下就出来了,原因是内层的循环没加 break 和其它一些全局内部不分的。属于是 gdb 一跑就能指出来。

过大样例

测样例二发现怎么第二个变量的 offset 错了,才看到原来全局变量也要对齐的?还以为不用。其实这个全局感觉有点麻烦了,我也不想重新写,就这样吧,后面样例都过了。

17:15

平常时间 10:45 什么幻想时间?

然后想象 T4。

首先菊花会不会?我们可以二分答案 \(lim\),然后处理一个 \(t_i\) 表示这棵树必须要在 \(t_i\) 时刻前(包括 \(t_i\))种掉,可以再写一个二分来点分段一次函数(\(\max(b_i+c_ix,1)\) 可以先求出相交点,然后分讨)。然后关于贪心的部分,有一个想法就是用一个优先队列存下当前可以种的树,然后选出 \(t_i\) 最小的那个种掉。例如第 \(i\) 天的决策是 \(u\),如果 \(t_u<i\) 就寄了,\(t_u=i\) 就一定是你了,但是 \(t_u>i\) 怎么说?相同的怎么说?

因为种了以后要将自己的儿子加进去,自己的儿子的 \(t\) 比自己小是确实的,我们不仅关心自己还关心儿子。不妨使得 \(g_i=\min_{v\in subtree(i)}t_i\),就是自己子树内的最小值,用这个作为比较关键字。然后就行了,\(O(n\log^2n)\)。

然后开始写,主要是 \(t_i\) 很难求,一直写错,拿暴力换掉二分就是对的,所以一定是我错了。发现有个乘法溢出问题,因为 \(b\leq 10^{18},|c|\leq 10^9\),然后保证 \(10^9\) 内有解,真的抽象,算的时候要对 1e18 取 min,然后别前缀相减啊。

18:00

终于写对了。过了四题大样例了。胜利宣言:

//I'm in vim of the ternimal of noi linux. I cannot type Chinese charaters.
//The time is 2023/10/21 18:02, 
//and I have passed all the samples.
// --caijianhong, GD-S01538, in Foshan Shimen School

但是 T4 大样例要跑 1.2s,一看时限怎么只有 1s,我复杂度假的?确实看上去是个 1log 题,但是我不是很会怎么 \(O(1)\) 求 \(t_i\)。考虑两个方向:

  • 把优先队列换掉,换成一个指针就行。但是有清空问题,我没调出来,最后回档了。
  • 把 \(g_i\) 从 dfs 换成 dfn 序倒推,要跑 0.8s,应该是过了。

18:13

由此我过了四题大样例,最后交到 windows 打包再测一次,写了一个脚本 test.sh 全部批量测大样例,但是发现不会用,./test.sh 没有权限,是说没有 sudo?sudo 也不行。不会了啊。于是只能复制出来测。

然后四个题的大样例都过得很顺利,user time 都在时限内。

监考真的我哭死,竟然问我有没有把文件放到 windows,他真的我哭死。

18:30

考完啦,估分直接 400 好吗?

18:45

好久不见彭老师了,我说我过了四题大样例。然后其他人好像都挺爆炸的,疯狂问做法。

天黑了,没有拍照。

黄队过了四题大样例,Mobius_127(我找不到一个合适的称呼。。。)过了四题大样例。

晚上

吃饭以后就在讨论自己怎么挂,云斗很快就有数据了,测出来 \(100+100+100+95\)?

然后黄队也挂 T4 了,\(t_i\) 求错,突然意识到 一次函数前缀和 的另一个说法是 不定积分,怎么想不到的,数学水平有点离谱。

然后发现 T4 的一次函数与 \(y=1\) 相交的点,写成了与 \(y=0\) 相交的点。草。

- LL pos = c[i] ? max(-b[i] / c[i], 1ll) : 1ll;
+ LL pos = c[i] ? max((1 - b[i]) / c[i], 1ll) : 1ll;

痛失 AK。然后其他人也很惨,运行时错误的好多,Mobius_127 挂没了?

Sunny郭 挂没了,怎么会是呢?

allenchoi 挂没了,怎么会是呢?

Lucky_Luo 怎么要起飞了,要提高一等了,膜拜。

10.22

洛谷 \(400\)

小图灵 \(400\)

云斗 \(395\)

计蒜客已经造了前三题,都过了。

就等吧,等就是了。

打的很开心,同时意味着下周不用回 HY 学校了。我到底是想去 HY 还是不想去 HY,我自己都说不好。上一句话到底应该是“去” go 还是”回“ return 我也不清楚。

标签:off,vars,S2,CSP2023,back,mpt,nowt,游记,typ
From: https://www.cnblogs.com/caijianhong/p/travel-in-csp2023.html

相关文章

  • CSP-S 2023 游记
    初赛部分Day1真的有必要写吗?如有。感觉还是要延续之前CSP游记的排版。考前复习了半个小时初赛,优势在我。好像迟到了一点点,监考员没有给我发试卷,但是给我发了两张知情同意书。睡觉。出来对答案,错了几个,一个忘了有二分上下界,还有一个是linux下编译。有人NOI考完之后忘......
  • CSP2023游记
    初赛忘了,反正记得很早做完开摆了,然后最后错了一个阅读,原因是直接默认\(A\)远大于\(n\),然后忽略了复杂度中的\(n\logn\)了。/cf复赛Day-1给J组小盆友出了点模拟赛,晚上去讲了两次题,顺便zyq去拿奶茶,被徐嘉正质问为什么不敢点ez(准备蹭xjz一顿大餐。本来xjz说要......
  • CSP-S2023 游记
    \[\text{比较抽象的一集}\]Day-INF初赛\(79\),过了Day-10~Day-1天天模拟赛挂分,无语住了Day0疯狂写板子,晚上写数学板子每一个一次过的,感觉要寄学习了如何使用Sublime,感觉吊打DevDay1早上打摆,看旁边的人玩了一上午CS1.6看了看普及组的题,感觉T4很难,预感要寄......
  • 游记——CSP-S2023 SD 第二轮游记
    游记——CSP-S2023SD第二轮游记Day0晚上从青岛出发,到了日照,路挺顺。试机,门口很堵,还好我进的早。考场是C404,转了几圈才找到(和几年前的小学组很近大学操场有小情侣,羡慕,呜呜呜。。。考场FTP没调好,说19:30考试19:45都没进屋。一堆普及组的来提高组试机(旁边的大佬1......
  • 2023CSP-S游记
    2023CSP-S游记赛前上午去花卉市场看了半天花,算是放松放松,主要是为了晚上给干妈过50岁生日。还以为是2点开始,1点40多就到了,然后去买了杯奶茶,然后进场。结果我是第一考室第一个QwQ赛时花了半个小时看题,思路都是很快的出来了。T1以为是一个分讨,结果直接枚举就可以了,......
  • CSP-S 2023 游记
    CSP-S2023游记Day1上午早上起来洗完漱,逛了一会淘宝便打开电脑,看了看谷群,结果J组的题已经出来了???这变成同步赛了吗?但群里没有人发(看来大家都遵纪守法),我顺着源头找到洛谷团队并成功收到了题和密码,看样子应该是有考场没关网(听说那个考场有人玩原神???)随即简单看了一下J组的题目......
  • CSP-J2023游记
    第一轮Day00天警告Day1开考,听说是姜sir批卷,也没啥好紧张的了。选择题靠我垃圾的C++,第一题就错了/cf,两道数学题和位运算倒是秒切。阅读程序很顺利,只错了一道,到了补全程序只剩\(10\text{min}\)了,瞎蒙了几个,居然对的还不少。出来后找byr对答案,他说他忘了,差评。Day\(\in......
  • CSP2023 游记
    前言停了大概二十几天的课,考出了这样一个难看的成绩。虽然用教练的话来说,只是CSP,还是要看noip。希望noip好运吧。初赛今年初赛成绩在高中部好像还不错?但是被初中学弟吊打了。https://www.luogu.com.cn/discuss/687363Day-1颓。一整天只看题不写题。上午和同学讨......
  • 【游记】记一次2天游桐庐雅鲁
    一、8月19号下午12:00出门吃个午饭 下午13:10出发去桐庐 下午17:05到达桐庐县城,先去了预定的电竞酒店 下午17:30办理好入住信息,开机玩会儿游戏 下午18:53出门吃饭,搜了个附近的烧烤店,大概1.88公里,走了半个多小时到了之后发现店里没啥人,而且周边也没啥吃饭的店,......
  • CSP2023 补题游记
    day-?10月14日,和zybzxh打洛谷普及组模拟赛,我们三个没一个ak(xs)我和zyb挂T3,zxh不会T4。大概就这样打了356.10月15日切CF的dp题。爽洛谷的膜你赛没打16日至19日继续磕CFdp题。有点上难度哈。21日,比赛日上午继续怼恶心的CFdp。中午12......