EC Final 2024 题面简要翻译
Redshift_Shine
·
·
生活·游记
A. Hitoshizuku / 壱雫空
给出整数 n，并给出 3n 个二元组 (a_i,b_i)。要求给出一种三个一组的划分方案，使得划分结果中每一组 (x,y,z) 均满足 \max(a_x,a_y,a_z)\le\min(b_x,b_y,b_z)。
多测，1\le n, \sum n\le 10^5。
B. Guess the Polygon 2 / 猜多边形 2
给出 n 个平面直角坐标系上的点，这 n 个点组成了一个多边形。该多边形满足对于该多边形的任意两条边，存在交点当且仅当它们有一个共同的顶点。你可以进行不多于 (n-2) 次询问，每次询问给出三个参数 a,b,c，返回值为函数 ax+by+c=0 在该多边形内部的长度。该长度将会以两个整数 r,s 的形式返回，代表长度为 \frac{r\sqrt{a^2+b^2}}{s}。你需要以逆时针顺序输出每个点的位置。
多测，3\le n,\sum n\le 200,0\le x,y\le 10^3。
C. Norte da Universidade / 大学北部
给出 n\times m 的矩阵，其中每个位置包含一个字符，保证这些字符 \in\{\space \texttt{N,S,W,E,?}\space\}。要求将所有 \texttt{?} 替换为 \texttt{N,S,W,E} 中的一种，满足对于所有的 \texttt{N}，其上方为边界或 \texttt{N}；对于所有的 \texttt{S}，其下方为边界或 \texttt{S}；对于所有的 \texttt{W}，其左侧为边界或 \texttt{W}；对于所有的 \texttt{E}，其右侧为边界或 \texttt{E}。计算替换方案总数对 998244353 取模的结果。
多测，1\le n,m\le 10^3，1\le \sum (n\times m)\le 2\times 10^6。
D. Keystone Correction / 投影校准
给定光源和一块面板以及一块幕布，求通过调整面板使得面板在幕布上的投影各边分别与幕布平行且完全处于幕布内部且长宽比例与面板相同后的最大面积。
（这个实在不会翻了就将就着看吧）
E. Corrupted Scoreboard Log / 崩坏的排行榜
给定整数 n,m，并给出 n 个字符串 s_i。对每个字符串求一组将字符串进行分割的合法方案。
划分方法如下：
- 第一个部分为一个整数，记为 x。x 不可为空。
- 第二个部分为一个整数，记为 T。T 不可为空。
- 从第三个部分开始，每个部分被分为三段。
- 第一段为一个整数，记为 t_i。t_i 可以为空。
- 第二段为一个整数，记为 r_i。r_i 不可为空。
- 第三段为 \texttt{try,tries} 中的一种，记为 g_i。
对于一个合法划分 D，需要满足：
-
2\le |D|\le m+2
-
\sum [t_i\neq\varnothing]=x
-
\sum ([t_i\neq\varnothing](t_i+20(r_i-1)))=T
对于一个合法划分中的每一组，需要满足：
-
[r_i=1]=[g_i=\texttt{try}]
-
t_i=\varnothing\space\lor\space 0\le t_i\le 299
-
1\le r_i\le 100
求出任意一组合法划分。保证合法划分存在。
## F. Boolean Function Reconstruction / 布尔表达式重构
给定整数 $n$，表示有 $n$ 个布尔变量。给出**所有** $n$ 个变量分别为 $\texttt{True}$ 或 $\texttt{False}$ 时该表达式的结果，在使用不超过 $(2^{n-1}+10)$ 个 $\texttt{\&}$ 和 $\texttt{|}$ 符号以及不超过 $100$ 层括号嵌套的前提下构造一个符合要求的表达式，或报告无解。所有的二元运算都需要通过括号指明运算顺序。
该表达式可以包含 $\texttt{T,F}$， 分别代表 $\texttt{True,False}$。
多测，$1\le T\le 2^{16},1\le n\le 15,1\le \sum 2^{2n}\le 2^{30}$。
## G. Collatz Conjecture / 变体冰雹猜想
给出两个互质正整数 $a,b$ 和一个正整数 $n$。
定义函数：
$$
f(x)=\begin{cases}
\frac{x}{a} & a\mid n\\
x+b & \text{otherwise}
\end{cases}
$$
定义 $f^t(x)$ 为将 $x$ 作为函数 $f$ 初始参数连续调用 $t$ 次的结果。
判断 $\exist t\in\N^+\space f^t(n)=n$。
多测，$1\le T\le 10^5,2\le a\le 10^9,1\le b\le 10^9,1\le n\le 10^{18}$。
## H. Staircase Museum / 阶梯博物馆
给出 $n$ 组整数二元组 $(l_i,r_i)$。要求找到最大的整数 $m$，满足存在一个二元组集合 $S$ 满足以下条件：
* $|S|=m
- 对于 S 内的任意二元组 (x_i,y_i)，满足：
-
l_{\lceil x_i\rceil}-1\le y_i\le r_{\lfloor x_i\rfloor+1}
- 对于 S 内任意两个不同二元组组成的点对的连线，满足：
- 线上存在至少一个点 (a,b)，满足 b\not\in[l_{\lceil a\rceil}-1,r_{\lfloor a\rfloor+1}]。
多测，1\le n,\sum n\le 5\times 10^5，1\le l_i\le\bold{l_{i+1}}\le r_i\le\bold{r_{i+1}}\le 10^9。
I. Color-Balanced Tree / 颜色平衡树
给定一棵包含 2n 个节点的树，要求给每个节点染上青白两色中的一种，满足树上青白节点数目相等并且树上任一路径上青白节点数目差不超过 3，或报告无解。
多测，1\le n,\sum n\le 10^5。
J. The Mysterious Shop / 神秘商店
定义函数 f(x,y) 如下：
f(x,y)=\begin{cases}
x+y & x+y\le n\\
x & x+y>n
\end{cases}
现有一整数 x=0。对从 n 到 1 的每个整数 i，有 \frac{1}{2} 的概率执行 x\leftarrow f(x,i)。注意，i 是降序枚举的。
对于从 1 到 n 的每个整数 i，输出枚举完毕后 x=i 的概率乘 2^n 后对 998244353 取模的结果。
## K. Exploration Boundary / 探索边界
定义**探索边界**为 Dijkstra 算法在一张图上运行时某次**取出堆顶元素前**的堆。
给出一张图和 $k$ 个探索边界，要求为每条边赋予正权值，使得每条边权值不超过 $10^9$，且从节点 $1$ 开始到任一节点的最短路径长度均不同，且所有给出的探索边界均会出现在以 $1$ 为起始节点的 Dijkstra 算法中。
多测，$2\le n\le 2\times 10^5$，$1\le m\le 2\times 10^5$，$\sum n,\sum m,\sum b_i\le 10^6$，给出的所有图均为无重边或自环的连通图。
## L. Shiori / 栞
维护一个长度为 $n$ 的序列 $a$，支持以下操作：
1. $\forall l\le i\le r\space a_i\leftarrow a_i+v
-
\forall l\le i\le r\space a_i\leftarrow a_i+\operatorname{mex}(a_{[l,r]})
-
\text{query }\sum_{i=l}^r a_i
注意，操作 2 对区间内所有数同时进行。