ROIR 2023
评分 \(\in[0,10]\)。
https://www.luogu.com.cn/problem/list?type=luogu&page=1&tag=479|60&orderBy=pid&order=asc
矩形分割 (Day 1)
\(3\)。
根据题意列出二元二次方程,用 \(k\) 换元得到一元二次方程。
然后套求根公式解就行了。
留意无解的判断。
斐波那契乘积 (Day 1)
\(2.5\)。
意义不明。
处理到 \(f_{86}\),因为 \(f_{87}>10^{18}\)。
容易猜到状态数很少。
考虑直接爆搜枚举 \(f_k\),从 \(now=n\) 开始跑,如果当前 \(f_k\) 是 \(now\) 的因数,则转移到 \(\frac{now}{f_k}\),\(now=1\) 时退出并计入答案。
扫地机器人 (Day 1)
\(3\)。
意义不明。
记录一下每次正方形位移经过的矩形,做一个矩形面积并,这是扫描线的板子,呃呃。
彩点 (Day 1)
\(5.5\)。
考虑建图,记 \((i,j)\) 为一个点,表示 \(i\) 作为起始点 \(j\) 作为终止点,可以建出若干形如 \((i,j)\to (j,k)\) 的有向边。
则可以枚举每个点作为 \(j\),然后极角排序,可以做到 \(O(n^2 \log n)\) 建图。
观察图的形态,不难发现是内向基环树森林,更是 DAG。
考虑绿点的判定,\(i\) 是绿点当且仅当存在 \(j\) 使得 \((i,j)\) 在环中,即大小 \(>1\) 的强连通分量,可以使用有向图 Tarjan 判断。
接下来就是蓝点,\(i\) 是蓝点当且仅当它不是绿点,且存在 \(j\) 使得从 \((i,j)\) 能到达 \((i,k)\),是一个可达性的问题,拓扑排序时用 bitset
维护一下连通性(注意是点 \(i\) 的情况而不是 \((i,j)\) 的情况,含义为形如 \((i,k)\) 的点的连通性,相当于一起处理了,显然判断蓝点确实只需要知道这样的信息),可以做到 \(O(\frac{n^3}{\omega})\)。
地铁建设 (Day 2)
\(2.5\)。
一个发电机的功率与电压关系虽然是分段函数,但是容易发现仍然据有单调性,直接二分。
美丽序列 (Day 2)
\(3.5\)。
意义不明。
\(n\le 100,m\le 8\),直接状压,设计 dp 状态 \(dp_{i,\{x_1,x_2,\dots,x_7,x_8\}}\),表示当前序列长度和每个数字上次出现的位置的到 \(i\) 的距离,然后直接转移即可。
状态数是 \(O(nm!)\) 的,能过。
也可以直接存 \(i\) 往前 \(7\) 位序列的具体数字,目测也能过。
石头 (Day 2)
\(5.5\)。
大分讨,题目出得不错。
观察最终状态,如果要使 \(p\) 在第 \(k\) 次被染白,则可以是 \([p,p+k-1]\) 全部被染白,也可以是 \([p-k+1,p]\) 全部被染白,两种情况等价。
考虑 \([p,p+k-1]\) 被染白的情况,设 \(\argmax_{i=p}^{p+k-1} a_i=j\),则可以通过 \(j\) 为跳板,进行分类讨论,如果想到了这个,离切这题就不远了。
最前置的要求,\(a_p<a_{p+k}\),否则在 \([p+1,p+k-1]\) 时肯定会先染 \(p+k\)。
显然 \([p,j-1]\) 肯定都不存在贡献,因为都比 \(a_j\) 小,肯定会在 \(a_j\) 前先被染色。
然后进行讨论:
-
\(a_j<a_{p+k}\),此时 \([j+1,p+k-1]\) 都可以产生贡献,路径都是先往右拓展到 \(p+k-1\),然后再往左一直到 \(p\)。而 \(j\) 产生贡献,当且仅当 \(p\) 最后被染色,此时要求 \([p,j-1]\) 存在一个数大于 \([j+1,p+k-1]\) 的所有数,使得右边先染色完。
-
\(a_j>a_{p+k}\),此时 \([j+1,p+k-1]\) 一定没有贡献,这是显然的。此时只有 \(j\) 可能产生贡献,首先得满足 \([p,j-1]\) 存在一个数大于 \([j+1,p+k-1]\) 的所有数,且出了 \(a_j\) 之外的数都得 \(<a_{p+k}\) 否则一定会先染到它。
特判 \(k=1\)。
一个普通的字符串问题 (Day 2)
\(?\)。
BEST 定理,没学,待填坑。