题目大意：对于一个序列 \(A=a_i,a_i\in[1,m]\) ，定义 \(f(A)\) 为
对于一个全零的初始序列，每次选择一个区间对于某一个值取 \(\max\) ，最少生成 \(A\) 的步数
求所有 \(m^n\) 种 \(A\) 的 \(f(A)\) 之和
首先考虑 \(f(A)\) 的计算，显然可以采用如下方法
1 | b[i]=0 |
那么考虑计算一个区间 \([l,r]\) 被 \(\text{Solve}\) 的次数
显然区间 \([l,r]\) 被 \(\text{Solve}\) 当且仅当
\(\min\{a_i|i\in[l,r]\}>\max(a_{l-1},a_{r+1})\)
对于不同的 \(r-l+1\) ，枚举 \(\min\) ，计算方案数即可
注意考虑 \(l=1\or r=n\) 的边界情况
1 | const int N=5010,P=998244353; |
白色的数轴上有 \(n\) 个球 \(a_i\) ，给定若干递增且不交的区间 \([t_i,t_{i+1})\)
每次选择一个球向左或者向右滚，且将滚过的一段反色
求最小步数恰好仅将给定区间染黑色，或者确定不存在方案
首先显然可以发现，每个小球只会滚过一段区间一次
设小球 \(i\) 最终停在 \(b_i\) ，则滚过这段数轴会被反色，且代价为 \(|a_i-b_i|\)
将最终颜色做异或差分，那么对于目标的反色，我们认为就是在每个 \(t_i\) 处放置了一个1
而对于所有 \(a_i\) ，就是在 \(a_i,b_i\) 处分别放置了一个1，这样就完全避免了关于 \(a_i,b_i\) 大小关系的问题
由于已经固定了 \(a_i\) (设 \(a_i\) 已经排好序)，我们需要决策 \(b_i\)
那么可以预先得到哪些位置需要放置奇数个 \(b_i\) ，设这个集合为 \(pos\)
若 \(|pos|>n\) ，显然无解
否则， \(b_i\) 的放置仅有两种情况
1.放在某一个 \(pos_i\) 处
2.让两个 \(b_i\) 放在同一个位置
对于 \(a,pos\) 排序之后的情况，显然较小的 \(a_i\) 会匹配较小的 \(pos_i\) ，代价为 \(|a_i-pos_i|\)
而情况2用掉的两个 \(b_i\) ，选择使用 \(b_i,b_{i+1}\) 一定不劣，并且代价就是 \(a_{i+1}-a_i\)
那么令 \(dp_{i,j}\) 表示前 \(i\) 个 \(a_i\) ，已经匹配了 \(j\) 个 \(pos_j\) 的代价，如上决策即可
1 |
|
考虑用 \(\text{FWT}\) 来理解这个式子，容易发现 \(\text{FWT}\) 之后求积的式子，满足
对于任意 \((u_i,v_i)\)
如果 \(u_i,v_i\) 中有一者被选择，答案为0，否则权值 \(\times 2\)
那么显然对于一个连通块，设其大小为 \(c\) ，放在一起考虑
在 \(\text{FWT}\) 的式子里它们同时出现或者同时不出现
枚举最后 \(\text{FWT}\) 回来时的项与在这 \(c\) 个位置中出现 \(i\) 个
对于选择这个连通块的情况，贡献为 \((-1)^i\)
对于不选的情况，贡献为 \(1\)
显然只有 \(2|i\) 时贡献为2，乘上组合数完成转移，连通块之间背包合并
就能得到最终计算答案的项中出现了几个1，然后与 \(\text{FWT}\) 的系数合并即可
\[ \ \]
对于一个连通块，考虑取出一个生成树
容易发现，仅使用这个生成树上的边，就能构成任何一个包含 \(2k\) 个奇点的情况
对于多余的边，类似异或线性基，它们都是可选可不选的
于是直接统计答案即可
Sol1 和 Sol2 的式子是一样的
1 | const int N=5010,P=998244353; |
题目大意：给定一个长度为 \(2n\) 的非负环序列 \(x_0,x_1,\cdots x_{2n-1}\) ，以及 \(2n\) 条限制，每条都是
\(\forall A_i,\sum_{j=0}^{n-1} x_{i+j\mod 2n}\ge A_i\)
求最小化 \(\sum x_i\)
\[ \ \]
转化为前缀和作差之后，令人联想到差分约束，但是难以处理跨过环末的限制
于是二分答案 \(s=x_{2n-1}\) ，建立最长路图
\(\forall i<n,dis_{i+n}\ge dis_{i}+A_i\)
\(\forall i\ge n,dis_{i-n}\ge dis_{i}+A_i-s\)
\(\forall i<2n-1,dis_{i+1}\leq dis_i\)
那么无解的条件就是：存在正环或者求得 \(dis_{2n-1}>s\)
自然无法直接通过 \(\text{SPFA}\) 来跑。。。
考虑所有的边构成了一条 \(0-2n-1\) 的零链 和若干极小的二元环
如果二元环出现正环则无解，否则任意一条最长路路径总是可以描述为
\(i<j<n , i(+n)\rightarrow j(+n)\)
在中间点 \(k\) 可以选择花费0的代价向后走，或者
\(k<n:k\rightarrow k+n,cost=A_k\)
\(k\ge n:k\rightarrow k-n,cost=A_k-s\)
也就是在 \(k,k+n\) 之间反复横跳，由此发现一条路径就是
从 \(0-n-1\) 进行扫描，并且允许中间 \(\pm n\) 横跳
（当然这里漏掉了一个特殊边，即 \(dis_{n}\ge dis_{n-1}\) ，这是构成环的边）
这样写出一个变种的 \(\text{Bellman Ford}\) ，由于图的特殊性，只需要常数轮即可确定正环
具体的，当图上不存在正环时，扫描最多经过一次环就会停止更新
也就是这样横跳的扫描更新只会进行常数轮（2轮？）
如果若干轮后依然在更新，说明出现了正环
1 |
|
话说我只能蒙结论。。。
打表或者理性分析可以发现一些性质
2.如果确定 \(E_i\) 从小到大的顺序 \(P_i\) ，就能确定一组最优的 \(E_i\)
（但是对于平凡的 \(P_i\) ，这个过程会极其恶心，因此考虑特殊化 \(P_i\) ）
3.设 \(\displaystyle f(P)=\sum_{i=2}^n dis(P_{i-1},P_i)\) ，即遍历排列的距离和
则 \(\max\{E_i\}\ge \min\{f(P)\}+1\)
显然
由此确定了一个下界，接下来将说明可以取到下界
1.对于一个排列 \(P_{i}\) ，如果 \(P_i\) 是一组 \(\text{dfs}\) 序，那么满足 \(\max\{E_i\}=f(P)+1\) (容易模拟发现)
由此确定了答案 \(P\) 可以是任何一组以某一条直径两个端点为 \(P_1,P_n\) 的 \(\text{dfs}\) 序
容易给出一个合法解，代码实现极为暴力
1 | const int N=2e5+10,INF=1e9+10; |
题目大意：计算由 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 构成的序列，且 包含恰好 \(k\) 个和为零的区间 的数量
显然需要转化为前缀和，通过前缀和相等的二元组数确定和为0的数量
而恰好 \(n\) 个 \(+1,-1\) 可以转化为 \(s_{2n}=0\)
设 \(m=2n+1\) ，接下来我们要计算 \(m\) 个元素，且 \(s_1=s_m=0,s_{i}=s_{i-1}\pm 1\) 的序列
\(s_i\) 的变化是连续的，考虑分为 \(s_i\ge 0,s_i<0\) 的两部分
以 \(\ge 0\) 为例，从高到低确定每个连续的峰折线的情况，折线组的位置不重要，只需要知道个数
令 \(dp_{i,j,c}\) 表示当前 \(i\) 个元素确定，且已经确定的元素分成了 \(j\) 段，得到 \(c\) 个相同对的方案数
每个段中可能包含折线组，且两端一定是当前的最低值，状态数为 \(O(n^4)\)
每次 \(dp\) 在当前状态上扩展下一层的情况，由于变化连续，得到新的状态
1.每个段两边应该出现新的位置
2.两个段向两边扩展时，可能共用一个位置
3.可能出现新的峰顶
根据2,3的情况，组合数转移
如果直接枚举2,3情况，复杂度为 \(O(n^6)\)
实际上容易发现2,3情况可以放在一起处理
具体的，对于新出现的 \(j+1\) 个位置（也就是每两个段之间的间隔）是一定会出现的，用这 \(j+1\) 个可以合并为一整个段
剩余的情况，额外插入一个元素，就是在 \(j+1\) 个位置中分配，且每额外加入一个就能额外产生一个新的段
复杂度为 \(O(n^5)\)
最终合并 \(s_i\ge 0,s_i<0\) 的两部分，由于 \(s_1=s_m=0\) ，所以开头结尾两端必须是0，然后两部分的段交替排列
1 |
|
我们将一个操作序列看做由左右括号，空格构成的字符串，则序列大致长这个样子
\(\text{_ ( ( ) _ ( ) ) ( _ ( ( ) ) ( }\)
很显然，一个失配的左括号只能在最外层出现，而空格可以出现在任意位置
dp一个括号序列让人想到区间dp，但是这个题目的区间实际只需要用长度就可以描述
令 \(dp[t][l][r][f1][f2]\) 表示用 \(t\) 的时间从 \(l\) 走到 \(r\) ， \(f1\) 表示是不是最外层括号， \(f2\) 表示当前 \(dp\) 是否受到单纯括号序列的限制
其中，引入的单纯括号序列是为了防止出现重复转移，其意思就是这个括号序列两端必须是一对匹配的左右括号，而中间随意
转移大致如下:
1.那么对于非单纯的括号序列，可以在序列插入空格或者失配的左括号(需要满足 \(f1\) )，从 \(dp[t-1]\) 转移过来
2.对于任何的括号序列，都可以在两端找到匹配的的左右括号，从 \(dp[t-2]\) 转移过来，且完成匹配后 \(f1\) 应为 \(0\)
3.且一个非单纯的括号序列是可以分割的，为了不重复，强制分割的左序列是单纯的即可
实际会发现，一个单纯的括号序列可以认为一定不是最外层括号，即 \(f2\) 为真时， \(f1\) 一定为假，所以可以压缩为三种状态
1 |
|
不知道题解在写什么.jpg
令 \(dp_{i,a,b,j}\) 表示当前时刻 \(i\) ，两队比分为 \(a,b\) ，球在 \(j\) 手上的概率
转移非常简单就不说了，单次转移为 \(O(n)\) ，复杂度为 \(O(n^2r^2T)\)
在优秀卡常+O2下跑进700ms
优化的话: 1.float
2.分小块加速
3.循环展开
1 |
|
\[\ \]
定义每个球进的时间为关键点，我们发现关键点的状态非常单一，只有两种
一个合法的转移序列可以被分为若干关键点的段以及最后一段到达 \(T\) 之后停止转移
考虑预处理两个关键点之间的转移概率
令 \(g_{a,b,i}\) 为当球在 \(a\) 队一号队员时， \(i\) 次后 \(b\) 队进球的概率
可以枚举 \(a\) ，类似上面的 \(dp\) ，去掉比分的一维即可
预处理复杂度为 \(O(Tn^2)\)
然后 \(dp\) 时直接枚举两个关键点转移，令
\(h_{i,a,b,j}\) 时刻 \(i\) 比分为 \(a,b\) ，球在 \(j\) 队一号队员手上的概率
转移分两种
1.枚举下一个在 \(T\) 以内的关键点转移
复杂度为 \(O(T)\)
2.考虑在 \(T\) 以内的时间不再出现进球了
需要预处理出当球在 \(i\) 队手上时， \(j\) 次内出现进球的概率 \(s_{i,j}\) ，这个直接由 \(g\) 数组累前缀和即可
\(dp\) 关键点的复杂度为 \(O(T^2r^2)\)
大概比上面代码快4-5倍
1 |
|
其实挺妙的一个数据结构题
题意: 给定一个A串，对于查询的每个 \(B\) 串，从头开始匹配匹配 \(A\) 的每个后缀，每次匹配失败的代价是 \(\text{LCP}+1\) 可，匹配成功的代价是 \(|B|\) ，且立即停止，求代价总和
设 \(A\) 串长为 \(n\) ，查询个数为 \(q\) ，查询总长为 \(m\)
我们知道求两个串的 \(\text{LCP}\) 可以把两个串中间放一个符号分开，跑后缀数组/后缀自动机
但是首先是 \(m=3\cdot 10^6\) ，内存就开不下
而且发现，如果 \(|B|\) 的某个前缀未出现在 \(A\) 中，后面的部分都不造成贡献，所以可以在 \(A\) 串中定位 \(B\) 的每个前缀
这样就只需要求 \(A\) 的后缀数组即可，然而，这个并不好实现
假设当前已经定位了一个长度为 \(i\) 的前缀，其对应的合法后缀排名范围为 \([L_i,R_i]\)
那么接下来就是在当前前缀上接上下一个字符 \(c\) ，这个如果再外加数据结构并不好实现
考虑后缀数组的性质， \([L_i,R_i]\) 这些后缀前 \(d\) 个字符相同， \(d+1\) 个字符呈单调非递减
所以字符 \(c\) 出现的范围也一定是一段区间，可以直接两次二分得到
这样查询 \([L_i,R_i]\) 的复杂度为 \(\log n\) ，这样就用 \(O(m\log n)\) 的复杂度完成了串定位
如果不考虑每次完成匹配后停止，其实答案就是 \(\sum R_i-L_i+1\) ，即 \(\sum_i LCP_i=\sum_i \sum_j [LCP_j\ge i]\)
设最终的匹配位置为 \(p\) ，这个位置可以用线段树在最后的一段 \([L_{|B|},R_{|B|}]\) 中求最小值得到
考虑减掉多余的部分，即减去实际位置 \(>p\) 的且在后缀数组排名在 \([L_i,R_i]\) 中的部分
可以把所有的 \([L_i,R_i]\) 拿出来作为，离线询问，用树状数组维护查询，复杂度为 \(O((n+m)\log n)\)
因此总复杂度为 \(O((n+m)\log n)\)
1 |
|
考虑每个小区间 \([x_i,x_{i+1}]\) 中，外部光照进来只能是这样
其中两边是光源，红色表示被照到了
那么所有合法的被照到的段可以表示为 \([x_i,x_{i+1}]\) 中的两个小段，即
1.左边照进来的 \([s0_i,x_{i+1}]\)
2.右边照进来的 \([x_i,s1_i]\)
考虑从左到右维护可能照到右边的较优光源
显然对于每一个光源都有一个当前能遮住它最多的城市，构成(光源，限制城市)这样的点对
对于每一个较优的这样的点对 可以维护一个单调栈，维护出来应该是这样的
有几个较为显然的性质:
1.所有点对的 \(h_i\) 递减，否则要么是上一个光源被完全遮住了，要么是这个点可以遮住上一个光源更多
2.靠右的点对能够覆盖的范围较大，即可行区间的左端点较小
否则它此时不会产生贡献，而当后面较高的点进来时，相对更矮的它也更容易被遮住
实际上，这样的形状就会构成一个类似上凸包的东西，但是凸包上只有一部分点产生贡献
\[ \ \]
考虑依次加入点 \((x_i,h_i)\) ，显然可以弹掉 \(h_j<h_i\) 的所有点对(为了防止下面计算左端点时出现问题)
接下来的情况，类似维护凸包，但是要考虑更新限制城市 或者 弹掉点对
\[ \ \]
对于向左的情况，反着求一遍即可，最后可以减去两种区间都覆盖不到的部分
1 |
|