NOI 2023 游记

· · 生活·游记

觉得应该写一写游记，毕竟大考机会很少，把每次考试的策略记下来没准会有用。

Day ?

没进省队，意料之中，买了 D。当时 pdqb 心情不好，没有报名，血亏。

教练说不应在国赛上做过多准备，我觉得很对。

Day -9

久仰 UNR 大名，没想到这天就是 Day 0，我还没背笔试呢！没有参加。

看了 UNR 2022 D1T1，很快写完了，然后 WA 了两发才过。

Day -8

UNR Day 1。没有切 T1，觉得这场比赛不太好，就没再管了，赛后写了个 T1 最短代码，后来有人更短了。

Day -7

高一有模拟赛，所以没参加 UNR Day 2。

Day -2

和教练、fzj2007 坐高铁，然后打车，晚上到了成都七中旁边的酒店，十二点多才睡，睡前闲着没事给 Dr_Gilbert 发了 [糗大了]\times 114，Dr_Gilbert：半夜十二点不睡觉，小心我告诉\blacksquare老师。

Day -1

教练说早点过去报道，没准儿能买到纪念品，于是我们很早就去了，被拍了好多照片，还被采访了。好多照片被剪到了开幕式里，由于采访时我俩的发言太拉胯，只被剪进去了一点。fzj 把名字签到了空着的签名版的中间，我签到了他左下方。送了不少纪念品，但没发现能买的。我以为 D 类宿舍会被分到一起，然而并不是，和我同住的是 fzj2007、Ignotus 和 ice_cup。中午原来是打算等高二的来了之后一起吃必胜客，结果高二的堵半路上了，王老师带着我们吃的火锅。晚饭在学校吃的，非常有水平，以后的饭都有水平，不再赘述。写了原神。

Day 0

开幕式非常有水平，好评！下午试机、笔试，等着进去的时候我问了问 Ignotus：“不带座次条扣几分？”Ignotus：“5 分。”

结果笔试真的考了这题！我寻思门口也没贴这题啊（门口啥也没贴），要不是我问了，就要扣分了，Ignotus 好闪，拜谢 Ignotus！笔试用机子登录自己的账号线上答题，题目与给的题库有一定区别，有的题我不确定，好在有惊无险。

得分 100 pts。

Day 1

考试日。感觉纪律不如中考严。机位 D043。

08:00~08:10

开始答题，秒了 T1。

08:10~09:15

写完 T1 了，连过 6 个样例，样例 7 RE 了，是第三类询问的去重没处理好，在 sanitizer 的帮助下很快调过了所有大样例。

09:15~10:30

写 T1 的拍。我不太会使 Linux，过程中终端崩了两次（考后分析应该是我数据造错了，导致程序 RE）。写拍的时间竟然跟写 T1 的时间一样长，严重失误。

10:30~12:36

开始做 T2，直接看部分分。前一段时间不知道在干啥，好像是吃东西和上厕所？厕所有人喊“怎么调不出来线段树合并啊！”

想了一下 m=2，假了，感觉不太能做，换思路想出 m=1，m=1 我大概是这么写的：

int r=0;
memset(g,0,sizeof g);
for(int i=n;i;--i) ++g[f[i]],r+=g[i]+1;
return r;

考后发现这就是 return n*2-1。

一看表卧槽怎么这么晚了，赶紧写 n,m\le 4。感觉爆搜会 T（确实会 T，但数据水了大部分人的搜过了），于是打的表，发现答案与树的形态无关，我以为表打错了，但没时间了，粘上“错”表赶紧去看 T3（如果时间充足，接着 m=1 的思路应该能想出 m=2）。

ps：十分弱智的俩小时，不知道当时我在干啥。

12:36~13:00

狂写 T3 爆搜，写完了。收卷。

出去之后老师问分，我垫底了。ice_cup 说他打表发现答案与树的形态无关，还打出来了 k=0 的式子，喜提 70 pts。我打了表，发现答案与树无关没往规律上想，反而怀疑表有问题，血亏。

