2.6 寒假训练营补题

C Tokitsukaze and Balance String (hard)

题目描述

本题为《Tokitsukaze and Balance String (easy)》的困难版本，两题的唯一区别在于 $n$ 的范围。

一个字符串是平衡的，当且仅当字符串中 "01" 连续子串的个数与 "10" 连续子串的个数相同。

定义字符串 $s$ 的 $val(s)$ 为这样的位置数量：

• 若当前位置上的字符为 '0'，将其反置后成为 '1'，此时字符串 $s$ 是平衡的；
• 若当前位置上的字符为 '1'，将其反置后成为 '0'，此时字符串 $s$ 是平衡的。

现在 Tokitsukaze 有一个长度为 $n$，仅由字符 '0'、'1'、'?' 构成的字符串 $s$。

其中，'?' 可以替换成 '0' 或者 '1'。假设 '?' 的个数为 $p$，显然将每个 '?' 都替换后，总共可以得到 $2^p$ 个不同的 $s$，Tokitsukaze 想知道所有 $2^p$ 个不同的 $s$ 对应的 $val(s)$ 之和是多少。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 2\times 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(1\le n\le 2\times 10^5)$ 代表字符串长度。
• 第二行输入一个长度为 $n$、仅由 '0'、'1'、'?' 构成的字符串 $s$。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2\times 10^5$。

输出描述

对于每一组测试数据，新起一行。输出一个整数，代表全部 $2^p$ 个不同的 $s$ 对应的 $val(s)$ 之和。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

示例

输入

5
1
0
4
??01
5
?????
10
010??1101?
50
??1??0?0???????0?1??00?1???1??0?11??1011001???00??

输出

1
8
80
40
421772709

说明

• 对于第一组测试数据，反置字符串的第一个字符，得到字符串 "1"，此时，"01" 子串与 "10" 子串个数均为 $0$，平衡。由于在这个样例中，只有一种不同的 $s$，所以答案即为 $val("1")=1$。
• 对于第二组测试数据，通过替换 '?' 得到 $4$ 种不同的 $s$，分别为："0001"、"0101"、"1001"、"1101"。限制于篇幅，我们在此仅详细展开讨论 "0001" 的情况。
  • 翻转第一个字符，得到 "1001"，此时，"01" 子串与 "10" 子串个数均为 $1$，平衡。
  • 翻转第二个字符，得到 "0101"，此时，"01" 子串个数为 $2$，"10" 子串个数为 $1$，不平衡。
  • 翻转第三个字符，得到 "0011"，此时，"01" 子串个数为 $1$，"10" 子串个数为 $0$，不平衡。
  • 翻转第四个字符，得到 "0000"，此时，"01" 子串与 "10" 子串个数均为 $0$，平衡。
    综上，得到 $val("0001")=2$。同理可得其他三个字符串。最终答案为 $2+2+2+2=8$。

解题思路

核心性质

对于长度为 $n$ 的 01 字符串 $s$，当 $s_1$ 与 $s_n$ 相等时，“01” 与 “10” 子串数量相等。所以在 $2\le i\le n-1$ 范围内的 ? 可以随意填充，不会影响 “01” 与 “10” 子串的数量。

定义变量

令 $2\le i\le n-1$ 中的 ? 个数为 $cnt$。

不考虑 $s_1$ 与 $s_n$ 为 ? 的情况

情况一：$s_1=s_n$

当 $s_1$ 等于 $s_n$ 时，$2\le i\le n-1$ 中的 $s_i$ 可以随意翻转。此时 $val(s)=n-2$，那么这部分对结果的贡献为 $2^{cnt}\cdot (n-2)$。

情况二：$s_1\ne s_n$

当 $s_1$ 不等于 $s_n$ 时，必须翻转 $s_1$ 或者 $s_n$ 才能使字符串满足条件，即 $val(s)=2$，这部分对结果的贡献为 $2^{cnt}\cdot 2$。

考虑 $s_1$ 与 $s_n$ 为 ? 的情况

