Codeforces Round #544 (Div. 3)（A、B、C、D、E、F1、F2）

Codeforces Round #544 (Div. 3)（A、B、C、D、E、F1、F2）

欢迎访问本菜鸡的独立博客：Codecho

比赛名称

Codeforces Round #544 (Div. 3)

比赛链接

比赛情况

解题数： 4 / 7 4/7 4/7

补题数： 7 / 7 7/7 7/7

排名： 968 968 968

比赛总结

自从自己上了 1768 1768 1768 分以来，打了很多场，状态都非常差，都很自闭，真的不知道为什么。

也许是因为这种比赛有很多不确定性？？

但我觉得，那些强者怎么打都很强，说明还是自己太菜，不用找任何借口。

感觉 Codeforces ≠ ne ̸​= 训练，不能只靠这个网站的比赛来达到多好的训练效果。

固然，比赛和补题都很重要，但这只是自己进步的一个必要条件，远远达不到充分条件。

更重要的是，学习新的算法，不断刷专题，这才是训练的重头戏。

等到自己平时训练扎实之后，再去打CF，很可能**“无心插柳柳成荫”**，会看到意想不到的好结果。

还有一个多月校赛，两个多月省赛和东北赛，凭着你现在所学到的东西，你拿什么跟别人去比赛？？

希望今天下午的比赛，能够恢复到之前的巅峰状态。

A题签到题，4min1A；

B题取模之后统计个数，乱搞一下就过了，中间出现了一些BUG（因为自己没把做法完全理清就开始码了！），最后20min1A；

C题将序列排个序，按照题意统计个数，找到最大答案，最后31min1A；

D题跟 double 杠上了，一直出精度问题，赛后才想起来可以用 pair 存最简分数，直接避免了精度问题，WA了 12 12 12发，赛后补完；

E题线性dp，最初考虑的状态时截止到前 i i i 个数字，恰好分成 j j j 组的最佳答案，但是死活在第 11 11 11 组数据**WA，赛后知道当一个状态不能得到正确答案的时候，可以考虑将状态“放宽”**，赛后补完；

F1题是寻找一棵最大度数最大的生成树，因为变量名写错 WA 了一发，因为并查集没按秩合并超时了一发，最后76min3A；

F2题是寻找一棵 1 1 1 号点度数恰好为 D D D 的生成树，赛后补完。

这一场的题目整体难度不大，很适合 Div. 3 类型的比赛，但是自己状态欠佳，导致失去了一次赛中 AK 的机会。

1133A - Middle of the Contest

题意

给你一天之内的两个按先后顺序排好的时间 h 1 : m 1 h_1:m_1 h1​:m1​ 和 h 2 : m 2 h_2:m_2 h2​:m2​，保证两个时间间隔了偶数分钟。

问这两个时间点的中间时间。

解题思路

将两个时间都化为分钟，取它们的平均值，再按格式化回标准时间即可。

注意前导零的输出。

时间复杂度： O ( 1 ) O(1) O(1)

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 1e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlint main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int h1, m1, h2, m2;scanf("%d:%d", &h1, &m1);scanf("%d:%d", &h2, &m2);int t1 = h1 * 60 + m1;int t2 = h2 * 60 + m2;int t = (t1 + t2) / 2;printf("%02d:%02dn", t / 60, t % 60);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133B - Preparation for International Women’s Day

题意

给你 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n(1 le n le 2 cdot 10^5) n(1≤n≤2⋅105) 个盒子，每个盒子有 d i d_i di​ 个糖果。

现在要将这些盒子的糖果包成礼物，每两个盒子组成一份礼物（盒子不可拆分），规定一份礼物中的糖果数量必须能够被 k ( 1 ≤ k ≤ 100 ) k(1 le k le 100) k(1≤k≤100) 整除。

问最多有多少个盒子能被装进礼物中。

解题思路

注意到 k k k 的范围为 1 ≤ k ≤ 100 1 le k le 100 1≤k≤100。

并且注意到，对于两个整数 a a a 和 b b b，满足

a % k + b % k = ( a + b ) % k a%k+b%k=left( a+b right) %k a%k+b%k=(a+b)%k

因此，我们可以将所有的 d i d_i di​ 对 k k k 取模，统计每种取模结果 j ( 0 ≤ j &lt; k ) j(0 le j &lt; k) j(0≤j<k) 出现的次数 c n t j cnt_j cntj​。

之后，我们分 n n n 为奇数和偶数两种情况来讨论：