出分了，没挂，得分 100+25+24=149 pts。

主要失误在于写拍时间过长、中间俩小时不知道在干啥、T3 预留时间过短以至于没写 k\le 6 的 12 pts。

晚上听讲题，T2 正解也与树的形态无关，差评！

查成绩时看到坐我右边的人了是 ZJ-02。

Day 1.5

虽然叫 Day 1.5，但其实是 Day 1 和 Day 2 中间的一整天。原计划为社会活动，但大运会将在成都举办，上面不允许我们乱跑，于是改为活力嘉年华。8 个通关活动，通关任意 3 个可以去领钥匙扣。

先射箭，第三箭射到第二箭上了，没上靶，寄。然后去敲锣，通关。然后扔飞盘，通关。然后反复尝试另一个扔飞盘，过不去，决定回去排队射箭。在活动快结束时轮到我了，通关，喜提钥匙扣。fzj2007 射中十环，拜谢 fzj2007！Ignotus 通关我觉得最难的“穿越火线”，拜谢 Ignotus！Alex_Wei Ak Day 1.5（通关所有活动），拜谢 Alex_Wei！

排队太久，太阳太闪，有点头疼，睡了一觉好点了。

晚上 fzj2007 押 Day 2 考字符串，我打算复习 SA，然后忘了，成功伏笔。

Day 2

考前问了问 fzj2007 和 Ignotus，得知历年 D2T1 可做，于是打算刚一刚 T1，但想正解不能超过 2 小时，总耗时不能超过 3 小时。机位 A065。

07:52~08:00

发现 Alex_Wei 坐我右边，杨耀良在我左边监考。

08:00~10:??

开考，做 T1，发现 u 到 v 的路径一定是先到一个 u,v 的公共祖先然后再往下走，可以维护由 lca 向上再向下的路径。码码码，过不去样例 2，写拍调试。往下走这一部分的处理连着假了好几次，改成 DP，再改成 Dijkstra，终于过掉前几个样例，然后过不去后两个样例。

10:??~11:08

为什么过不去还拍不出来？这么大的样例咋调啊？然后发现样例输出比我答案小很多。仔细读题，发现“你只需输出答案对 998244353 取模的结果”，赶紧加上 fsanitize=undefined 测了一下，发现没有整型溢出，答案模 998244353 还是不对。此时快到 11 点了，我决定弃掉 T1，弃之前先把 long long 换成 int，然后加了一堆取模。然后，然后它就过了所有样例。我懵了，看来之前的写法溢出了，而 sanitizer 没查出来，浪费了我几十分钟，差评！

Alex_Wei 经常上厕所，看他游记，原来是上一次厕所切一道题。听到杨耀良一边监考一边吃东西。

11:08~12:00

发现 T2 暴力有 36 pts，但比较字典序用哈希比 SA 多个 log，可能会少 4 pts，于是决定先写 T3，根据剩余时间决定 T2 写哪个做法。

T3 打算模拟退火，但是发现不好退，保险起见写了个 10 pts 暴力。

12:00~13:00

感觉时间够用，想到 Ignotus 说过“SA 3 分钟就能写出来”，于是决定写 SA。然后没调出来，发现 rk 里有 0，最后一分钟加了个 if(rk[i]<1) rk[i]=1; 考试就结束了。

出场问分，没有垫底。

下午查分，右边 Alex_Wei 那聚着一堆人，他 275 pts。我 T2 没挂完，剩了 16 pts。

得分 100+16+10=126 pts。

主要失误在于又双叒叕没有一次写对 Dijkstra，以及没写出 SA。

upd：看代码发现写对 SA 了，-20 是因为多测没清空。

考完一共 375 pts，教练和 youwike 都说我 Ag 稳了。zfy2006 T3 模拟退火得了 50 pts，害怕。晚上看流传出来的成绩单和分数线，吓了一跳，大家说 Ag 线不可能到 407，我也有一丝侥幸，不过有 Cu 我就满意了。

