【题解】Codeforces Round-814 Virtual

一场cn round,然后每次cn round的最后一题都会很奇怪……

⑧说了,计数是不可能会的,这辈子都不可能了QAQ

$\Omega $

$\rm virtual$了一场……说实话这种div2 only的场次最后一题就经常比较毒……

老规矩,前面几题用来水字数

$A$

给出一个长度为$N$的非负整数序列$a_i$与长度为$K$的正整数序列$b_i$,满足$a_i$中刚好有$K$个$0$,且任一正整数在序列$a$和序列$b$中的出现次数的和不会超过$1$。

现在试判断是否存在一种方法,使得用$b_i$中的元素替换$a_i$中的$0$得到的序列不是递增序列。

sb一眼题,显然如果递减放进去还是递增就无解。

1
2
3
4
5
6
7
8
9
inline bool cmp(int a, int b){ return a > b ;}
int main(){
cin >> N >> K ; int j = 1 ;
for (i = 1 ; i <= N ; ++ i) cin >> base[i] ;
for (i = 1 ; i <= K ; ++ i) cin >> t[i] ; sort(t + 1, t + K + 1, cmp) ;
for (i = 1 ; i <= N ; ++ i) if (!base[i]) base[i] = t[j ++] ;
for (i = 1 ; i < N ; ++ i) if (base[i] > base[i + 1]) return puts("Yes"), 0 ;
return puts("No"), 0 ;
}

$B$

给定两个长度为$n$的不相同序列$a$和$b$,这两个序列至少有一个位置不同

现在需要构造一个长度为$n$的排列$p$,使得$p$与$a$只有一个地方不同,且$p$与$b$也只有一个地方不同

一眼就可以看出最多有两个位置不同,否则一定不合法。考虑分类讨论,如果只有一个位置不同那就放上那个没出现过的数字;如果有两个位置不同,那就考虑是$A$中第一个位置放多了还是第二个位置放多了,放上$B$的就完了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	for (i = 1 ; i <= N ; ++ i) scanf("%d", &A[i]), Ma[A[i]] ++ ;
for (i = 1 ; i <= N ; ++ i) scanf("%d", &B[i]), Mb[B[i]] ++ ;
for (i = 1 ; i <= N ; ++ i) if (A[i] != B[i]) pos[++ cnt] = i ;
if (cnt == 1){
for (i = 1 ; i <= N ; ++ i)
if (!Ma.count(i) && !Mb.count(i)) { A[pos[1]] = i ; break ; }
for (i = 1 ; i <= N ; ++ i) cout << A[i] << " " ; return 0 ;
}
if (Ma[A[pos[1]]] > 1 && !Ma[B[pos[1]]]){
A[pos[1]] = B[pos[1]] ;
for (i = 1 ; i <= N ; ++ i) cout << A[i] << " " ;
}
else {
A[pos[2]] = B[pos[2]] ;
for (i = 1 ; i <= N ; ++ i) cout << A[i] << " " ;
}
}

本来觉得是道构造题,后来发现是道细节模拟题。。。

$C$

给你一个由小写字母构成的字符串.
有$q$个询问,每个询问给出数字$m$和小写字母$c$,你可以任意地修改字符串中的$m$个字符,求最多能够使字符串中含有多少个连续相同的字母$c$.
每个询问各自独立.
$|\rm S|\leq 1,500$

其实感觉复杂度一点也不对……比如我觉得这题可以做到$5e4$以上……

考虑弱化版(原版)的解法,大概就是用$f_{i,j}$表示前$i$个字符用了$k$次机会最长的连续段有多长。然后就可以直接$O(26n^2)$给预处理出来,每次询问回答一下即可。

但是我们发现这玩意儿复杂度一点也不平衡,因为预处理贼慢但是回答贼快。于是考虑有哪些性质没用。我们考虑预处理出原串中对于一个字符$c$,最近的两个$c$之间的位置来,然后如果要修改就显然先修改跨度小的$c_i$和$c_{i+1}$中间的部分,因为这样肯定不会更劣。同时只有把中间的非$c$区域占满才能使之连通,故每次对于一个给定的$k$,二分查找一下可以占满的区间,剩下的随便铺,对于这些占满的区间提前预处理出贡献的前缀和就完了。复杂度大概是$q\log n+26n$

