NOIP2025游记

xiaoyang222 · 2025-11-28 18:12:34 · 生活·游记

我纯乐子，凑合着看。SC-0551。希望能上迷惑大赏。

初二弱鸡一枚，反正是体验名额，如果能去省选看看世面也好。

大致时间

考完 S 后：期中复习复习复习复习复习，期中考试考试，秋假假假假假哈哈哈。回来进行了 5 天 whk 学习又去 NOIP 集训一周了哈哈哈。

2025.11.24~28：模拟赛模拟赛自习体测模拟赛自习，没错有一个体测。28天没运动的我能赢吗？

立定跳远	1000	50	引体向上	坐位体前屈
231	3min53	7.3	4	10.3

没错我引体向上只有 4 个，不会摆硬拉了 4 个。有个人还在批量进货镁粉。

关于 1000 米：纯炸，200 米的时候鞋带散了，也没有一个能吃风的。

关于 50 米：纯炸飞，运动会 100 米（S 模拟赛打着打着下去跑了个）也跑炸了。

NOIP 模拟赛

6 场炸穿了 4 场，希望能攒点 RP 吧。这 4 场高年级说像是三道NOI+一道水。

我们OJ加了个新的功能，若一个人干了不该干的事情（比如划水），就要抽一发 RPGainer，是个惩罚，例如：

1 跑1600 + 10^{-8} m

2 唱一首值班老师指定的歌

老师也会抽，有个老师抽了个：

在 Alice（备注：机房A）用一体机播放《Faded》并反复调大调小音量，然后看股市涨跌并点头说“跌了吗，有点意思”，然后再打开 cmd 并运行 color a & dir /s c:

在现场，但是 Faded 没看到。确实比特币跌了。

学校高年级的还搞了个插件，真的太好用了！可以改背景还有很多强大的功能。

怎么半路中我 SPFA 被 hack 了？

由于机房电脑改成了两个用户，只能用 user 而用不了 admin（之前默认admin），所以没有了管理员权限。之前我们机房的人学会了建局域网服务器，还有局域网聊天器，还有 LocalSend 发些好玩的东西（例如丝之歌）。但是现在防火墙和管理员权限都关了，我和我同学又找到一个不是那么好的替代品（具体是什么就不说了）。

还有某个同学（不方便透露）自己写了个扫雷，还多加了几个模式，玩了一会儿提了点建议改了。确实很好玩！基本复刻了原版，用的小熊猫做的绘制。

在 vjudge 上建了个模板练习，原来的 OJ 上的功能太弱了。还没打完呢！

突然 Kaury 问我 AC 自动机咋做，把他给讲懂的同时把我自己内心深藏很久的困惑也给解开了，KMP 也彻底会了！

给 liuchenyu 讲了 FHQ，也会了！然后写了 3 次。很好写，功能也很好实现。

最后一天我们在小学机房（中学机房要弄弄），然鹅小学机房开了网，这就意味着可以干巨多事情，可惜只有最后一天开发不了什么，但是还是有人开了云原神（抽了发但是歪了），florr（打到了红撞到了su）（是谁就不说了）。我开了B站看了会历史喵，嘿嘿嘿。

可惜没什么好玩的有趣的。机房是关了网的，所以只能去共用机上网。吃完饭后老师没回来的空隙可以划一会儿。

最后一场模拟赛是黎队 251Sec 出的，T1出的很神！也去听了听白鸟过河滩（真惭愧，我之前还没听过）。

正赛

cdjx。

嘿嘿嘿刚好在我上课的原位的右移两个位置（我在嘉祥的艺体楼 B 机房）。

在机房：先把壁纸换了，发现 NOI Linux 下的五子棋没有被删，玩了一会儿，嘿嘿嘿。下赢了很多次。

早上没吃多少，带了个巧克力但是考试中间一直没动。

0:00~0:05 建文件+开题 ok
0:05~0:10 想T1 ok
0:10~0:20 写T1 ok
0:20~0:35 开T2 不会
0:30~0:45 开T3 不会
0:45~1:00 开T4 不会
1:00~1:30 想想T2的最优策略是什么+暴力 题读假了
1:30~1:45 改T2 ok
1:45~2:15 想想T3有哪些分 先把甲酸写了好像假飞了,dp只会n^4的，还假了
2:15~2:30 想想T4有哪些分 会O(nVlogn)了
2:30~3:15 写T4的O(nVlogn) 3:20才弄完
3:20~3:40 想想T3怎么打暴力（较高档的） 先把最低档超级暴力写了（写到3:35）算了先把T2写完
3:30~3:55 把T2的暴力补充完 ok
3:55~4:20 写T3的超级暴力 ok
4:15~4:30 jc ok

