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

G - Balance Update Query

n种卡，每种无限多，初始每种 单价ai,最多取bi张

q个询问，每次三种可能操作

1. 修改一个的上限bi

2. 修改一个的单价ai

3. 问 恰好取x张的最大价值

范围

n,q 2e5

ai [0,1e9]

bi [0,1e4]

2s

1024mb

我的想法

如果固定，贪心从单价大到小的去取

对单价排序 做根号分治

让每个块的个数 保持在sqrt(n)个

这样每次修改操作就是 最多改变 sqrt(n)个块， 每个块内部就是 log(sqrt(n)) 的操作次数 时间复杂度 O(q sqrt(n) log(sqrt(n)))

而查询， 因为可以做块的个数和与代价和记录， 所以 暴力找在哪个块，再在块里暴力搜，O(q (sqrt(n)+log(sqrt(n))))

2s 还是会tle的

200000*math.sqrt(200000)*math.log(math.sqrt(200000))/math.log(2) = 91203683.14743526

它的确也tle了

https://atcoder.jp/contests/abc287/submissions/38429726

21AC + 19TLE

如果Latex在解密后没有渲染，刷新网页即可, 相关Issue

题目

统计 整数对$(a,b,c)$个数 满足

$1\le a \le b \le c$

$a+b+c \le 25,000,000$

$a^2+b^2=c^2+1$

我的思路

$(a-1)(a+1) = (c-b)(c+b)$

$a \le \frac{25,000,000}{3}$

提前线性筛的方式处理 可能的$a$的一个质因子

然后暴力 枚举a, 这样可以log 级别得到 a-1和a+1的分解

然后 dfs(分解) 去凑 $c+b$和$c-b$, 注意奇偶性可以剪枝，然后$c+b>c-b$也可以剪枝， $(c+b)-(c-b) = 2b \ge 2a$也可以剪枝

这样大概是 O(n * 分解的幂次之积) 的时间复杂度

i7-7700HQ 单核python3 跑了 810.686072 s, 十多分钟有点慢

https://codeforces.com/contest/1787

E. The Harmonization of XOR

问 [1,2,3,…,n] 能否拆成k个非空序列(不一定连续), 且每个序列内的数字xor为x

如果可以给具体方案

范围

n 2e5

x [1,1e9]

1s

256mb

我的思路

想了很久线性基, 没啥办法, 感觉都是O(n^2)以上

然后 显然 如果 k为奇数那么 x = xor[1..n], 如果k为偶数, 0 = xor[1…n]

然后n%4==3 的时候 xor[1..n] = 0

然后n%4==0 的时候 xor[1..n] = n

然后n%4==1 的时候 xor[1..n] = 1

然后n%4==2 的时候 xor[1..n] = n+1

其中 n%4==1 很好做, 相邻取偶数和偶数+1 就能构成

n%4==0和n%4==2没有什么办法, 但是这个如果暴力出来,是可以打表的

但是n%4==3 就连打表都不行

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^叶子