首战NOIP——2025NOIP游记

· · 生活·游记

序

第一次参加NOIP，高估了T1的难度，也没有料到后三题的难度，不愧是CCF......

前 2 Day

沉浸在生日的喜悦中... ...

前 1 Day

突然头疼无力，一疑似某流行感冒... 考前一晚因为离考场太远，提前到考场旁的酒店住下，去附近医院化验，万幸，并未感染

前 2 Hour

走路去考场，寒风中吃了早饭，喝了药，在考场门口领了牌子，进了考场。

1 Hour

根据考试的策略我先通读了四道题目，当然T3和T4并没有停留太长时间，当看到T1我有思路时，首先告诉自己：绝对不会爆零了。因为并未参加过之前的NOIP，我对T1的难度估计很高，心理预期并没有想过要AC掉这道题（事实上也没有AC ）。 首先关注到了特殊性质A，当x_i = y_i时，小X只会买价格最小的唯一一种糖果，直接判断特殊性质，输出答案15tps拿到！

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+7;
long long n,m;

int minte=INT_MAX;
int lis[N][5];
long long ans=0;
bool xxx1=true;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>lis[i][1]>>lis[i][2];
        minte=min(minte,lis[i][1]);
        if(lis[i][1]!=lis[i][2])xxx1=false;
    }

    if(xxx1){
        cout<<m/minte<<endl;
        return 0;
    }
}

2-3 Hour

在之后就没有什么思路，那就直接暴力深搜吧，爆搜小X的所有买糖果的可能性。

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+7;
long long n,m;

int minte=INT_MAX;
int lis[N][5];
int ci[N];
long long ans=0;
bool xxx1=true;

void dfs(int qian,long long t){

    for(int i=1;i<=n;i++){
        if(ci[i]%2==0&&qian-lis[i][1]>=0){
            ci[i]++;
            dfs(qian-lis[i][1],t+1);
            ci[i]--;
        }else if(ci[i]%2==1&&qian-lis[i][2]>=0){
            ci[i]++;
            dfs(qian-lis[i][2],t+1);
            ci[i]--;
        }
    }
    ans=max(ans,t);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>lis[i][1]>>lis[i][2];
        minte=min(minte,lis[i][1]);
        if(lis[i][1]!=lis[i][2])xxx1=false;
    }

    if(xxx1){
        cout<<m/minte<<endl;
        return 0;
    }else{
        dfs(m,0);
        cout<<ans<<endl;
    }
}

成功得到了一段能输出正解的非满分程序（40tps）

3-3.5 Hour

感觉T1再没有思路，去瞅了瞅T2，看到特殊性质A，不就是输出2的n次方吗？你猜为什么考场所给的样例中并没有特殊性质A的？因为可以直接算出来。直接一段快速幂奉上（结果忘取余了且忘开了long long。。。 ），成功消耗掉了一段时间

3.5-4 Hour

返回继续想T1，如果将每一种糖果的两种价格打包一起看，那么当m很大时，只会优先买x_i + y_i最小的糖果，我们叫他最优糖果，之后再去搜索剩余的钱m_n能买到的糖果最大值，我们记为f(m_n)，让深搜的量大幅减少。 但是，是否存在一种情况，当购买2n个最优糖果之后所剩余的钱所能购买的其他糖果的数量与2n的和要比购买2(n-1)个最优糖果之后所剩余的钱所能购买的剩余糖果的值与2(n-1)的和小呢？ 也即是是否存在这种情况：

2n+f(m_n)<2(n-1)+f(m_{n-1})

显然是有可能的，因此我们在深搜的时候应深搜m_{n-1}元，这样就就不会出现问题了，于是有了我的最终代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+7;
long long n,m;

int minx=INT_MAX;
int minte=INT_MAX;
int lis[N][5];
int ci[N];
long long ans=0;
bool xxx1=true;

void dfs(int qian,long long t){

    for(int i=1;i<=n;i++){
        if(ci[i]%2==0&&qian-lis[i][1]>=0){
            ci[i]++;
            dfs(qian-lis[i][1],t+1);
            ci[i]--;
        }else if(ci[i]%2==1&&qian-lis[i][2]>=0){
            ci[i]++;
            dfs(qian-lis[i][2],t+1);
            ci[i]--;
        }
    }
    ans=max(ans,t);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>lis[i][1]>>lis[i][2];
        minte=min(minte,lis[i][1]);
        if(lis[i][1]!=lis[i][2])xxx1=false;
        minx=min(minx,lis[i][1]+lis[i][2]);
    }

    if(xxx1){
        cout<<m/minte<<endl;
        return 0;
    }else{
        int lin=m/minx;
        dfs(m-(lin-1)*minx,0);
        cout<<ans+2*(lin-1)<<endl;
    }
}

最终成功拿下75tps 但前面有个测试点TLE掉了啊qwq,痛失5分。

4-4.5 Hour

再没有怎么更改代码，一直在想还能如何优化，其实离正解以及不算太远了，但是并没有想出来。 遗憾离场，最终75分结束比赛。

After 4.5 Hour

还没出考场，考场中的其他选手激烈讨论T2的做法，我默默听着，出来之后才得知了这次T1的难度其实是偏简单的所谓的（签到题 ）。

听说了这次后三题的难度，也是懒得锐评CCF了。

反思

对于贪心的题目还是练的不够扎实，今年的S T1也是贪心，也是连3=也没有混上，遗憾离场（详情请看），虽然在考前一直在练区间贪心类的题目，但是对贪心题的敏感度还是不够，没有得到系统的解题方式，并不能精确分析题意，找到突破口，导致做这类题只能走一步看一步。好在深搜和广搜这两个算法还算扎实，可以保证所有题暴力都能有分。

之后得训练建立标准的贪心解题流程（分析问题→识别贪心性质→证明正确性→实现算法），再练习更多的题，提升对题目的分析能力吧。