感觉还是挺顺的，可惜没把 T4 的 A 性质做了（因为我的预处理是 O(nV\log V) 的，V 是询问的点的个数）。

考试结束，在电脑桌面上摆了个 rp=INF（当然是在有时间的情况下）。

最终 100+32+8+30，希望不挂吧。

赛后

哦哦哦忘记打 ABC 了。

感觉进不了省选了/ll没事，反正未来还有机会。

后面又要补文化课啦！语文PPT已经拿到了，竟然孟子三章有 108 页？？？

烦死了还有午课要做。

对了，后面把历史喵的最新一篇没看完的看完了。后面还要看那兔。

NOIP 喜获甲流，早上打算带口罩但是怕烦就没带。

周天作业做着做着就脑子痛了（37.4），星期一有了咽炎（38.4），包了点药，但星期二更痛了（37.5），降了一点。头痛周末的考试都炸了。周三物理考+头更痛+嗓子更痛显然炸掉。周四好些了，周五完全好了！

等下压缩包怎么被爆破成功了？折磨牛？

开始 whk 了。

代码出来了，T3 为啥小凸零挂 8 分熨斗挂 4 分？来洛谷测测，极限过掉。后面没时间码的，运气爆棚刚好过（但是本地只有 1.1s 啊/yiw）！感谢神机！

最后附上 T1234 代码（原版），可以看出我的抽象想法。

::::info[T1]

//1s 512MB
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll INF=3e18;
struct Node{
    ll x,y;
}a[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("candy.in","r",stdin);
    freopen("candy.out","w",stdout);
    int n;cin >> n;ll m;cin >> m;
    ll mn=INF;
    for (int i=1;i<=n;++i) cin >> a[i].x >> a[i].y,mn=min(mn,a[i].x+a[i].y);
    sort(a+1,a+1+n,[](const Node &a,const Node &b){
        return a.x<b.x;
    });
    ll ans=0;ll sm=0;
    for (int i=0;i<=n;++i){
        sm+=a[i].x;
        if (sm>m) continue;
        ans=max(ans,i+(m-sm)/mn*2);
    }
    cout<<ans<<"\n";
    cout.flush();
    return 0;
}
//好像是dp，然后优化？矩快？
/*
我要上迷惑大赏 洛谷 锣鼓 luogu luogu.com.cn www.luogu.com.cn
我是xiaoyang111(890311/1220111),SC-0551,初二，祝我RP++
没啥活可以整了啊！！！
----------
好像是贪心，什么个策略？
能否逮着一个和最小的糖果一直买？
然后其他糖果要么只买一个要么不买？好像这个是对的
A性质：逮住一个糖果最小价格一直买
好的，优势在我，现在才8:50把T1切掉了！
*/
//Intel Core Ultra 9 285K CPU @ 3.70 GHz
/*
qwq:
0:00~0:05 建文件+开题 ok
0:05~0:10 想T1 ok
0:10~0:20 写T1 ok
0:20~0:35 开T2 不会
0:30~0:45 开T3 不会
0:45~1:00 开T4 不会
1:00~1:30 想想T2的最优策略是什么+暴力 题读假了
1:30~1:45 改T2 ok
1:45~2:15 想想T3有哪些分 先把甲酸写了好像假飞了,dp只会n^4的，还假了
2:15~2:30 想想T4有哪些分 会O(nVlogn)了
2:30~3:15 写T4的O(nVlogn) 3:20才弄完
3:20~3:40 想想T3怎么打暴力（较高档的） 先把最低档超级暴力写了（写到3:35）算了先把T2写完
3:30~3:55 把T2的暴力补充完 ok
3:55~4:20 写T3的超级暴力 ok
4:15~4:30 jc ok
*/

::::

::::info[T2]

//1s 512MB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define int long long
using namespace std;
const int N=5000+5,MOD=998244353,INF=1e18;
int c,t,n,m;
int a[N],f[N][N];
int qpow(int a,int b){
    int ans=1;
    while (b){
        if (b&1) ans=ans*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans;
}
void solve(){
    cin >> n >> m;
    set<int> s;
    for (int i=1;i<=n;++i) cin >> a[i],s.insert(a[i]);
    if (n==1 || s.size()==1 || m==2*n-1){
        cout<<qpow(2,n)<<"\n";
        return;
    }
    int t1,t2,t3,ans=0,mn,mx,sm,res;
    if (n>10 && m==2*n-2){
        ans=qpow(2,n);
//      cout<<"fkwefjklefewf"<<'\n';
        vector<pair<int,int>> prz;
        for (int i=1;i<=n;++i){
            prz.emplace_back(a[i],2);
        }
        sort(prz.begin(),prz.end(),[&t1,&t2](const pair<int,int> &a,const pair<int,int> &b){
            t1=2*a.first/a.second,t2=2*b.first/b.second;
            if (t1==t2) return a.first>b.first;
            return t1>t2;
        });
        pair<int,int> cp;
        for (int w=1;w<=n;++w){
            cp=prz.back();
            if (cp.first==a[w]) cp=prz[prz.size()-2];
//          cout<<a[w]<<" "<<cp.first<<"\n";
            if (a[w]<cp.first && a[w]*2>cp.first) --ans;//你强强
            ans=(ans+MOD)%MOD;//我弱弱
        }
        cout<<ans<<'\n';//嘤嘤嘤
        return;
    }else if (n<=10){
        for (int s=0;s<(1<<n);++s){
            ++ans;ans%=MOD;
            vector<pair<int,int>> prz;
//      cout<<"fwelkfelwelkfe\n";
            for (int i=1;i<=n;++i){
                if (s>>(i-1)&1) prz.emplace_back(a[i],1);
                else prz.emplace_back(a[i],2);
            }
            sort(prz.begin(),prz.end(),[&t1,&t2](const pair<int,int> &a,const pair<int,int> &b){
                t1=2*a.first/a.second,t2=2*b.first/b.second;
                if (t1==t2) return a.first>b.first;
                return t1>t2;
            });
            t1=m;sm=0;
            for (t2=0;t2<n;++t2){
                if (t1>=prz[t2].second)
                    t1-=prz[t2].second,t3=t2,sm+=prz[t2].first;
            }
            for (int i=0;i<=m+3;++i) f[0][i]=-INF;
            f[0][0]=0;res=0;
            for (int i=1;i<=n;++i){
                for (int j=0;j<=m;++j){
                    f[i][j]=f[i-1][j];
                    if (j>=prz[i-1].second) f[i][j]=max(f[i][j],f[i-1][j-prz[i-1].second]+prz[i-1].first);
                    res=max(res,f[i][j]);
                }
            }
            if (res!=sm){
                --ans;ans+=MOD;ans%=MOD;
            }
        }
        cout<<ans<<"\n";
    }else{
        cout<<qpow(2,n)<<"\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("sale.in","r",stdin);
    freopen("sale.out","w",stdout);
    cin >> c >> t;
    for (int qwq=0;qwq<t;++qwq) solve();
    cout.flush();
    return 0;
}
//记得有多测
/*
考虑什么时候为满足条件的
好像是一个重量为12的01背包
A性质：任何方案都是满足的
B性质：这啥啊，糖果原价极大
m=2咋做？只能买1个/2个
枚举买什么
m=2可以只看前两个地方，合法的方案数减去不合法的方案数
m=2n-1:都可以买，所有方案都是满足的（不完全，情况有且仅有全是2的，但是这样选还是最优的）
m=2n-2:不合法情况：有一个点w=1。但是最多只会有一种不合法
枚举w=1的点然后chk？
*/

::::

::::info[T3]

//2s 512MB
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N=8000+5;
int p[N],mx[N],ans,n,m,t,w[N];
vector<int> g[N];
set<int> s[N];
void gdfs(int u,int &ans){
    s[u].insert(w[u]);
    for (const int &v:g[u]){
        gdfs(v,ans);
        for (const int &t:s[v]){
            s[u].insert(t);
        }
    }
    for (int i=0;s[u].count(i);++i) ++ans;
}
int cost(){
    for (int i=1;i<=n;++i) s[i].clear();
    int res=0;
    gdfs(1,res);
    return res;
}
void solve(){
    cin >> n >> m;
    for (int i=1;i<=n;++i) g[i].clear();
    for (int i=2;i<=n;++i) cin >> p[i],g[p[i]].emplace_back(i);
    int ans=0;
    for (w[1]=0;w[1]<=n-1;++w[1]){
        for (w[2]=0;w[2]<=n-1;++w[2]){
            for (w[3]=0;w[3]<=n-1;++w[3]){
                for (w[4]=0;w[4]<=n-1;++w[4]){
                    for (w[5]=0;w[5]<=n-1;++w[5]){
//                      cout<<11<<"\n";
                        for (w[6]=0;w[6]<=n-1;++w[6]){
                            for (w[7]=0;w[7]<=n-1;++w[7]){
                                ans=max(ans,cost());
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    int T;cin >> T;
    for (int _=0;_<T;++_) solve();
    cout.flush();
    return 0;
}
//可不可以用bitset维护？这个是个dp还是贪心？
/*
5
7 2
1 1 2 2 2 3
7 2
1 1 2 2 2 3
7 2
1 1 2 2 2 3
7 2
1 1 2 2 2 3
7 2
1 1 2 2 2 3
首先状态和树高度有关
首先，他和他的子树的值肯定是一段区间
然后就有f(u,l,r)表这个状态的最大贡献
当r-l+1<=siz[u]才合法
当l!=0，此值一定是0
当l=0，分配资源，贪心的想，当l=0的时候一定最优
但是又要把这个区间拼起来，咋拼？
分类，l=0和l!=0
哦好像会正解了！
f(u,r)表示u点的子树内值域都是[0..r]，满足这个的最大的价值
然后对于儿子之间的，做01背包，尝试把这个值域拼起来
具体的，g(i,j)表示现在已经拼出了[0..i]和某某长度为j的区间（考虑了前多少个儿子）
的最大价值
f就可以快速计算了
可是这个好像转移是n的呢qwq状态是n^2个，点数是n个
若一个子树，他要当被牺牲的，要当就当彻底，全部都加入进入末尾
对于第一维，可以取max
*/

::::

::::info[T4]

//2s 512MB
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e4+3,B=35,K=3000+3,Q=7,W=13;
const ll INF=1e18;
int d[N],l[N],r[N];
ll q1[N],q2[N],lg[N];
ll a[N],ans1[N][B][Q],ans2[K][K];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("query.in","r",stdin);
    freopen("query.out","w",stdout);
    int n,q;cin >> n;
    lg[0]=-1;
    for (int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;++i) cin >> a[i],a[i]+=a[i-1];
    cin >> q;
    for (int i=0;i<q;++i){
        cin >> l[i] >> r[i];
        ++d[l[i]],--d[r[i]+1];
    }
    vector<int> v;
    map<int,int> m;int tot=0;
    for (int i=1;i<=n;++i){
        d[i]+=d[i-1];
        if (d[i]) v.emplace_back(i),m[i]=++tot;
    }
    for (int i=0;i<q;++i)
        l[i]=m[l[i]],r[i]=m[r[i]];
    priority_queue<ll> p1,p2;tot=0;
    for (int &k:v){++tot;
        for (int i=1;i<=n;++i) q1[i]=q2[i]=-INF;
        for (int i=1;i<=n-k+1;++i){
            q1[i]=a[i+k-1]-a[i-1],q2[i+k-1]=a[i+k-1]-a[i-1];
        }
//      cout<<k<<" : ";
//      for (int i=1;i<=n;++i) cout<<q1[i]<<" "<<q2[i]<<'\n';
        for (int i=1;i<=n;++i){
            if (q1[i]!=-INF) p1.emplace(q1[i]);
            while (!p1.empty() && !p2.empty() && p1.top()==p2.top()) p1.pop(),p2.pop();
            if (n<=3000){
                ans2[i][tot]=p1.top();
//              cout<<i<<" "<<tot<<" "<<p1.top()<<"\n";
            }else{
                ans1[i][tot][0]=p1.top();
//              cout<<i<<" "<<tot<<" "<<0<<" "<<p1.top()<<"\n";
            }
            if (q2[i]!=-INF) p2.emplace(q2[i]);
        }
    }
    if (n>3000){
        for (int i=1;i<=n;++i)
            for (int k=1;k<Q;++k)
                for (int j=1;j<=tot;++j){
                    if (j+(1<<k-1)<=tot) ans1[i][j][k]=max(ans1[i][j][k-1],ans1[i][j+(1<<k-1)][k-1]);
                }
    }
    ull ans=0,res;ll mx;
    for (int i=0;i<q;++i){
        ans=0;
        for (int j=1,t;j<=n;++j){
            mx=-INF;
            if (n<=3000){
                for (int k=l[i];k<=r[i];++k)
                    mx=max(mx,ans2[j][k]);
            }else{
                t=lg[r[i]-l[i]+1];
                mx=max(ans1[j][l[i]][t],ans1[j][r[i]-(1<<t)+1][t]);
            }
//          cout<<mx<<" "<<ans1[j][l[i]][t]<<" "<<ans1[j][r[i]-(1<<t)+1][t]<<" "<<j<<" "<<l[i]<<" "<<t<<" | ";
            res=mx;res*=j;ans^=res;
        }
        cout<<ans<<"\n";
    }
    cout.flush();
    return 0;
}
//
//O(nq)是必要的，那么怎么快速得到答案呢？好像是猫树
//首先肯定不可以O(n^2)预处理
/*
首先可以把式子列完全
可以转换为扫描线？
根号分治？
现在会O(nVlogn+nq)了V=min(r_i,n)但是空间不够啊（不够开st表）！！！
A：不会，若会这个就会B性质了
B：预处理？
C：不会
D：暴力
E：不会
*/

::::