内部比赛链接：周赛14

A. 修改序列 modify

考虑且最小值和最大值之差最多为 \(1\)，那么最终序列肯定呈 均分状态。又因为最终序列总和不变，则可以算出均分状态下的每一个值。然后每个数 \(A_i\) 则变成距离它最近的最终序列值就行。

B. 表示法 knuth

模拟题，注意需要在除了前缀 ten 之外的所有前缀前放一个 one.

C. 魔力塔 tower

自学过线段树优化建图，考试时不知道为什么忘了咋写。于是开始思考单调队列优化 dp，未果。然后只能打暴力，忘了咋打 bfs（？），感觉 dijstra 好写，骗了 75。 \(\color{white}{CF786B}\)

线段树优化建图基本操作：点到区间连边。

如下图，若节点 \(8\) 向区间 \([3,7]\) 连边。

别忘了，还有区间到点连边的操作（这道题没有），如果这两个操作混合起来，则需要建立出树和入树。

代码：code

这道题还有暴力过题做法，但我不会。

D. 卡牌 card

理一理题面，初始有两堆牌，初始时第一堆只有一张牌 \(S\)，第二堆的牌从上到下由输入给出。

有孵化和克制两种规则，孵化 \(C,A,B\) 表示若第一堆上面那张为 \(C\)，可以将其变成两张 \(A,B\)。克制 \(A,B\) 表示若第一堆为最上面为 \(A\)，第二堆最上面为 \(B\)，两张牌可以同时消失。

区间 dp，第一堆的牌其实可以克制一段连续区间。设 \(dp_{i,j,x}\) 表示第一堆的牌 \(x\) 能否消除第二堆牌从上到下 \([i,j]\)。

通过给出的克制关系，初始化所有 \(dp_{i,i,j}\)。

通过给出的孵化关系进行转移：\(dp_{i,j,x}=dp_{i,k,a}\&dp_{k+1,j,b}\)，表示牌 \(x\) 孵化成 \(A,B\)，来克制 \([i,k]\) 和 \([k+1,j]\)