2025年CSP-J&CSP-S游记CQ
eric202311 · · 生活·游记
前言
本篇的语言可能不太严谨,也有一点散;\ 本篇的思路都是考试时的代码思路;\ 以后可能会更新CSP-J的考式时的思路;\ 今年的考点在重庆1中;\ 去年是在101;
试机
点击\ 今年的考点在重庆1中;\ 去年是在101;
CSP-J
进入考场.\
快速做完T1,T2\
T3想了20分钟做出来了;\
T4想了一会,想不出来,写了64分的暴力.\
预期得分:
CSP-S
进入考场.
T1:
发现是不能超过
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a1,a2,a3,x;
};
node a[100001];
vector<node>v[4];
bool cmp(node xx,node yy)
{
return xx.x<yy.x;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("club.in","r",stdin);
//freopen("club.out","w",stdout);
int t;
cin>>t;
while(t--)
{
v[1].clear();
v[2].clear();
v[3].clear();
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].a1>>a[i].a2>>a[i].a3;
int maxn=max(a[i].a1,max(a[i].a2,a[i].a3));
if(maxn==a[i].a1)v[1].push_back(a[i]);
else if(maxn==a[i].a2)v[2].push_back(a[i]);
else v[3].push_back(a[i]);
sum+=maxn;
}
if(v[1].size()>n/2)
{
for(int i=0;i<v[1].size();i++)
{
if(v[1][i].a2>v[1][i].a3)v[1][i].x=v[1][i].a1-v[1][i].a2;
else v[1][i].x=v[1][i].a1-v[1][i].a3;
}
sort(v[1].begin(),v[1].end(),cmp);
int sum2=0;
for(int i=0;i<v[1].size()-n/2;i++)
{
sum2+=v[1][i].x;
}
cout<<sum-sum2<<endl;
}
else if(v[2].size()>n/2)
{
for(int i=0;i<v[2].size();i++)
{
if(v[2][i].a3>v[2][i].a1)v[2][i].x=v[2][i].a2-v[2][i].a3;
else v[2][i].x=v[2][i].a2-v[2][i].a1;
}
sort(v[2].begin(),v[2].end(),cmp);
int sum2=0;
for(int i=0;i<v[2].size()-n/2;i++)
{
sum2+=v[2][i].x;
}
cout<<sum-sum2<<endl;
}
else if(v[3].size()>n/2)
{
for(int i=0;i<v[3].size();i++)
{
if(v[3][i].a1>v[3][i].a2)v[3][i].x=v[3][i].a3-v[3][i].a1;
else v[3][i].x=v[3][i].a3-v[3][i].a2;
}
sort(v[3].begin(),v[3].end(),cmp);
int sum2=0;
for(int i=0;i<v[3].size()-n/2;i++)
{
sum2+=v[3][i].x;
}
cout<<sum-sum2<<endl;
}
else
{
cout<<sum<<endl;
}
}
return 0;
}T2
发现特殊性质A(k=0是也满足特殊性质A)中进行改造的代价为0,所以可以直接改造所有,再跑最小生成树;因为每个改造后的城市都会有一条边的新建代价为0所以即使新改造的没用也不会增加花费. 考试时的代码(已标记沉余设计,已注释freopen):
#include<bits/stdc++.h>
using namespace std;
struct node
{
int u,v;
long long w;
};
vector<node>p[10011],p2[10011];
node a[1100001];
long long c[11],b[11][10001];
int fa[10011];
node tonode(int nu,int nv,int nw)
{
node ret;
ret.u=nu;
ret.v=nv;
ret.w=nw;
return ret;
}
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void mer(int x,int y)
{
fa[find(x)]=find(y);
}
bool cmp(node xx,node yy)
{
return xx.w<yy.w;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("road.in","r",stdin);
//freopen("road.out","w",stdout);
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
int u,v;
long long w;
cin>>u>>v>>w;
p[u].push_back(tonode(u,v,w));
p[v].push_back(tonode(v,u,w));
a[i]=tonode(u,v,w);
}
long long sum=0;
for(int i=1;i<=k;i++)
{
fa[i+n]=i+n;
cin>>c[i];
sum+=c[i];
for(int j=1;j<=n;j++)
{
cin>>b[i][j];
p[i+n].push_back(tonode(i+n,j,b[i][j]));
p[j].push_back(tonode(j,i+n,b[i][j]));
a[m+j+(i-1)*n]=tonode(i+n,j,b[i][j]);
}
}
sort(a+1,a+m+k*n+1,cmp);
for(int i=1;i<=m+k*n;i++)
{
int nu=a[i].u,nv=a[i].v,nw=a[i].w;
if(find(nu)!=find(nv))
{
sum+=nw;
p2[nu].push_back(tonode(nu,nv,nw));
p2[nv].push_back(tonode(nv,nu,nw));
mer(nu,nv);
//cout<<nu<<" "<<nv<<" "<<nw<<endl;
}
}
for(int i=1;i<=k;i++)//沉余设计
{
if(p2[i+n].size()==1)
{
sum-=p2[i+n][0].w;
sum-=c[i];
}
}
cout<<sum<<endl;
return 0;
}总结
后面的没时间做了.\
预期得分: