CSP-S2025 游寄

HKW0202 · 2025-11-03 11:31:18 · 生活·游记

文章末尾有彩蛋，是回学校后观察坐在我机位考试的人的代码，真的绷不住了！\ 又是在福建师大附中考，先找到 clz 的大头照膜拜orz。\ 大胆赌一把，这次不考图论和字符串！\ 检查完食物，进入考场。很快的找到了座位。\ 旁边的位置还是空的，好在 ccf 把小学生给 ban 了，不会遇到去年 NOIP 旁边的小学生拿着键盘打音游。\ 然后，一个年轻的身影走来。\ WC，不能真遇到 12 岁小学生了吧，畏惧了。\ 他看到我带的零食，惊叹我带了如此之多的食物。\ 趁着这个机会，社恐的我难得开口询问对面年龄。\ 不好，\color{red}是初一 。\ 还是很活泼的那种！\ “你们高二的脑子那么消耗能量吗？”\ 想到去年的经历，我反复强调了不要在考试的时候和我讲话。 强调完，我靠在椅子上。\ wC,机房奶龙坐在我斜后方，喂了点糖之后，考试开始了。\

T1

信心满满开 T1 ，诶？这不是裸的贪心吗，美美开打。\ 不对，再看一眼题目，不能超过 \frac{n}{2} ，如何做。\ 考虑 dp ，一秒后放弃。 发现了超过 \frac{n}{2} 的部分无论怎么调整都是合法的，直接优先队列维护。\ 为什么 -O2 -std=c++14 报错了？\ 不知道，那就关掉。\ 为什么一直报 CE ，万能头也加了没问题啊，再次检查，priority_queue也没有拼错，仔细翻阅后。\ using namespace std;消失了。\ 美美过题，调 CE 调了 10min ，14:58 过题。

T2

啊，果然是我最不擅长的图论，既然放在第二题，肯定还是可以看一看的吧。\ 嗯，肯定要用到最小生成树吧，然后呢，消耗 20min 思考不出来，再看一遍题目。\ 哦，所有边的损坏了，乡镇不是城市，k\le 10 ,感觉会做了，直接 2^k 状压枚举乡镇，然后暴力跑 Kruskal ，嗯，M 太大了。 \ 陷入沉思，此时甚至还有 \color{red}BGM 响起。\ MD，哪来的音乐。\ 哦，原来是可可爱爱的初一小朋友正躺在椅子上唱歌呢。\ 咳咳，我试图提醒这小东西。\ 好像是消停了一点。\ 大胆猜测可以把 M 降到 N 级别的，那就是只保留原图的最小生成树的边，感觉很对，开写，写挂了好几次，排序就直接提前排好然后后期类归并排序状物。\ 不知道为什么，代码写了很久。\ 感觉有一点地震了，想想地震就地震吧，反正楼倒不了。\ 不对啊，怎么没有人发现？\ 诶唷，怎么又是您啊，喜欢抖腿，我真是服了！\ 应该能过，时间复杂度 O(mlogm+nklognk+2^knk\alpha(n+k)) ，跑不满，感觉时间复杂度很正确，不管了，看看下一题，此时大概已经 16 点多了，200 分，下一题。

T3（1）

虽说过了前面两题，看到字符串题，我真是服了！\ 怎么图论和字符串都考啊，我真的不会了啊！\ 抱着幻想看一眼，算了，不会，打个交暴力先，看看特殊性质，嗯，秒不掉，看看下一题。

T4（1）

哦，我恨计数！\ 直接写一个 O(n*n!) \ 看看特殊性质，m=1，是阶乘吗，嗯嗯嗯，不对，因为大样例没过想太简单了。\ 诶？ n=m，白送的四分，现在也是拿到 12 分了，再看看上一题吧。

T3(2)

尝试优化暴力，尝试哈希，尝试 trie。 算了吧，真不会，研究一下特殊性质，感觉 B 性质是好打的，只要判断一下 b 移动了多少，然后其他的乱判就可以了。\ 不知道能得几分，按 50 算吧。