当 $s_1$ 与 $s_n$ 为 ? 时，需要再进行分类讨论，具体细节可参考后续代码实现。

优化点

由于 $cnt$ 最多等于 $n-2$，我们可以对 $2$ 的幂进行预处理，这样就不需要使用快速幂算法，能将时间复杂度控制在 $O(n)$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod= 1e9+7;
int qpow(int a,int b)
{int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b/=2;}return res;
}
void solve()
{int n;cin>>n;string s;cin>>s;s=" "+s;if(n==1){if(s[1]!='?')cout<<1<<'\n';else cout<<2<<'\n';}else{int cnt=0;for(int i=2;i<=n-1;i++)if(s[i]=='?')cnt++;int ans=qpow(2,cnt);if(s[1]==s[n]){if(s[1]!='?')ans=ans*(n-2)%mod;else ans=ans*2*n%mod;}else{if(s[1]=='?' && s[n]!='?')ans=ans*n%mod;else if(s[1]!='?' && s[n]=='?')ans=ans*n%mod;else ans=ans*2%mod;}cout<<ans<<'\n';}
}signed main()
{  int t;cin>>t;while(t--)solve();return 0;
}

A Tokitsukaze and Absolute Expectation

题目描述

Tokitsukaze 有一个由 $n$ 个整数组成的序列 { a 1 , a 2 , … , a n } \{a_1, a_2, \ldots, a_n\} {a1​,a2​,…,an​}，其中第 $i$ 个元素 $a_i$ 的值在区间 $[l_i,r_i]$ 中独立地、等概率随机生成。

定义一个序列的价值为 $val(a)={\sum }_{i=2}^n|a_{i-1}-a_i|$，Tokitsukaze 想知道 $val(a)$ 的期望。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(2\le n\le 2\times 10^5)$ 代表序列中元素的数量。
• 此后 $n$ 行，第 $i$ 行输入两个整数 $l_i,r_i(1\le l_i\le r_i\le 10^9)$ 代表第 $i$ 个元素的取值范围。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2\times 10^5$。

输出描述

可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，为了避免精度问题，请直接输出整数 $(p\cdot q^{-1}\mathrm{mod}M)$ 作为答案，其中 $M=10^9+7$，$q^{-1}$ 是满足 $q\times q^{-1}\equiv 1(\mathrm{mod}M)$ 的整数。

更具体地，你需要找到一个整数 $x\in [0,10^9+7)$ 满足 $x\times q$ 对 $10^9+7$ 取模等于 $p$，您可以查看样例解释得到更具体的说明。

示例

输入

2
3
1 2
1 2
1 3
4
4 8
2 3
4 10
4 7

输出

333333337
214285726

说明

对于第一组测试数据，总共有 $12$ 种序列，每种序列出现的概率均相等，如下：