然而升级版只是口胡,什么时候闲下来再写吧qwq

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (i = 0 ; i < 26 ; ++ i)
for (j = 1 ; j <= N ; ++ j)
if ((int)S[j] == 'a' + i) dp[i][j][0] = dp[i][j - 1][0] + 1 ;
for (i = 0 ; i < 26 ; ++ i){
for (j = 1 ; j <= N ; ++ j)
for (k = 1 ; k <= N ; ++ k){
if ((int)S[j] - 'a' == i) dp[i][j][k] = dp[i][j - 1][k] + 1 ;
else dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k - 1] + 1) ;
ans[i][k] = max(ans[i][k], dp[i][j][k]) ;
}
}
cin >> T ;
while (T --){
scanf("%d %c", &k, &In) ;
cout << ans[(int)In - 'a'][k] << endl ;
}

$D$

有$n$个圆,将其分为两组。每组中,只有奇数个圆覆盖的区域的才会算入面积,求可能的最大面积。

首先考虑贪心。大概就是说原本的覆盖一定可以看做一团一团独立的子问题。将圆按照面积大小排序,之后考虑选每一堆最大的放到第一堆,然后把与之原本冲突的放到第二堆。这样可以发现最终减去的部分面积变成了之前产生贡献的部分面积……然而这不重要,重要的是这样保证了每次选的一定都是面积最大的圆的集合。

1
2
3
4
5
6
7
8
9
10
inline bool Comp(C A, C B){ return A.r > B.r ; }
void solve2(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j])) ++ mark[j] ;
for (i = 1 ; i <= N ; ++ i)
if (!mark[i] || (mark[i] & 1)) Ans += get_S(base[i]) ; else Ans -= get_S(base[i]) ;
printf("%.8lf", Ans) ;
}

然而这个贪心似乎不好想,于是考虑一种精妙的$\rm dp$其实更不好想。考虑按照圆从大到小枚举顺次连边,最后连出来的会是一个森林状物。然后对于这个东西, 定义$dp[u][0/1][0/1]$表示以点$u$为根的子树里面,除$u$之外分成两堆之后,两堆分别的高度为偶数/奇数时的最优值。这东西就可以直接分类讨论求和+转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
inline double dist(C A, C B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)) ;
}
inline double get_S(C A){ return Pi * A.r * A.r ; }
inline bool check_in(C A, C B){ return A.r + B.r > dist(A, B) ; }
namespace DP{
#define to(k) E[k].to
struct Edge{
int next, to ;
}E[MAXN << 1] ;
int head[MAXN], cnt ;
inline void Add(int u, int v){
E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
E[++ cnt].to = u, E[cnt].next = head[v], head[v] = cnt ;
}
void do_dp(int u, int faa){
long long f[2][2] ; memset(f, 0, sizeof(f)) ;
for (int k = head[u] ; k ; k = E[k].next){
if (to(k) == faa) continue ;
do_dp(to(k), u) ;
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
f[ii][jj] += dp[to(k)][ii][jj] ;
}
for (int ii = 0 ; ii <= 1 ; ++ ii)
for (int jj = 0 ; jj <= 1 ; ++ jj)
dp[u][ii][jj] = max(
f[ii ^ 1][jj] + (1ll * (ii ? -1 : 1) * base[u].r * base[u].r),
f[ii][jj ^ 1] + (1ll * (jj ? -1 : 1) * base[u].r * base[u].r)) ;
}
inline bool Comp(C A, C B){ return A.r > B.r ; }
void solve1(){
sort(base + 1, base + N + 1, Comp) ;
for (i = 1 ; i <= N ; ++ i)
for(j = i + 1 ; j <= N ; ++ j)
if (check_in(base[i], base[j]))
if (!fa[j] || base[fa[j]].r > base[i].r) fa[j] = i ;
for (i = 1 ; i <= N ; ++ i) if (fa[i]) Add(i, fa[i]) ;
for (i = 1 ; i <= N ; ++ i) if (!fa[i]) do_dp(i, 0), Ans += dp[i][0][0] ;
printf("%.8lf", Ans * Pi) ;
}
}

$E$

给出$n$个点和每个点的度让你构造出一张无向图满足以下两条性质:

  • $1.$点1到点$i$仅有唯一一条最短路

  • $2.$点$1$到点$i$的最短路长度大于等于点$1$到点$i-1$的最短路长度

求能构成满足条件的无向图的个数 $n\leq 50, 2\leq degree_i\leq 3$

这种计数题会是不可能会的,这辈子都不可能会了qaq

考虑一个$idea$,因为这张图无权,所以最短路一定会是$\it bfs$的分层。那么对于一个$i$来讲,他的要么和$i-1$在同一层,要么就在$i-1$的下一层。

