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

F - Erase and Rotate

给一个长n排列A

问不超过k次操作后能得到的最小字典序列

每次操作 可以删除一个数, 或循环右移1个单位

范围

n 2e5

k [0,n-1]

2s

1024mb

我的思路

考虑两种一个是不移动, 从左删除, 那么就是前 k个中取最小, 然后 后面塞入一个, minPQ维护

右侧移动, 也可以确定 首个数字是啥

问题是 当右侧移动时, 可能和删除是同一个, 这个感觉没啥简单的想法去记录

比如样例数据三

如果看成先移动,再删除, 其实会删除移动过的数字

不知道能不能移动+标记+贪心局部?

然后因为k可能比较大,可以从左侧删除和右侧移动 来得到, 所以考虑两个方向来算, 算完了比较?

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

Ex - I like Query Problem

长n序列A

q个操作

类型1, a[l..r] 整除 x

类型2, a[l..r] = x

类型3, 求 sum a[l..r]

范围

8s

1024mb

n 5e5

q 1e5

ai [1,1e5]

x [2,1e5]

我的思路

感觉就线段树啊

(a/x) = (a/(x * y)) 吧

所以记录一下区间 的操作,

问题是求和的话??

另一个思路就是, 记录连续一样的段, 这样每次操作到连续一样的段上, 如果本来就是一致的就直接除就行了, 而不一致的,每个位置的值在重新赋值前最多除log(2,a[i]) 次

似乎就被均摊了?

然后向上搜集的时候, 注意把原来不一样但除了以后一样的也做合并

似乎就没了?

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也不需要求凸包,直接枚举所有就行,因为内部的不会产生贡献