【题解】Codeforces Round-840 Virtual

virtual了一场div1,发现题目有点清新,但是至今还是没有做$E$,因为$E$是个分块233

$A$

Leha喜欢各种各样奇怪的事。最近他喜欢上了函数$F(n,k)$。考虑所有集合$[1,2,\dots,n]$ 的有$k$个元素的子集。为这些子集找到其中最小的元素。$F(n,k)$ — 就是所有$k$个元素子集中的最小元素的数学期望。

但是仅仅这个函数还不够使他高兴。他想要在这上面做一些更有趣的事情。他的妈妈给他带来了两个数组$A$和$B$,每个都有$m$ 个整数。对于所有的$i,j$ ($1\leq i,j\leq m$)都有$a_i\geq b_j$。帮助Leha重新排列$A$数组来使得有最大的$\sum_{i=1}^m F(A_i’,B_i)$ ,$A$ 是重排后的数组。

$n\leq 10^5$

刚看到这题发现可以猜结论233……通过观察样例可以发现,应该是第二个序列中第$k$小的对应第一个序列中第$k$大的……

然后证明,考虑对$F(n,k)$进行变形(以下是$\mathsf{\color{black}{B}\color{red}{enq}}$的过程)

然后就是对于每一项,都应该让$k+1$尽量小,让$n+1$尽量大,就变成了一个贪心问题了233

$B$

给定你一些边,可能有重边。对于每个点给定一个$d_i$,如果为$1$表示这个点的度数为奇数,$0$表示这个点的度数为偶数,为$-1$表示这个点的度数没有限制。

你需要选出一些边(不一定联通),使得这些边构成的图符合要求。

$n\leq 3\cdot 10^5$

首先考虑如果没有-1并且奇度点数量为奇数,那么一定无解。因为整张图的度数之和一定是$2m$为偶数。

发现似乎最简单的方式是生成一棵树,于是决定生成树;并且根据上一句的性质,只要任意时刻保证度数为和偶数即可(不要求连通)。

然后分类讨论:0的点和1的点

  • 0的点。直接忽略,因为不产生影响;
  • 1的点。选择它的上行边、取反其父亲并且忽略这个点。原因还是度数和不变。

于是可知这是一个合理的方案……直观上很难感觉起来是对的,但是只要紧握住“度数和为偶数”这个性质不变即可。代码实现上也可圈可点,每个点的状态在没遍历完整棵子树时都是未知,是很鲜明的信竞特点……总之我不会,学到了。

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
//e.g.2: -1表示不能有一种方案,而0则表示我如果一条边都不选,依旧可以满足这个条件 
bool vis[MAXN] ;
bool ST(int u){
vis[u] = 1 ; int ret = base[u] ;
for (int k = head[u] ; k ; k = E[k].next){
if (vis[to(k)]) continue ;
if (ST(to(k)))
res[++ tot] = (k + 1) >> 1, ret ^= 1 ;
}
if (base[u] < 0) ret = 0 ;
return ret ;
}
int main(){
cin >> N >> M ;
for (i = 1 ; i <= N ; ++ i)
scanf("%d", &base[i]),
(base[i] < 0) ? mr1 = i : (mr2 ^= base[i]) ;
if (!mr1 && mr2)
return puts("-1"), 0 ;
for (i = 1 ; i <= M ; ++ i)
scanf("%d%d", &A, &B), Add(A, B) ;
ST(mr1 ? mr1 : 1) ;
cout << tot << endl ;
sort(res + 1, res + tot + 1) ;
for (i = 1 ; i <= tot ; ++ i) printf("%d ", res[i]) ;
}

$C$

给定$n(1≤n≤300)$个数,求问有多少种排列方案使得任意两个相邻的数之积都不是完全平方数。由于方案数可能很大,输出方案数$\bmod 10^9+7$的值。

考虑相邻两个数之积是完全平方数的充要条件,当且仅当将两个数的所有质因子次数$\bmod ~2$ 后,两个数相同时,其乘积才会为完全平方数。

那么也就是说,这种性质可以传递,即$a\cdot b$为完全平方数,$b\cdot c$为完全平方数,那么$a\cdot c$也是。于是可以对所有的数暴力分组,每个组找一个代表元来记录。设每一组中有$cnt_i$个数,前$i$个组的$cnt$前缀和为$s_i$。

那么问题转化成了给定$n$个数,同一组的元素不能放在一起,求排列数。那么就是$f_{i,j}$表示前$i$个组,有$j$对相邻元素的乘积为完全平方数的排列数,转移时考虑,枚举当前这一组被分成了$k$块,插板法插出来的方案数为$\binom{cnt_i-1}{k-1}$,并且会多加上$cnt_i-k$个不合法的位置;然后考虑这$k$块插到了上一个状态中,$j$对不合法相邻的数中,$o$对不合法的数之间(即有$o$对数被拆开了),那么就会少$o$对非法数对。然后就是$\binom{j}{o}$。考虑剩下的了$k-o$块,这$k-o$块可以放到$s_i-j+1$个正常的空隙里面,于是再乘一个$\binom{s_i-j+1}{k-o}$

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
inline ll expow(ll d, ll z){
ll res = 1 ;
if (d == 1) return 1 ;
while (z){
if (z & 1) (res *= d) %= Mod ;
( d *= d ) %= Mod, z >>= 1 ;
}
return res ;
}
int main(){
cin >> N, dp[0][0] = 1 ;
for (i = 1 ; i <= N ; ++ i){
cin >> base[i] ; bool mk = 0 ;
for (j = 1 ; j <= cnt ; ++ j){
ll p = trunc(sqrt(base[i] * grp[j])) ;
if (p * p == base[i] * grp[j]){++ tm[j], mk = 1 ; break ; }
}
if (!mk) grp[++ cnt] = base[i], tm[cnt] = 1 ;
}
for (Cm[0][0] = 1, i = 1 ; i <= N ; ++ i) Cm[i][0] = 1 ;
for (Frac[0] = 1, i = 1 ; i <= N ; ++ i) Frac[i] = Frac[i - 1] * i % Mod ;
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 (i = 1 ; i <= cnt ; tot += tm[i], ++ i)
for (j = 0 ; j <= tot ; ++ j)
for (k = 1 ; k <= tm[i] ; ++ k)
for (l = 0, t = tm[i] - k + j ; l <= j ; ++ l, t --)
if(t >= 0 && t < N)
(dp[i][t] +=
Frac[tm[i]] * Cm[tm[i] - 1][k - 1] % Mod
* Cm[j][l] % Mod * Cm[tot - j + 1][k - l] % Mod
* dp[i - 1][j] % Mod) %= Mod ;
cout << dp[cnt][0] << endl ; return 0 ;
}

$D$

这个D曾经单独写过:Link

233反正就是乱搞就对了