T1

难度普及，暴力N^3其实卡不掉。

当然也可以用STL函数a.compare(b)

T2

难度提高，讲讲推导思路

Case3和4是送的，用数组模拟即可

然后发现只有最后的赋值是有用的，然后有贪心思路：

1. 有矛盾则无解（扩展域/带权都可以维护）
2. 与U连接则无解

无解等价于有奇数环，观察可以发现，用带权维持到根的奇偶性，在连环哪一步判断即可。

然后可以发现我们新建一个无解结点，然后与它相连的变量都无解，再用上面的策略维护即可。

T4

难度提高，讲讲推导思路

36pts有O(n^2+m)的简单做法。

56pts可以线段树优化。

值得一提的是有弱化版 CF115E

首先对于52分，有思路维护前面最大值。

然而不能直接转移，因为要满足k的限制。

解决思路先不说，看一下性质B，可以直接贪心，get 44pts

贪心思路具体是枚举m个区间边界，对于之前的dp式子，变式：

$f_i=f_j+w(j,i)-d*(i-j-1)$

为了消除后效性，规定 $f_i$ 为 i 天不跑的最大贡献。

如果我们对于每个挑战，都动态将在 $l-1$ 之前的 $f_i$ 加上 $w$，就可以消掉 $w(j,i)$ 因为显然之后遍历到会累积当前挑战。

然后明显的处理区间端点前后一个一个点以外的点转移都更劣，离散化后跑DP即可。

T3

思维题。

C1 可以判断是否相同。

然后可以发现要求实质上是能不能扩展使得任意位置的数具有相同偏序关系。

不难想到有最优子结构可以DP,建立二维数组f[i][j]表示A到i,B到j是否有可行解。

然后发现可以建成二维表格，直接DP是O(n^2)，有35pts，预先扫描特判有四十五分。

值得一提的是这道题bfs爆搜也能拿到四十分，但想想并不奇怪，因为转折点的数量似乎可以非常少。

关于优化，明显地在应大于B时有元素小于B是无解的。

而明显，我们的目标是要让最后一个元素和B的最后一个元素对齐。

所以有贪心策略，对于可以控制的格子维护到最右端，在继续搜一定不会劣于&O(n^2)&，如果用ST表可以达到O(nlogn)复杂度，事实上可以拿到100分。

但是还有线性做法，对于特殊性质，考虑所有有效扩展，则只要中间无法扩展的数合法即可，而快速判断非法等价于判断其中最大（如最小数）的数会大于上一个拓展中拓展的所有B中的数，维护前缀最大值比较即可。

特殊性质可以这么做是因为最后一行及最后一列都为1，如果不是呢？

因为没有这个性质所以前面能拓展到哪里就很重要了。

所以直接把第一个序列按最小值分开（两段都含最小值），第二个序列按最大值分开（两段都含最大值），两部分分别跑特殊性质即可。

结语：

此次比赛难度略高于CSP2023，但并不存在不可做题。

特点是涉及算法都很基本，且只有一个核心idea，本套试卷在省一级别上较有区分度，但不好区分省队及以上选手。

考场策略：

1. 识别T1签到，用最简洁方式解决，因为小写字符串两两不同，所以难以卡掉
2. 根据部分分推出剩下题目的正解。
3. 检查多测清空，数组大小，查错。