https://atcoder.jp/contests/abc253/tasks

Ex - We Love Forest

一个n点0边的图 G

给序列u[1..m], v[1..m]

做k次操作

每次1~m中等概率选i, 连接ui,vi, (允许重边, 没有自环

对于k = 1…n-1

计算 图是森林的概率

mod 998244353

n 14

m 500

2s

1024mb

我的思路

n 这么小

问题其实就是说k次选择没有出现重边, 也没有产生环的概率

如果只是重边 还很好做, 但是问题是如何判断没有环的概率

然后说 有没有把并查集状态 全部表示出来, 但这样看似乎n又很大

f(x) = x个点的并查集状态的数

考虑和其中最小点1在一起的点数

f(x) = sum binom(x,i) f(x-1-i), i = 0..x-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

n = 15
a = [0 for i in range(n)]
a[0] = 1

fac = [1 for i in range(n)]
for i in range(1,n):
    fac[i] = fac[i-1]*i
def binom(n,m):
    return fac[n]//fac[n-m]//fac[m]

for i in range(1,n):
    for j in range(i):
        a[i] += binom(i-1,j) * a[i-1-j]
    print(i,a[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14

1 1
2 2
3 5
4 15
5 52
6 203
7 877
8 4140
9 21147
10 115975
11 678570
12 4213597
13 27644437
14 190899322

状态数量接受不了, 更别提转移代价了

但是如果 容斥看 指定一个mask中的点构成树, 其余任意的话, 能否容斥

并想不出 容斥的单独属性

除非是 每个mask中是森林, 但是既然都是森林了不如直接算出答案

如果每个mask是树, 所有的并交没有意义?

https://atcoder.jp/contests/abc252/tasks

G - Pre-Order

给一个n点多叉树的前序遍历结果, 问有多少个树满足, mod 998244353

其中子节点多个时, 按子节点数字从小到大遍历

范围

n 500

2s

1024mb

我的思路

当成父子结构时候, 顺序显然

所以感觉主要在兄弟结构

也就是现在 f(序列a)的方案数

f(a) = a[0]为根, a[1]为第一个树的根, a[i]为第二个树的根

f(a) = g(a[1…])

g(a) = sum f(a[0…i-1]) * g(a[i..])

其中a[0] < a[i]

整合一下 g(a) = sum g(a[1…i-1]) * g(a[i..]), a[0] < a[i]

似乎就没了

https://atcoder.jp/contests/abc251/tasks

G - Intersection of Polygons

N点 凸convex多边形

按照逆向时针给点

考虑 m个 n点凸多边形

第i个,是通过把原来的平移(ui,vi)

q个询问, 问(ai,bi) 是否被所有m个凸多边形覆盖

范围

n 50

m 2e5

q 2e5

x,y,u,v,a,b [-1e8,1e8]

2s

1024mb

我的思路

两个方向

1. 把m个的交算出来, 然后查询,

2. 对m个偏移量算偏移量的凸包, 每个Q去找 最差的叠加?

因为一个凸包 沿着(ui,vi) 移动后的交

= 这个凸包与 (ui/2,vi/2), (ui,vi) 的交

因此无限划分

所以 等于平移过程中所有的交

所以对于m个平移量也可以求凸包

也就是原图形 与一个凸包内的向量集的偏移的叠加图怎么求

而实际上凸包从线性规划角度看,就是 边的数量个不等式, 而平移的话就是每边的沿着法线方向最大的偏移量

所以也是得到 n(50) 个 不等式, 不再去求交,而直接用不等式

最后每个q就暴力求就完了?

然后似乎m也不需要求凸包,直接枚举所有就行,因为内部的不会产生贡献

https://atcoder.jp/contests/abc250/tasks

F - One Fourth

平面凸n边形

选非相邻点切割

求min( 8 abs(size/4 - eated))

就是选一些点, 围成的凸多边形 min(8abs(size * 3/4 - 选定凸多边形 ))

只切一次!!!!!!!!!!!!!!!!!!!!

范围

n 1e5

x,y [-4e8,4e8]

2s

1024 mb

我的思路

没做过多少计算几何相关的题目

一个想法是, 假设一个点会被保留, 想做前i个点, 第i个点保留的 最大, 小于目标的面积, 但似乎没有局部性

因为看起来像有相互冲突的背包

如果不是1/4, 是1/2呢, 我似乎1/2也不会做

干,读错题, 只切一次………….

https://atcoder.jp/contests/abc249/tasks

G - Xor Cards

n个卡, 每张有正面ai,背面bi

求让正面的 xor 和 <= K时, 背面 xor和 最大

求最大值

范围

n 1000

k (1<<30)

ai,bi [0,1<<30)

我的思路

对于xor和不等式没啥想法

一个是 对结果从高位到低位去贪心

比如 第i位 结果xor为1

那么 假设当前集合中, 对应b的i位为1的选奇数个, i位为0的选偶数个

但如何控制与Ai 的关系

第二个方向就是 xor 是不是有线性基, 但是如何把线性基的 结果大小 和 对应的xor和 尽量大

第三个就是N只有1000, 有啥n^2 的方法

dp[i][j], 前i的j个, 感觉”个数” 和目标之间没啥关系