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

Ex - Don’t Swim

二维平面, 有N点的凸多边形C(逆时针给点),

以及两个点S和T(保证在多边形外部)

求从S到T不经过多边形内部的最短距离

范围

n 1e5

所有坐标 [-1e9,1e9]

2s

1024mb

我的思路

看错题了

如果是凸包, 那就还好, 按S排个角度, 每次找下一个点和S哪个夹角更小, 就完了

问题是这里可能是奇怪的形状

1
2
3
4

   xxxx
S x   x
 x  xTx
    xxx

一个事实是, 如果从当前点能不穿过其它点到S,那么就直接走, 但是又该如何判断 中间不被阻挡, 需要O(n)条边的判断?

那么其实 任意两点都满足这个性质, 如果直接能到就直接走

最短路? 还是 如何在非凸包 判断不被阻断, 不会了

CF tracker

Edu List

https://codeforces.com/contest/1613

F. Tree Coloring

根1的n点树

给点上排列色ci = 1~n (每个颜色出现且仅出现一次)

p[i]=i的父节点

如果所有点满足c[i] != c[p[i]] -1, 则认为美丽

问有多少种美丽的染色方案mod 998244353

范围

n 250000

4.5s

512mb

我的思路

也就是 每个点的颜色不能正好比父节点小1

一般来说, 树的兄弟之间没有关系, 但是这里 如果一个非法的子树, 和兄弟的子树, 值进行穿插, 这有可能变得合法

例如

1
2
3

  root
2     2
1     1

1
2
3

  root
3     4
1     2

一个方向就是去考虑容斥, 把边作为属性, 拥有属性表示边连的两个点相邻

有指定属性连接在一起的点, 在子树之间 做穿插时就不能拆开了,

而注意到当子树穿插时, 只与有几个可穿插的有关

考虑f[u][c] = 节点u的子树中, 可连可不连的自由节点个数为c时的方案数

先不考虑根, v1 和 v2 之间的穿插

[c1 + c2] = sum f[u][c1] * f[u][c2] * binom(c1+c2,c1)

[c1 + c2]/(c1+c2)! = sum f[u][c1]/c1! * f[u][c2]/c2!

看起来就是ntt

最后考虑根u

f[u][c1+c2+...] = [c1+c2+...]*count(child), 直接放(某个子树的最大+1) 且指定边不可移动

f[u][c1+c2+...+1] = [c1+c2+...]*(c1+c2+...+1), 放任意地方(包括 最大+1), 但不指定边

f[u][c] = (count child)[c] + [c-1]*c

变形 f[u][c]/c! = (count child)[c]/c! + [c-1]/(c-1)!

那么就是 g[u] = (c+x) g(v0) g(v1) g(v2) ...

g(leaf) = x

ans = sum f[1][c]*c!

但是看起来暴力算感觉会tle

仔细一看表达式 原来是 f[1] = (c1+x)(c2+x) * x^叶子

CF tracker

Edu List

https://codeforces.com/contest/1620

F. Bipartite Array

给你1~n排列数组a

问能否 给每个数乘上 1或-1,

然后对所有逆序点连边, 让所有点能二分图

范围

n 1e6

2s

256mb

我的思路

考虑一个点是负数, 那么它前面所有点和它相连, 所以前面点和它 都在二分图对面, 所以它们之间不能有边, 所以它们需要单调递增,

如果考虑n是正数, 同理 它右侧的点 需要单调递增

如果n是负数,那么它左侧的点要单调递增

问题是这样分割, 会产生n个分支?

dfs 来控制 ?

CF tracker

Edu List

https://codeforces.com/contest/1622

E. Math Test

n个学生,

m个题目

你知道每个学生 哪些题目对了哪些题目错了, 正确得分错误不得分

r[i] = 第i个学生的真实得分 = 正确题目得分之和

x[i] = 第i个学生的标准得分, 给定

问如何给题目 的分设置为 1~m 的排列

能让 sum |xi-ri| 最大, 求最大值

范围

n 10

m 1e4

2s

256mb

我的思路

这n很小, 就很想bitmask

但是 bitmask怎么用

想的是 分别计算 f(bitmask) = bitmask中的学生真实得分 >= 标准得分, 其它的学生 真实 < 标准

这样去掉了绝对值

然后如何算呢

这样得到 10个 不等式 和一个要求的最大值

正确错误的1/0串[i] * 题目分数设置 = r[i] >= x[i]

…

正确错误的1/0串[j] * 题目分数设置 = r[j] < x[j]

…

要求 max( 正确错误1/0加权和 * 题目分数设置)

有点像线性规划?

但一个是排列, 一个是又有大于等于, 又有小于等于, 并不知道怎么搞

CF tracker

Edu List

https://codeforces.com/contest/1626

F. A Random Code Problem

给长度n的数组a

执行k次i=1..k

每次随机取下标idx,

ans+=a[idx]

a[idx] -= (a[idx] % i)

求 ans的期望, mod998244353

范围

n 1e7

1 <= a[0],x,y < M <= 998244353

1 <= k <= 17

a[i] = (a[i-1] * x + y)%M

3s

512mb

我的思路

这个操作就是 a[idx]变成贡献, 然后a[idx]变成不大于它的最大的i的倍数

这好几个神奇的地方, 首先n很大, 数组都是通过 递推式子给的, 这个递推式如果M小还有周期, 如果M大,不太知道怎么用

然后这个k <= 17 真的很小, 小到 甚至在想 bitmask

f[index][bitmask] = 贡献, 虽然这个状态大小都接受不了

但注意到第一次 的期望就是所有的平均数,

第二次也是, 当第二次选的偶数时, 那么第三次也是, 当第二次选的奇数时, 第三次 = 所有平均数 - 1/n

所以 经过第 i 轮 损失的量的 期望如果能算的话, 也是一个角度

算了下lcm(1…17) = 12252240, 也不小

而且 分支变化 状态也多

要快速计算 a[j] 可以用矩阵乘法, 但是 又要mod 又要加法, 算和也不知道怎么搞, 所以应该直接暴力掉?

12252240 似乎也可以, 每次相当于 n种操作, 那么就是所有 产生n 分, 第i份 处理i

只是在统计上,把它们加在一起, 这样每次 每个产生 1份处理的 和 n-1份没被处理的

r[i][w] += r[i-1][w]*(n-1)

r[i][next(w)] += r[i-1][w]

处理后的一定不大于当前的, 所以可以从大到小滚动掉,

所以可以滚动掉, 大概 O(k lcm(1…k)) ? 能过吗?

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

import math

def f(l,r):
    s = 1
    for i in range(l,r+1):
        s=math.lcm(i,s)
    return s

for i in range(1,17+1):
    print(i, f(i,17))

1 12252240
2 12252240
3 12252240
4 12252240
5 12252240
6 12252240
7 12252240
8 12252240
9 12252240
10 4084080
11 4084080
12 371280
13 371280
14 28560
15 4080
16 272
17 17

题解

还真是这样, 问题在于我想多了, 17并不需要, 因为17虽然改变, 但是贡献是由16决定的

所以 lcm(1..16) = 720720 就相当的小了

就随便做了

总结

试了一下, 看来补atcoder和补cf还是开vp补 比较好, 这场VP了

E 没有在时间内写出来, 翻来覆去才写出, 花了接近1.5h, 还是应该想清楚所有情况才写,不要想一半写一半

F 细节想得有问题, 但总体的思路没问题

然后1e7 果然 for还是随便for的, 不直接给, 估计是因为read慢

参考

官方