• v a l ( { 1 , 1 , 1 } ) = ∣ 1 − 1 ∣ + ∣ 1 − 1 ∣ = 0 val(\{1, 1, 1\}) = |1 - 1|+|1 - 1| = 0 val({1,1,1})=∣1−1∣+∣1−1∣=0；
• v a l ( { 1 , 1 , 2 } ) = ∣ 1 − 1 ∣ + ∣ 1 − 2 ∣ = 1 val(\{1, 1, 2\}) = |1 - 1|+|1 - 2| = 1 val({1,1,2})=∣1−1∣+∣1−2∣=1；
• v a l ( { 1 , 1 , 3 } ) = ∣ 1 − 1 ∣ + ∣ 1 − 3 ∣ = 2 val(\{1, 1, 3\}) = |1 - 1|+|1 - 3| = 2 val({1,1,3})=∣1−1∣+∣1−3∣=2；
• v a l ( { 1 , 2 , 1 } ) = ∣ 1 − 2 ∣ + ∣ 2 − 1 ∣ = 2 val(\{1, 2, 1\}) = |1 - 2|+|2 - 1| = 2 val({1,2,1})=∣1−2∣+∣2−1∣=2；
• v a l ( { 1 , 2 , 2 } ) = ∣ 1 − 2 ∣ + ∣ 2 − 2 ∣ = 1 val(\{1, 2, 2\}) = |1 - 2|+|2 - 2| = 1 val({1,2,2})=∣1−2∣+∣2−2∣=1；
• v a l ( { 1 , 2 , 3 } ) = ∣ 1 − 2 ∣ + ∣ 2 − 3 ∣ = 2 val(\{1, 2, 3\}) = |1 - 2|+|2 - 3| = 2 val({1,2,3})=∣1−2∣+∣2−3∣=2；
• v a l ( { 2 , 1 , 1 } ) = ∣ 2 − 1 ∣ + ∣ 1 − 1 ∣ = 1 val(\{2, 1, 1\}) = |2 - 1|+|1 - 1| = 1 val({2,1,1})=∣2−1∣+∣1−1∣=1；
• v a l ( { 2 , 1 , 2 } ) = ∣ 2 − 1 ∣ + ∣ 1 − 2 ∣ = 2 val(\{2, 1, 2\}) = |2 - 1|+|1 - 2| = 2 val({2,1,2})=∣2−1∣+∣1−2∣=2；
• v a l ( { 2 , 1 , 3 } ) = ∣ 2 − 1 ∣ + ∣ 1 − 3 ∣ = 3 val(\{2, 1, 3\}) = |2 - 1|+|1 - 3| = 3 val({2,1,3})=∣2−1∣+∣1−3∣=3；
• v a l ( { 2 , 2 , 1 } ) = ∣ 2 − 2 ∣ + ∣ 2 − 1 ∣ = 1 val(\{2, 2, 1\}) = |2 - 2|+|2 - 1| = 1 val({2,2,1})=∣2−2∣+∣2−1∣=1；
• v a l ( { 2 , 2 , 2 } ) = ∣ 2 − 2 ∣ + ∣ 2 − 2 ∣ = 0 val(\{2, 2, 2\}) = |2 - 2|+|2 - 2| = 0 val({2,2,2})=∣2−2∣+∣2−2∣=0；
• v a l ( { 2 , 2 , 3 } ) = ∣ 2 − 2 ∣ + ∣ 2 − 3 ∣ = 1 val(\{2, 2, 3\}) = |2 - 2|+|2 - 3| = 1 val({2,2,3})=∣2−2∣+∣2−3∣=1；

综上所述，期望值为 $\frac{0+1+2+2+1+2+1+2+3+1+0+1}{12}=\frac{4}{3}$。我们能够找到，$333333337\times 3=1000000011$，对 $10^9+7$ 取模后恰好等于分子 $4$，所以 $333333337$ 是需要输出的答案。

解题思路

链接：https://ac.nowcoder.com/discuss/1454104
来源：牛客网

核心转化

根据期望的线性性质，可以转化成求 $|a_i-a_{i-1}|$ 的期望之和。那么问题就转化成了 $|a_i-a_{i-1}|$ 的期望。

分母计算

由于 $a_{i-1}$ 和 $a_i$ 在区间 $[l_{i-1},r_{i-1}]$ 和 $[l_i,r_i]$ 等概率随机，所以分母为 $(r_{i-1}-l_{i-1}+1)\cdot (r_i-l_i+1)$。

分子计算

分子是 $a_{i-1}$ 和 $a_i$ 绝对值之差的所有情况之和。假设目前计算的是 $[l_1,r_1]$，$[l_2,r_2]$。设 $[x,y]$ 为这两个区间的交，即 $x=\max (l_1,l_2)$，$y=\min (r_1,r_2)$。然后通过下面 3 个部分进行计算：

1. $[l_1,x-1]$ 与 $[l_2,r_2]$
2. $[x,y]$ 与 $[y+1,r_2]$
3. $[x,y]$ 与 $[x,y]$

情况 1 和情况 2 很好算，因为它们区间都没有交。实现可以参考代码中的 cal2 函数。

