The 2025 ICPC Asia East Continent Online Contest (I) 7/13 A/B/C/D/G/I/M

比赛链接：https://qoj.ac/contest/2513

G Sorting

拓扑排序后，保证每一层都只有一个数，且 \(1-n\) 每个数都在一层

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;void solve(){int n,m;cin>>n>>m;vector<vector<int>> g(n+1);vector<int> d(n+1);map<pii,int> mp;bool f=1;while(m--){int u,v;cin>>u>>v;if(mp[{u,v}]) continue;else if(mp[{v,u}]){f=0;continue;}g[u].push_back(v);d[v]++;}int cnt=0;queue<int> q;for(int i=1;i<=n;i++){if(d[i]==0) q.push(i);}while(q.size()){if(q.size()!=1){cout<<"No\n";return;}auto t=q.front();q.pop();cnt++;for(auto v:g[t]){d[v]--;if(d[v]==0) q.push(v);}}if(cnt!=n) f=0;if(f==0) cout<<"No\n";else cout<<"Yes\n";}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

B Creating Chaos

队友秒的，赛时没看题

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,k;cin>>n>>k;for(int i=1;i<=k;i++){cout<<i<<" ";}}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

A Who Can Win

小模拟，按照 ICPC 规则模拟即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using pss=pair<string,string>;struct node{string name;string ti;int t;string value;bool operator< (const node &other) const {return t<other.t;}}w[100005];void solve(){int n,k;map<string,pii> ac;map<pss,int> re;map<pss,int> yes;map<string,map<string,int>>m;vector<string> v;cin>>n;for(int i=1;i<=n;i++) {int t;string name,ti,value;cin>>name>>ti>>t>>value;w[i]={name,ti,t,value};}sort(w+1,w+1+n);for(int i=1;i<=n;i++){int t=w[i].t;string name=w[i].name,ti=w[i].ti;string value=w[i].value;if(value=="Unknown"){if(m[name].count(ti)){m[name][ti]=min(m[name][ti],t);}else{m[name][ti]=t;}}else if(value=="Accepted"){if(yes.find({name,ti})!=yes.end()) continue;ac[name].first+=1;yes[{name,ti}]=1;if(re.find({name,ti})==re.end()){ac[name].second+=t;}else ac[name].second+=t+20*re[{name,ti}];}else{if(yes.find({name,ti})!=yes.end()) continue;re[{name,ti}]++;}}int bnum=0,bt=0;for(auto [a,b]:ac){auto [t,num]=b;if(t>bt){bt=t;bnum=num;}if(t==bt&&num<bnum){bnum=num;}}for(auto [a,b]:ac){auto [t,num]=b;if(t==bt&&num==bnum){v.push_back(a);}}for(auto [a,b]:m){int t=ac[a].first,time=ac[a].second;for(auto [c,d]:b){if(yes.find({a,c})!=yes.end()) continue;t++;time+=d+20*re[{a,c}];}if(t>bt||t==bt&&time<=bnum){v.push_back(a);}}v.erase(unique(v.begin(),v.end()),v.end());sort(v.begin(),v.end());for(auto it:v) cout<<it<<" ";cout<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}
}

I Knapsack Problem

从起点走到终点和反方向走的代价相等，反向跑最短路即可

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
const int inf=1e18;void solve(){int n,m,v,t;cin>>n>>m>>v>>t;vector<vector<pii>> g(n+1);while(m--){int a,b,w;cin>>a>>b>>w;g[a].push_back({b,w});g[b].push_back({a,w});}vector<int> st(n+1);vector<pii> dist(n+1,{inf,inf});dist[t]={0,0};priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> q;q.push({0,0,t});while(q.size()){auto [cnt,ex,u]=q.top();q.pop();if(st[u]) continue;st[u]=1;for(auto [ne,w]:g[u]){int r=cnt,now=w+ex;if(now>v){r++;now=w;}if(r<dist[ne].first || (r==dist[ne].first && now<dist[ne].second)){dist[ne]={r,now};q.push({r,now,ne});}}}for(int i=1;i<=n;i++){if(dist[i].first==inf){cout<<-1<<" ";continue;}if(dist[i].first==0 && dist[i].second==0) cout<<1<<" ";else cout<<dist[i].first+(dist[i].second!=0)<<" ";}}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}

M Teleporter

分层图，按照传送次数分层，在每层跑多源最短路即可。

