random fact：难度预期：A|KL|BCIJ|FGH|DE，好像预期的相对顺序没有太大问题，但BCIJ这档比出题人想象的要难很多就是了（

random fact：DEL出题人：Wildfire032；其它题出题人：fried-chicken。

random fact：本场的 gpt-o3-mini-high 战绩是 9/12，没做出来的是 D(-1)E(-4)H(-4) 三题。在AC的题目中，gpt在F题有两发罚时、J题有一发罚时（但gpt写的是可以做 的做法）、L题有一发罚时，此外所有题都是一发过。我们AI真是太牛了。

A. 复制鸡

我们发现题目里的操作其实有点骗人，因为一个操作 可以看作 次长度为 的操作，因此我们取长度为 的区间操作可以做到任意操作的效果。于是考虑长为 的操作能做到什么？发现可以把一个数字 变成任意长的一段数字 ，因此反过来，一段连续的数字可以认为在原始数组中是一个数字。

于是，问题变成了，输入数组中连续的相同数字称为一段，问输入数组一共有几段，这个有多种求法，一种常见而好写的写法是：

ans += (a[i]!=a[i-1]);

random fact：在题面示例里用橙色做标注是Wida老师的好主意，但生成pdf的时候发现橙色生成不太出来，于是pdf题面中使用了下划线。

K. 鸡翻题

我们发现相邻两页的页码和一定是奇数（因为相邻两页一定是一个奇数和一个偶数），因此如果 为偶数一定做不到。

接下来样例提示我们，如果一本书开头的两页是 和 ，则相邻两页的页码之和依次是；否则，若一本书开头的两页是 和 ，则相邻两页的页码之和依次是 。我们发现这两个序列的区别是对 取模得 还是得 。因此，判断 取模 的结果和 取模 （这反映了书开头的是哪两页）的结果并比较即可。

random fact: 本题是最后为了调难度加入的两道简单题之一。

L. 变鸡器

首先最终得到的字符串是由原字符串删去偶数个字符所得到的，因此“chicken”必然是原串的一个子序列，且原字符串的长度为奇数。考虑删去的字符，字符集合是一定的，不难证明将这些字符能够删去的一个充要条件是出现次数最多的字符小于等于总需要删去字符数量的(必要性：对于一种字符，每次操作最多删去一个；充分性：用一个大根堆维护即可)。因此判断原串是否满足这些条件即可，时间复杂度.

C. 数列之和

为了防止被出题人骗着输出 获得WA（嘻嘻），我们最好先计算一下。

根据初高中数学知识，可以算出第 个数到第 个数的和为

样例提醒我们从奇偶性角度分析这个式子：若 都为奇数或都为偶数，则第一项为偶数、第二项为奇数；若 一个是奇数一个是偶数，则第一项为奇数、第二项为偶数。即 总是一个奇数乘以偶数，哪些数字不能分解成奇数乘以偶数的形式？形如 的整数都不可以。唯一一个例外是样例中的 ，因为此时奇数可以取 （这对应了 ），可以验证其它 都不能像这样拆成 和 相乘。

综上，结论是：除了形如 的整数不能表示，其他数字都可以表示。

代码实现上，相当于要找第 个非 形式的偶数。这里写法比较多、也不乏 O(1) 的式子，为了减少动脑，出题人的写法是二分答案为第 个偶数，检查

- (不超过 的 数) （输入的 ）

是否成立。

random fact：本题抄袭自 2024 海淀高三 10 月月考 21 题。

J. 铁刀磨成针

首先可以观察到：磨刀一定是从第一回合开始连续磨到不能磨为止，因为早磨刀在任何情况下都不会吃亏。所以磨刀策略是固定的。

我们需要决定的其实只是什么时候砍，这里又有一个结论：只考虑砍的时间是连续的一段、一定能考虑到最优方案（一个直觉的证明是：比如考虑某回合砍完之后隔了 4 回合才砍下一刀，这样的好处是什么，如果是为了隔 4 回合后刀的攻击力更高了、那就应该把最开始砍的若干回合直接往后挪 4 回合攻击更高）。

所以我们只要枚举从什么时候开始砍即可，又因为在 时，取第 秒作为砍的起点一定不优于在第 秒就开始砍，所以枚举开始砍的时间只需要枚举到第 秒，总复杂度 。

