当前位置：首页 > news >正文

CF1379

news 2026/6/24 14:19:31

A.Acacius and String

我们需要找到一个方法，将包含问号的字符串替换为小写字母，使得生成的字符串中恰好包含一次子串abacaba。

字符串长度才50，直接暴力枚举起始点判断即可

B.Dubious Cyrpto

给定 \(l,r,m\) ，找到任意一组 \(a\)、\(b\) 和 \(c\)，使得：

\(a\)、\(b\) 和 \(c\) 是整数，

\(l \leq a, b, c \leq r\)，

存在一个严格正整数 \(n\)，使得 \(n \cdot a + b - c = m\)。

转换成 \(n \cdot a = m - b + c\)，则\(m+l-r<=n \cdot a<=m+r-l\)
枚举 \(a\) 看是否有符合的 \(n\) 即可

C.Choosing flowers

有 \(m\) 种物品，每种物品有无限个，你可以购买 \(n\) 个物品
对于第 \(i\) 种物品：
第一次买时的贡献是 \(a_i\) ,接下来每购买一个的贡献都是 \(b_i\)。即当你买了 \(x_i\) 个第 \(i\) 种物品时，贡献是 \(a_i+b_i \times (x_i-1)\)
现在要你求出最大贡献

发现我们会购买的 \(b_i\) 只会有一种，但是大于这个 \(b_i\) 的所有 \(a_i\) 也都会买
按照 \(a_i\) 排序并求前缀和，枚举选择的 \(b_i\) ，答案取 \(max\)

D.New Passenger Trams

Kirnes 星球的一天由 \(h\) 小时，每小时 \(m\) 分钟组成（\(m\) 是偶数）。每天有 \(n\) 辆货车从 Kirnes 出发，其中第 \(i\) 辆的出发时间是 \(h_i\) 时 \(m_i\) 分。
现计划增添 \(2h\) 辆电车，第 \(1\) 辆电车出发于 \(0\) 时 \(t\) 分，电车的发车间隔为 \(\dfrac{m}{2}\) 分钟。形式化地，若 \(i\) 为奇数，则第 \(i\) 辆电车出发于 \(\dfrac{i-1}{2}\) 时 \(t\) 分；若 \(i\) 为偶数，则第 \(i\) 辆电车出发于 \(\dfrac{i}{2}-1\) 时 \(t+\dfrac{m}{2}\) 分。\(t\) 是一个可以由你决定的整数。
乘客上车需要 \(k\) 分钟，为了保证安全，每辆电车出发的前 \(k\) 分钟都不能有货车出发。特别地，乘客开始上车的瞬间和电车出发的瞬间，货车可以出发。
为了满足上述要求，必须要取消一些货车。选择合适的 \(t\)，使得取消的货车数最小。

注意到整个题目都与 \(h\) 无关，只需要知道所有 \(m_i\) 对 \(\dfrac{m}{2}\) 取模的结果
问题就变成了在 \(0\) 到 \(\dfrac{m}{2}-1\) 之间取一段长度为 \(m-k+1\) 的区间使发车的火车最多
双指针维护即可

E.Inverse Genealogy

给你树上的节点数，这棵树满足对于任意节点，要不为叶子节点，要不有两个子节点
定义不平衡节点当且仅当其中一个子结点的子树内节点个数至少是令一个子结点的子树内节点个数的两倍
给定 \(k\) 代表不平衡节点个数，判断是否有 \(n\) 个节点的树满足并构造一种合法方案

由树的性质首先可得 \(n\) 为奇数是有解的充要条件
重点在构造上，\(k\) 的上界可以由以下的构造方案得到：

          o/ \o   o/ \o   o/.../o/ \
o   o

这样构造有 \(\dfrac{n-3}{2}\) 个不平衡节点
而 \(k\) 的下界则是满二叉树或完全二叉树，当为满二叉树时，\(k\) 可以取到 \(0\)，否则最少取到 \(1\)
让我们把这两种构造方案结合起来：
用 \(2 \cdot (k-1)\) 个点（把最左下角的左儿子空出来）构造一棵有 \(k-2\) 个不平衡点的树，并在左下角接入一棵完全二叉树，这样正好是 \(k\) 个不平衡点（ \(k-2+1\) 再加上本来没有左儿子的那个点）
但如果剩余的 \(n-2\cdot (k-1)\) 个点只能构成满二叉树怎么办？
拿出来两个点直接接到根节点右子树上就好了
其实有个反例就是 n=9 k=2 但它其实无解