情况 3 因为它是对称的，可以推出一个式子。式子可以参考代码中的 cal3 函数。

复杂度分析

求完分子就做完了。由于每次需要求一下分母的逆元，所以时间复杂度为 $O(n\log m)$，$m=10^9+7$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=5e5+10;
const int mod=1e9+7;
ll qpow(ll a,ll b)
{ll res=1;while(b>0){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
ll inv(ll x){return qpow(x,mod-2);}
const ll inv3=inv(3);
ll cal3(int l,int r)
{int n=r-l+1;return 1LL*(n-1)*n%mod*(n+1)%mod*inv3%mod;
}
ll cal2(int l1,int r1,int l2,int r2)
{if(l1>r1||l2>r2) return 0;ll res=0;res+=1LL*(l2+r2)*(r2-l2+1)/2%mod*(r1-l1+1);res-=1LL*(l1+r1)*(r1-l1+1)/2%mod*(r2-l2+1);res%=mod;if(res<0) return res+mod;return res;
}
ll cal(int l1,int r1,int l2,int r2)
{if(l1>l2){swap(l1,l2);swap(r1,r2);}int x,y;x=max(l1,l2);y=min(r1,r2);if(x>y) return cal2(l1,r1,l2,r2);ll res=0;res+=cal2(l1,x-1,l2,r2);res+=cal2(x,y,y+1,max(r1,r2));res+=cal3(x,y);return res%mod;
}
int l[MAX],r[MAX];
signed main()
{int t,n,i;ll ans,fz,fm;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]);ans=0;for(i=2;i<=n;i++){fz=cal(l[i-1],r[i-1],l[i],r[i]);fm=1LL*(r[i-1]-l[i-1]+1)*(r[i]-l[i]+1)%mod;ans=(ans+fz*inv(fm))%mod;}printf("%lld\n",ans);}return 0;
}

F Tokitsukaze and Kth Problem (easy)

题目描述

本题与《Tokitsukaze and Kth Problem (hard)》共享题目背景，可以视作困难版本的子问题。若能通过 hard，在做简单修改后，必能通过 easy。

Tokitsukaze 有一个由 $n$ 个整数组成的序列 { a 1 , a 2 , … , a n } \{a_1, a_2, \ldots, a_n\} {a1​,a2​,…,an​}。他定义一个二元组 $(i,j)$ 满足 $1\le i<j\le n$，并定义这个二元组对应的值 $f(i,j)=(a_i+a_j)\mathrm{mod}p$。

他想知道，对于全部不同的二元组 $(i,j)$，全部值 $f(i,j)$ 的前 $k$ 大值分别为多少。如果不存在，则输出 $-1$ 替代。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入三个整数 $n,p,k(2\le n\le 2\times 10^5;1\le p\le 10^9;1\le k\le 2\times 10^5)$ 代表序列中的元素数量、模数、询问大小。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots ,a_n(0\le a_i\le 10^9)$ 代表序列中的元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2\times 10^5$，$k$ 之和不超过 $2\times 10^5$。

输出描述

对于每一组测试数据，新起一行。连续输出 $k$ 个整数，第 $x$ 个整数表示 $f(i,j)$ 的第 $x$ 大值，如果不存在第 $x$ 大值，输出 $-1$ 替代。

示例

输入

3
3 10 8
2 4 8
4 6 4
1 2 3 3
5 10 10
1 2 3 4 5

输出

6 2 0 -1 -1 -1 -1 -1
5 5 4 4
9 8 7 7 6 6 5 5 4 3

说明

对于第二组测试数据，一共有六个不同的二元组，对应的值分别为：

• $f(1,2)=(1+2)\mathrm{mod}6=3$；
• $f(1,3)=(1+3)\mathrm{mod}6=4$；
• $f(1,4)=(1+3)\mathrm{mod}6=4$；
• $f(2,3)=(2+3)\mathrm{mod}6=5$；
• $f(2,4)=(2+3)\mathrm{mod}6=5$；
• $f(3,4)=(3+3)\mathrm{mod}6=0$；

