11.11 写题

AGC001F

已单独写题解就不粘过来了。

Gym101806T

根据某知名贪心,先给 LL 加上 DD ,然后按照 LL 排序,可以得到一个正确的顺序,最后答案的序列一定是在这个顺序下选取的。

相当于我们需要选择一个最长子序列,满足这个子序列任意一段前缀的和小于等于这个位置的 LL

这个问题类似于 LIS 。有一种直接贪心的做法。我们考虑对当前位置,维护出满足当前位置以及之前所有位置的限制的的最长的子序列,且满足 D\sum D 尽量小。

我们用堆维护当前子序列中所有的 DD 。每次到一个位置 ii ,我们先尝试把这个数给加进去,然后看看是否满足限制。如果不满足,我们弹出堆中最大的元素。不难发现弹出一个元素后一定可以满足这个位置的限制,同时由于弹出的是最大的,我们可以得到这个位置前缀的最优序列。

复杂度 O(nlogn)O(n\log n)

阅读全文 »

AGC006

AGC006D

非常有意思的一个题。

直接做复杂度是 O(n2)O(n^2) 的而且看不出什么优化空间。

“中位数”的题往往和二分答案有关,因为这样可以转化成区间内 0/10/1 的个数。这个题,可以先二分答案,设二分出来的值是 xx ,我们尝试判断第一层的数是否 x\le x 。我们把所有 x\le x 的数设置为 00 ,把剩下的数设置为 11 。不难发现这个序列在进行操作后得到的序列的 0101 含义是不变的。现在我们转化成了一个 0101 序列进行操作,最后堆顶的数是 00 还是 11

然后画个图手玩一下,会发现所有长度 2\ge 2 的连续段在往上的过程中必然会复读,而长度为 11 的连续段必然会翻转。而在 2\ge 2 的连续段复读的过程中会和附近翻转的 0101 变得相同。而且,一个长度不少于 22 的连续段一定会一直向左同化,直到遇到一个同样长度不小于 22 的连续段。

现在问题就变得很简单了。考虑最中间这个格子最早会被谁同化,就是枚举它左边和右边看看第一个长度大于等于 22 的连续段的距离。如果不会被同化,也就是说相邻互不相同,那么这个东西就会一直反色直到结束。

复杂度 O(nlogn)O(n\log n)

阅读全文 »

AGC005

A STring

操作这么多次。。显然能消的 ST 都没了变成了 TTT...TSSS...S 。不难发现其实就是括号匹配,直接拿栈匹配就行了。

B Minimum Sum

按最小值来分治即可。每次贡献就是左右两端长度加 11 的乘积。

复杂度 O(nlogn)O(n\log n),需要预处理 ST 表。

C Tree Restoring

考虑这 nn 个数字中最大的,必然是直径长度。然后我们先把直径画出来:

image.png

不难发现,对于 [d2,d][\lceil\frac d 2\rceil,d] 的长度我们至少的有两个点,才能构造出直径。然后如果多于 22 ,比如需要多构造一个直径长度的点就可以像红色边那样挂一个点,如果需要构造多一个长度为 33 可以在绿边位置挂一个点。所以这区间内的长度都可以有多于二任意多个。

但是如果像图上直径长度是偶数,那么发现长度是 d2\frac d 2 的点只有一个,如果是奇数可以发现长度是 d+12\frac{d+1}{2} 有两个。这些点的个数是不能随意增加的。

小于 d2\frac d 2 的点是必然构造不出来的。然后就做完了。

阅读全文 »

AGC004F

神仙题。

考虑一个 nn 个点的树的情况怎么处理。

首先进行一次转化,树是一个二分图,于是就进行一次二分图染色。不难发现新图上两端颜色不同当且仅当原图两端颜色相同,所以我们可以把操作从同色翻转变成异色反转,也就是我们进行的操作其实就是在新图上移动黑色点。抄一个官方题解的图:

_ZJXZH7_FJJB91Y`3TKZRI0.png

然后问题就变成了一棵树,有一些位置是黑色点,一些位置是白色点,我们每次要移动一个黑色点到相邻的白色点,最后要让所有黑色点归位。

对于树的情况,如果黑点白点数量不同,必然无解。

这是一个经典模型,首先答案是有下界的。我们随意取一个根,对于一个子树,我们设它内部的黑点数减去白点数量为 aa ,那么这个子树向上的边至少会被经过 aa 次。我们可以证明这个下界是可以达到的。首先,如果不考虑同一个点上不能有两个黑色点,那么移动的次数相当于是一个最小权匹配。这个东西对于一条边,它被经过的次数显然可以是它一边的黑色点个数与白色点个数的差值。因为剩下的可以在内部匹配。然后考虑黑色点不能覆盖,那么对于之前的一种 uvu \to v 的移动方案,假设中间存在第一个 ttuvu \to v ,那么我们可以让 tvt \to v 并且让 utu \to t 。这样不断调整,一定可以达成 uu 上的黑点到达 vv 上的目的。

于是答案就是下界 ai\sum |a_i|

阅读全文 »

AGC003

A Wanna go back home

判一下 S,NW,E 是否同时存在或者同时不存在即可。

B Simplified mahjong

考虑一种贪心,从 11nn 逐个操作,我们假定已经把 1n11\sim n-1 给操作完了,并且 1n11\sim n-1 的位置如果剩余奇数就会留下 11 。对于 nn 这个位置,可以贪心一下,尽量和前面的剩下的那个先配对。如果这个位置是奇数,那么配对了必然是优秀的。否则,如果这个位置是偶数,那么这个位置本身就变成了奇数,只能往后操作,这里相当于把一个 11 往后挪动了一位,感性认知一下这样贪心是对的。

阅读全文 »

AGC002

AGC002C

找到一个结两边和不小于 LL 然后把剩下的依次删除即可。如果不存在显然无解。

AGC002 D

首先一种不动脑子的做法,直接建 kruskal 重构树然后二分 + 倍增跳即可。复杂度 O(nlog2n)O(n\log^2 n)

然后,通过整体二分 + 可撤销并查集也可以做。但是可撤销并查集无法路径压缩,所以也是 O(nlog2n)O(n\log^2 n)

然后其实是可以做到单 log\log 的。

如果我们按照 bfs 的顺序来做整体二分。如果当前加入的边超过了我们期望的边,那么就删掉所有边重做。不难发现由于是 bfs 序,这样的重做操作只有 O(logm)O(\log m) 次,所以复杂度就是单 log\log

阅读全文 »

AGC001F

首先考虑求出原排列的逆置换,设为 QQ ,于是交换就变成了如果 QiQi+1<k|Q_i - Q_{i+1}| < k 那么可以交换相邻的两个元素。

于是,对于任意 i,ji,j 如果满足 QiQj<k|Q_i - Q_j| < k 那么他们的相对顺序一定无法改变。

而且可以证明,如果两个排列 Q,PQ,P 中所有元素的相对位置的关系是一样的,那么一定可以从 QQ 移到 PP 。考虑这种情况下的一次移动就可以让逆序减少 11 。有限步的操作后一定可以让 QQ 成为 PP (画一下发现很对)。

于是有了一种做法,对于 i<ji<j 满足 QiQj<k|Q_i - Q_j| < k 我们连一条 QiQjQ_i \to Q_j 的有向边表示先 QiQ_iQjQ_j ,于是我们要求的就是这个图上的一个拓扑序,满足 11 尽量靠前,在 11 尽量靠前的情况下 22 尽量靠前... 不难发现这样的限制等价于原排列字典序尽量小。这个限制与字典序是没有关系的。比如 31,243 \to 1 , 2 \to 4 在这个限制下应该拿 3,1,2,43,1,2,4 但是字典序最小的应当是 2,3,1,42,3,1,4

求这个拓扑序的方法可以参照 LOJ2114 这个题。我们每次拿可以放在最后的最大的数放在最后一定不劣。所以我们可以建反图再跑拓扑序,最后把拓扑序倒过来就得到了所求。

现在问题在于这样的边有 O(n2)O(n^2) 条。优化方法大致有两种。首先可以不建边,直接在线段树上判断一个点的出度来做拓扑排序,这是官方题解的做法。大概还有一个做法是优化边的数量。

考虑我们当前已经通过加边让 1i11 \sim i - 1 的点对间都满足了之前提到的限制。现在我们加入 QiQ_i 。我们只给满足 0<QjQi<k0< Q_j - Q_i < k 以及 0<QiQj<k0 < Q_i - Q_j < k 且大的两个 jjQiQ_i 连边。由于上下是对称的,我们只考虑 Qj>QiQ_j > Q_i 的情况。因为之前 1i11 \sim i - 1 中与 ii 满足 QtQi<kQ_t -Q_i < k 的位置 与 QjQ_j 的相对顺序已经是确定好的,并且一定是 QjQ_j 处于最靠后,所以直接拿 QjQ_jQiQ_i 连边即可满足所有的限制。这样连边最多也就连 2n2n 条,边数变成了 O(n)O(n) 级别。连边过程用线段树维护,总复杂度是连边的 O(nlogn)O(n\log n)

最后别忘了要还原成原排列。。这毒瘤样例全部不还原都能过

阅读全文 »

10.30 模拟赛 D

题目

首先嘛,这个 bb 放到这里就是吓人的,明显这个式子就是

i=0nai(nkik)\sum_{i=0}^n a^i \binom{nk}{ik}

考虑 a=1a=1 怎么做,也就是

i=0n(nkik)\sum_{i=0}^n \binom{nk}{ik}

这个东西可以单位根反演,但是不难发现也可以循环卷积来做。也就是

(x+1)nk(x+1)^{nk}

在长度为 kk 的情况下做循环卷积的 [x0][x^0] 系数。

阅读全文 »

10.29 写题

CF388D

对于一个不同的线性基,对应着一种不同的 Perfect Set 。只要线性基能异或出来的数都得在 Perfect Set 里面。

于是考虑一个数位 dpdp ,设 dp[i][j][0/1]dp[i][j][0/1] 表示当前考虑到了第 ii 位,已经有 jj 个位的线性基填过数,到现在最高位是否贴着上界的方案数量。

我们考虑第 i1i-1 位。

阅读全文 »

10.28 写题

P5901 regions

按颜色数量进行根号分治。离线下来,对于出现次数 n\le \sqrt n 的点作为下方点的情况,我们处理出这个点到根路径上每种颜色数量,那么对于一次询问,我们只会在这个询问的下方点进行一次询问,这里下方点数量是 O(n)O(\sqrt n) 的。然后考虑出现次数 >n> \sqrt n 的点作为下方点。对于每个点处理出子树内的出现次数 >n> \sqrt n 的点的数量,然后从每个上方点查询即可。每个点最多只会进行 O(n)O(\sqrt n) 次这种询问。复杂度就是 O(nn)O(n\sqrt n)

阅读全文 »

10.26 模拟赛 C

C 秋天的第一杯奶茶

以下复杂度默认 n,m,qn,m,q 同阶。

考虑询问 [x,y][x,y] ,差分一下就是区间 [1,x1][1,x-1] 的修改对 [x,y][x,y] 的询问的影响(记作 [1,x1][x,y][1,x-1][x,y])。

然后可以直接莫队一下,这个往左往右加入拿 BIT 维护即可。复杂度 O(nnlogn)O(n\sqrt n \log n) ,期望得分 859585\sim 95

阅读全文 »

10.26 & 10.27 写题

草关机没保存。。重写一遍。。

CF1434D

题解证明了答案的一端一定是直径的一端。

于是对每个点维护它到根的距离以及它到根的路径的颜色即可。相当于区间反转,全局 00 位置最大值。线段树维护即可。

阅读全文 »

10.22 写题

CF576D Flights for Regular Customers

考虑从小到大加入边,一个众所周知的结论是邻接矩阵的 kk 次幂就相当于走 kk 次后的路径条数。在这里我们只关心 kk 步后能否走到一个点,于是是 0101 矩阵。每加入一条边就进行一次矩阵快速幂,然后加入下一条边。

考虑如何计算答案。当且仅当加入一条边后在 nn 步内能走到终点,才说明可以走到终点,每加入一条边后判一下能否 nn 步内走到终点即可。

阅读全文 »

10.21 模拟赛

T1 食堂计划

最短路图是一张拓扑图,并且只要再这个图上走出的路径就一定是最短路。

于是考虑一个 dpdp :设 dp[u][v]dp[u][v] 表示当前一个路径结尾在 uu 另一个在 vv 的方案数量。但是直接转移会出现重点。

阅读全文 »

10.20 写题

(多数都是水题

最优贸易

缩点,拓扑排序,然后考虑 dpdpMn 表示 11 到这个位置的最小买入价格,然后用在下一个位置卖出的收益更新一下 dpdp

阅读全文 »

10.19 模拟赛

contest

A 二次剩余

明显,当 xm320|x-m| \ge 320 的时候,这个二次函数的值必然大于了 10510^5 ,但是 k105k \le 10^5 ,于是我们往两边枚举 O(n)O(\sqrt n) 个,对于每个值维护一个堆即可。

阅读全文 »

ICPC 2014 WF I

目前做的这四个题里面最神仙的一个。

考虑任意枚举一对合法点,然后画出下面这种图:

阅读全文 »

CF704B Ant Man

考虑对于一个位置,如果它不是 s,es,e ,那么这个位置必然有一个入度一个出度。也就是说一个位置的方案有从右边进入,从左边进入,向左边出去,向右边出去。

我们考虑当前已经填完了前 ii 个位置,到现在为止还剩 jj 个向左的边和 kk 个向右的边。不难发现,如果这个点不是 s,es,e 的一种,那么对于任何一种填这个点边的方案,要么使向左的、向右的边的个数同时 +1,1+1,-1 要么使向左、向右的边的个数不变,分别对应:

然后如果新增的点是 ss ,那么只能是

阅读全文 »