T4(2)

突然，铃声响了，看了眼时间，才六点，不应该啊。\ 哦，清校铃啊，那没事了。\ 当心眼睛！\ 沟槽的初中生又在发力了，我没有看他的电脑，但是能感受到旁边的电脑在以5赫兹的频率闪烁，眼睛瞎了。\ 感觉O(2^k*?)，想想状压，令 f[S][k] 为当前已经考虑的状态为 S ，已经失败了 k 个人，不难写，写完有了 24 分，已经 18:21 了，开始睡觉。

千万不要挂分啊！！！\ 100+100+[50\pm eps]+24\

彩蛋

::::success[T1 0分不知是否正确代码]

#include <bits/stdc++.h>
using namespace std;
int a1[100010],a2[100010],a3[100010];
int main()
{
    int t;
    cin>>t;
    int y=0,s=0,e=0;
    bool f=true;
    while(t--)
    {
        int n;
        cin>>n;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a1[i]>>a2[i]>>a3[i];
        }
        for(int i=1;i<=n;i++)
        {
            if(a1[i]>=a2[i]&&a1[i]>=a3[i])
                y++;
            else if(a2[i]>=a1[i]&&a2[i]>=a3[i])
                e++;
            else 
                s++;
        }
        for(int i=1;i<=n;i++)
        {
            if(y<=n/2&&e<=n/2&&s<=n/2)
            {
                int g=max(a1[i],a2[i]);
                ans+=max(g,a3[i]);
            }
            if(y>n/2)
            {
                if(a2[i]>=a3[i])
                {
                    e++;
                    if(e>n/2)
                    {
                        ans+=a3[i];
                    }
                    ans+=a2[i];
                }
                ans+=a1[n-i+1];
            }
            else if(e>n/2)
            {
                if(a1[i]>=a3[i])
                {
                    y++;
                    if(y>n/2)
                    {
                        ans+=a3[i];
                    }
                    ans+=a1[i];
                }
                ans+=a2[n-i+1];
            }
            else if(s>n/2)
            {
                if(a2[i]>=a1[i])
                {
                    y++;
                    if(y>n/2)
                    {
                        ans+=a1[i];
                    }
                    ans+=a2[i];
                }
            }
        }
        freopen("club.in","r",stdin);
        freopen("club.out","w",stdout);
        cout<<ans<<endl;
        y=0,s=0,e=0;
    }
    return 0;
}

:::: ::::success[T2 0分不知是否正确代码]

#include <bits/stdc++.h>
using namespace std;
int v[1000010],u[1000010],w[1000010],c[10010],a[10010];
int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
    }
    for(int i=1;i<=k;i++)
    {
        cin>>c[i];
        for(int j=1;j<=n;j++)
        {
            cin>>a[j];
        }
    }
    //freopen("road.in","r",stdin);
    //freopen("road.out","w",stdout);
    int minv=2e9,minx=2e9,minc=2e9;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        minv=min(minv,w[i]);
        ans+=minv;
    }
    for(int i=1;i<=k;i++)
    {
        minc=min(minc,c[i]);
        ans+=minc;
        for(int j=1;j<=n;j++)
        {
            minx=min(minx,a[j]);
            ans+=minx;
        }
    }
    cout<<ans%10*10+ans/10;
    return 0;
}

:::: ::::success[T3 0分不知是否正确代码]

#include <bits/stdc++.h>
using namespace std;
int a[510];
int main()
{
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int cnt=0,ans=0;
//  freopen("replace.in","r",stdin);
//  freopen("replace.out","w",stdout);
    sort(a,a+n);
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0')
        {
            a[i]=0;
            a[i+1]--;
        }
        if(a[i]>0)
        {
            cnt++;
        }
        if(cnt>=m)
        {
            ans++;
        }
    }
    cout<<ans*cnt;
    return 0;
}

::::

::::success[T4 唯一freopen正确代码]

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

int main()
{
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    return 0;
}

::::