排序后得到 { 0 , 3 , 4 , 4 , 5 , 5 } \{0, 3, 4, 4, 5, 5\} {0,3,4,4,5,5}。

解题思路

Solution 1：二分答案

这类求第 $k$ 大，或者前 $k$ 大类的题，一般可以先考虑二分答案。

• 由于 easy 版本与序列顺序无关，所以可以先对序列进行排序（sort），然后二分答案后用双指针数一下有多少对大于等于答案。
• 求出第 $k$ 大后，大于答案的对可以暴力求出来，剩下的再用答案填。

时间复杂度：$O(n\log V+k)$，其中 $V$ 为值域。

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75401127

Solution 2：堆

我们可以构造一种方案，使得堆内必定存在当前的最大值。这样只要从堆中弹出 $k$ 次就是前 $k$ 大。

• 对于这道题，可以枚举 $a_i$，对于每个 $a_i$，找到与它匹配能使 $f(i,j)$ 最大的 $a_j$ 放入堆中。
• 每次从堆中弹出一个东西，我们就把下一个与 $a_i$ 匹配的 $a_j$ 放入堆中（如果有的话）。

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

代码链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75401133

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010, mod = 1e9 + 7;
#define int long long 
int a[N], b[N];
int n, m, k;
void solve() {int p;cin >> n >> p >> k;for (int i = 1; i <= n; i++) {cin >> a[i];a[i] %= p;}sort(a + 1, a + 1 + n);auto work = [&](int x) -> long long {int ans = 0;for (int i = 1, j = n; i <= n; i++) {while (j >= 1 && a[i] + a[j] >= x) j--;if (j > i)  ans += n - j;else ans += n - i;}return ans;};auto check = [&](int x) -> long long {return work(x) + work(p + x) - work(p);};int l = 0, r = p - 1;while (l <= r) {int mid = l + r >> 1;if (check(mid) >= k)  l = mid + 1;else r = mid - 1;}vector<int> ans;for (int i = 1, j = n, c = n; i <= n; i++) {while (j >= 1 && a[i] + a[j] >= l) j--;while (c >= 1 && a[i] + a[c] >= l + p) c--;for (int ii = max(i, j) + 1; ii <= n; ii++) {if (a[i] + a[ii] >= p)  break;ans.push_back(a[i] + a[ii]);}for (int ii = max(i, c) + 1; ii <= n; ii++)ans.push_back((a[i] + a[ii]) % p);}while (ans.size() < k)  ans.push_back(r);sort(ans.begin(), ans.end(), greater<int>());for (auto t : ans)  cout << t << ' ';cout << '\n';
}
signed main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}return 0;
}

J Tokitsukaze and Recall

题目描述

在初代《星际争霸》中，神族的仲裁者有“recall”技能，可将一定范围的我方部队从地图任意地点传送到仲裁者所在位置，且仲裁者可部署在任意敌方区域上空，能使用任意次该技能。

Tokitsukaze 玩“岛屿”地图，地图区域不一定连通，敌方占领 $n$ 块区域，有 $m$ 条双向道路连接不同区域。我方部队可在已占领区域随意移动，但无法穿过敌方占领区域，不过可通过在目标区域部署仲裁者使用“recall”技能将部队传送过去。

Tokitsukaze 有一个无敌地面部队，部队初始在区域 $0$（与敌方区域不相连），她只能建造 $k$ 个仲裁者，想合理部署以尽可能多地占领敌方区域。要求输出最多能占领的敌方区域数量，以及按占领顺序输出区域编号，若有多种方案，输出字典序最小的那种。

字典序规则：数组 $c$ 在字典序上小于数组 $d$ 当且仅当以下任一情况成立：