( 1 ) (1) (1) 若 n n n 为奇数，则我们假设 n = 7 n=7 n=7，则

j = 0 j=0 j=0 的糖果和 j = 0 j=0 j=0 的糖果配对；

j = 1 j=1 j=1 的糖果和 j = 6 j=6 j=6 的糖果配对；

j = 2 j=2 j=2 的糖果和 j = 5 j=5 j=5 的糖果配对；

j = 3 j=3 j=3 的糖果和 j = 4 j=4 j=4 的糖果配对。

因此这种情况下的答案为

a n s w e r = 2 ⋅ ( ⌊ c n t 0 2 ⌋ + min ⁡ { c n t 1 , c n t 6 } + min ⁡ { c n t 2 , c n t 5 } + min ⁡ { c n t 3 , c n t 4 } ) answer=2cdot left( lfloor frac{cnt_0}{2} rfloor +min left{ cnt_1,cnt_6 right} +min left{ cnt_2,cnt_5 right} +min left{ cnt_3,cnt_4 right} right) answer=2⋅(⌊2cnt0​​⌋+min{cnt1​,cnt6​}+min{cnt2​,cnt5​}+min{cnt3​,cnt4​})

( 2 ) (2) (2) 若 n n n 为偶数，则我们假设 n = 6 n=6 n=6，则

j = 0 j=0 j=0 的糖果和 j = 0 j=0 j=0 的糖果配对；

j = 1 j=1 j=1 的糖果和 j = 5 j=5 j=5 的糖果配对；

j = 2 j=2 j=2 的糖果和 j = 4 j=4 j=4 的糖果配对；

j = 3 j=3 j=3 的糖果和 j = 3 j=3 j=3 的糖果配对。

因此这种情况下的答案为

a n s w e r = 2 ⋅ ( ⌊ c n t 0 2 ⌋ + ⌊ c n t 3 2 ⌋ + min ⁡ { c n t 1 , c n t 5 } + min ⁡ { c n t 2 , c n t 4 } ) answer=2cdot left( lfloor frac{cnt_0}{2} rfloor +lfloor frac{cnt_3}{2} rfloor +min left{ cnt_1,cnt_5 right} +min left{ cnt_2,cnt_4 right} right) answer=2⋅(⌊2cnt0​​⌋+⌊2cnt3​​⌋+min{cnt1​,cnt5​}+min{cnt2​,cnt4​})

一般情况与上面同理。

时间复杂度： O ( n + k ) O(n + k) O(n+k)

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlint d[maxn], cnt[105];int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int n, k;scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++){scanf("%d", &d[i]);d[i] %= k;cnt[d[i]]++;}int answer = 0;answer += cnt[0] / 2 * 2;if(k % 2 == 0)  answer += cnt[k / 2] / 2 * 2;int range = (k % 2 == 0) ? (k / 2 - 1) : k / 2;for(int i = 1; i <= range; i++){answer += 2 * min(cnt[i], cnt[k - i]);}//answer /= 2;//answer += cnt[0];printf("%dn", answer);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133C - Balanced Team

题意

有 n ( 1 ≤ n ≤ 2 ⋅ 1 0 5 ) n(1 le n le 2 cdot 10^5) n(1≤n≤2⋅105) 个学生，每个学生的编程水平为 a i a_i ai​。

现在要组成一个队伍，保证队伍中的学生两两编程水平的差距不超过 5 5 5。

问队伍中最多有多少学生。

解题思路

将序列 a a a 从小到大排序，之后我们可采取一种类似**滑动窗口（即双指针）**的思路。

设 p o s pos pos 为当前处理的小组中，水平最低的学生的编号， i i i 为当前正在处理的学生编号，当前小组的学生数为 c n t cnt cnt。

若 a i − a p o s ≤ 5 a_i - a_{pos} le 5 ai​−apos​≤5，则将 i i i 加入到当前小组中， c n t : = c n t + 1 cnt:=cnt+1 cnt:=cnt+1；

否则，将答案与 c n t cnt cnt 取个最大值，向右更新 p o s pos pos 的位置，直到 a i − a p o s ≤ 5 a_i - a_{pos} le 5 ai​−apos​≤5.