代码实现上，每回合砍的话就两种情况：又磨又砍、只砍，前者是每回合攻击力不变的、后者是一个每回合攻击力减一的等差数列，分别求和即可。

参考代码：

for(ll t=1;t<=min(n,y);t++){ // 开始砍的时间
    ll tmp=0;
    ll atk=x+t,s1=min(n,y)-t; // s1是 又磨又砍 阶段的时间
    tmp+=atk*s1; // 又磨又砍 阶段的伤害和
    tmp+=dc(atk,min(atk,n-min(n,y)+1)); // 只砍 阶段的伤害和
    // dc是手写的函数，输入首项、项数，求 -1 为公差的等差数列和
    ans=max(ans,tmp);
}

random fact：小火强烈建议出 的版本。

I. 小鸡的排列构造的checker

本题预期的做法是使用离线将查询排序的技巧，使用树状数组进行维护。

我们举一个例子说明该做法的思路，例如输入的数组 为 ，查询分别为 和 ，我们发现 查询相当于在问： 区间里有多少个小于等于 的数字？（因为这些数的个数能得出排序后 的位置）。

于是我们可以维护一个初始全 的树状数组，按照 从小到大给树状数组的对应位置 ，也就是在上述例子中，树状数组维护的原数组依次是：

状态1： 状态2： 状态3： 状态4： 状态5：

这样询问 其实是在对状态2的数组求 区间的和，使用树状数组可以做到；询问 其实是在对状态4的数组求 区间的和，使用树状数组可以做到。

因此，像上述过程一样，把所有 询问按照 从小到大排序，树状数组维护上述过程即可，复杂度 。

其它做法，例如主席树，没有刻意去卡。但一些复杂度 、 的做法和未关同步流cin的做法是比较容易 TLE 的。

B. 好火鸡猜拳

前置知识：使用动态规划求解最长上升子序列。

首先一个合法序列需要满足的要求其实就是 ，因此这很像最长上升子序列，回忆一下，最长上升子序列的状态定义是 表示以 处的数字结尾的最长上升子序列的长度。

我们想类似定义dp数组，但发现还有一个交换操作，但其实交换也并不麻烦、只会多出每个位置一个状态，即我们可以定义： 表示以位置 处作为结尾、位置 处是否交换（第二维为 表示交换）时所对应的最长合法序列。转移时假设当前位置为 ，枚举上一个位置 ，如果能把 （或）接到 (或)后面，则可以花费来删除两者中间的那段。

H. 小鸡的排列构造

对于限制长度为偶数（ 是偶数）的情况：我们发现输出倒序排列（）即可。

对于限制长度为奇数（ 是奇数）的情况：我们的第一反应可能是发现仅在时会让倒序排列出问题，于是试图在倒序排列的基础上微调，但如果走这条路就很容易写出错误的乱搞做法。下一个正确的想法是，考虑最难满足的情况是什么样的，也就是把所有限制拉满，因为限制区间长是奇数且不允许是 ，最小的区间长是 。所以我们考虑把限制拉满，也就是对于每个长为 的区间，我们把 三个限制都考虑到，这实际上相当于每个长为 的区间（把最小、中间、最大值分别当作 后）都是一个 的错排，而 的错排只有两种：。所以我们可以打表（比如令，把所有限制拉满、看什么排列满足）或手推得到答案，手推的方法是发现对于 的区间， 和 两个区间都要是错排，因此看 怎么能拼起来，发现直接可以拼成：（注意这里的数字只说明长为3区间内的大小关系、不是真实值），因此还原一下就是 。综上，限制长度为奇数时输出的就是形如 、这样的排列。

G. 目标是【L2】传说高手

第一问出锅了，非常抱歉。先介绍一下第二问。

第二问，假设答案为 ，则要求每张牌的使用率都可以通分后写成 的形式，我们发现这样的 最大的范围是 （因为 取 时可以表示所有的小数点后精确到一位的数字）。于是我们可以枚举 ，假设 ，则 ，我们随后要验证是否成立（注意左闭右开），这里需要使用整数验证而非浮点数（因为考虑如果 恰好是形如 这样的数字、则判断等号那里使用浮点数是无法准确判断的）。

