CSP-S 2025 游寄

UnionRE · 2025-11-06 14:00:01 · 生活·游记

前情提要

我太蒟了。

不要用 Windows 打 CSP！

【数据删除】 T1

边打 T2 T3 T4，边想了 3h，过了。

#include<bits/stdc++.h>
using namespace std;
#define ak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sqrt sqrtl
#define int long long
const int maxn=100005;
struct cl{int fi,se,th;}a[maxn];
struct pe{int v,_id;friend bool operator<(pe aa,pe bb){return aa.v<bb.v;}};
signed main(){
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    int T;
    ak;
    cin>>T;
    while(T--){
        vector<pe> nod1,nod2,nod3,n11,n22,n33;
        int n,lim,s1=0,s2=0,s3=0;
        memset(a,0,sizeof(a));
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se>>a[i].th;
        lim=n/2;
        for(int i=1;i<=n;i++){
            if(a[i].fi>=a[i].se&&a[i].fi>=a[i].th)nod1.push_back({a[i].fi,i});
            else if(a[i].se>=a[i].fi&&a[i].se>=a[i].th)nod2.push_back({a[i].se,i});
            else nod3.push_back({a[i].th,i});
        }
        for(auto ii:nod1)s1+=ii.v;
        for(auto ii:nod2)s2+=ii.v;
        for(auto ii:nod3)s3+=ii.v;
        if(nod1.size()<=lim&&nod2.size()<=lim&&nod3.size()<=lim){cout<<s1+s2+s3<<endl;continue;}
        for(int i=0;i<nod1.size();i++){
            int id1=nod1[i]._id;
            int leave=min(a[id1].fi-a[id1].se,a[id1].fi-a[id1].th);
            n11.push_back({leave,id1});
        }
        for(int i=0;i<nod2.size();i++){
            int id2=nod2[i]._id;
            int leave=min(a[id2].se-a[id2].fi,a[id2].se-a[id2].th);
            n22.push_back({leave,id2});
        }
        for(int i=0;i<nod3.size();i++){
            int id3=nod3[i]._id;
            int leave=min(a[id3].th-a[id3].se,a[id3].th-a[id3].fi);
            n33.push_back({leave,id3});
        }
        sort(n11.begin(),n11.end());reverse(n11.begin(),n11.end());
        sort(n22.begin(),n22.end());reverse(n22.begin(),n22.end());
        sort(n33.begin(),n33.end());reverse(n33.begin(),n33.end());
        while(n11.size()>lim){
            pe bc=n11.back();
            n11.pop_back();
            int idl=bc._id;
            if(a[idl].se>a[idl].th)n22.push_back({a[idl].se,idl});
            else n33.push_back({a[idl].th,idl});
        }
        while(n22.size()>lim){
            pe bc=n22.back();
            n22.pop_back();
            int idl=bc._id;
            if(a[idl].fi>a[idl].th)n11.push_back({a[idl].fi,idl});
            else n33.push_back({a[idl].th,idl});
        }
        while(n33.size()>lim){
            pe bc=n33.back();
            n33.pop_back();
            int idl=bc._id;
            if(a[idl].fi>a[idl].se)n11.push_back({a[idl].fi,idl});
            else n22.push_back({a[idl].se,idl});
        }
#define ____ cerr<<"ok"<<endl;
        for(int i=0;i<n11.size();i++){
            n11[i].v=a[n11[i]._id].fi;
        }
        for(int i=0;i<n22.size();i++){
            n22[i].v=a[n22[i]._id].se;
        }
        for(int i=0;i<n33.size();i++){
            n33[i].v=a[n33[i]._id].th;
        }
        s1=s2=s3=0;
        for(auto i:n11)s1+=i.v;
        for(auto i:n22)s2+=i.v;
        for(auto i:n33)s3+=i.v;
        cout<<s1+s2+s3<<endl;
    }
    return 0;
}
/*
3
4
4 2 1
3 2 4
5 3 4
3 5 1
4
0 1 0
0 1 0
0 2 0
0 2 0
2
10 9 8
4 0 0

*/

【数据删除】 T2。

这是我考场代码：（神秘贪心）

#include<bits/stdc++.h>
using namespace std;
#define AK ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sqrt sqrtl
#define int long long
struct edge{
    int u,v,w;
    friend bool operator<(edge aa,edge bb){
        return aa.w<bb.w;
    }
};
const int maxn=10006;
int c[maxn],dis[maxn];
bool vis[maxn];
vector<edge> G;
int fa[maxn];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[fa[x]]=fa[y];
}
void reset(){
    for(int i=1;i<=maxn;i++)fa[i]=i;
}
int mst(){
    int ans=0;
    reset();
    sort(G.begin(),G.end());
    for(edge i:G){
        int u=i.u,v=i.v,w=i.w;
        if(find(u)!=find(v)){
            merge(u,v);
            ans+=w;
        }
    }
    return ans;
}
signed main(){

    //大概就是一个MST，花费一定的价格多开一个点
    //跑k次MST
    //
    AK;
    int n,m,k;
    bool tsA=1;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        G.push_back({u,v,w});
        G.push_back({v,u,w});
    }
    cerr<<"ok";
    int tans=mst();
    for(int i=1;i<=k;i++){
        cin>>c[i];
        if(c[i]!=0)tsA=0;
        for(int j=1;j<=n;j++){
            int aij;
            cin>>aij;
            G.push_back({i+n,j,aij});
            G.push_back({j,i+n,aij});
            if(aij!=0)tsA=0;
        }
        tans=min(tans,mst()+c[i]);
    }
    if(tsA){
        cout<<0;
        return 0;
    }
    cout<<tans;
    return 0;
}
/*
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4

*/

