NOIP

The_Chariot · 2025-11-18 21:54:53 · 生活·游记

Week 1

11.16

0 + 20 + 70 + 0 = 90，rk inf。

鉴定为纯菜狗。

T1 附加题忘写了。

T2 dp 组合数学，考场就死揣着手不动笔做 dp，chariot 你也是个神人了。

T3 拼尽全力拿下所有部分分，然后挂了 10 pts。

赛后发现又是简单贪心。

T4 不可做。

11.18

80 + 100 + 0 + 0 = 180，rk 4。

T1 优化建边，正解是线段树或者并查集缩点。

但我的赛事疑似是假的复杂度（n 方过 5e5），但过了，错因甚至是没有判 -1。

T2 是一道比较简单的贪心，没看懂难点在哪里（蓝）。

大意就是二分答案，易得敌方最优方案为越多的奖金配能力越强的人。

然后 check 就是用下等马对对面的上等马，用上等马匹配下等马，按奖金排序即可。

T3 名字叫“数据结构”，但基本无思路。

T4 没看，听完讲题感觉挺有意思的黑题。

黑题啊，写不出来为什么会觉得有意思。

11.19

树分块+珂朵莉树。

珂朵莉树骗分太爽了。

::::info[学习笔记]

1.树分块

用于解决树上莫队的分块，或是解决树上路径的在线问题。

具体实现分四步：

1. 预处理整棵树的lca。
2. dfs分块，每当一棵树达到块长便新开一个块，取最高点为“关键点”。
4. 查询一条路径便被拆成三部分：u、v 所在块，一些完整块，lca所在块，分别暴力+预处理+暴力即可。

例题P6177。

2.珂朵莉树

用于颜色段均摊问题，即有类似“推平”操作的区间问题。

随机数据的时间复杂度 O(N\log N)，非随机数据的时间复杂度退化到 O(n^2)。我不会证

模版题CF896C。

其实归根结底，珂朵莉树不是严格的数据结构，只是一种暴力。

其通过用 set&map&list 来维护三元组 {l,r,v}

第一步，建一个如下的结构体：

struct node{
    ll l,r;
    mutable ll v;
    node(ll L,ll R=0,ll V=0):l(L),r(R),v(V){}
    bool operator<(const node &p) const{
        return l<p.l;
    }
};

其中 mutable 为可变常量，即可通过指针改变在 set 中的值。

用 set<node> 来维护数组。

最核心的split操作：

it split(ll pos){
    it nxt=s.lower_bound(node(pos));
    if(nxt!=s.end()&&nxt->l==pos) return nxt;
    nxt--;
    if(nxt->r<pos) return s.end();
    ll l=nxt->l,r=nxt->r;ll v=nxt->v;
    s.erase(nxt);
    s.insert(node(l,pos-1,v));
    s.insert(node(pos,r,v));
    it ans=s.lower_bound(node(pos));
    return ans;
}

类似染色体点裂什么奇妙比喻，以 pos 为界，将包含 pos 的区间 [l,r] 分为 [l,pos] 和 [pos+1,r]，再加入 set 维护。

assign推平操作：

void assign(ll l,ll r,ll v){
    it rt=split(r+1),lt=split(l);
    s.erase(lt,rt);
    s.insert(node(l,r,v));
}

不难理解。

一定先split(r+1)再split(l)!!!!

然后珂朵莉树就建好了。

然后操作异常暴力，但时间复杂度正确，直接看下面 CF896C 正解代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+5;
const ll P=1e9+7;
ll n,m,p;
ll seed;
ll rnd(){
    ll ret=seed;
    seed=(seed*7+13)%P;
    return ret;
}
ll a[N];
struct node{
    ll l,r;
    mutable ll v;
    node(ll L,ll R=0,ll V=0):l(L),r(R),v(V){}
    bool operator<(const node &p) const{
        return l<p.l;
    }
};
set<node> s;
typedef set<node>::iterator it;

