警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

简单题合集

RT.

TODO

  • 1185G2
  • 1181E

1185

E - Polycarp and Snakes

题意

传送门:Codeforces 1185E - Polycarp and Snakes

给一个 \(n\times m\) 的字符矩阵,由 [a-z.] 组成。其中 . 代表空白。问能不能由一个全是 . 的矩阵,按 a-z 的顺序覆盖得到。

多组数据,\(1\le T\le10^5,1\le n,m\le2000\)

更加清晰的解释详见原题面。

解法

傻逼题。直接模拟,做完了。

代码

F - Two Pizzas

题意

传送门:Codeforces 1185F - Two Pizzas

给你一个 \(n\) 个元素的集合 \(S\),和一个 \(m\) 个元素的集合 \(T\)

集合 \(S\) 中的元素是包含 \(\mathbf{1\sim9}\) 之间数字的非空集合

集合 \(T\) 中的元素是形如 \(\mathbf{(x, A)}\) 的数对,其中 \(\mathbf x\) 是一个数,\(\mathbf A\) 是一个包含 \(\mathbf{1\sim9}\) 之间数字的非空集合

你要从 \(T\) 中选两个元素 \(p,q\),使得 \(\sum_{i\in S}[i\subseteq p_A\cup q_A]\) 最大,且在满足上一个条件的情况下,最小化 \(p_x+q_x\)

\(1\le n\le10^5,2\le m\le10^5\)

更加清晰的解释详见原题面。

解法

一眼题。

