智障行为+2
T1 | T2 | T3 | T4 |
---|---|---|---|
0 | 0 | 0 | 0 |
好吧至少下一次不会考更低了
T1
你有个 n 个点 m 条边的无向图,每条边都有红蓝两种颜色中的一种,保证红色的边形成了这个图的一个生成树。
你希望给这些边赋上边权,保证边权是 1 ∼ m 的排列,使得红色的边是最小生成树。
希望这些边权形成的序列字典序最小,也就是先比较第一条边的边权,再比较第二条边的边权,依次类推。
对于所有数据,保证 n, m ≤ 5 × 10^5 , m ≥ n − 1。
对,这道题(感觉像绿)卡了我很久,挂了
Time:2s
Memory:128M
正确思路:
首先,我们先看一张图:
绿字代表加入顺序(边序)
根据题意,我们会发现:红边会构成一棵树,之后每加入一条蓝边就会构成一个环(除了这条边其他环上边均为红边),由于蓝边一定是环上最大边(红边为最小生成树上的边,一定比他小),所以我们就可以用拓扑排序解决此题(时间复杂度n方,TLE)
我们可以尝试对上述方法用数据结构进行优化,但时间复杂度还是会有问题(线段树时间可能没问题,but MLE)
我们可以考虑从前往后,按顺序贪心确定每条边的大小。对于一条非树边,考虑有k条它对应的树边没
确定,那么把这些树边按顺序从小到大赋值,然后把这条树边赋上环上最大红边的边权+1即可。因为一条边被赋完值之
后不会再被修改,所以可以用并查集实现,也就是确定的边直接缩起来,时间复杂度O(nlogn) 。
code:
#include <bits/stdc++.h>
// #include<windows.h>
using namespace std;
// #pragma GCC optimize(2)
#define int long long
#define pii pair<int, int>
#define il inline
#define p_q priority_queue
#define map unordered_map
#define rg registerconst int N1 = 100005;
const int N2 = 1000006;
const int mod = 998244353;#define debug 0
#define endl '\n'int _test_ = 1;
int n,m;
vector<pii> a[N1*5];
struct edge{int x,y,col;
}e[N2];
int fa[N1*5],deep[N1*5];
int tot=0;
int top[N2],ans[N2];
int fid[N1*5];// 用来存这个节点连向父亲的边的id
namespace third_coming {void dfs(int x,int f,int dep){fa[x]=f;deep[x]=dep;for(int i=0;i<a[x].size();i++){if(f==a[x][i].first){continue;}fid[a[x][i].first]=a[x][i].second;dfs(a[x][i].first,x,dep+1);}}int asdf[5*N1];void add_edge(int id){if(e[id].col){//红边if(!ans[id]) ans[id]=++tot;//没有记录过ansreturn;//红边不需要判断环}int x=e[id].x,y=e[id].y;int u=x,v=y,tt=0;//tt,asdf是用来记录环上没有ans的红边的idwhile(top[u]!=top[v]){// cout<<u<<' '<<v<<endl;// cout<<top[u]<<' '<<top[v]<<endl;// cout<<fa[u]<<' '<<fa[v]<<endl;// Sleep(100);if(deep[top[u]]>deep[top[v]]){if(!ans[fid[top[u]]]) asdf[++tt]=fid[top[u]];u=fa[top[u]];}//u比v深,u往上爬else{if(!ans[fid[top[v]]]) asdf[++tt]=fid[top[v]];v=fa[top[v]];}//v比u深,v往上爬}//LCA+环上计算红边sort(asdf+1,asdf+tt+1);for(int i=1;i<=tt;i++){int x=asdf[i];// pq.pop();ans[x]=++tot;}ans[id]=++tot;int p=u,q=v;u=x,v=y;while(top[u]!=top[v]){if(deep[top[u]]>deep[top[v]]){// int p=top[u];int x=u;u=fa[top[u]];top[x]=top[p];}else{int x=v;v=fa[top[v]];top[x]=top[q];}}//路径压缩}void init() {// cout<<endl;cin>>n>>m;for(int i=1;i<=m;i++){// int x,y,z;cin>>e[i].x>>e[i].y>>e[i].col;if(!e[i].col) continue;a[e[i].x].push_back({e[i].y,i});a[e[i].y].push_back({e[i].x,i});}dfs(e[1].x,0,1);//预处理for(int i=1;i<=n;i++){top[i]=i;}//top用于LCA的运算(优化)for(int i=1;i<=m;i++){add_edge(i);}//一条一条加进去算for(int i=1;i<=m;i++){cout<<ans[i]<<" ";}}void solve() {}void main() {init();solve();}
}
using namespace third_coming;
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef debug// freopen("series.in", "r", stdin);// freopen("series.out", "w", stdout);
#endifthird_coming::main();return 0;
}
T2
现在有 n 个区间 [li, ri],每个区间有个权值 wi。我们把这 n 个区间当成 n 个点,如果两个区间它们之间有交(包括端点),那么我们就在这两个区间之间连边,形成了一个区间图。
现在希望你删除一些区间,使得每个连通块大小不超过 k。输出删除区间最小的权值和。
保证 1 ≤ k ≤ n ≤ 2500, 1 ≤ li ≤ ri ≤ 10^9(区间左右端点), 1 ≤ wi ≤ 10^9。
Time:1s
Memory:1G