it split(ll pos){
    it nxt=s.lower_bound(node(pos));
    if(nxt!=s.end()&&nxt->l==pos) return nxt;
    nxt--;
    if(nxt->r<pos) return s.end();
    ll l=nxt->l,r=nxt->r;ll v=nxt->v;
    s.erase(nxt);
    s.insert(node(l,pos-1,v));
    s.insert(node(pos,r,v));
    it ans=s.lower_bound(node(pos));
    return ans;
}
void assign(ll l,ll r,ll v){
    it rt=split(r+1),lt=split(l);
    s.erase(lt,rt);
    s.insert(node(l,r,v));
}
void add(ll l,ll r,ll v){
    it rt=split(r+1),lt=split(l);
    for(it i=lt;i!=rt;i++){
        i->v+=v;
    }
}
struct st{
    ll len;ll v;
    st(ll l,ll V):len(l),v(V){}
    bool operator<(const st &p) const{
        return v<p.v;
    }
};
vector<st>v;
ll resort(ll l,ll r,ll k){
    it rt=split(r+1),lt=split(l);
    v.clear();
    for(it i=lt;i!=rt;i++){
        ll R=i->r,L=i->l;
        v.push_back(st(R-L+1,i->v));
    }
    sort(v.begin(),v.end());
    ll sum=0;
    for(auto i=v.begin();i!=v.end();i++){
        sum+=(i->len);ll v=i->v;
        if(sum>=k) return v;
    }
    return 0;
}
ll qpow(ll a,ll b,ll MOD){
    ll res=1,x=b;
    while(x){
        if(x&1) res=res*a%MOD;
        a=a%MOD*a%MOD;x>>=1;
    }
    return res;
}
ll powplus(ll l,ll r,ll mi,ll MOD){
    it rt=split(r+1),lt=split(l);
    ll ans=0;
    for(it i=lt;i!=rt;i++){
        ll v=i->v;
        ll len=(i->r)-(i->l)+1;
        ans=(ans+len*qpow(v,mi,MOD)%MOD)%MOD;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>seed>>p;
    for(ll i=1;i<=n;i++){
        a[i]=rnd()%p+1;
    }
    for(ll i=1;i<=n;i++){
        s.insert(node(i,i,a[i]));
    }
    while(m--){
        ll op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1;
        if(l>r) swap(l,r);
        ll x=0,y=0;
        if(op==3) x=rnd()%(r-l+1)+1;
        else x=rnd()%p+1;
        if(op==4) y=rnd()%p+1;
        if(op==1) add(l,r,x);
        else if(op==2) assign(l,r,x);
        else if(op==3) cout<<resort(l,r,x)<<'\n';
        else cout<<powplus(l,r,x,y)<<'\n';
    }
    return 0;
}

:::: ps：珂朵莉树太板了，这使我一遍过 P5350。

11.20

上午讲了 EXKMP 和后缀数组 + LCP，有点没听懂，有待二次学习。

又爽刷珂朵莉树的题。

下午体测没有 OI，魂要跑没了。

晚上浅学了无旋 treap，同学讲的，听起来无比优雅，但还是有待学习。

11.21

好久没打模拟赛了，感觉有点手生。

100 + 50 + 50 + 0 = 200。

T1 是贪心水题，优先队列秒了。

T2 千束泷奈99。是道最短路 + 拓扑 dp，考场上想到一点，没敢往下了。

T3 别样的数据结构题，已经被击败了。

T4 没学过二分图匹配，直接不理解题意然后倒闭，然后赛后发现是个 dp + 平衡树。

Week 2

11.24-11.27

超绝林黛玉体质使我躺床四天。

11.28

恶补各种大纲上我不会或者不熟练的算法。

下面是报菜名：

1. 30min 塔尖。
2. 10min SPFA。
3. 30min 二分图匹配。
4. 20min 哈希。
5. 30min KMP+ACAM。
6. 30min 马拉车。
7. 5min 快读。
8. 5h b站。

明天别饿死了。

Final

11.29

T1 水贪心直接切了。此时还剩 3.8h。

然后我就动不了手了。

考场上就没啥细节了，写了一些东西希望能进迷惑行为大赏。

After

出分，108 = 80 + 28 + 0 + 0。

T1 的贪心假了？？？

目前还没有找到 bug。

现在正在恶补文化课。

赛后看到的黄紫黑黑，后面三道思维题，让我不禁思考：NOIP 现在还是无天赋选手能打的比赛吗？

明明和 CSPS 一个大纲，T2 就动不了手，更别说后面的两道黑题。90% 是我不努力的问题，但是这样的难度膨胀，使我不得不确信：现在的信息学竞赛，没有天赋，没有思路的人真的能打吗？

总之，CCF 用这一场 NOIP 告诉我，竞赛对我来说是没有出路的。

现在没法决定是否退役，但这样的集训经历是一定不会再有的了。

再见 OI。