真NOIP2024游记

这回是真的游记了。

省流：初三 HE 蒟蒻拿了 100+100+4+20=224 pts 不到大众分的“好成绩”。

Day-6

OK 啊，开始集训。

Day-5

呜呜，好像全机房就我最蒟。

Day-4

开始做 zroi noip 模拟赛。

今天的题一看就是比较可做啊。

看了眼 T2：区间互质个数，可做！

于是，死了。

Day-3

wc，怎么又是 noip plus 模拟赛，tm 不做了。

哎，还是 noi.ac 的 T1 正常。

Day-2

做云斗。

Day-1

补前一天云斗的 T5，但还是没写出来。

Day0

上午赶路。

下午复习。

晚上攒 rp，play 了一次 2048game，但是没成功。

Day1

开始去考场。

哦，监考老师好像是上回 CSP-J and S 的老师呢。

到位置上已经是 8:10 了，不慌，先趴一会。

过了一会，醒来了，然后开始看题。

T1：这不一眼贪心吗，40min KO 了。

T2：先让我推一推。。。推了 15min，知道怎么做了，开写（35min）！

T3：让我想一想，推一推。不会惹 qwq，T3 输出 1 吧。

T4：然我推一推。。。呜呜，只会打暴力，但好像没时间打倍增 LCA 了耶，于是就只用了暴力跳的方法。

快点看我考场上的 T4 代码：

#include<bits/stdc++.h>
using namespace std;
template<typename S,int N>class st_table{
    private:S a[-~N][-~-~(1<<N)];
    private:int n,lg[-~-~(1<<N)],k;
    private:S(*f)(S,S);

    public :inline S push_back(S x){return a[0][++n]=x;}
    public :inline void build(S(*fu)(S,S)){
        f=fu;
        for(k=2;k<=n;++k)lg[k]=-~lg[k>>1];
        for(k=1;(1<<k)<=n;++k){
            for(int i=1;i+(1<<k)-1<=n;++i){
                a[k][i]=(*f)(a[k-1][i],a[k-1][i+(1<<k>>1)]);
            }
        }
    }
    public :inline S query(int l,int r){
        k=lg[r-l+1];
        return (*f)(a[k][l],a[k][r-(1<<k)+1]);
    }
};
st_table<int,20>s;
int n,m;
vector<int>e[500005];
int f[500005],dep[500005];
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    while(dep[x]>dep[y])x=f[x];
    while(x!=y)x=f[x],y=f[y];
    return x;
}
void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    f[x]=fa;
    for(int i=0;i<e[x].size();++i){
        if(e[x][i]==fa)continue;
        dfs(e[x][i],x);
    }
}
int main()
{
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)s.push_back(i);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        e[u].push_back(v),
        e[v].push_back(u);
    }
    dep[1]=1;dfs(1,0);
    scanf("%d",&m);
    s.build(lca);
    int l,r,k,d;
    while(m--){
        scanf("%d%d%d",&l,&r,&k);
        d=0;
        for(int i=l;i+k-1<=r;++i)d=max(d,dep[s.query(i,i+k-1)]);
        printf("%d\n",d);
        if(0==1)printf("YUANSHENQIDONG!\n");
    }
    return 0;
}

然后把所有题的样例测一下：嗯，能过的都能过，不能过的还是不能过（别问为什么不做完一个题试一个题样例，因为这样如果没过的话会心态爆炸，我已经逝过了）。

出考场了，最终只有 [0,100]+[0,100]+[0,4]+[0,20]=[0,224] pts 的不到大众分的分数，我还是太菜了呜呜。

Day1e9+7

出分了。

我不管，一分不挂就是赢！