Day 3

颁奖，蒋婷婷宣布分数线的时候全场鸦雀无声，结果 Ag 真就 407，而我如果多测清空、D1T3 写了 k\le 6 就有恰好 407，悲。

成都下雨，飞机晚点了。

徽章

主要在 Day -2 换了徽章，我有个徽章掉到柜子缝里捡不出来了，还有个徽章给 HE 的淸梣ling留着，后来他徽章不够了没跟我换，所以只换了 28 个，有些是跟 fzj2007 蹭的，不知道是谁的，下面写这 28 个徽章的来历（忽略大小写和下划线后按字典序排序）：

1kri

Acestar

Alex_Wei

APJifengc

asmend

Chen_jr

_Cx330

Delov

Dr_Gilbert

fzj2007

_gch_

H_Kaguya

ice_cup

Ignotus

Johnsonloy

Linshey

Mitama

peop1e

sleeping_crawlers

SoyTony

steven144

worldvanquisher

youwike

zfy2006

zhoukangyang

?

?

?

代码

Day 1 看完成绩之后回宿舍，学长说可以把自己的代码拍下来，但是我懒得再去了，就没拍，后悔。Day 2 拍了，以便调试寄了的 D2T2。

home > HE-17 > trade > trade.cpp

#include<bits/stdc++.h>
using namespace std;
const int N=262200,p=998244353;
int n,m,q,f[N],sz[N],h[N],ans;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long g[N];
struct node{
    bool sz;
    long long tag;
    vector<pair<int,long long>>vec;
    void build(){
        vector<pair<int,long long>>tmp;
        for(auto x:vec) if(!tmp.size()||x.second<tmp.back().second) tmp.push_back(x);
        vec=tmp,sz=1,tag=0;
    }
    void upd(int x){
        tag-=f[x];
        if(sz&&vec.back().first==x) vec.pop_back();
        sz=!vec.empty();
    }
    int sum(){return sz?(vec.back().second+tag)%p:0;}
}tr[N];
vector<int>son[N];
#define ls (i<<1)
#define rs (ls|1)
vector<pair<int,int>>e[N];
long long dis[N];
bool vis[N];
void dij(int s){
    for(int x:son[s]){
        if(x!=s) e[x].push_back({x/2,f[x]});
        dis[x]=inf,vis[x]=0;
    }
    dis[s]=0;
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<pair<long long,int>>>q;
    for(int k=0,x=s;k<son[s].size();++k){
        while(vis[x]&&q.size()) x=q.top().second,q.pop();
        if(vis[x]) break;
        vis[x]=1;
        // printf("updated %d in %d\n",x,s);
        for(auto y:e[x])
            if(dis[y.first]>dis[x]+y.second)
                q.push({dis[y.first]=dis[x]+y.second,y.first});
    }
    for(int x:son[s]){
        if(x!=s) e[x].pop_back();
        if(dis[x]<inf) tr[x].vec.push_back({s,dis[x]+g[x]-g[s]});
    }
}
void add(int&x,int y){if((x+=y)>=p) x-=p;}
int main(){
    freopen("trade.in","r",stdin);
    freopen("trade.out","w",stdout);
    scanf("%d%d",&n,&m),q=1<<n;
    for(int i=2;i<q;++i) scanf("%d",&f[i]),g[i]=g[i/2]+f[i];
    for(int i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),e[u].push_back({v,w});
    for(int i=1;i<q;++i) for(int j=i;j;j/=2) son[j].push_back(i);
    for(int i=1;i<q;++i) dij(i),tr[i].build();
    int _sz,_sum;
    // for(int i=1;i<q;++i){
    //     printf("%d:",i);
    //     for(auto y:tr[i].vec) printf("(%d,%lld)",y.first,y.second);
    //     puts("");
    // }
    for(int i=q-1;i;--i){
        sz[i]=son[i].size();
        if(ls<q){
            _sz=_sum=0;
            for(int x:son[rs]) add(_sum,tr[x].sum()),_sz+=tr[x].sz;
            ans=(ans+(h[ls]+sz[ls]*1ll*f[ls])%p*_sz+_sum*1ll*(sz[ls]+1))%p;
            _sz=_sum=0;
            for(int x:son[ls]) add(_sum,tr[x].sum()),_sz+=tr[x].sz;
            ans=(ans+(h[rs]+sz[rs]*1ll*f[rs])%p*_sz+_sum*1ll*(sz[rs]+1))%p;
            add(ans,h[i]);
        }
        h[i/2]=(h[i/2]+h[i]+sz[i]*1ll*f[i])%p;
        // printf("i=%d ans=%lld\n",i,ans);
        for(int x:son[i]) tr[x].upd(i);
    }
    printf("%d",ans);
    return 0;
}