那么考虑记$f_{i,j}$表示前$i$个点中有$j$个和$i$在同一层的方案数。那么考虑这东西的转移跟上一层中点的度数有关,也就是需要记$dp_{k,c_1,c_2}$表示当前层有$k$个点,上一层度数为$2$的点有$c_1$个,度数为$3$的点有$c_2$个这一子状态的方案数。那么有如下:

其中$N_i$表示$\boldsymbol{i-}$项链数,也就是长度为$i$、元素各异、镜像对称的单环的数量,计算方式如下:

对于第二个转移,就是考虑向上一层插入一个点使其成为度数为$3$的点。考虑因为度数为$3$且题目要求“有位移最短路”,所以同一层中只有可能是简单的平边相连。所以就是考虑枚举原来的点里面可以与新加入的点组成项链的方案数。注意这里项链数必须$>2$原因是题目中强调了不能有两个点之间连$>1$条边。

对于第三个转移,考虑插入一个点使其度数为$2$,这一步转移即考虑$j-1$个点中选择一个可能变成$2$度的点和新加近来这个点相连有$j-1$种方案,相连之后两个点度数都变为$2$;同时考虑另一种可能性,就是这一个点和一个可能变成$3$度的点相连,那么原来的二度点变为三度点,新加进来的变成二度点。

对于第四个转移,考虑这一层最后一个加进来的节点,要么和上一层中一个可能变成$2$度的点相连要么和可能变成$3$度的点相连。

然后最后的答案就是枚举最后一层的点数

其中$c_1$和$c_2$表示枚举到现在有多少个$d=2$和$d=3$的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <iostream>

#define MAXN 105
#define ll long long
#define Mod 1000000007

using namespace std ;
int N, clr1, clr2, base[MAXN] ;
int i, j, k, l ; ll dp[MAXN][MAXN] ;
ll Ans, A[MAXN], f[MAXN][MAXN][MAXN], Cm[MAXN][MAXN] ;

int main(){
cin >> N ; Cm[0][0] = 1 ;
for (i = 1 ; i <= N ; ++ i) Cm[i][0] = 1 ;
for (i = 1 ; i <= N ; ++ i)
for(j = 1 ; j <= i ; ++ j)
Cm[i][j] = (Cm[i - 1][j] + Cm[i - 1][j - 1]) % Mod ;
for ( A[1] = A[0] = 0, A[2] = A[3] = 1, i = 4 ; i <= N ; ++ i) A[i] = A[i - 1] * (i - 1) % Mod ;
f[0][0][0] = 1 ; //Calculate g
for (j = 0; j <= N ; ++ j)
for (k = 0 ; k <= N - j ; ++ k)
if (!j && k)
for (l = 2 ; l < k ; ++ l)
(f[0][j][k] += f[0][j][k - l - 1] * Cm[k - 1][l] % Mod * A[l + 1] % Mod) %= Mod ;
else {
if (j >= 2) (f[0][j][k] += f[0][j - 2][k] * (j - 1) % Mod) %= Mod ;
if (k) (f[0][j][k] += f[0][j][k - 1] * k % Mod) %= Mod ;
}
for (i = 1 ; i <= N ; ++ i)
for (j = 0 ; j <= N - i ; ++ j)
for (k = 0 ; k <= N - i - j ; ++ k){
if (j) (f[i][j][k] += f[i - 1][j - 1][k] * j % Mod) %= Mod ;
if (k) (f[i][j][k] += f[i - 1][j + 1][k - 1] * k % Mod) %= Mod ;
// cout << f[i][j][k] << endl ;
}
//Calculate dp
for (i = 1 ; i <= N ; ++ i) cin >> base[i] ; dp[base[1] + 1][base[1]] = 1 ;
for (i = base[1] + 2 ; i <= N ; ++ i)
for (j = 1 ; j <= i - base[1] - 1 ; ++ j)
for (clr1 = clr2 = 0, k = 1 ; k <= i - j ; ++ k){
if (base[i - j - k + 1] <= 2) ++ clr1 ; else ++ clr2 ;
(dp[i][j] += (dp[i - j][k] * f[j][clr1][clr2] % Mod)) %= Mod ;
}
for (clr1 = clr2 = 0, i = 1 ; i < N ; ++ i){
if (base[N - i + 1] == 2) ++ clr1 ; else ++ clr2 ;
(Ans += (dp[N][i] * f[0][clr1][clr2]) % Mod) %= Mod ;
}
cout << Ans << endl ; return 0 ;
}