Good Bye 2021: 2022 is NEAR
source link: http://www.shuizilong.com/house/archives/good-bye-2021-2022-is-near/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
https://codeforces.com/contest/1616
和 去年一样 。。。今年的 GoodBye Round 的 Pretest 也很强。。。
大家新年快乐啦。。。
Problem D. Keep the Average High
数列选数，要求如果原序列中多于1个连续的全被挑中，则满足平均值大于给定的 x，问最多可以选多少
dp，只要考虑长度为 2、3 的段满足条件即可，其它长度自动满足。
Problem E. Lexicographically Small Enough
给定两个字符串 s, t ，每次可以交换两个相邻字符，问至少几次交换可以使得 s 字典序小于 t。
考察 t[0]，方案一：找小于 t[0] 的字符交换到 s[0] 位置。方案二：找等于 t[0] 的字符交换到 s[0] 位置，之后迭代到下个位置。
每次都贪心的找最靠前的，可以开 26 个 deque 去记录这些位置，同时用树状数组维护删除事件。
Problem F. Tricolor Triangles
给定一个无向图 (n <= 64,m <= 256) 要求对边进行三染色，使得对于任意三元组，如果存在三条边的话，要么颜色全相等，要么全部不相等。
有点类似解 xor 方程组。。。这里我们建立模 3 方程组。。那么要么必要条件就是 xi + xj + xk = 0，然后求这个矩阵的 Kernal。
注意估计一下复杂度，这里可以用 bitset 加速，而且未知数规模是 m，方程组数为 msqrt(m)。。（直播里 Neal Wu 说一眼就看出要 Gauss 但是没好好估复杂度认为不可做就跳去做 H 了囧）。
Problem G. Just Add an Edge
给定一个 dag，问有多少种加一条边的方案，使得加完后图中存在 Hamiltonian path。
Problem H. Keep XOR Low
给一个数集，问有多少种 subset 方案，使得 subset 种任意两个数的 xor < 给定的数 x。
2-sat？二进制 tire?
Posted by
xiaodao
Category: 日常
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK