T1 合并果子

给自己的评价依旧三个字

拉完了

可能是因为之前做过很像的题吧 也是合并 也是相邻 用的是区间dp

P1880 [NOI1995] 石子合并

但是大哥你有没有想过那题求的是得分，区间dp集训也还没学到

最小值的最大值都把二分身份证号报出来了啊

…已经沉迷在dp的海洋里无法自拔了，也是完全没有往二分这方面想

于是链表暴力 结果逻辑不对答案还错了…

唉，估分0分，运气拿25分也不错了QwQ

本题思路小总结：

• 操作 k 次后剩余 n-k 个数，等价于把原序列切成 n-k 个连续段，每段和为最终一个数。
• 目标：最小化这些段和的最大值，经典二分答案。
• 二分下界 l = min(a[i])，上界 r = sum(a[i])，答案满足单调性。
• 判定函数 check(x)：贪心从左往右累加，当前和 >= x 就切一段，统计段数 cnt。
• 若 cnt >= n-k 则可行（因为可再合并多余的段，不会使最大值变大）。
• 二分查找最大的可行 x 并输出。
• 时间复杂度 O(n log sum)，满足 ∑n ≤ 2e6。

25pts

订正

补充：

突然发现自己订正时手欠long long的INF用的是0x7fffffffffffffff

注意还是换成0x3f3f3f3f3f3f3f3f比较好，这题也是侥幸过了，但很容易溢出（吃过一堑）

T2 旮旯给木

这是哪个神秘出题人想出来的名字，和旮旯给木也没关系啊…

还有为什么我感觉T1比T2难:(

总的来说这种题解题方法两种：

1. 用大数据找规律（有大数据的前提下）
2. 自己推出规律

但这题第二种方法其实也挺好做的

还有就是lowbityyds

本题思路小总结：

• 博弈结论：小 lizimin（后手）获胜 ⇔ 初始 x 是 2 的幂。
• 若 x = 2^k，则任何合法操作都会使 x 变成非 2 的幂，故当前玩家必败。
• 若 x 非 2 的幂，设最高位为 2^k，取 y = x xor 2^k（小于 x），可一步到达 2^k，将必败态交给对手。
• 因此非 2 的幂为必胜态，2 的幂为必败态。
• 判断条件：(x & -x) == x。
• 满足输出 Win，否则 Lose。

100pts

T3 晚安。

吐槽一下，这种直接给一长串数学公式不解释的题是真的难懂

光看数学公式都花了两分钟

然后看懂题也不知道咋dp:( 暴力都有点想不出来

于是换T4了

唉，还是得多刷点dp啊QAQ 连背包都快忘光哩 只会01哩

本题思路小总结：

• 将 h 位拆成低 h1、高 h2 两部分，代价拆为 w1[低][低] + w[高][高]，预处理两张表。
• 初始序列通过高位 DP：从每个初始数出发，从高到低逐位转移，得到 f[0][v] 直接求初始答案，同时将 f[h1][v] 存入 c[低][高]，表示该低半部分组内所有数与某高半部分的最大代价。
• 每次插入新数 (x, y)，先更新它所属低半部分组 c[y][*] = max(c[y][*], w[x][*])。
• 查询新数与已有数的最大代价：枚举低半部分组 j，用 c[j]+ w1[j][y] 更新全局答案。
• 所有操作仅需增量更新，复杂度 O(h·2^h + (n+q)·2^{h/2})，空间 O(2^h)。

（无提交记录）

订正

T4 括号序列

我的括号匹配问题啊，还记得上一次见到你，我只送了你一个栈，你欣然接受

这次怎么狮子大开口要树状数组了。？

连大佬们的线段树都满足不了你吗

还是轻敌了啊，没复习到树状数组，太可恶了

只能打个暴力骗分哩qwq

本题思路小总结：

• 令 ( 为 +1，) 为 -1，前缀和数组 a。合法括号序列等价于 a[0]=a[n]=0 且所有前缀和 >=0。翻转区间 [l,r] 等价于交换该段的前缀和镜像，条件可转化为对任意 i∈[l,r] 有 a[i] >= a[l-1]+a[r] - a[i]，且总和不改变。
• 使用 CDQ 分治，对跨越中点的区间计数。维护左侧最大值 mx 和右侧预处理的最小前缀限制 pre，利用树状数组动态维护右侧点对左侧的贡献。
• 两个树状数组分别统计 a[i] 和 mx-a[i] 的计数，支持前缀/后缀查询，时间复杂度 O(n log² n)（实际均摊 O(n log n)）。
• 注意 a 下标从 0 到 n，分治区间 [0,n]；树状数组坐标平移避免负数。
• 正确实现后缀查询（反向索引）避免数组越界；递归分治注意清空树状数组。

15pts

订正

《一看到我的比赛结果我就发现了三个问题》

1. 不要受到以前题目的影响，每道题都自己想一下，多审题，找关键信息
2. 赛前要多复习
3. 多练习一下dp，加强推导能力