淘客网站系统免费源码,免费培训机构,谷歌怎么推广自己的网站,湛江网站制作C Tokitsukaze and Balance String (hard)
题目描述
本题为《Tokitsukaze and Balance String (easy)》的困难版本#xff0c;两题的唯一区别在于 n n n 的范围。
一个字符串是平衡的#xff0c;当且仅当字符串中 01 连续子串的个数与 10 连续子…C Tokitsukaze and Balance String (hard)
题目描述
本题为《Tokitsukaze and Balance String (easy)》的困难版本两题的唯一区别在于 n n n 的范围。
一个字符串是平衡的当且仅当字符串中 01 连续子串的个数与 10 连续子串的个数相同。
定义字符串 s s s 的 v a l ( s ) val(s) val(s) 为这样的位置数量
若当前位置上的字符为 0将其反置后成为 1此时字符串 s s s 是平衡的若当前位置上的字符为 1将其反置后成为 0此时字符串 s s s 是平衡的。
现在 Tokitsukaze 有一个长度为 n n n仅由字符 0、1、? 构成的字符串 s s s。
其中? 可以替换成 0 或者 1。假设 ? 的个数为 p p p显然将每个 ? 都替换后总共可以得到 2 p 2^p 2p 个不同的 s s sTokitsukaze 想知道所有 2 p 2^p 2p 个不同的 s s s 对应的 v a l ( s ) val(s) val(s) 之和是多少。由于答案可能很大请将答案对 ( 1 0 9 7 ) (10^9 7) (1097) 取模后输出。
子串为从原字符串中连续的选择一段字符可以全选、可以不选得到的新字符串。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T ( 1 ≤ T ≤ 2 × 1 0 5 ) T(1\leq T\leq 2\times 10^5) T(1≤T≤2×105) 代表数据组数每组测试数据描述如下
第一行输入一个整数 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1\leq n\leq 2\times 10^5) n(1≤n≤2×105) 代表字符串长度。第二行输入一个长度为 n n n、仅由 0、1、? 构成的字符串 s s s。
除此之外保证单个测试文件的 n n n 之和不超过 2 × 1 0 5 2\times 10^5 2×105。
输出描述
对于每一组测试数据新起一行。输出一个整数代表全部 2 p 2^p 2p 个不同的 s s s 对应的 v a l ( s ) val(s) val(s) 之和。由于答案可能很大请将答案对 ( 1 0 9 7 ) (10^9 7) (1097) 取模后输出。
示例
输入
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 0 0平衡。由于在这个样例中只有一种不同的 s s s所以答案即为 v a l ( 1 ) 1 val(1) 1 val(1)1。对于第二组测试数据通过替换 ? 得到 4 4 4 种不同的 s s s分别为0001、0101、1001、1101。限制于篇幅我们在此仅详细展开讨论 0001 的情况。 翻转第一个字符得到 1001此时01 子串与 10 子串个数均为 1 1 1平衡。翻转第二个字符得到 0101此时01 子串个数为 2 2 210 子串个数为 1 1 1不平衡。翻转第三个字符得到 0011此时01 子串个数为 1 1 110 子串个数为 0 0 0不平衡。翻转第四个字符得到 0000此时01 子串与 10 子串个数均为 0 0 0平衡。 综上得到 v a l ( 0001 ) 2 val(0001) 2 val(0001)2。同理可得其他三个字符串。最终答案为 2 2 2 2 8 2 2 2 2 8 22228。
解题思路
核心性质
对于长度为 n n n 的 01 字符串 s s s当 s 1 s_1 s1 与 s n s_n sn 相等时“01” 与 “10” 子串数量相等。所以在 2 ≤ i ≤ n − 1 2\leq i\leq n - 1 2≤i≤n−1 范围内的 ? 可以随意填充不会影响 “01” 与 “10” 子串的数量。
定义变量
令 2 ≤ i ≤ n − 1 2\leq i\leq n - 1 2≤i≤n−1 中的 ? 个数为 c n t cnt cnt。
不考虑 s 1 s_1 s1 与 s n s_n sn 为 ? 的情况
情况一 s 1 s n s_1 s_n s1sn
当 s 1 s_1 s1 等于 s n s_n sn 时 2 ≤ i ≤ n − 1 2\leq i\leq n - 1 2≤i≤n−1 中的 s i s_i si 可以随意翻转。此时 v a l ( s ) n − 2 val(s)n - 2 val(s)n−2那么这部分对结果的贡献为 2 c n t ⋅ ( n − 2 ) 2^{cnt}\cdot(n - 2) 2cnt⋅(n−2)。
情况二 s 1 ≠ s n s_1 \neq s_n s1sn
当 s 1 s_1 s1 不等于 s n s_n sn 时必须翻转 s 1 s_1 s1 或者 s n s_n sn 才能使字符串满足条件即 v a l ( s ) 2 val(s)2 val(s)2这部分对结果的贡献为 2 c n t ⋅ 2 2^{cnt}\cdot2 2cnt⋅2。
考虑 s 1 s_1 s1 与 s n s_n sn 为 ? 的情况
当 s 1 s_1 s1 与 s n s_n sn 为 ? 时需要再进行分类讨论具体细节可参考后续代码实现。
优化点
由于 c n t cnt cnt 最多等于 n − 2 n - 2 n−2我们可以对 2 2 2 的幂进行预处理这样就不需要使用快速幂算法能将时间复杂度控制在 O ( n ) O(n) O(n)。
代码
#include bits/stdc.h
#define int long long
using namespace std;
const int mod 1e97;
int qpow(int a,int b)
{int res1;while(b){if(b1)resres*a%mod;aa*a%mod;b/2;}return res;
}
void solve()
{int n;cinn;string s;cins;s s;if(n1){if(s[1]!?)cout1\n;else cout2\n;}else{int cnt0;for(int i2;in-1;i)if(s[i]?)cnt;int ansqpow(2,cnt);if(s[1]s[n]){if(s[1]!?)ansans*(n-2)%mod;else ansans*2*n%mod;}else{if(s[1]? s[n]!?)ansans*n%mod;else if(s[1]!? s[n]?)ansans*n%mod;else ansans*2%mod;}coutans\n;}
}signed main()
{ int t;cint;while(t--)solve();return 0;
}A Tokitsukaze and Absolute Expectation
题目描述
Tokitsukaze 有一个由 n n n 个整数组成的序列 { a 1 , a 2 , … , a n } \{a_1, a_2, \ldots, a_n\} {a1,a2,…,an}其中第 i i i 个元素 a i a_i ai 的值在区间 [ l i , r i ] [l_i, r_i] [li,ri] 中独立地、等概率随机生成。
定义一个序列的价值为 v a l ( a ) ∑ i 2 n ∣ a i − 1 − a i ∣ val(a)\sum_{i 2}^{n}|a_{i - 1}-a_i| val(a)∑i2n∣ai−1−ai∣Tokitsukaze 想知道 v a l ( a ) val(a) val(a) 的期望。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T ( 1 ≤ T ≤ 1 0 5 ) T(1\leq T\leq 10^5) T(1≤T≤105) 代表数据组数每组测试数据描述如下
第一行输入一个整数 n ( 2 ≤ n ≤ 2 × 1 0 5 ) n(2\leq n\leq 2\times 10^5) n(2≤n≤2×105) 代表序列中元素的数量。此后 n n n 行第 i i i 行输入两个整数 l i , r i ( 1 ≤ l i ≤ r i ≤ 1 0 9 ) l_i, r_i(1\leq l_i\leq r_i\leq 10^9) li,ri(1≤li≤ri≤109) 代表第 i i i 个元素的取值范围。
除此之外保证单个测试文件的 n n n 之和不超过 2 × 1 0 5 2\times 10^5 2×105。
输出描述
可以证明答案可以表示为一个不可约分数 p q \frac{p}{q} qp为了避免精度问题请直接输出整数 ( p ⋅ q − 1 m o d M ) (p\cdot q^{-1}\bmod M) (p⋅q−1modM) 作为答案其中 M 1 0 9 7 M 10^9 7 M1097 q − 1 q^{-1} q−1 是满足 q × q − 1 ≡ 1 ( m o d M ) q\times q^{-1}\equiv 1(\bmod M) q×q−1≡1(modM) 的整数。
更具体地你需要找到一个整数 x ∈ [ 0 , 1 0 9 7 ) x\in[0, 10^9 7) x∈[0,1097) 满足 x × q x\times q x×q 对 1 0 9 7 10^9 7 1097 取模等于 p p p您可以查看样例解释得到更具体的说明。
示例
输入
2
3
1 2
1 2
1 3
4
4 8
2 3
4 10
4 7输出
333333337
214285726说明
对于第一组测试数据总共有 12 12 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
综上所述期望值为 0 1 2 2 1 2 1 2 3 1 0 1 12 4 3 \frac{0 12 21 21 23 10 1}{12}\frac{4}{3} 1201221212310134。我们能够找到 333333337 × 3 1000000011 333333337\times 3 1000000011 333333337×31000000011对 1 0 9 7 10^9 7 1097 取模后恰好等于分子 4 4 4所以 333333337 333333337 333333337 是需要输出的答案。
解题思路
链接https://ac.nowcoder.com/discuss/1454104 来源牛客网
核心转化
根据期望的线性性质可以转化成求 ∣ a i − a i − 1 ∣ |a_i - a_{i - 1}| ∣ai−ai−1∣ 的期望之和。那么问题就转化成了 ∣ a i − a i − 1 ∣ |a_i - a_{i - 1}| ∣ai−ai−1∣ 的期望。
分母计算
由于 a i − 1 a_{i - 1} ai−1 和 a i a_i ai 在区间 [ l i − 1 , r i − 1 ] [l_{i - 1}, r_{i - 1}] [li−1,ri−1] 和 [ l i , r i ] [l_i, r_i] [li,ri] 等概率随机所以分母为 ( r i − 1 − l i − 1 1 ) ⋅ ( r i − l i 1 ) (r_{i - 1}-l_{i - 1}1)\cdot(r_i - l_i 1) (ri−1−li−11)⋅(ri−li1)。
分子计算
分子是 a i − 1 a_{i - 1} ai−1 和 a i a_i ai 绝对值之差的所有情况之和。假设目前计算的是 [ l 1 , r 1 ] [l_1, r_1] [l1,r1] [ l 2 , r 2 ] [l_2, r_2] [l2,r2]。设 [ x , y ] [x, y] [x,y] 为这两个区间的交即 x max ( l 1 , l 2 ) x \max(l_1, l_2) xmax(l1,l2) y min ( r 1 , r 2 ) y\min(r_1, r_2) ymin(r1,r2)。然后通过下面 3 个部分进行计算 [ l 1 , x − 1 ] [l_1, x - 1] [l1,x−1] 与 [ l 2 , r 2 ] [l_2, r_2] [l2,r2] [ x , y ] [x, y] [x,y] 与 [ y 1 , r 2 ] [y 1, r_2] [y1,r2] [ x , y ] [x, y] [x,y] 与 [ x , y ] [x, y] [x,y]
情况 1 和情况 2 很好算因为它们区间都没有交。实现可以参考代码中的 cal2 函数。
情况 3 因为它是对称的可以推出一个式子。式子可以参考代码中的 cal3 函数。
复杂度分析
求完分子就做完了。由于每次需要求一下分母的逆元所以时间复杂度为 O ( n log m ) O(n\log m) O(nlogm) m 1 0 9 7 m 10^9 7 m1097。
代码
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int MAX5e510;
const int mod1e97;
ll qpow(ll a,ll b)
{ll res1;while(b0){if(b1) resres*a%mod;aa*a%mod;b1;}return res;
}
ll inv(ll x){return qpow(x,mod-2);}
const ll inv3inv(3);
ll cal3(int l,int r)
{int nr-l1;return 1LL*(n-1)*n%mod*(n1)%mod*inv3%mod;
}
ll cal2(int l1,int r1,int l2,int r2)
{if(l1r1||l2r2) return 0;ll res0;res1LL*(l2r2)*(r2-l21)/2%mod*(r1-l11);res-1LL*(l1r1)*(r1-l11)/2%mod*(r2-l21);res%mod;if(res0) return resmod;return res;
}
ll cal(int l1,int r1,int l2,int r2)
{if(l1l2){swap(l1,l2);swap(r1,r2);}int x,y;xmax(l1,l2);ymin(r1,r2);if(xy) return cal2(l1,r1,l2,r2);ll res0;rescal2(l1,x-1,l2,r2);rescal2(x,y,y1,max(r1,r2));rescal3(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(i1;in;i) scanf(%d%d,l[i],r[i]);ans0;for(i2;in;i){fzcal(l[i-1],r[i-1],l[i],r[i]);fm1LL*(r[i-1]-l[i-1]1)*(r[i]-l[i]1)%mod;ans(ansfz*inv(fm))%mod;}printf(%lld\n,ans);}return 0;
}F Tokitsukaze and Kth Problem (easy)
题目描述
本题与《Tokitsukaze and Kth Problem (hard)》共享题目背景可以视作困难版本的子问题。若能通过 hard在做简单修改后必能通过 easy。
Tokitsukaze 有一个由 n n n 个整数组成的序列 { a 1 , a 2 , … , a n } \{a_1, a_2, \ldots, a_n\} {a1,a2,…,an}。他定义一个二元组 ( i , j ) (i, j) (i,j) 满足 1 ≤ i j ≤ n 1\leq i j\leq n 1≤ij≤n并定义这个二元组对应的值 f ( i , j ) ( a i a j ) m o d p f(i,j)(a_i a_j)\bmod p f(i,j)(aiaj)modp。
他想知道对于全部不同的二元组 ( i , j ) (i, j) (i,j)全部值 f ( i , j ) f(i,j) f(i,j) 的前 k k k 大值分别为多少。如果不存在则输出 − 1 -1 −1 替代。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T ( 1 ≤ T ≤ 1 0 5 ) T(1\leq T\leq 10^5) T(1≤T≤105) 代表数据组数每组测试数据描述如下
第一行输入三个整数 n , p , k ( 2 ≤ n ≤ 2 × 1 0 5 ; 1 ≤ p ≤ 1 0 9 ; 1 ≤ k ≤ 2 × 1 0 5 ) n, p, k(2\leq n\leq 2\times 10^5; 1\leq p\leq 10^9; 1\leq k\leq 2\times 10^5) n,p,k(2≤n≤2×105;1≤p≤109;1≤k≤2×105) 代表序列中的元素数量、模数、询问大小。第二行输入 n n n 个整数 a 1 , a 2 , … , a n ( 0 ≤ a i ≤ 1 0 9 ) a_1, a_2, \ldots, a_n(0\leq a_i\leq 10^9) a1,a2,…,an(0≤ai≤109) 代表序列中的元素。
除此之外保证单个测试文件的 n n n 之和不超过 2 × 1 0 5 2\times 10^5 2×105 k k k 之和不超过 2 × 1 0 5 2\times 10^5 2×105。
输出描述
对于每一组测试数据新起一行。连续输出 k k k 个整数第 x x x 个整数表示 f ( i , j ) f(i,j) f(i,j) 的第 x x x 大值如果不存在第 x x x 大值输出 − 1 -1 −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 ) m o d 6 3 f(1,2)(1 2)\bmod 6 3 f(1,2)(12)mod63 f ( 1 , 3 ) ( 1 3 ) m o d 6 4 f(1,3)(1 3)\bmod 6 4 f(1,3)(13)mod64 f ( 1 , 4 ) ( 1 3 ) m o d 6 4 f(1,4)(1 3)\bmod 6 4 f(1,4)(13)mod64 f ( 2 , 3 ) ( 2 3 ) m o d 6 5 f(2,3)(2 3)\bmod 6 5 f(2,3)(23)mod65 f ( 2 , 4 ) ( 2 3 ) m o d 6 5 f(2,4)(2 3)\bmod 6 5 f(2,4)(23)mod65 f ( 3 , 4 ) ( 3 3 ) m o d 6 0 f(3,4)(3 3)\bmod 6 0 f(3,4)(33)mod60
排序后得到 { 0 , 3 , 4 , 4 , 5 , 5 } \{0, 3, 4, 4, 5, 5\} {0,3,4,4,5,5}。
解题思路
Solution 1二分答案
这类求第 k k k 大或者前 k k k 大类的题一般可以先考虑二分答案。
由于 easy 版本与序列顺序无关所以可以先对序列进行排序sort然后二分答案后用双指针数一下有多少对大于等于答案。求出第 k k k 大后大于答案的对可以暴力求出来剩下的再用答案填。
时间复杂度 O ( n log V k ) O(n\log V k) O(nlogVk)其中 V V V 为值域。
代码链接https://ac.nowcoder.com/acm/contest/view-submission?submissionId75401127
Solution 2堆
我们可以构造一种方案使得堆内必定存在当前的最大值。这样只要从堆中弹出 k k k 次就是前 k k k 大。
对于这道题可以枚举 a i a_i ai对于每个 a i a_i ai找到与它匹配能使 f ( i , j ) f(i,j) f(i,j) 最大的 a j a_j aj 放入堆中。每次从堆中弹出一个东西我们就把下一个与 a i a_i ai 匹配的 a j a_j aj 放入堆中如果有的话。
时间复杂度 O ( ( n k ) log n ) O((n k)\log n) O((nk)logn)
代码链接https://ac.nowcoder.com/acm/contest/view-submission?submissionId75401133
代码
#includebits/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;}vectorint 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(), greaterint());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 n n 块区域有 m m m 条双向道路连接不同区域。我方部队可在已占领区域随意移动但无法穿过敌方占领区域不过可通过在目标区域部署仲裁者使用“recall”技能将部队传送过去。
Tokitsukaze 有一个无敌地面部队部队初始在区域 0 0 0与敌方区域不相连她只能建造 k k k 个仲裁者想合理部署以尽可能多地占领敌方区域。要求输出最多能占领的敌方区域数量以及按占领顺序输出区域编号若有多种方案输出字典序最小的那种。
字典序规则数组 c c c 在字典序上小于数组 d d d 当且仅当以下任一情况成立 ∣ c ∣ ∣ d ∣ |c| |d| ∣c∣∣d∣ 并且对于所有 1 ≤ i ≤ ∣ c ∣ 1\leq i\leq |c| 1≤i≤∣c∣ 满足 c i d i c_i d_i cidi其中 ∣ c ∣ |c| ∣c∣ 表示数组 c c c 的长度在 c c c 和 d d d 不同的第一个位置上数组 c c c 的元素小于数组 d d d 中对应的元素。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数 T ( 1 ≤ T ≤ 2 × 1 0 5 ) T(1\leq T\leq 2\times 10^5) T(1≤T≤2×105) 代表数据组数每组测试数据描述如下
第一行输入三个整数 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 m m 行第 i i i 行输入两个整数 u i , v i ( 1 ≤ u i , v i ≤ n ; u i ≠ v i ) u_i, v_i(1\leq u_i, v_i\leq n; u_i\neq v_i) ui,vi(1≤ui,vi≤n;uivi) 代表第 i i i 条双向道路连接区域 u i u_i ui 和 v i v_i vi。保证不存在重复道路即每两块区域之间最多只有一条道路直接连接。
除此之外保证单个测试文件的 n n n 之和不超过 2 × 1 0 5 2\times 10^5 2×105 m m m 之和不超过 5 × 1 0 5 5\times 10^5 5×105。
输出描述
对于每一组测试数据输出两行
第一行输出一个整数 s ( 1 ≤ s ≤ n ) s(1\leq s\leq n) s(1≤s≤n) 代表 Tokitsukaze 最多占领的敌方区域数量。第二行输出 s s s 个互不相同的整数 c 1 , c 2 , … , c s ( 1 ≤ c i ≤ n ) c_1, c_2, \ldots, c_s(1\leq c_i\leq n) c1,c2,…,cs(1≤ci≤n)第 i i i 个整数 c i c_i ci 表示 Tokitsukaze 第 i i i 次占领的是区域 c i c_i ci。如果有多种方案输出字典序最小的那种。
示例
示例 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 1 个仲裁者部署在区域 1 1 1Tokitsukaze 将部队传送到区域 1 1 1 并占领接着让部队到达区域 2 2 2 并占领接着让部队从区域 2 2 2 回到区域 1 1 1然后前往区域 3 3 3 并占领最后让部队从区域 3 3 3 前往区域 4 4 4 并占领。所以占领的顺序是 { 1 , 2 , 3 , 4 } \{1, 2, 3, 4\} {1,2,3,4}。对于第二组测试数据将仅有 1 1 1 个仲裁者部署在区域 1 1 1Tokitsukaze 将部队传送到区域 1 1 1 并占领接着让部队到达区域 3 3 3 并占领接着让部队从区域 3 3 3 前往区域 4 4 4 并占领最后让部队从区域 4 4 4 前往区域 2 2 2 并占领。所以占领的顺序是 { 1 , 3 , 4 , 2 } \{1, 3, 4, 2\} {1,3,4,2}。对于第三组测试数据将 2 2 2 个仲裁者分别部署在区域 1 1 1 和区域 2 2 2。对于第四组测试数据将 1 1 1 个仲裁者部署在区域 1 1 1 或者区域 2 2 2 只能占领 2 2 2 个敌方区域而部署在区域 3 3 3、 4 4 4、 5 5 5 中任意一个区域均可以占领 3 3 3 个敌方区域并且部署在区域 3 3 3 可以使占领顺序的区域编号字典序最小占领的顺序为 { 3 , 4 , 5 } \{3, 4, 5\} {3,4,5}。对于第五组测试数据将 1 1 1 个仲裁者部署在区域 1 1 1、 2 2 2、 6 6 6 中任意一个区域可以占领 3 3 3 个敌方区域部署在区域 3 3 3、 4 4 4、 5 5 5 中任意一个区域也可以占领 3 3 3 个敌方区域。字典序最小的方案是部署在区域 1 1 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 k 多的连通块如果 k k k 大于等于连通块个数则可以全选。
考虑字典序最小
选择连通块时如果两个连通块的点数相同但只能选一个设连通块内编号最小的节点的编号为 m n mn mn在排序时优先选择 m n mn mn 小的那个连通块。统计连通块信息统计连通块内节点个数与最小编号可以建图后使用深度优先搜索dfs或者并查集实现。维护可访问节点为了使字典序最小用一个优先队列来维护所有可访问的节点每次弹出最小编号。部署仲裁者因为要求访问顺序字典序最小所以仲裁者肯定会被部署在一个连通块的编号最小的节点上即部署在连通块的 m n mn mn 节点。最初把所有选择的连通块的 m n mn mn 节点都放入优先队列。处理剩余仲裁者如果 k k k 大于连通块个数即 k k k 还有剩余可以把剩余的 k k k 服务于最小字典序。具体的如果当前 k 0 k 0 k0并且存在编号比队列弹出来的编号更小的节点那么直接在那个节点上部署是更优的。
复杂度分析
由于使用了优先队列每个节点最多会入队出队一次所以时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
代码链接
https://ac.nowcoder.com/acm/contest/view-submission?submissionId75401084
代码
#includebits/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.szb.sz)return a.mnb.mn;return a.szb.sz;
}
void add(int x,int y)
{ver[tot]y,Next[tot]head[x],head[x]tot;
}
int find(int x)
{if(xfa[x])return fa[x];return fa[x]find(fa[x]);
}
void merge(int x,int y)
{int t1find(x),t2find(y);if(t1!t2){fa[t2]t1;sz[t1]sz[t2];minn[t1]min(minn[t1],minn[t2]);}
}
signed main()
{int tt;cintt;while(tt--){int sum0;tot0,num0;int k;cinnmk;for(int i1;in;i){fa[i]i;sz[i]1;minn[i]i;}for(int i1;im;i){int x,y;cinxy;add(x,y);add(y,x);merge(x,y);}int cnt0;mapint,intmp;for(int i1;in;i){if(!mp[find(i)]){t[cnt].mnminn[find(i)];t[cnt].szsz[find(i)];mp[find(i)]1;}}sort(t1,tcnt1,cmp);priority_queueintq;mapint,intv;for(int i1;imin(k,cnt);i){sumt[i].sz;q.push(-t[i].mn);v[t[i].mn]1;}if(kcnt)k-cnt;elsek0;int mex1;while(q.size()){int u-q.top();q.pop();ans[num]u;for(int ihead[u];i;iNext[i]){int yver[i];if(!v[y]){q.push(-y);v[y]1;}}if(k){int p-q.top();if(p!u1){v[u1]1;q.push(-u-1);k--;}}}coutsumendl;for(int i1;isum;i){coutans[i] ;}coutendl;for(int i0;in;i){head[i]0;ans[i]0;t[i].sz0;t[i].mn0;}}return 0;
}
