CF1886

A

给你一个正整数 \(n\)，问是否存在 \(3\) 个正整数 \(a,b,c\) 满足 \(a+b+c=n\) 且 \(a,b,c\not\equiv 0 \pmod{3}\)。

分类讨论：

如果 \(n \not\equiv 0 \pmod{3}\) :若 \(n\le 5\) 则无解，否则可以拆分成 \(1,2,n-3\)。

否则：若 \(n\le 9\) 则误解，否则拆分成 \(1,4,n-5\)。

思路是尽量先取两个满足条件的最小的数。

Code

B

在一个二位平面内，你要从 \(O\) 点走到 \(P\) 点，给出两点 \(A,B\)，你可以以 \(A,B\) 为圆心覆盖半径为 \(w\) 的圆形区域。从 \(O\) 点 \(P\) 点过程中必须在被两圆覆盖的区域内。给出四点坐标，问满足条件的 \(w\) 的最小值。

分类讨论即可：

\(1.\odot A\) 覆盖 \(O,P\) 两点。

\(2.\odot B\) 覆盖 \(O,P\) 两点。

\(3.\odot A,\odot B\) 相切（或相交），\(\odot A\) 覆盖 \(O\) , \(\odot B\) 覆盖 \(P\)。

\(4.\odot A,\odot B\) 相切（或相交），\(\odot A\) 覆盖 \(P\) , \(\odot B\) 覆盖 \(O\)。

注意： float 用 %f ,double 用%lf,long double 用 %Lf

Code

C

比赛的时候楞是没想到是单调栈QWQ。

给定一个字符串 \(s\)，每次操作删除其中一个字符，且得到的新字符串 \(s'\)满足字典序在所有可能得到的结果中最小。依次进行 \(n-1\) 次操作，设第 \(i\) 次操作得到的字符串为 \(s_i\),定义字符串 \(t=s+s_1+s_2+...+s_{n-1}\)。给定一个整数 \(p\)，输出\(t[pos]\)这一字符。\(|s|\le 10^6\)。

可以发现规律：设 \(s_i\) 满足条件为当前字符串 \(s\) 中字符 \(s_i>s_{i+1}\),则位置最左的满足这一条件的字符 \(s_i\)就会被删去。特别地，如果没有满足条件的 \(s_1\) ,则删除当前字符串的最后一个字符。（不用分类讨论，一开始在 \(s\) 之后插一个比 \(z\) 字典序大的字符即可。）

每次插入一个字符 \(a\) 入栈，若栈顶元素字典序比 \(a\) 大，则弹出栈顶元素，弹到栈为空或满足条件为止，注意每次弹栈都是一次删除操作，需要判断一下，弹栈操作 \(k\) 次之后就不弹了。

Code

D

给定 \(n\) 个整数 \(1\) ~ \(n\)和字符串 \(s\)，以一定顺序一次插入到一个集合中，若第 \(i\) 次操作 $(i\ge 2) $插入的数是大于当前集合中的所有数,则 \(s_{i-1}='>'\)
,若小于当前集合中的所有数，则 \(s_{i-1}='<'\),否则 \(s_{i-1}='?'\)。

现在告诉你字符串 \(s\) ，\(m\) 个询问，每次询问修改 \(s\) 中的一个字符使其变为 \(s'\) ，每次回答有多少中操作可以获得 \(s'\) 。

其中 \(2\le n\le 3\times 10^5\) , \(1 \le m \le 3\times 10^5\) 。

orz思维题。

如果将操作倒过来，问题难度就大大减小。即将操作转换为从集合中一次删除数字。可以发现，每次删除当前集合最大值得到 \(>\) , 删除最小值得到 \(<\) ,否则得到 \(?\) 。这跟当前集合中具体由哪些数没有关系。

问题迎刃而解：我们遍历 \(s_i\) ，如果是 \(?\) 则将答案 $\times(i-2) $ 即可。\(O(1)\)修改即可。可以发现如果 \(s_2 = '?'\) 则答案一定为 \(0\) ，特判一下就可以了。

Code

E

给定 \(n\) 个正整数 \(a_1,a_2,...a_n\) ,将其分到 \(m\) 组中，第 \(i\) 组有一个值 \(b_i\),设该组集合大小为 \(k\) ,对于每一个该组的 \(a_i\) 满足 \(a_i\le \lfloor \frac{b_i}{k}\rfloor\) 。

考虑现将 \(a\) 数组排序。对于每一组 \(b_i\) ，可以证明得到在它组内的元素在排序后的数组中一定是连续的。因为我们观察到影响每个组合法性的是这个组 \(a_i\) 的最小值以及元素数量。因此对于不连续的方案，我们都可以改为从最小值依次递增的一段连续区间，这样不会影响该组合法性，也会使其它方案更优。并且我们可以确定最终方案一定是排序后 \(a\) 数组的一个后缀。

因此可以设计状态： $dp_{i} : $ 用 \(i\) 表示选择的组的方案。并且预处理出 \(mn_{i,j}\) ，即第 \(j\) 组从第 \(i\) 位开始可以选择的连续区间的最小值。具体转移见代码。