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个, 感觉”个数” 和目标之间没啥关系

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

G - GCD cost on the tree

n点无向树

点i上有值ai

C(u,v) = 简单路径u..v上 点个数 乘 点上ai的gcd

求所有点对的 C的和,mod 998244353

范围

n 1e5

ai [1,1e5]

8s

2048mb

我的思路

显然暴力算 至少要 n^2

注意到的是 Ai很小, 如果能变成 不同gcd结果的贡献值的和 就好了

有点想做容斥, 但容斥的代价函数并不能用当前gcd

如果选定一个点必定经过, 那么可能的gcd都是它的因数, 虽然这里log了,但是要找路径还是n, 这样依然是n^2 以上

再看贡献count(u..v) * gcd(a[u]...a[v])

可以转化成, u 会贡献了覆盖了u的线段次数, 每次都是u的因子

那么每个 v1…u…v2 在u上的贡献是 gcd(gcd(v1..u),gcd(v2..u)), 且v1,v2 不在u的同一个分叉上

f[child v0] = sum c0[g] x^g

f[child v1] = sum c1[g] x^g

sf[v1,v2] = f[v1] + f[v2]

ans += sf[0..i-1] * f[vi] (k[gcd(g0,g1)] += k0[g0] * k1[g1]`

= ((E+f[0]+f[1]+…+f[i]) ^ 2 - E^2 - f[0]^2 -f[1]^2 -…-f[i]^2)/2

---

换根dp ???

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

G - Dream Team

n个人第i个, 有值Ai,Bi,Ci

考虑从中选一些

满足Ai,Bi两两不同

对于所有可能的构成 人数 = 1…k

求最大的Ci的和

范围

n 3e4

ai, bi, [1,150]

ci [1,1e9]

2s

1024mb

我的思路

emmmm, 这个ai,bi 这么小, 但感觉又像费用流+限流?

ai,bi建立点

S->ai 每个1容量,0代价

bi->T, 每个1容量,0代价

中间就是ai->bi, -Ci 代价, 然后限流让总代价小

然后为了不能让代价为负, 所以全部+Max(Ci)

最后答案 - flow * max(Ci)?

似乎就没了