25年ICPC第一场网络赛题解
主题介绍
介绍
Problem A. Who Can Win
题意：
有T个样例，每个样例有S个提交，每个提交由队伍名字、题目、提交时间、提交状态构成。
提交状态分为AC、RE、UN，如果RE，罚时加20min，如果AC，以提交时间为基础罚时，如果UN，可能AC或WA。
将最终可能夺得冠军的队伍按字典序输出。
题解：
按照提交时间进行排序，利用map存储队伍名字+题目、状态+时间。这样可以统计一支队伍在某道题目上的状态。
如果已经AC或UN，将跳过后面对于这道题目的所有提交。如果RE，罚时+20。
不考虑UN，只考虑AC和RE，最后得到冠军AC题目数量和罚时。
再将队伍进行字典序排序，将所有UN考虑变成AC，大于等于前面冠军的输出。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int li=1e6;
int t,n,len;
struct sut{
string sna;
char ti;
int shi;
int zhuang;
int unti,unshi;
}a[N],b[N];
bool cmp(sut x,sut y){
if(x.shi!=y.shi) return x.shi<y.shi;
if(x.zhuang!=y.zhuang){
return x.zhuang>y.zhuang;
}
return x.sna<y.sna;
}
bool cmp1(sut x,sut y){
return x.sna<y.sna;
}
map<string,int> mp1;
map<string,int> mp2;//哈希
void solve(){
cin>>n;
len=0;
for(int i=1;i<=n;i++){
b[i].shi=b[i].unshi=b[i].unti=b[i].zhuang=0;
b[i].sna="";b[i].ti=0;
a[i].shi=a[i].unshi=a[i].unti=a[i].zhuang=0;
a[i].sna="";a[i].ti=0;
}
mp1.clear();mp2.clear();
for(int i=1;i<=n;i++){
cin>>a[i].sna>>a[i].ti>>a[i].shi;
string s1;cin>>s1;
if(s1=="Accepted") a[i].zhuang=1;
else if(s1=="Rejected") a[i].zhuang=2;
else a[i].zhuang=3;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
int tmp1=a[i].zhuang,tmp2=a[i].shi;
string s1=a[i].sna+a[i].ti;
if(mp1[s1]==0){
if(tmp1==2) mp1[s1]=tmp1*li+20;
else mp1[s1]=tmp1*li+tmp2;
}else{
int tmp3=mp1[s1]/li;
if(tmp3==1||tmp3==3) continue;
else if(tmp3==2){
if(tmp1==1){
int zzz=mp1[s1];
mp1[s1]=li+zzz%li+tmp2;
}else if(tmp1==2) mp1[s1]+=20;
else{
int zzz=mp1[s1];
mp1[s1]=3*li+zzz%li+tmp2;
}
}
}
}
for(map<string,int>::iterator it=mp1.begin();it!=mp1.end();it++){
string s1=(*it).first;
int tmp1=(*it).second/li,tmp2=(*it).second%li;
s1.erase(s1.size()-1,1);
if(mp2[s1]==0) mp2[s1]=++len;
b[mp2[s1]].sna=s1;
if(tmp1==1){
b[mp2[s1]].zhuang++;
b[mp2[s1]].shi+=tmp2;
}else if(tmp1==3){
b[mp2[s1]].unti++;
b[mp2[s1]].unshi+=tmp2;
}
}
int ans1=0,ans2=1e9;
for(int i=1;i<=len;i++){
if(b[i].zhuang>ans1){
ans1=b[i].zhuang;
ans2=b[i].shi;
}else if(b[i].zhuang==ans1){
ans2=min(ans2,b[i].shi);
}
}
sort(b+1,b+len+1,cmp1);
for(int i=1;i<=len;i++){
int a1=b[i].zhuang,a2=b[i].unti,a3=b[i].shi,a4=b[i].unshi;
if((a1>ans1)||(a1==ans1&&a3<=ans2)||(a1+a2>ans1)||(a1+a2==ans1&&a3+a4<=ans2)){
cout<<b[i].sna<<" ";
}
}
cout<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>t;
while(t--) solve();
return 0;
}
Problem B. Creating Chaos
题意：
| 给定一个序列1~n，你删除k个数，使得剩下的数两两之间 $$gcd( | a_i-a_j | ,n)$$ 之和最少，输出一组方案即可。 |
题解：
删除1~k即可。严格证明请看B题证明
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;cin>>n>>k;
for(int i=1;i<=k;i++) cout<<i<<" ";
return 0;
}
Problem C. Canvas Painting
题意：
给定一个长度为n的数列1~n，接下来给定m个区间，可以任意顺序排列这些区间，然后依次对每个区间 \([l,r]\) 选定其中两个位置，让其中一个位置的数等于另一个位置的数，问数列不同数字的个数最终的最小值。
题解：
贪心。我们先对区间进行排序，以左端点从小到大，相同看右端点从小到大。
先排除掉长度为1的区间，不会发挥作用。
如果区间的左端点单调递增，那么我每次只需要选中最靠左的两个数，每次操作可以让颜色数-1，此时答案是n-m。
如果区间左端点相等不递增，可以先贪心用掉区间长度最短的那个（即右端点小的），把其他与左端点相等的区间左端点加一。
整个过程需要排除长度本来就为1的区间和在操作中长度变为1的区间，并动态维护顺序。可以用堆来实现。时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6;
int n,m;
struct qu{
int l,r;
friend bool operator < (qu a,qu b){
if(a.l!=b.l) return a.l<b.l;
return a.r<b.r;
}
}e[N];
priority_queue<int,vector<int>,greater<int> > pq;
void solve(){
cin>>m>>n;
for(int i=1;i<=m;i++){
cin>>e[i].l>>e[i].r;
}
sort(e+1,e+m+1);
int t=1,xl=0,k=0;//t第几区间,k删除数目
while(t<=m){
xl=e[t].l;
do{
while(t<=m&&e[t].l==xl){//将左端点相同的放入队列
if(xl<e[t].r) pq.push(e[t].r);
t++;
}
if(pq.empty()) break;//防止上一步没有导致下一步pop错误
xl++,k++,pq.pop();//使用top这个区间
while(!pq.empty()&&xl>=pq.top()) pq.pop();//留下所有右区间大于xl的
}while(!pq.empty());
}
cout<<n-k<<"\n";
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
while(T--) solve();
return 0;
}
Problem D. Min-Max Tree
树形DP，不会。ICPC2025 网络赛（一）简单习题详解（7/13）
Problem G. Sorting
题意：
给定m对二元组，如果左下标对应数字大于右下标对应数字，你就可以使用这些二元组交换两者为下标的位置。能否将所有排列经过任意次操作后变成从小到大的有序。
题解：
观察发现如果出现所有的 \([i,i+1]\)，即可将所有排列变为有序。
个人推论。如果取消掉数字大于才能排序的规则，则联通即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[200010];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
while(m--){
int l,r;cin>>l>>r;
if(l+1==r) a[l]=1;
}
for(int i=1;i<n;i++)
if(a[i]!=1){
cout<<"No\n";return 0;
}
cout<<"Yes\n";
return 0;
}
Problem I. Knapsack Problem
题意：
给一个具有n个顶点和m条边的无向图，每条边具有一个权值w，固定背包容量V。一开始带一个背包，经过相应权值的边就把权值放入背包，如果放不下就新开一个背包并且放进新背包。
给定节点T，问每个节点到T分别所需要消耗的最小背包数。
题解：
Dijkstra板子，维护每个点的（最小背包数，所用容量）即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f;
const int N=1e5+10,M=5e5+10;
int n,m,T;
ll V;
struct num{
ll v,c;//背包个数,背包所装容量
num(ll vv=0,ll cc=0){v=vv,c=cc;}
friend bool operator < (num a,num b){
if(a.v==b.v) return a.c<b.c;
return a.v<b.v;
}
num operator + (int w)const{
if(c+w<=V) return num(v,c+w);
return num(v+1,w);
}
};
num dis[N];
struct edge{
int v;//终点
num w;
bool operator <(edge b)const{
return b.w<w;
}
};
struct eg{
ll v,w;
};
priority_queue<edge> pq;
vector<eg> E[N];
void add(int u,int v,ll w){
E[u].push_back({v,w});
}
int main(){
cin>>n>>m>>V>>T;
for(int i=1;i<=n;i++) dis[i]=num(n+1,0);//等同初始最大
dis[T]=num(0,0);//起点
pq.push({T,dis[T]});//起点放入优先队列
while(m--){//存边
ll u,v,w;cin>>u>>v>>w;add(v,u,w);add(u,v,w);
}
while(!pq.empty()){
int u=pq.top().v;pq.pop();
for(int i=0;i<E[u].size();i++){
eg z=E[u][i];
if(dis[u]+z.w<dis[z.v])
pq.push({z.v,dis[z.v]=dis[u]+z.w});
}
while(!pq.empty()&&dis[pq.top().v]<pq.top().w) pq.pop();
}
for(int i=1;i<=n;i++){
if(dis[i].v<=n) cout<<dis[i].v+1<<" ";
else cout<<"-1 ";
}
}
Problem M. Teleporter
题意：
有n个城市，每个城市有n-1条道路连接，每条道路有w的权值花费。每个城市互相到达，形成一棵树。
有m条传送路径，连接某两座城市，无需任何代价即可到达。
想知道使用传送阵不超过k次，从1到各个城市的最小花费之和。
数据范围:1<=n<=5000,0<=m<=10000,1<=w<=10,0<=k<=n
题解：
分层图做这道题目超时是因为每一层中有很多重复的路径。
把每一层分开算，计算一下在走了 i-1 条附加边的基础上再走一条会给哪几个点的dist缩小。然后用这几个点跑最短路即可。
时间复杂度是 \(O(n^2\log n+nm)\) 但是跑不满，还有 \(O(n(n+m))\) 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
int n,m;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
vector<vector<pair<int,int> > > to(n+1);//存图
for(int i=1;i<n;i++){
int u,v,w;cin>>u>>v>>w;
to[u].push_back({v,w});
to[v].push_back({u,w});
}
vector<pair<int,int> > xl(m);//传送
for(int i=0;i<m;i++) cin>>xl[i].first>>xl[i].second;
vector<ll> dis(n+1,inf);
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<> > q;
q.push({0,1});
dis[0]=dis[1]=0;
vector<int> in(n+1);
auto dj=[&]{
in.assign(n+1,0);
while(!q.empty()){
auto [t,now]=q.top();q.pop();
if(in[now]) continue;
in[now]=true;
for(auto &[e,d1]:to[now]){
if(d1+t<dis[e]){
dis[e]=d1+t;
q.push({dis[e],e});
}
}
}
return accumulate(dis.begin(),dis.end(),0ll);
};
cout<<dj()<<"\n";
for(int k=1;k<=n;k++){
vector<ll> nw(dis);
for(auto &[a,b]:xl){
nw[a]=min(nw[a],dis[b]);
nw[b]=min(nw[b],dis[a]);
}
for(int i=1;i<=n;i++){
if(nw[i]<dis[i]) q.push({nw[i],i}),dis[i]=nw[i];
}
cout<<dj()<<"\n";
}
return 0;
}
