本来以为会保龄的，没想到一分没挂，感觉好像阳寿少了一点了（（（
T1
题面：给定一个数组 AAA，你需要生成一个序列 BBB，使 BBB 包含 AAA 所有的非空子集。用序列 BBB 生成一个新的序列 CCC，使 CCC 的每一项都与 BBB 的一项的最大值一一对应。求 CCC 的所有众数中的最大值
老师说这题是个人都做得出来。
显然，AAA 中的最大值至少会占 CCC 中的一半。所以直接输出 AAA 的最大值即可。
时间复杂度：O(n)O(n)O(n)。
个人感觉 T3 比 T2 简单，先开的题也是 T3，所以我先讲 T3。
T3
由于题意非常重要，所以直接放题面。
题面：有 2N2N2N 张卡牌从左到右依次放在桌子上，编号为 1,2,...,2N1,2,...,2N1,2,...,2N，卡牌 iii 上写有整数 AiA_iAi 。对于 x=1,2,3,4,5,...,Nx=1,2,3,4,5,...,Nx=1,2,3,4,5,...,N，存在恰好两张卡牌上写的整数为 xxx。
24老师吃饱了没事干，因此决定用这些卡牌玩一个游戏；该游戏的流程如下：
依次考虑卡牌 1,2,3,...,2N1,2,3,...,2N1,2,3,...,2N：
* 24老师决定是否拿起这张卡牌：如果他决定拿起，那么依次进行以下的步骤；如果他决定不拿起该卡牌（跳过该卡牌），则跳过以下的步骤；
* 如果24老师的手中持有一张写有 AiA_iAi 的卡牌，那么该卡牌和卡牌 iii 同时消失，他获得 VAiV_{A_i}VAi 分；
* 如果24老师左手中有一张卡牌，那么他将其丢弃；
* 如果24老师右手中有一张卡牌，那么他将其转移到左手；
* 如果卡牌 iii 没有在步骤 2 中消失，那么他将其放在右手中。
通过上面的流程，每次得到的分数之和即为24老师的最终得分。
请求出24老师能获得的最大得分。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
显然被丢掉的牌没有用，所以我们应使所有选中的牌都被消除，问题的关键在于如何选择可以使得分最大。
注意到步骤 3，我们发现即使右手的牌被消除，左手的牌依旧会丢掉。所以当一张牌被拿起，并且没有被消除时，最多只能再拿一张其他牌。
注意到这题是一个很染色的题目，而且染色有一个很简便的转换成区间问题的做法，所以考虑将本题转化成区间问题。
染色转化成区间问题后变为没有重复元素的区间的分数和的最大值，这题则转化成区间中可以与一个区间有交集，但不能包含那个区间的分数和的最大值。例如下图中，
区间 1,41,41,4、1,21,21,2 都是合法的选择方案，但是 3,43,43,4 就不能选。
对此，我使用了一个特别猎奇的做法：
定义 lil_ili 为第 iii 张牌前面写上的整数与 AiA_iAi 相同的卡牌的下标，定义 dp[i][j]dp[i][j]dp[i][j] 为插入了尾下标为 iii 的区间后，iii 是否与前面的一个区间有交集，的得分最大值。则有如下状态转移方程：
dp[i][0]=(maxj=1j<limax{dp[j][0],dp[j][1]})+VAidp[i][1]=(maxj<i∧lj<lidp[j][0])+VAidp[i][0]=(\max_{j=1}^{j\lt l_i}\max\{dp[j][0],dp[j][1]\})+V_{A_i}\\ dp[i][1]=(\max_{j\lt i∧l_j\lt l_i} dp[j][0])+V_{A_i} dp[i][0]=(j=1maxj<li max{dp[j][0],dp[j][1]})+VAi dp[i][1]=(j<i∧lj <li max dp[j][0])+VAi
按照这个转移方程写的初始代码如下：
时间复杂度：O(n2)O(n^2)O(n2)。
注意到最大值都是以 111 开始的，所以可以使用树状数组优化，分别维护 max{dp[j][0],dp[j][1]}\max\{dp[j][0],dp[j][1]\}max{dp[j][0],dp[j][1]}，dp[j][1](1≤lj≤i)dp[j][1](1\le l_j\le i)dp[j][1](1≤lj ≤i) 的最大值。
时间复杂度：O(nlogn)O(n\log n)O(nlogn)。
T2
题意解析：给定一个 NNN 个节点 MMM 条边的图，你可以进行一次操作，给任意 u,vu,vu,v 两个点连一条长度为 LLL 的边。求有多少种方案可以使 S→TS\rarr TS→T 的最短路长度 ≤K\le K≤K。
我们可以跑两遍 Dij 求出 S→i,i→TS\to i,i\to TS→i,i→T 的最短路 dis1[i],dis2[i]dis1[i],dis2[i]dis1[i],dis2[i]，然后二分求出有多少个满足 dis1[i]+dis2[i]+L≤Kdis1[i]+dis2[i]+L\le Kdis1[i]+dis2[i]+L≤K 即可。特判 dis1[T]≤Kdis1[T]\le Kdis1[T]≤K 的情况，此时应输出 N(N−1)2\frac{N(N-1)}{2}2N(N−1) 。这么简单的做法这个贵物甚至想了一个多小时
时间复杂度：O(mlogm+nlogn)O(m\log m+n\log n)O(mlogm+nlogn)。
T4 写了个 O(n3)O(n^3)O(n3)，看看能不能拿到 40pts。
赛后
分出来了， 100+100+100+40=340100+100+100+40=340100+100+100+40=340，一分没挂
什么你说 T4 O(n6)O(n^6)O(n6) 暴力加剪枝能过 40pts？那我辛辛苦苦优化的算什么？？？