• $|c|<|d|$ 并且对于所有 $1\le i\le |c|$ 满足 $c_i=d_i$，其中 $|c|$ 表示数组 $c$ 的长度；
• 在 $c$ 和 $d$ 不同的第一个位置上，数组 $c$ 的元素小于数组 $d$ 中对应的元素。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1\le T\le 2\times 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入三个整数 n , m , k ( 1 ≤ k ≤ n ≤ 2 × 1 0 5 ; 0 ≤ m ≤ min ⁡ { n × ( n − 1 ) 2 , 5 × 1 0 5 } ) n, m, k(1\leq k\leq n\leq 2\times 10^5; 0\leq m\leq \min\{\frac{n\times(n - 1)}{2}, 5\times 10^5\}) n,m,k(1≤k≤n≤2×105;0≤m≤min{2n×(n−1)​,5×105}) 代表地图区域数量、双向道路数量、仲裁者数量。
• 此后 $m$ 行，第 $i$ 行输入两个整数 $u_i,v_i(1\le u_i,v_i\le n;u_i\ne v_i)$ 代表第 $i$ 条双向道路连接区域 $u_i$ 和 $v_i$。保证不存在重复道路，即每两块区域之间最多只有一条道路直接连接。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2\times 10^5$，$m$ 之和不超过 $5\times 10^5$。

输出描述

对于每一组测试数据，输出两行：

• 第一行输出一个整数 $s(1\le s\le n)$ 代表 Tokitsukaze 最多占领的敌方区域数量。
• 第二行输出 $s$ 个互不相同的整数 $c_1,c_2,\dots ,c_s(1\le c_i\le n)$，第 $i$ 个整数 $c_i$ 表示 Tokitsukaze 第 $i$ 次占领的是区域 $c_i$。如果有多种方案，输出字典序最小的那种。

示例

示例 1

输入

5
4 3 1
2 1
1 3
3 4
4 3 1
1 3
3 4
4 2
4 3 2
1 3
3 4
4 2
5 3 1
1 2
3 4
4 5
6 4 1
1 2
2 6
3 4
4 5

输出

4
1 2 3 4
4
1 3 4 2
4
1 2 3 4
3
3 4 5
3
1 2 6

说明

• 对于第一组测试数据：将仅有 $1$ 个仲裁者部署在区域 $1$，Tokitsukaze 将部队传送到区域 $1$ 并占领；接着让部队到达区域 $2$ 并占领；接着让部队从区域 $2$ 回到区域 $1$，然后前往区域 $3$ 并占领；最后让部队从区域 $3$ 前往区域 $4$ 并占领。所以占领的顺序是 { 1 , 2 , 3 , 4 } \{1, 2, 3, 4\} {1,2,3,4}。
• 对于第二组测试数据：将仅有 $1$ 个仲裁者部署在区域 $1$，Tokitsukaze 将部队传送到区域 $1$ 并占领；接着让部队到达区域 $3$ 并占领；接着让部队从区域 $3$ 前往区域 $4$ 并占领；最后让部队从区域 $4$ 前往区域 $2$ 并占领。所以占领的顺序是 { 1 , 3 , 4 , 2 } \{1, 3, 4, 2\} {1,3,4,2}。
• 对于第三组测试数据：将 $2$ 个仲裁者分别部署在区域 $1$ 和区域 $2$。
• 对于第四组测试数据：将 $1$ 个仲裁者部署在区域 $1$ 或者区域 $2$ 只能占领 $2$ 个敌方区域；而部署在区域 $3$、$4$、$5$ 中任意一个区域，均可以占领 $3$ 个敌方区域，并且部署在区域 $3$ 可以使占领顺序的区域编号字典序最小，占领的顺序为 { 3 , 4 , 5 } \{3, 4, 5\} {3,4,5}。
• 对于第五组测试数据：将 $1$ 个仲裁者部署在区域 $1$、$2$、$6$ 中任意一个区域可以占领 $3$ 个敌方区域；部署在区域 $3$、$4$、$5$ 中任意一个区域也可以占领 $3$ 个敌方区域。字典序最小的方案是部署在区域 $1$，占领顺序为 { 1 , 2 , 6 } \{1, 2, 6\} {1,2,6}。

