上接NOIP备考
T1 难度普及,暴力N^3其实卡不掉。
当然也可以用STL函数a.compare(b)
T2 难度提高,讲讲推导思路
Case3和4是送的,用数组模拟即可
然后发现只有最后的赋值是有用的,然后有贪心思路:
- 有矛盾则无解(扩展域/带权都可以维护)
- 与U连接则无解
然后可以发现我们新建一个无解结点,然后与它相连的变量都无解,再用上面的策略维护即可。
T4 难度提高,讲讲推导思路
36pts有O(n^2+m)的简单做法。
56pts可以线段树优化。
对于A性质,首先可以发现有效点只有最多10^7个。
离散化后对于这些点发现可以贪心,然后有效点变成了10^5个。且一次循环只贡献最多10^3复杂度
最终复杂度在10^8级别,实现好可过。
对于B性质,直接贪心。
对于C性质,区间只有分离和相交,没有重合。基本是正解分了。
不难发现A性质做法可以扩展,对于所有有效点,只需要用线段树转移即可。
直接维护等差数列很麻烦,不如考虑维护左端点。
C性质可以直接求解了。
如果还有包含和重合,可以改变包含中较大区间贡献,然后用同样方法维护。
T3 思维题。
C1 可以判断是否相同。
然后可以发现要求实质上是能不能扩展使得任意位置的数具有相同偏序关系。
不难想到有最优子结构可以DP,建立二维数组f[i][j]表示A到i,B到j是否有可行解。
然后发现可以建成二维表格,直接DP是O(n^2),有35pts。
然后发现拐点最优是极值点,可以优化到O(n)复杂度。
结语:
此次比赛难度略高于CSP2023,但并不存在不可做题。
特点是涉及算法都很基本,且只有一个核心idea,本套试卷在省一级别上较有区分度,但不好区分省队及以上选手。
考场策略:
- 识别T1签到,用最简洁方式解决,因为小写字符串两两不同,所以难以卡掉
- 根据部分分推出剩下题目的正解。
- 检查多测清空,数组大小,查错。