时间复杂度： O ( n log ⁡ n + n ) O(n log n + n) O(nlogn+n)

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll a[maxn];int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int n;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%I64d", &a[i]);sort(a + 1, a + 1 + n);int answer = 0, cnt = 1, pos = 1;a[n + 1] = 0x3f3f3f3f3f3f3f3f;for(int i = 2; i <= n + 1; i++){if(a[i] - a[pos] <= 5LL)  cnt++;else{answer = max(answer, cnt);while(a[i] - a[pos] > 5LL && pos <= n)  pos++;cnt = i - pos + 1;}//dbg2(i, cnt);}printf("%dn", answer);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133D - Zero Quantity Maximization

题意

给你两个长度为 n n n 的整数序列 a a a 和 b b b。

你要创建一个新的序列 c c c，对于任意的 i ∈ [ 1 , n ] i in [1, n] i∈[1,n]，满足 c i : = d ⋅ a i + b i c_i := d cdot a_i + b_i ci​:=d⋅ai​+bi​。

其中， d d d 为任意实数。

问如何选择 d d d，可使 c c c 中 0 0 0 的数量最多。

解题思路

0 : = d ⋅ a i + b i 0 := d cdot a_i + b_i 0:=d⋅ai​+bi​ 这个式子可转化为 d = − b i a i d=-frac{b_i}{a_i} d=−ai​bi​​。

因此，我们需要讨论三种情况：

( 1 ) (1) (1) 当 a i = 0 a_i=0 ai​=0 并且 b i = 0 b_i=0 bi​=0 的时候，则无论如何选择 d d d， c i ≡ 0 c_iequiv 0 ci​≡0，因此统计这部分 i i i 的数量 t o t tot tot，最后加到答案中；

( 2 ) (2) (2) 当 a i = 0 a_i=0 ai​=0 并且 b i ≠ 0 b_ine 0 bi​̸​=0 的时候，则无论如何选择 d d d， c i ≠ 0 c_ine 0 ci​̸​=0，直接跳过；

( 3 ) (3) (3) 其他情况，直接将 d = − b i a i d=-frac{b_i}{a_i} d=−ai​bi​​ 存入数组 a r r a y array array 中。

在将分数存入数组时，我们可以使用 pair 来表示分数，要注意分子和分母必须使用它们的 g c d gcd gcd 约分完毕，才能存入 pair中。

之后将 a r r a y array array 排序，统计出现次数最多的分数的出现次数 c n t cnt cnt。

则最后， c n t + t o t cnt+tot cnt+tot 就是答案。

特别注意：本题若使用 double 直接存储小数，会导致精度问题！！

时间复杂度： O ( n log ⁡ 1 0 9 ) O(n log 10^9) O(nlog109)

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll gcd(ll a, ll b)
{return (b == 0) ? a : gcd(b, a % b);
}ll a[maxn], b[maxn];
pll c[maxn];int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int n;scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);for(int i = 1; i <= n; i++) scanf("%lld", &b[i]);int tot = 0, flag = 0;for(int i = 1; i <= n; i++){if(a[i] == 0 && b[i] == 0){tot++;continue;}else if(a[i] == 0)  continue;ll d = gcd(a[i], b[i]);c[++flag] = make_pair(a[i] / d, b[i] / d);}int answer = 0, cnt = 1;sort(c + 1, c + 1 + flag);c[flag + 1] = make_pair(LL_INF, LL_INF);for(int i = 2; i <= flag + 1; i++){if(c[i] == c[i - 1])   cnt++;else{answer = max(answer, cnt);cnt = 1;}}printf("%dn", answer + tot);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133E - K Balanced Teams

题意

有 n ( 1 ≤ n ≤ 5000 ) n(1 le n le 5000) n(1≤n≤5000) 个学生，每个学生的编程水平为 a i a_i ai​。

现在要组成 k ( 1 ≤ k ≤ n ≤ 5000 ) k(1 le k le n le 5000) k(1≤k≤n≤5000) 个队伍，保证每支队伍中的学生两两编程水平的差距不超过 5 5 5。

允许有不分到任何小组中的学生，问最多有多少学生可以被分到小组中。

解题思路

本题为线性dp问题。

将序列 a a a 从小到大排序。

设 d p [ i ] [ j ] dp[i][j] dp[i][j] 为截止到第 i i i 个学生，最多分成 j j j 组的最佳答案，

设 p o s i pos_i posi​ 为从左到右****第一个满足 a i − a p o s i ≤ 5 a_i-a_{pos_i} le 5 ai​−aposi​​≤5 的学生编号，则状态转移方程为