示例 2

输入

4
4 0 1
4 0 2
4 0 3
4 0 4

输出

1
1
2
1 2
3
1 2 3
4
1 2 3 4

解题思路

整体思路

题目要求访问到的点数最多，并且访问顺序的字典序最小。可以分两步解决：先求出能访问到的最多点数，再考虑访问顺序的字典序最小。

解决点数最多的问题

求出每个连通块有多少个点，并按点的数量从大到小排序。优先选择点数前 $k$ 多的连通块；如果 $k$ 大于等于连通块个数，则可以全选。

考虑字典序最小

• 选择连通块时：如果两个连通块的点数相同但只能选一个，设连通块内编号最小的节点的编号为 $mn$，在排序时，优先选择 $mn$ 小的那个连通块。
• 统计连通块信息：统计连通块内节点个数与最小编号可以建图后使用深度优先搜索（dfs）或者并查集实现。
• 维护可访问节点：为了使字典序最小，用一个优先队列来维护所有可访问的节点，每次弹出最小编号。
• 部署仲裁者：因为要求访问顺序字典序最小，所以仲裁者肯定会被部署在一个连通块的编号最小的节点上，即部署在连通块的 $mn$ 节点。最初，把所有选择的连通块的 $mn$ 节点都放入优先队列。
• 处理剩余仲裁者：如果 $k$ 大于连通块个数，即 $k$ 还有剩余，可以把剩余的 $k$ 服务于最小字典序。具体的，如果当前 $k>0$，并且存在编号比队列弹出来的编号更小的节点，那么直接在那个节点上部署是更优的。

复杂度分析

由于使用了优先队列，每个节点最多会入队出队一次，所以时间复杂度为 $O(n\log n)$。

代码链接

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75401084

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f[2000005];
int ver[2000005],Next[2000005],head[2000005],tot;
int fa[2000005],sz[2000005],minn[2000005];
int ans[2000005],num;
struct node
{int mn,sz;
}t[2000005];
int cmp(node a,node b)
{if(a.sz==b.sz)return a.mn<b.mn;return a.sz>b.sz;
}
void add(int x,int y)
{ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
int find(int x)
{if(x==fa[x])return fa[x];return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{int t1=find(x),t2=find(y);if(t1!=t2){fa[t2]=t1;sz[t1]+=sz[t2];minn[t1]=min(minn[t1],minn[t2]);}
}
signed main()
{int tt;cin>>tt;while(tt--){int sum=0;tot=0,num=0;int k;cin>>n>>m>>k;for(int i=1;i<=n;i++){fa[i]=i;sz[i]=1;minn[i]=i;}for(int i=1;i<=m;i++){int x,y;cin>>x>>y;add(x,y);add(y,x);merge(x,y);}int cnt=0;map<int,int>mp;for(int i=1;i<=n;i++){if(!mp[find(i)]){t[++cnt].mn=minn[find(i)];t[cnt].sz=sz[find(i)];mp[find(i)]=1;}}sort(t+1,t+cnt+1,cmp);priority_queue<int>q;map<int,int>v;for(int i=1;i<=min(k,cnt);i++){sum+=t[i].sz;q.push(-t[i].mn);v[t[i].mn]=1;}if(k>=cnt)k-=cnt;elsek=0;int mex=1;while(q.size()){int u=-q.top();q.pop();ans[++num]=u;for(int i=head[u];i;i=Next[i]){int y=ver[i];if(!v[y]){q.push(-y);v[y]=1;}}if(k){int p=-q.top();if(p!=u+1){v[u+1]=1;q.push(-u-1);k--;}}}cout<<sum<<endl;for(int i=1;i<=sum;i++){cout<<ans[i]<<" ";}cout<<endl;for(int i=0;i<=n;i++){head[i]=0;ans[i]=0;t[i].sz=0;t[i].mn=0;}}return 0;
}