home > HE-17 > string > string.cpp

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
char s[N];
int rk[N],sa[N],st[20][N],lg[N];
void ss(int n){
    static int id[N],bu[N],p;p=0;
    for(int i=1;i<=n;++i) ++bu[s[i]],lg[i]=lg[i-1]+(2<<lg[i-1]==i);
    for(int i='b';i<='z';++i) bu[i]+=bu[i-1];
    for(int i=n;i;--i) sa[bu[s[i]]--]=i;
    for(int i=1;i<=n;++i) rk[sa[i]]=s[sa[i]]==s[sa[i-1]]?p:++p;
    for(int i=1;i<n&&p<n;i<<=1){
        memset(bu,0,sizeof bu);
        for(int j=n-i+1;j<=n;++j) id[j+i-n]=j;
        for(int j=1,k=i;j<=n;++j) if(sa[j]>i) id[++k]=sa[j]-i;
        for(int j=1;j<=n;++j) ++bu[rk[j]];
        for(int j=2;j<=p;++j) bu[j]+=bu[j-1];
        for(int j=n;j;--j) sa[bu[rk[id[j]]]--]=id[j],id[j]=rk[j];p=0;
        for(int j=1;j<=n;++j) rk[sa[j]]=id[sa[j]]==id[sa[j-1]]&&id[sa[j]+i]==id[sa[j-1]+i]?p:++p;
    }
    for(int i=1,k=0;i<=n;++i){
        if(k) --k;
        if(rk[i]<1) rk[i]=1;
        if(rk[i]>1) while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
        st[0][rk[i]]=k;
    }
    for(int i=1,p=2;p<=n;++i,p<<=1)
        for(int j=1;j+p-1<=n;++j)
            st[i][j]=min(st[i-1][j],st[i-1][j+(p>>1)]);
    // for(int i=1;i<=n;++i) printf("%d ",rk[i]);puts("");
    // sort(sa+1,sa+n+1);
    // for(int i=1;i<=n;++i) printf("%d ",sa[i]);puts("");
    // for(int i=1;i<=n;++i) printf("%d ",lg[i]);puts("");
}
int lcp(int x,int y){
    x=rk[x]+1,y=rk[y];
    int t=lg[y-x+1];
    return min(st[t][x],st[t][y-(1<<t)+1]);
}
bool cmp(int x,int y,int l){/*printf("cmp(%d,%d)",x,y);*/return rk[x]<rk[y]&&lcp(x,y)<l;}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    int c,t,x,r,n,q,ans;
    scanf("%d%d",&c,&t);
    while(t--){
        scanf("%d%d%s",&n,&q,s+1);
        memcpy(s+n+1,s+1,n),reverse(s+n+1,s+n*2+1);
        // for(int i=1;i<=n*2;++i) printf("%c",s[i]);puts("");
        ss(n*2);
        while(q--){
            ans=0,scanf("%d%d",&x,&r);
            for(int i=1;i<=r;++i) ans+=cmp(x,2*n-x-2*i+2,i);
            printf("%d\n",ans);
        }
    }
    return 0;
}

home > HE-17 > book > book.cpp