注意到包含 \(\mathbf{1\sim9}\) 之间数字的非空集合只有 \(511\) 个,所以对于每种集合只要留下 \(x\) 最小的数对,然后把它们丢到 \(T'\) 里。复杂度 \(O(m)\)

于是会剩下 \(|T'|=m'\) 个数对,有 \(m'\le511\)

然后预处理 \(f_A=\sum_{i\in S}[i\subseteq A]\),最后枚举所有的 \(p,q\in T'\) 得到 \(p_x+q_x\) 最小的。

注意到 \(S\) 去重后也最多只有 \(511\) 个,可以进一步优化复杂度。反正怎么写都不会 T

注意合理设置 INF 的取值。

代码

1182

D - Complete Mirror

题意

传送门:Codeforces 1182D - Complete Mirror

给一棵无根树,定一个根,满足到根距离相同的点度数也相同。输出任意一个解或 \(-1\)

对称二叉树·改

\(1\le n\le10^5\)

解法

简单题。

找重心,然后 check 一下就好了。

有个坑。如果出现类似下列的图

12345

那么重心是 \(2,4\),而答案是 \(1\)。此时应该沿着度数为 \(2\) 的链走到末尾作为答案。

令两条链相等当且仅当它们的长度相等。

正确做法是,任意找一条出现次数为 \(1\) 的链,将他的末端定为根,然后 check。

证明十分简单,在此不详细阐述。

代码

吐槽

这题评分也有 \(2500\)?CF 怎么自己都恶评啊……

感觉 901D(评分 \(2700\))和这题难度差不止 \(200\) 分啊……

Behind story of D: Honestly I predicted D as hell hard problem. But other high rated people said it's not that hard.

出题人你是在搞笑么?

E - Product Oriented Recurrence

题意

传送门:Codeforces 1182E - Product Oriented Recurrence

给出 \(n,f_1,f_2,f_3,c\),对于 \(x\ge4\)\(f_x=c^{2x-6}f_{x-1}f_{x-2}f_{x-3}\)。求 \(f_n\bmod(10^9+7)\)

\(4\le n\le10^{18},1\le f_1,f_2,f_3,c\le10^9\)

解法

套路题。

考虑将 \(f_n\) 表示为四元组 \((a_n,b_n,c_n,d_n)\) 分别代表 \(c,f_1,f_2,f_3\) 的指数。那么根据递推式,可以推出转移如下:

\[ \begin{aligned} a_n&=a_{n-1}+a_{n-2}+a_{n-3}+2n-6\\ b_n&=b_{n-1}+b_{n-2}+b_{n-3}\\ c_n&=c_{n-1}+c_{n-2}+c_{n-3}\\ d_n&=d_{n-1}+d_{n-2}+d_{n-3} \end{aligned} \]

然后就是矩阵加速一眼题了。

\(\{b\},\{c\},\{d\}\) 的转移很套路:

\[ \begin{bmatrix}1&1&1\\1&0&0\\0&1&0\end{bmatrix}\cdot\begin{bmatrix}b_n&c_n&d_n\\b_{n-1}&c_{n-1}&d_{n-1}\\b_{n-2}&c_{n-2}&d_{n-2}\end{bmatrix}=\begin{bmatrix}b_{n+1}&c_{n+1}&d_{n+1}\\b_n&c_n&d_n\\b_{n-1}&c_{n-1}&d_{n-1}\end{bmatrix} \]

\(\{a\}\) 的转移稍微麻烦一点:

\[ \begin{bmatrix}1&1&1&2&-4\\1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&1\\0&0&0&0&1\\\end{bmatrix}\cdot\begin{bmatrix}a_n\\a_{n-1}\\a_{n-2}\\n\\1\end{bmatrix}=\begin{bmatrix}a_{n+1}\\a_n\\a_{n-1}\\n+1\\1\end{bmatrix} \]

然后就做完了。

其实还可以用离散对数乱搞,但是大同小异。

代码

吐槽

Behind story of E: I didn't expected such well-known problem. My solution for E is more complicated.

海星……

F - Maximum Sine

题意

传送门:Codeforces 1182F - Maximum Sine

\(p,q,a,b\),求 \([a,b]\) 中使得 \(\left|\sin\left(\frac pq\pi x\right)\right|\) 取得最大值的最小整数 \(x\)

\(0\le a\le b\le10^9,1\le p,q\le10^9\)

解法

毒瘤题。

根据 \(\sin\) 的性质,当 \(x,y\in[0,\pi]\) 时,\(|x-\frac\pi2|<|y-\frac\pi2|\Leftrightarrow|\sin x|>|\sin y|\)

那么就变成了求最小的整数 \(x\in[a,b]\) 使得 \(\frac pqx\pi\bmod\pi\) 最接近 \(\frac\pi2\)。即使得 \(2px\bmod2q\) 最接近 \(q\)

\(g(x)=2px\bmod 2q\)。然后考虑对区间分块。

令块数为 \(T\)。考虑对 \([a,b]\) 中的前 \(T\) 个数构造一个序列 \([(g(a),a),(g(a+1),a+1),\cdots,(g(a+T-1),a+T-1)]\) 然后只保留相同权值里下标最小的并排序。复杂度 \(O(T\log T)\)

因为有 \(g(x)+g(y)\equiv g(x+y)\pmod{2q}\),所以可以根据第一块的大小关系推出每一块的。

第一块里找的是与 \(q\) 最接近的数,那么第二块加上了一个 \(g(T)=2pT\),所以找的是与 \(q-2pT\) 最接近的数。同理,第 \(k\) 块找的就是与 \(q-2pTk\) 最接近的数。复杂度 \(O(\frac nT\log T)\)

\(T\) 显然取 \(\sqrt n\)。所以复杂度 \(O(\sqrt n\log\sqrt n)\)\(O(\sqrt n\log n)\)

细节繁多,注意各种边界问题。

代码

吐槽

Behind story of F: This problem was located at D originally.

Mathforces?我觉得要是放到 D 这场比赛就要被喷死了吧……

1181

D - Irrigation

题意

传送门:Codeforces 1181D - Irrigation

给你一个数 \(m\),和一个数列 \(\{a\}\) 的前 \(n\) 项。这个数列有下列性质:

  • 数列 \(\{a\}\) 中的每一个数都是区间 \([1,m]\) 中的整数。
  • 从数列的第 \(n+1\) 项开始,每一项都是前面所有项中出现次数最少的数。如果有多个则选最小的。

\(q\) 次查询,每次给一个数 \(x\),查询 \(a_x\)

解法

一眼题。考虑离线。

构造一个二元组序列 \([(a_1,1),\cdots,(a_n,n)]\) 然后排序。递增枚举每个极大区间 \([l,r]\) 满足排序后这一段下标的的 \(a\) 相同,注意到这个下标区间一定对应某个时间区间,使得 \([l,r]\) 中的数周期出现。

然后模拟就好了。

代码