2025ICPC网络赛第一场复盘

顺序从易到难：G,B,A,I,C

G:Sorting

#include <bits/stdc++.h>
using namespace std;
int n,m;
int vis[200005];
int cnt=0;
int x,y;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		if(y==x+1)
		{
			if(!vis[x]) cnt++;
			vis[x]=1;
		}
	}
	if(cnt==n-1) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

---

B:Creating Chaos

#include <bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++)
	cout<<i<<" ";
	cout<<"\n";
	return 0;
}

---

A:Who Can Win

#include <bits/stdc++.h>
using namespace std;
struct N{
	string name;
	int nam;
	char id;
	int tim;
	string sta; 
}a[100005];
struct T{
	string name;
	int tim;
	int rem[30];
	int num;
	int tim2;
	int num2;
}b[100005];
int n;
map<pair<string,char>,int> mp;
map<string,int> po;
int cmp(N aa, N bb)
{
	return aa.tim<bb.tim;
}
int cmp2(T aa,T bb)
{
	return aa.name<bb.name;
}
int big(T aa,T bb)
{
	return aa.num>bb.num||(aa.num==bb.num&&aa.tim<=bb.tim);
}
void solve()
{
	cin>>n;
	mp.clear();
	po.clear();
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].name>>a[i].id>>a[i].tim>>a[i].sta;
		if(!po[a[i].name])
		{
			po[a[i].name]=++cnt;
			b[cnt].name=a[i].name;
			b[cnt].tim=0;
			b[cnt].num=0;
			b[cnt].tim2=0;
			b[cnt].num2=0;
			for(int j=0;j<26;j++) b[cnt].rem[j]=0;
		}
		a[i].nam=po[a[i].name];
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		if(!mp[make_pair(a[i].name,a[i].id)])
		{
			if(a[i].sta[0]=='A')
			{
				b[a[i].nam].num++;
				b[a[i].nam].tim+=a[i].tim;
				b[a[i].nam].tim+=b[a[i].nam].rem[a[i].id-'A']*20;
				mp[make_pair(a[i].name,a[i].id)]=1;
			}
			if(a[i].sta[0]=='R')
			{
				b[a[i].nam].rem[a[i].id-'A']++;
			}
			if(a[i].sta[0]=='U')
			{
				b[a[i].nam].num2++;
				b[a[i].nam].tim2+=a[i].tim;
				b[a[i].nam].tim2+=b[a[i].nam].rem[a[i].id-'A']*20;
				mp[make_pair(a[i].name,a[i].id)]=1;
			}
		}
	}
	sort(b+1,b+cnt+1,cmp2);
	T maxn;
	maxn.num=0;
	maxn.tim=666;
	for(int i=1;i<=cnt;i++)
	{
		// cout<<">> "<<b[i].name<<" "<<b[i].num<<" "<<b[i].tim<<" "<<b[i].num2<<" "<<b[i].tim2<<"\n";
		if(big(b[i],maxn)) maxn=b[i];
	}
	// cout<<"maxn> "<<maxn.name<<" "<<maxn.num<<" "<<maxn.tim<<"\n";
	for(int i=1;i<=cnt;i++)
	{
		b[i].num+=b[i].num2;
		b[i].tim+=b[i].tim2;
		if(big(b[i],maxn)) 
		{
			cout<<b[i].name<<" ";
		}
	}
	cout<<"\n";
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

---

I:Knapsack Problem

#include <bits/stdc++.h>
#define ll long long
#define PII pair<pair<ll,ll>,int >
using namespace std;
struct E{
	int v;
	ll w;
	int nex;
}e[200005];
int cnt=0;
int head[200005];
int vis[200005];
pair<ll,ll> dis[200005];
int n,m,V,t;
int x,y;
ll z;
priority_queue<PII,vector<PII>,greater<PII> > q;
void add(int u,int v,int w)
{
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt;
}
pair<ll,ll> ad(pair<ll,ll> aa,int bb)
{
	if(aa.second+bb<=V)
	{
		aa.second+=bb;
	}
	else
	{
		aa.first++;
		aa.second=bb;
	}
	return aa;
}
int main()
{
	memset(head,-1,sizeof(head));
	cin>>n>>m>>V>>t;
	for(int i=1;i<=n;i++)
		dis[i]={0x7fffffff,0x7fffffff};
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	dis[t]={1,0};
	q.push({{1,0},t});
	while(!q.empty())
	{
		int now=q.top().second;
		q.pop();
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=head[now];i!=-1;i=e[i].nex)
		{
			int v=e[i].v;
			int w=e[i].w;
			if(ad(dis[now],w)<dis[v])
			{
				dis[v]=ad(dis[now],w);
				q.push({dis[v],v});
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(dis[i].first!=0x7fffffff)
			cout<<dis[i].first<<" ";
		else cout<<"-1 ";
	}
	cout<<"\n";
	return 0;
}

---

C:Canvas Painting

#include<bits/stdc++.h>
using namespace std;
const int MAXN=220000;

struct Seg{
    int L,R;
}seg[MAXN];

bool cmp(Seg a,Seg b)
{
    return a.L==b.L?a.R<b.R:a.L<b.L;
}

priority_queue<int,vector<int>,greater<int>> pq;
void solve()
{
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        cin>>seg[i].L>>seg[i].R;
    sort(seg+1,seg+m+1,cmp);
    int idx=1,cur=0,cnt=0;
    while(idx<=m)
    {
        cur=seg[idx].L;
        do{
            while(idx<=m&&seg[idx].L<=cur)
            {
                if(cur<seg[idx].R)pq.push(seg[idx].R);
                idx++;
            }
            if(pq.empty())
                break;
            cur++;
            cnt++;
            pq.pop();
            while(!pq.empty()&&cur>=pq.top())
                pq.pop();
        }while(!pq.empty());
    }
    cout<<n-cnt<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}