发现 \small\color{#9D3DCF}{\textbf{\textsf{RE 0pts}}} 。

于是检查到 reset() 函数里面是 [1,maxn]，显然越界了（本地可以运行）

于是 \small\color{#F39C11}{\textbf{\textsf{40 WA}}} \small\color{#052242}{\textbf{\textsf{ TLE}}} 。

发现神秘 krus 添加了两次边，于是 \small\color{#F39C11}{\textbf{\textsf{48 WA}}} 。

发现神秘特殊性质 A 判断没有意义，但是把 k=0 的点全部干掉了，于是\small\color{#FADB14}{\textbf{\textsf{ 64 WA}}} 。

挂了 64，可以跳了。

【删除】

小熊猫可以运行 RE 的代码。于是我尝试放到 NOI Linux 系统下测试。

我没用过 code::block，看不懂。另外由于开了 ios 在 RE 时不会让 freopen 覆盖掉原来的文件。

我发现在 Linux 运行时出现了报错信息，返回了非 0 数，但是不确定是不是 RE！

于是我开始检查大样例输出，发现过了（其实是 Windows 下小熊猫的原来的输出）

于是『放心大胆地』打 T3 T4 去了。

最后上交的是 RE 代码。

诡异 T3

没有分。

太菜了，犯了【】错误。

#include<bits/extc++.h>
using namespace std;
#define AK ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sqrt sqrtl
#define int long long
using namespace __gnu_cxx;
map<crope,crope> mp;
map<crope,bool> ex;
signed main(){
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    //不好是KMP，我们没救了！
    //不好是trie，我忘了！
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        crope s1,s2;
        string ss1,ss2;
        cin>>ss1>>ss2;
        for(int i=0;i<ss1.size();i++)s1.push_back(ss1[i]);
        for(int i=0;i<ss2.size();i++)s2.push_back(ss2[i]);
        mp[s1]=s2;
        ex[s1]=1;
    }
    while(q--){
        crope s1,s2;
        string ss1,ss2;
        cin>>ss1>>ss2;
        crope dif;
        for(int i=0;i<ss1.size();i++){
            if(ss1[i]!=ss2[i])dif.push_back(ss1[i]);
        }
        for(int i=0;i<ss1.size();i++)s1.push_back(ss1[i]);
        for(int i=0;i<ss2.size();i++)s2.push_back(ss2[i]);
        int ans=0;
        for(int l=0;l<ss1.size();l++){
            for(int r=l;r<ss1.size();r++){
                if((ex[s1.substr(l,r)]&&mp[s1.substr(l,r)]==s2.substr(l,r)&&s1.substr(0,l-1)==s2.substr(0,l-1)&&s1.substr(r+1,ss1.size()-1)==s2.substr(r+1,ss2.size()-1))||(ex[s1]&&mp[s1]==s2&&l==0&&r==ss1.size()-1)){
                    ans++;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
4 2
xabcx xadex
ab cd
bc de
aa bb
xabcx xadex
aaaa bbbb

*/

神秘 T4

反正是乱打的。8 分。

没有考虑到 n=m 的情况。

#include<bits/stdc++.h>
using namespace std;
#define AK ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define sqrt sqrtl
#define int long long
const int mod=998244353;
const int maxn=510;
int s[maxn],c[maxn];
bool ly[maxn];
int jc(int x){
    int res=1;
    for(int i=2;i<=x;i++)res*=i,res%=mod;
    return res;
}
signed main(){
    freopen("employ.in","r",stdin);
    freopen("employ.out","w",stdout);
    int n,m,ans=0;
    bool tsA=1;
    cin>>n>>m;
    string ssx;
    cin>>ssx;
    for(int i=0;i<n;i++){s[i+1]=ssx[i]-48;if(s[i]==0)tsA=0;}
    for(int i=1;i<=n;i++)cin>>c[i];
    if(tsA){cout<<jc(n);return 0;}
    else if(n<=10){
        int my=jc(n);
        while(my--){
            memset(ly,1,sizeof(ly));
            int re=0;
            for(int i=1;i<=n;i++){//人数
                int cnt=0;
                if(s[i]==0){ly[i]=0;continue;}
                for(int j=1;j<i;j++){//前面的！
                    if(ly[j]==0)cnt++;//放弃
                }
                if(cnt>=c[i])ly[i]=0;
            }
            for(int i=1;i<=n;i++)if(ly[i])re++;
            if(re>=m)ans++;
            next_permutation(c+1,c+n+1);
        }
        cout<<ans;
    }
    return 0;
}
/*
3 2
101
1 1 2

10 5
1101111011
6 0 4 2 1 2 5 4 3 3

*/

总结