处理完本层后，尝试使用每个传送器，扩展到下一层

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,m;cin>>n>>m;vector<vector<pii>> g(n+1);vector<int> dist(n+1,inf);dist[1]=0;for(int i=1;i<n;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}vector<pii> tele;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;tele.push_back({u,v});}priority_queue<pii,vector<pii>,greater<pii>> q;q.push({0,1});auto dijkstra=[&]()-> int {vector<int> st(n+1);while(q.size()){auto [d,u]=q.top();q.pop();if(st[u]) continue;st[u]=1;for(auto [v,w]:g[u]){if(dist[v]>d+w){dist[v]=d+w;q.push({dist[v],v});}}}int res=0;for(int i=1;i<=n;i++){res+=dist[i];}return res;};cout<<dijkstra()<<endl;for(int k=1;k<=n;k++){vector<int> ndist=dist;for(auto [u,v]:tele){ndist[u]=min(dist[v],ndist[u]);ndist[v]=min(dist[u],ndist[v]);}for(int u=1;u<=n;u++){if(ndist[u]<dist[u]){dist[u]=ndist[u];q.push({dist[u],u});}}cout<<dijkstra()<<endl;}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}return 0;
}

C Canvas Painting

按照左端点 \(l\) 排序，排序后，优先 处理最小的 \(l\) 和其对应的线段中最小的 \(r\)

可以使用优先队列维护，每处理一个就要尝试添加和删除堆中的元素

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
using ll = long long;
using ull = unsigned long long;
const ll inf = 1e18;
const int mod = 998244353;void solve(){int n,m;cin>>m>>n;int ans=n;vector<pii> seg(m);for(int i=0;i<m;i++){cin>>seg[i].first>>seg[i].second;}sort(seg.begin(),seg.end());priority_queue<int,vector<int>,greater<int>> q;int now=0;while(now<m){int L=seg[now].first;//把所有l<=L 且 r>L的r放进q里while(now<m && seg[now].first<=L){if(seg[now].second>L){q.push(seg[now].second);}now++;}while(q.size()){auto r=q.top();q.pop();//堆顶的元素一定能被处理，处理掉堆顶if(r>L){ans--;L++;}while(q.size() && q.top()<=L) q.pop();//因为L被更新了，所以尝试再次把所有l<=L 且 r>L的r放进q里while(now<m && seg[now].first<=L){if(seg[now].second>L){q.push(seg[now].second);}now++;}}}cout<<ans<<endl;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;cin>>ct;while(ct--){solve();}return 0;
}

D Min-Max Tree

对以 \(u\) 为根的子树，一定可以划分成，一些完整的块，和一个通过节点 \(u\) 和子树外部连接的不完整的块

这个块的状态可以是 00 01 10 11，这两位分别表示，在子树内部，这个不完整的块有无正贡献值/副贡献值

设状态 \(f[u] [0/1/2/3]\)，节点 \(u\) 的状态可以从下层节点转移得到

答案即为 \(max(f[u] [0],~f[u] [3])\)

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using pii=pair<int,int>;
const int N=1e6+10;
const int inf = 1e18;void solve(){int n;cin>>n;vector<int> w(n+1);vector<vector<int>> g(n+1);for(int i=1;i<=n;i++){cin>>w[i];}for(int i=1;i<n;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}//f[u][x]:以u为根的子树，连接子树和子树外的块，已有x//x:00,01,10,11 //两位分别表示这个连接子树和子树外的块有无正贡献和副贡献的点vector<vector<int>> f(n+1,vector<int>(4));for(int i=1;i<=n;i++){f[i][0]=0;f[i][1]=w[i];f[i][2]=-w[i];f[i][3]=-inf;}auto dfs=[&](auto dfs,int u,int pre)->void {for(auto v:g[u]){if(v==pre) continue;dfs(dfs,v,u);vector<int> nf(4,-inf);for(int i=0;i<4;i++){for(int j=0;j<4;j++){if(i&j) continue;nf[i|j]=max(nf[i|j],f[u][i]+f[v][j]);}}f[u]=nf;}f[u][0]=max(f[u][0],f[u][3]);};dfs(dfs,1,0);cout<<f[1][0]<<endl;}signed main(){ios::sync_with_stdio(0);cin.tie(0);int ct=1;// cin>>ct;while(ct--){solve();}
}