2020牛客暑期多校训练营（第三场）题解
文章目录
- A. Clam ans Fish
- B. Classical String Problem
- C. Operation Love
- D. Points Construction Problem
- E. Two Matchings
- F. Fraction Construction
- G. Operating on the graph
- H. Sort the Strings Revision
- I. Sorting the Array
- J. Operating on the Tree
- L. Problem L is the Only Lovely Problem
A. Clam ans Fish
有 n n n 个鱼塘，每个鱼塘是四种鱼塘中的一种，这四种分别是啥都没、有鱼饵、有鱼、都有，每次可以选择四种操作之一：不动、拿鱼、拿鱼饵、用鱼饵钓鱼（可以在没鱼的鱼塘里钓），求最后的最大鱼数。
有饵没鱼的肯定拿饵，有鱼没饵的肯定拿鱼，啥都没有的肯定尝试钓鱼，都有的肯定拿鱼，因为不知道鱼饵后面能不能有机会钓。
然后后面还剩了 k k k 个饵，可以考虑只要前 k 2 \dfrac k 2 2k 个，在遇到后面的 k 2 \dfrac k 2 2k 个饵时，由于是多余的，就不拿了，操作换成钓鱼。
代码如下：
#include B. Classical String Problem
给出一个字符串，有三种操作，1、将前 k k k 个字符移到后面，2、将后 k k k 个字符移到前面，3、询问第 k k k 个字符是谁。
前两个操作其实可以看成字符串的整体左移和右移，所以记录一下字符串的开头在哪里可以搞询问了。
代码如下：
#include C. Operation Love
给出一个手掌，问这是右手还是左手。
我的做法是先找到手掌底部的两个点，只有他们的距离是 9 9 9，很好找，分别记为第 i i i 和 i + 1 i+1 i+1 个点。
然后再判断一下第 i − 1 i-1 i−1 个点与 i i i 的距离，看看是 6 6 6 还是 8 8 8，这样能判断大拇指位置。
然后再用叉积判一下点是顺时针给的还是逆时针给的即可。
代码如下：
#include D. Points Construction Problem
要求将平面上 n n n 个点染成黑色，其他都是白色，存在恰好有 m m m 对点 (X,Y)，满足点 X , Y X,Y X,Y 相邻，且一个为黑一个为白。
考虑将这 n n n 个点一行放 n \sqrt n n 个堆积起来，此时的答案是最小的。
然后逐渐将最上面那行的最右边那个放到最下面那行的最右边，每次移动一个可以使答案 + 2 +2 +2，直到所有点都在一条直线上并且都相邻。
然后再从左到右考虑第 i i i 个点，将第 i i i ~ n n n 个点整体右移一位，即让 i i i 和 i − 1 i-1 i−1 中间空出一位，这样又可以使答案 + 2 +2 +2。
在做上面这个过程时，当答案等于 m m m 时，输出即可。
代码如下：
#include E. Two Matchings
称 1 1 1 ~ n n n 的一个排列 p p p 是“配对的”当且仅当 ∀ i , p i ≠ i , p p i = i \forall i,p_i\neq i,p_{p_i}=i ∀i,pi=i,ppi=i，现在有一个长度为 n n n 的序列 A A A，定义一个排列的代价为 ∑ i = 1 n ∣ a i − a p i ∣ / 2 \sum_{i=1}^n |a_i-a_{p_i}|/2 ∑i=1n∣ai−api∣/2，现在要找两个完全不同的“配对的”排列使得总代价最小。
“配对的”排列其实就是将 1 1 1 ~ n n n 这个排列每一位都与其他位进行交换，且每一位仅交换一次，如 3 , 4 , 1 , 2 3,4,1,2 3,4,1,2 就是一个“配对的”排列， 1 1 1 与 3 3 3 交换了， 2 2 2 与 4 4 4 交换了，下面称交换的两位是相互配对的。
那么一个排列的代价其实就是将每个配对的 A i A_i Ai 之差加起来，那么显然最小的一个方案就是将 A A A 进行排序，然后相邻的两个进行配对。
考虑第二小的方案，由于两个方案不能有任何一个配对相同，所以此时只能考虑相邻的 4 4 4 个进行相互配对和相邻 6 6 6 个进行相互配对。相邻 8 8 8 个以上的配对就不需要考虑了，因为他们拆成 4 4 4 个和 6 6 6 个的一定不会更劣，然后做一次dp即可。
相邻 4 4 4 个的最优配对方案为 ( 1 , 3 ) , ( 2 , 4 ) (1,3),(2,4) (1,3),(2,4)，相邻 6 6 6 个的最优配对方案为 ( 1 , 3 ) , ( 2 , 5 ) , ( 4 , 6 ) (1,3),(2,5),(4,6) (1,3),(2,5),(4,6)。
代码如下：
#include F. Fraction Construction
找两个分数 c d , e f \dfrac c d,\dfrac e f dc,fe，满足 c d − e f = a b \dfrac c d-\dfrac e f=\dfrac a b dc−fe=ba，且 d , f < b d,fd,f<b。
先将 a , b a,b a,b 化简为 a ′ , b ′ a',b' a′,b′，然后转化一下上面的柿子：
c d − e f = a ′ b ′ c f − e d d f = a ′ b ′ \frac c d-\frac e f=\frac {a'} {b'}\\ \dfrac {cf-ed} {df}=\frac {a'} {b'} dc−fe=b′a′dfcf−ed=b′a′
下面不妨令 a ′ = c f − e d , b ′ = d f a'=cf-ed,b'=df a′=cf−ed,b′=df。
假如 b ′ < b b'b′<b，那么存在一组解 c = a ′ + b ′ , d = b ′ , f = 1 , e = 1 c=a'+b',d=b',f=1,e=1 c=a′+b′,d=b′,f=1,e=1。
如果 b ′ = b b'=b b′=b，那么 d d d 就不能等于 b ′ b' b′ 了，因为 d d d 要小于 b b b。
考虑枚举 d , f d,f d,f，因为要让 c f − e d = a ′ cf-ed=a' cf−ed=a′ 有解，所以 gcd ( d , f ) ∣ a ′ \gcd(d,f)|a' gcd(d,f)∣a′，而 gcd ( a ′ , b ′ ) = 1 \gcd(a',b')=1 gcd(a′,b′)=1，所以 gcd ( d , f ) = 1 \gcd(d,f)=1 gcd(d,f)=1。
枚举出 d , f d,f d,f 后，直接扩欧求 c , e c,e c,e 即可。
代码如下：
#include G. Operating on the graph
给出一张图，一开始第 i i i 个点属于第 i i i 个团队，有 q q q 次操作，每次选择一个团队 i i i，将与其相邻的团队都合并到 i i i 团队来，问最后每个人属于哪个团队。
显然每条边只能被扩展一次，用 set \text{set} set 啥的维护一下每次暴力拓展就好了。
需要注意一下空间，代码如下：
#include H. Sort the Strings Revision
你有 n + 1 n+1 n+1 个长度为 n n n 的字符串， s 0 s_0 s0 的第 i i i 位是数字 i m o d 10 i\bmod 10 imod10， s i ( i > 0 ) s_i(i>0) si(i>0) 由 s i − 1 s_{i-1} si−1 将第 p i − 1 p_{i-1} pi−1 位的数字换成 d i − 1 d_{i-1} di−1 得到，保证 p p p 是 0 0 0 ~ p − 1 p-1 p−1 的一个排列，现在要你将 s 0 s_0 s0 ~ s n s_n sn 进行排序，输出它们的排名。
由于 p p p 是 0 0 0 ~ p − 1 p-1 p−1 的一个排列，说明每个位置只会被替换一次，而由于是按字典序排序，所以在前面的位会比后面的位影响要大，当更改了 0 0 0 位置后，就可以确定更改前的串与更改后的串的大小关系，所以可以考虑分治，每次处理区间内最前面的位置。
求区间最值可以用笛卡尔树，代码如下：
#include I. Sorting the Array
有一个长度为 n n n 的序列 b b b，定义 f ( n , b , m ) f(n,b,m) f(n,b,m) 表示进行
for i=1 to n-m+1 do sort(b[i]~b[i+m-1])后的序列，现在给出 r e t ret ret 序列以及 k k k，要你求出满足 f ( n , b , m ) = r e t f(n,b,m)=ret f(n,b,m)=ret 的 b b b 中字典序第 k k k 小的 b b b 是什么。
有一个较容易发现的性质，对于一个 i i i，假如存在 j ∈ [ 1 , i ) j\in[1,i) j∈[1,i) 满足 r e t [ j ] > r e t [ i ] ret[j]>ret[i] ret[j]>ret[i]，那么 b [ i + m − 1 ] b[i+m-1] b[i+m−1] 一定等于 r e t [ i ] ret[i] ret[i]。
证明的话，考虑换个角度来看上面那个每m位sort一次操作——这相当于在维护一个大小为 m − 1 m-1 m−1 的集合，然后从左边第 m m m 位开始，每次加入一个数进集合，然后将最小的数丢掉放到最左边，那么 r e t [ i ] ret[i] ret[i] 就是加入了 b [ i + m − 1 ] b[i+m-1] b[i+m−1] 之后丢掉的数。
对于一个 i i i，假如存在 j ∈ [ 1 , i ) j\in[1,i) j∈[1,i) 满足 r e t [ j ] > r e t [ i ] ret[j]>ret[i] ret[j]>ret[i]，那么说明集合在经过第 j j j 位后，里面所有的数都大于 r e t [ j ] ret[j] ret[j] 了（否则 r e t [ j ] ret[j] ret[j] 不可能被踢出来），而 r e t [ i ] < r e t [ j ] ret[i]
我们发现，这些固定下来的位，是不会对集合产生任何贡献的，所以把他们删掉再求解也是可以的，假设删掉了 n − c n-c n−c 个数，那么现在的问题变成了求第 k k k 小的满足 f ( c , b , m ) = r e t f(c,b,m)=ret f(c,b,m)=ret 的 b b b。
可以发现，删掉固定的位后，剩下的 r e t ret ret 一定是一个严格上升序列，由于我们只关心其相对大小，所以下面认为 r e t [ i ] = i ret[i]=i ret[i]=i。
先考虑怎么求 b b b 的总方案数，由于 r e t [ i ] = i ret[i]=i ret[i]=i，所以sort完 1 1 1 ~ i + m − 1 i+m-1 i+m−1 后一定考虑过 i i i，即 i i i 只能放在 1 1 1 ~ i + m − 1 i+m-1 i+m−1 之间，前面已经放过 i − 1 i-1 i−1 个数了，剩下就只剩 m i n ( m , c − i ) min(m,c-i) min(m,c−i) 个位置可以考虑，总方案数为 ∏ i = 1 c min ( m , c − i ) \prod_{i=1}^c \min(m,c-i) ∏i=1cmin(m,c−i)。
于是可以考虑求出一个最大的 v v v 满足 ∏ i = v c min ( m , c − i ) ≥ k \prod_{i=v}^c \min(m,c-i)\geq k ∏i=vcmin(m,c−i)≥k，那么对于 i < v i
容易发现剩下的 c − v + 1 c-v+1 c−v+1 位不会超过 log k \log k logk 位，于是可以暴力考虑每一位填什么，然后统计一下后面的方案数与 k k k 的大小关系即可，时间复杂度大概是 O ( n log 3 k ) O(n\log^3k) O(nlog3k)，有一个地方可以优化，即枚举每一位填什么时，从一个数换成另一个数，可以 O ( 1 ) O(1) O(1) 计算出方案数，那么时间复杂度就优化到了 O ( n log 2 k ) O(n\log^2k) O(nlog2k)（大概）。
具体看代码吧：
#include J. Operating on the Tree
给出一棵树，以它为G题中的图，对于一个 1 1 1 ~ n n n 的排列，定义 f ( p ) f(p) f(p) 为将这个排列作为G题的操作序列，有多少个数 i i i 满足操作到 p i p_i pi 时，团队 p i p_i pi 不为空，求 ∑ p ∈ S f ( p ) \sum_{p\in S} f(p) ∑p∈Sf(p)， S S S 是 1 1 1 ~ n n n 的全排列。
做法膜的这位大佬，由于自己和大佬码风类似所以膜起来很舒适qwq。
注意到每个数只会被操作一次，是个重要性质。
假如一个点在操作时不为空，那么称其为好点，否则为坏点，那么有这样的限制：
- 每个坏点肯定和一个比他大的好点相邻
- 任意两个好点不相邻
这里的A比B大是指，在排列 p p p 中 A A A 在 B B B 的前面。
这样我们就可以 dp \text{dp} dp 了，令 f [ i ] [ 0 / 1 / 2 ] [ j ] f[i][0/1/2][j] f[i][0/1/2][j] 表示，第 i i i 个点是 好点/已有相邻的比 i i i 大的好点的坏点/未有相邻的比 i i i 大的好点的坏点，并且子树内有 j j j 个点比 i i i 大的方案数， g [ i ] [ 0 / 1 / 2 ] [ j ] g[i][0/1/2][j] g[i][0/1/2][j] 则表示这些方案的总贡献。
转移的时候讨论一下 自己是 0 / 1 / 2 × 0/1/2~\times 0/1/2 × 儿子是 0 / 1 / 2 0/1/2 0/1/2，一共 9 9 9 种情况即可，这个不难想。
转移时还要注意的就是求方案数上的细节，具体看代码：
#include L. Problem L is the Only Lovely Problem
判断一个字符串开头是否为 lovely，不在乎大小写。
签到题，代码如下：
#include 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！