d p [ i ] [ j ] = max ⁡ { d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] , d p [ p o s i − 1 ] [ j − 1 ] + i − p o s i + 1 } dpleft[ i right] left[ j right] =max left{ dpleft[ i-1 right] left[ j right] ,dpleft[ i right] left[ j-1 right] ,dpleft[ pos_i-1 right] left[ j-1 right] +i-pos_i+1 right} dp[i][j]=max{dp[i−1][j],dp[i][j−1],dp[posi​−1][j−1]+i−posi​+1}

时间复杂度： O ( n log ⁡ n + n 2 ) O(n log n + n^2) O(nlogn+n2)

代码

/*Written by NitrogensDesire for getting accepted!!Need for practice of dynamic programming!!!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 5e3+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlll a[maxn];
int dp[maxn][maxn];
int pos[maxn];int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int n, k;scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);sort(a + 1, a + 1 + n);for(int i = 1; i <= n; i++) pos[i] = lower_bound(a + 1, a + 1 + n, a[i] - 5LL) - a;for(int i = 1; i <= n; i++){for(int j = 1; j <= min(k, i); j++){dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);dp[i][j] = max(dp[i][j], dp[pos[i] - 1][j - 1] + i - pos[i] + 1);}}int answer = 0;for(int i = 1; i <= k; i++) answer = max(answer, dp[n][i]);printf("%dn", answer);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133F1 - Spanning Tree with Maximum Degree

题意

给你一张由 n ( 2 ≤ n ≤ 2 ⋅ 1 0 5 ) n(2 le n le 2 cdot 10^5) n(2≤n≤2⋅105) 个点和 m ( n − 1 ≤ m ≤ m i n ( 2 ⋅ 1 0 5 , n ( n − 1 ) 2 ) ) m(n - 1 le m le min(2 cdot 10^5, frac{n(n-1)}{2})) m(n−1≤m≤min(2⋅105,2n(n−1)​)) 条边组成的无向连通图，让你输出其最大度数最大的生成树的所有边。

解题思路

找到图中度数最大的节点 i d id id，以 i d id id 为根，建立生成树。

使用并查集维护生成树。

先将 i d id id 与其所有相邻的点连边（必须在原图中存在这条边），合并所连的边的两个节点到一个集合中，再使用并查集建立余下的边。

时间复杂度： O ( m ⋅ α ( n ) ) O(m cdot alpha (n)) O(m⋅α(n))

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlint father[maxn], n, deg[maxn], point[maxn], rankk[maxn];struct edge
{int u, v;
} Edge[2 * maxn];bool operator < (edge a, edge b)
{return a.u < b.u || (a.u == b.u && a.v < b.v);
}bool cmp(int a, int b)
{return deg[a] > deg[b];
}void init()
{for(int i = 0; i <= n; i++) father[i] = i, point[i] = i, rankk[i] = 0;
}int query(int id)
{return father[id] == id ? id : query(father[id]);
}void merge(int a, int b)
{a = query(a);b = query(b);if(a != b){if(rankk[a] > rankk[b]) father[b] = a;else{father[a] = b;if(rankk[a] == rankk[b])    rankk[b]++;}}
}int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int m, u, v;scanf("%d%d", &n, &m);init();int cnt = 0;for(int i = 1; i <= m; i++){scanf("%d%d", &u, &v);Edge[++cnt] = (edge){u, v};Edge[++cnt] = (edge){v, u};deg[u]++;deg[v]++;}sort(point + 1, point + 1 + n, cmp);int id = point[1];for(int i = 1; i <= cnt; i++){if(Edge[i].u == id){printf("%d %dn", Edge[i].u, Edge[i].v);merge(Edge[i].u, Edge[i].v);}}for(int i = 1; i <= cnt; i++){if(query(Edge[i].u) != query(Edge[i].v)){printf("%d %dn", Edge[i].u, Edge[i].v);merge(Edge[i].u, Edge[i].v);}}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}

1133F2 - Spanning Tree with One Fixed Degree

题意

给你一张由 n ( 2 ≤ n ≤ 2 ⋅ 1 0 5 ) n(2 le n le 2 cdot 10^5) n(2≤n≤2⋅105) 个点和 m ( n − 1 ≤ m ≤ m i n ( 2 ⋅ 1 0 5 , n ( n − 1 ) 2 ) ) m(n - 1 le m le min(2 cdot 10^5, frac{n(n-1)}{2})) m(n−1≤m≤min(2⋅105,2n(n−1)​)) 条边组成的无向连通图，让你输出其** 1 1 1 号节点度数恰好为 D D D 的生成树**的所有边。

若答案不存在，输出 NO。

解题思路

先不考虑 1 1 1 号点，此时整个图被拆成了若干个连通分量。

用 DFS 处理 1 1 1 号点之外所有的点，计算出每个点所在的连通分量编号，同时统计每个连通分量 i i i 与 1 1 1 号点所连边的集合 S i S_i Si​ 及其大小 ∣ S i ∣ |S_i| ∣Si​∣。

设连通分量的数量为 c n t cnt cnt， 1 1 1 号点在原图中的度数大小为 d e g 1 deg_1 deg1​。

若 c n t &gt; d cnt &gt; d cnt>d 或者 d e g 1 &lt; d deg_1 &lt; d deg1​<d，则答案不存在。

之后，将连通分量按照 ∣ S i ∣ |S_i| ∣Si​∣ 从小到大排序。

用并查集来维护生成树。

首先，将 1 1 1 号点与每个连通分量中的一个点连边（必须在原图中存在这条边），合并所连每一条边的两个节点到同一集合中。

之后，若 1 1 1 号点在生成树中度数还未达到 D D D，则将 1 1 1 号点与其未连过的点随意连边（必须在原图中存在这条边），合并所连每一条边的两个节点到同一集合中，直到度数达到 D D D。

最后，使用并查集建立余下的边。

时间复杂度： O ( n ⋅ α ( n ) ) O(n cdot alpha(n)) O(n⋅α(n))

代码

/*Written by NitrogensDesire for getting accepted!!
*/
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <bitset>
#include <stack>
#include <set>
#include <vector>
using namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;const int maxn = 2e5+5;
const int Mod = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const double e = exp(1);
const db PI = acos(-1);
const db ERR = 1e-10;#define Se second
#define Fi first
#define pb push_back
#define dbg(x) cout<<#x<<" = "<< (x)<< endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endlint head[maxn], father[maxn], n, cnt, belong[maxn], tot, deg[maxn], perm[maxn], rankk[maxn];
bool vis[maxn];vector <int> conn[maxn];bool cmp(int a, int b)
{return deg[a] < deg[b];
}struct edge
{int u, v, nxt;
} Edge[2 * maxn];void init()
{memset(head, -1, sizeof(head));memset(belong, 0, sizeof(belong));for(int i = 0; i <= n; i++) father[i] = i;cnt = 0, tot = 0;
}int query(int id)
{return father[id] == id ? id : query(father[id]);
}void merge(int x, int y)
{x = query(x);y = query(y);if(x != y){if(rankk[x] > rankk[y]) father[y] = x;else{father[x] = y;if(rankk[x] == rankk[y])    rankk[y]++;}}
}void addedge(int u, int v)
{Edge[cnt].u = u;Edge[cnt].v = v;Edge[cnt].nxt = head[u];head[u] = cnt++;
}void dfs(int id)
{if(vis[id]) return;vis[id] = true;belong[id] = tot;for(int i = head[id]; i != -1; i = Edge[i].nxt){int v = Edge[i].v;if(v == 1){deg[tot]++;conn[tot].pb(id);continue;}dfs(v);}
}int main()
{//ios::sync_with_stdio(false);//freopen(&#","r",stdin);//freopen(&#","w",stdout);int m, u, v, d;scanf("%d%d%d", &n, &m, &d);init();int degone = 0;for(int i = 1; i <= m; i++){scanf("%d%d", &u, &v);addedge(u, v);addedge(v, u);degone += (u == 1 || v == 1);}for(int i = 2; i <= n; i++){if(!vis[i]){tot++;dfs(i);}}if(tot > d || degone < d){printf("NOn");return 0;}for(int i = 1; i <= tot; i++)   perm[i] = i;sort(perm + 1, perm + 1 + tot);int num = 0;printf("YESn");for(int i = 1; i <= tot; i++){int id = perm[i];num++;printf("%d %dn", 1, conn[id][0]);merge(1, conn[id][0]);if(num == d)    break;}for(int i = 1; i <= tot; i++){int id = perm[i];for(int j = 1; j < conn[id].size(); j++){if(num >= d)    break;num++;printf("%d %dn", 1, conn[id][j]);merge(1, conn[id][j]);}if(num >= d)    break;}for(int i = 1; i <= cnt; i++){u = Edge[i].u;v = Edge[i].v;if(u == 1 || v == 1)    continue;if(query(u) != query(v)){printf("%d %dn", u, v);merge(u, v);}}//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}