ucup 2nd 做题记录

· · 个人记录

stage1

G

题意

给一个长度为 n （ n\le 10^5 ）的序列 a ，强制在线地每次 ban 掉一个元素，求当前不包含被 ban 元素的区间中，逆序对个数最多的有多少个

#### 题解 显然区间越大越好，所以只用考虑顶到头的区间 再区间 $[l,r]$ 中 ban 掉元素 $u$ ，形成两个新的区间 $[l,u-1]$ 和 $[u+1,r]$ 我们需要计算两个新区间内的逆序对个数 我们已知 $[l,r]$ 内的逆序对个数，可以暴力求长度较小的区间逆序对，再用主席树， $O(\min\{u-l,r-u\}\log n)$ 的时间求跨过两边的逆序对个数，减一下就可以得出长度较长的区间的逆序对个数 这样复杂度可以类比启发式合并，复杂度为 $O(n\log^2 n)

code

stage2

纯垃圾，别打了（

K

题意

有 n （n\le 5\times 10^4）个学生，每个学生可以在 k （k\le 10）个选项中选一个，第 i 个学生选 j 会有 c_{i,j} 的代价。对于每个选项 i ，选此项的人数不能多于 a_i 。

求如安排每个学生的选项使得总代价最小。

题解

首先一眼费用流，学生一列点，选项一列点，源点到学生连边，学生到选项连费用为 c_{i,j} 流量为 1 的边，选项到汇点连流量为 a_j 的边

但是费用流太慢，考虑模拟费用流

考虑一个残余网络，根据费用流的原理，我们可以在上面任意选一条最短路，流 1 的流量

只考虑形如：“源点 \to 学生 \to 选项 \to 学生 \to\cdots\to 选项 \to 汇点”，的路径，可以覆盖所有情况

考虑从选项到汇点的最短路，我们维护两两选项点间经过一次学生点的最短路，建立一个只包含选项点和汇点的图，再对这个图做SPFA就能 O(k^3) 得到选项到汇点的最短路

若一个学生点 u 有对选项点 v 的流量，那么从这条边推流再流向另一个选项 w 的权值就是 -c_{u,v}+c_{u,w} 用 k^2 个优先队列就能维护所有 v,w 之间最小的权值

我们现在已经得到了每个选项到汇点的最短路 dis_j ，开 k 个优先队列，第 j 个维护现在所有没流的学生 i 到 j 选项的最小距离 c_{i,j} ，选取 c_{i,j}+dis_j 最小的一条路径

路径取出来后，我们需要给路径上每个学生改换流向的选项，更新两个优先队列，这两个优先队列都要加懒删除

最终答案就是每一轮的 c_{i,j}+dis_j 加起来

code

D

题意

在 n\times m 的格子里最多能放多少国际象棋的象，输出方案

题解

人类智慧题/tuu

我的做法大概是把两个短边放满，然后如果短边为奇数就在中间放一个平行于长边长条，如果偶数就在中间放好多1\times 2的平行于短边的东西，需要特判 1\times 1 、 长边等于短边

code

L

题意

翻牌游戏，有 A-Y 25种颜色每种各两张牌，共 50 张，每轮先翻开一张牌，再翻开另外一张牌（不是同时，先看完第一张再决策第二张），如果相同就保留翻开，否则都返回去且算一次 miss

通讯题，第一次运行程序可以知道每张牌的内容，可以在每张牌上留下 0 或者 1 。第二次运行程序，根拒上次留下的 01 ，要求在平均 13.5 次 miss 以内翻开所有牌 （如果没有 01 的话最优策略需要平均 14.83 次）

题解

（只写完了 dp ，后面没时间写了，我相信应该是对的）

给每种颜色的两张牌分别留下一个 0 和一个 1

考虑 dp ，设 f_{i,u,v} 为当前共有 2i 张牌没翻开，已知了 u 张 0 牌，已知 v 张 1 牌

转移大概就是枚举接下来决策摸一张未知 0 牌还是一张未知 1 牌，翻开后可能与已知牌配对，也可能不会配对，不配对的话下一张要摸 0 牌还是 1 牌，第二张可能和第一张配对，也可能和已知牌配对，也可能不配对

dp 完需要大概 12.9 次，感觉很对

upd：只需要用13次 miss 得知所有1牌，然后每次翻0牌再翻对应的1牌