E - Colinear
https://atcoder.jp/contests/abc422/tasks/abc422_e
看到题目会有一个乱搞的想法:随机取一对点,那么是有 \(\dfrac 14\) 的概率都在直线上的。带进去暴力 check 一下,多来几次正确率就比较高。
什么,这是正解?abc 的风格真是越来越奇怪了。
F - Eat and Ride
https://atcoder.jp/contests/abc422/tasks/abc422_f
考虑一个费用提前计算的分层图,就可以跑 Dij 了。
官解给出了一个优化:搜索实际上是在给边定向;这样图就转化为 DAG(实际上反向边并不会产生有效更新,故直接朴素转移即可)。
B - Triangle Toggle
https://atcoder.jp/contests/arc205/tasks/arc205_b
现场是打表找规律做出来的 😅
发现这样一次操作之后每个点上黑边的奇偶性是不会变的,所以会有一个上界,难点在于是否可以达到这个上界。
发现只要存在一个点上连有两条白边,就可以把 001 反转为 110,一次操作至少可以新增一条黑边。故是可以达到的。
D - Non-Ancestor Matching
https://atcoder.jp/contests/arc205/tasks/arc205_d
没啥好说的摩尔投票,有一个非常简单的优先队列做法
但 Rosmist 打了另一个看起来有点玄学的东西:可以感受到每次只向最大的子树递归是合理的,尝试证明一下发现确实比较显然
E - Subset Product Problem
https://www.luogu.com.cn/problem/AT_arc205_e
奇怪题目
高维前缀和 + 分块其实不算特别罕见的 trick
用 \(f_{i,j}\) 表示前 \(10\) 位为 \(i\),后 \(10\) 位的高维前缀和
每次查询 / 更新都是 \(O(2^{10})\) 的,可以接受(吗)
然后还有一个科研性的做法 见 https://www.luogu.com.cn/article/1uyz0hn2
C. By the Assignment
https://codeforces.com/contest/2135/problem/C