对于第一问，先算出每张牌打出胜率的分数形式。一开始的std误以为答案就是，但其实反例也比较好找：对于输入 ，如果认为答案是 就错了，因为发现要求有三场输掉、而要求有三场获胜，导致 场不够分。

经过验题群一番激情四射的讨论，仍记分数形式为 （实现上，我们依然是对每张牌枚举其分母），则答案应当是 ，第一项对应了最大的胜场数要求、第二项对应了最大的败场数要求，同时这个值肯定是大于最大的的。我们可以据此构造一个方案，即把每张卡获胜的场都塞到 里、每张卡失败的场都赛到 。

我们会在今晚及时更新本题正确的数据，赛时代码不再进行重测，欢迎大家来补更新后的题。

F. 薪得体会

首先将公司按照 从小到大排序，我们想知道能否取到最大的 ，就是前 个公司能获取的最大offer是否大于等于 ，之中前 家公司的最大offer可以视作无视第 家公司之后的子问题，因此可以定义一个数组 表示只考虑前 家公司所能拿到的最大offer，每次比较 和 的大小关系来决定能否拿得到 ，这样就可以递推解决了。

实际上要考虑的情况还更多一些，std的核心部分如下：

// 下面代码里的 c[i].fs 是 ai，c[i].sc 是 ai+bi
sort(c+1,c+1+n,cmp1); // 按照 ai+bi 排序
for(int i=1;i<=n;i++){
    ans1[i]=ans1[i-1]; // ans1[i] 就是题解里的 ans[i]
    if(ans1[i-1]>=c[i].fs){ // 能否拿到 ai+bi 这个offer
        ans1[i]=max(ans1[i],c[i].sc);
    }
    else{
        ans1[i]=max(ans1[i],mx[i-1]);
        // else 说明拿不到这个offer，这说明 ai 一定大于此前所有的 ai'
        // 因此可以通过先选 ai 取到 mx[i-1]
    }
    ans1[i]=max(ans1[i],c[i].fs);
    mx[i]=max(mx[i-1],c[i].sc); // mx[i] 是 ai+bi 的前缀最大值
}

random fact：本来预期是个mid偏easy的题，结果出题人std就wa了两发，然后就意识到这题难度很神秘了。

D. Viva La Vida(Fried-Chicken's Version)

首先我们考察最终出现的图，我们先证明这个图中一定没有除了重边的其它环。采用反证法，假设有一个环，考察这个环中边权最大的边,记这个环上此边相邻的两条边为和,由于是这个环中边权最大的边因此其边权大于,因此城市不会修建边;同理城市也不会修建边,矛盾！

因此最终出现的图是森林，这说明某一条边要么联通两个块使得联通分量减一、要么是重边且不改变联通分量个数。有了这个性质之后本题有相当多的做法，最简单的做法是发现图的连通分量个数等于有多少条边 同时是城市相连所有边的边权最小者和的相连所有边的边权最小者（下称这样的边是好边），即这条边是城市和所相连的共条边的边权最小者。由于排列是随机的，可以得到这条边是好边的概率就是。而一共有条边，由期望的性质可以得到好边的数学期望是，即得。

E. 任造化落骰

数据随机的性质是很强的！本题也有多种做法，但本质上都是基于随机数据下对于一个左端点 ，所有 区间中具有不同的(区间最大值，区间最小值)对儿的种类不多，下面我们证明只有种。

为了便于理解，我们选择证明数列在区间上随着 的变化，最大值种类数的期望是的：第 个位置的数字是 最大值的概率为 （因为该区间一定有一个最大值，且每个数成为最大值的概率是相等的），因此，最大值种类数其实就是 ，即每个位置成为前缀最大值的概率相加就是最大值种类数的期望。根据调和级数， 是 的。

最小值的证明类似，因此在固定左端点时，随着右端点变化，得到的(区间最大值，区间最小值)对儿的种类数是的。

基于此性质，我们可以暴力的计算所有不同的(区间最大值，区间最小值)的出现次数（因为总共只有对儿，所以是能存的下的）。然后我们可以采用单调栈快速计算：对于每个左端点从到，用单调栈存储的所有前缀最大值位置和前缀最小值位置，由上面的证明我们可以知道这样的位置只有个，因此暴力计算即可。

由此我们得到了区间最大值乘最小值等于某个值有多少个区间（用map存储）。对于每个询问，只需在map上二分查找即可。时间复杂度。