Lynkcat的博客

博客

暂别

2024-07-21 22:36:03 By Lynkcat

暂时离开了,qoj,呜呜呜。希望尽快再见。拜拜ヾ(•ω•`)o

Public Round #13 公告

2024-06-12 11:41:46 By Lynkcat

NOI 2024 即将来临,Public Round #13 将在 2024 年 6 月 30 日 8:30 举行!比赛将进行 5 小时,共 3 道题,OI 赛制。

本次比赛的题目难度约为 NOI 难度,方便选手调整状态,所有题目都有部分分。

本次模拟赛的组题人为 Lynkcat,搬题人为 p_b_p_b, Crysfly, Lynkcat,验题人为 cmll02 。

赛后会公开原题链接和题解链接。

特别提醒:本次比赛的题目均为原题,但为了比赛的公平性,请勿在比赛时尝试查找原题地址。如不幸见过原题,请向管理员报告。

时代边哥团我们喜欢你第一期

2024-06-07 20:54:38 By Lynkcat

时代边哥团我们喜欢你

我们喜欢你啊我们喜欢你

你是最帅最帅的,最帅的

我们喜欢你啊我们喜欢你


CF1149D

一张 $n$ 个点 $m$ 条边的无向图,只有 $a,b$ 两种边权 $(a < b)$,对于每个 $i$,求图中所有的最小生成树中,从 $1$ 到 $i$ 距离的最小值。

$n\leq 70,m\leq min(300,n\times (n-1)/2)$。


很喜欢这种幽默到我不会做的题

我先来说一下我写的假做法,在 NOI 模拟赛赛时通过了所有数据。

先有一些很基本的观察:一条合法的路径不能重复经过一个 $a$ 边连通块。然后我啥也不会做了。编了一个锤子东西:

记 $f_{x,y,i,j}$ 为当经过了 $x$ 条 $a$ 边与 $y$ 条 $b$ 边时,到达 $i$ 点是否必须要经过 $j$ 号连通块。

然后转移,碰到不必须经过的就转移过去,形式是 bitset 的与操作,时间复杂度 $O(\frac{n^4m}{w})$。

为什么错了呢,因为当我 $f_{x,y,i,j}$ 为 $0$ 时,转移过去的 mask 实际上有一些位置应该要改为 $1$(换句话说,当我钦定一个某个不必须经过的点需要经过的时候,有些点会从不必须经过变成需要必须经过)


正解是一个简单至极的观察:连通块数 $\leq 3$ 的时候往外走一定不优,所以只要状压记大小 $>3$ 的连通块即可。

哈哈


Zoo Management

一张 $n$ 个点 $m$ 条边的图跟两个长度为 $n$ 的序列 $a,b$,每次可以把一个置换环上的 $a$ 同时顺时针/逆时针旋转一下,问能不能变成 $b$。

$n,m\leq 4\times 10^5$。


把这题出 OI 赛时比赛是不是多少有点歹毒。

首先有显然的观察:环的时候要做 kmp,不同边双的是割裂的

然后有简单的猜测:当边双不是环的时候可以取遍所有状态。

可以通过所有样例,并且 $n\leq 8$ 拍一万组也拍不出来。

但是你只要稍微注意力集中一点或者写个暴力试一下,会发现,是排列情况下且只有奇环的时候,并不能取满所有状态,而是只能取一半。

为什么呢,考虑排列情况下置换环个数的奇偶性,会发现 rotate 一个奇环不会改变置换环个数的奇偶性。。。

于是你需要判断边双之内存不存在偶环:具体地,抠出边双内的每个点双,若大小为偶数则一定存在偶环,否则大小为奇数时,若点双不为环,那么也一定有偶环。

然后你可以写完整个题的代码,但是在赛时最好别写挂,因为根本没法拍。。。


VietnamTeamSelectionTest-D1P2

给定一个长度 $m$ 不超过 20 的 01 串 $S$,求能选出多少长度为 $n$ 的 01 串满足两两不循环同构且不把其中一个翻转后做到循环同构,对 $10^9+7$ 取模。

$n\leq 10^9$。


出这个题的是变态吧??

套用一下带权 Burnside 引理,问题可以转化成求 $n$ 个循环置换以及 $n$ 个翻转循环置换之后,满足 $S$ 或者 $S^R$ 在串中出现(一个后缀拼一个前缀也算出现)的长度为 $n$ 的串的个数。

先解决一下翻转循环置换,手模一下情况就会发现等价于枚举对称轴,因此当 $n$ 是偶数的时候只要算两种情况的答案,而 $n$ 是奇数的时候只要算一种即可。

讨论其中一个情况,其他情况类似,问题变成数串 $T$满足是回文串且满足 $S$ 或者 $S^R$ 在串中出现。

容斥一下先算不出现的方案数,减一下即可得到原问题答案。

将 $S$ 跟 $S^R$ 建 KMP 自动机,设 $T=X+X^R$,其中 $+$ 是字符串拼接,首先枚举 $X$ 的前 $m$ 位然后判断是否能走一段 $X^R$ 的后缀然后走一段 $X$ 的前缀使得走到任意一个 $m$ 的状态,如果不可以,设当前 $X$ 的前 $m$ 位在两个自动机上的状态是 $(x,y)$,先把 $cnt_{x,y}$ 加一。然后对于不同的 $(x,y)$ 继续转移 $\frac{n}{2}-m$ 步,每次是 $(x,y)$ 转移到走 $0$ 或者走 $1$,这里可以矩阵快速幂优化。最后把每个最终状态 $(X,Y)$ 中能拼成 $m$ 的去掉,这个可以预处理。

接下来解决循环置换,设 $F(k)$ 为长度为 $k$ 的串满足 $S$ 或者 $S^R$ 在串中出现。$k\leq m$ 的情况显然可以暴力枚举每个串。$>m$ 的情况可以矩阵快速幂,因此不难发现 $F$ 在 $>m$ 时的答案应当是一个长度为 $O(m^2)$ 的整式递推。设常数 $B=500$。

设 $(x,y)$ 为一个串 $T$ 在自动机上的最终状态,如果 $T$ 不包含 $S$ 或者 $S^R$ 显然在初始状态是 $(x,y)$ 的情况下,每一步都不能走到任意一个自动机的 $m$。枚举 $(x,y)$ 然后求出长度 $\leq B$ 的所有答案,然后 BM 求一下递推式然后多项式取模随便算一下每个 $k|n$ 时的 $F(k)$ 即可。


总结:

边哥锐评:太不牛了。

PKUSC 2024 简单写写

2024-05-15 23:30:03 By Lynkcat

回文路径

枚举回文中心在哪一行的哪个位置,那么在这一行的回文串一定是取的越长越好,可以直接二分哈希。

正方形计数

枚举一条 $(x,y)$ 向量表示第二个点与第一个点之间的位移,满足 $x+y>0$,计算包含这个向量的合法正方形的个数。

把其他三个点相对于第一个点的位移都求出来,关于 $n$ 个半平面可以得到新的 $n$ 个半平面。

求出半平面交之后,可以得到若干 $ax+by+c\geq 0$ 的限制,使用一些差分的手段后可以转化成求一个 $[0,MAX]\times [0,MAX]$ 的矩形与一个半平面的交形成一个三角形,求这个三角形中的整点个数,由于斜率只有 $n$ 种,进行 $n$ 遍前缀和即可。

独立

树上最大权独立集的经典做法是设 $dp_{k,0/1}$ 表示 $k$ 这个位置是否被选中,不难发现有 $\max(dp_{k,0},dp_{k,1})-dp_{k,0}\leq V$。

考虑设 $siz_k$ 表示 $k$ 子树的大小,设 $f_{k,i}$ 表示 $k$ 子树内,$\max(dp_{k,0},dp_{k,1})-dp_{k,0}=i$ 的方案数。那么有答案为 $\sum_k\sum_i f_{k,i}\times i \times m^{n-siz_k}$。

可以证明 $f_{k,i}$ 在当 $i\not = 0$ 的时候是关于 $i$ 的一个 $siz$ 次多项式,因此考虑拉格朗日插值。

考虑 $u$ 转移到 $k$ 的时候是个减法卷积,因此我们试图求出 $f_{k,m-siz_k...m}$,这可以直接减法卷积。这部分复杂度是 $\sum siz_k\log siz_k$ 的。

接着我们直接使用 $f_{k,m-siz_k...m}$ 点值平移出 $f_{k,1...siz_k}$。这样就能够继续转移到 $k$ 的父亲了。求答案就用 $f_{k,i}\times i \times m^{n-siz_k}$ 的前缀和插一下就行了。同样的 $f_{k,0}$ 的处理也可以拉插,当 $u$ 转移到 $k$ 时($f'_k\otimes f_u\rightarrow f_k$),把 $\{f'_{k,i}\times (\sum_{j=i}f_{u,j})\}$ 弄几个能算的出来拉插就能转移到新的 $f_{k,0}$ 了,当然还要加上 $f'_{k,0}$ 的贡献,不过处理方式是一样的。

因此整个题可以做到 $O(n^2\log n)$ 的时间复杂度。

分流器

二分答案 $ans$,设 $f_i$ 表示 $i$ 被访问到的次数,那么接下来一定两条出边会各被访问一半,也就是 $f_{out_{i,0}}+=\frac{f_i}{2}$,$f_{out_{i,1}}+=\frac{f_i}{2}$。在过程中判一下是否满足每个点是奇数即可,用 ull 压位高精时间复杂度 $O(\frac{n^3}{w})$。

注意到 $ans$ 只有 lowbit 有用,所以答案一定是 $2$ 的某个次幂,二分指数即可做到时间复杂度 $O(\frac{n^2\log n}{w})$,可以通过。

upd:也可以不需要二分,直接求 $ans$ 为 $2^n$ 的时候每个点的 lowbit 的最小值即可。

排队

扫描线,每个询问在左端点处插入,右端点处查询。

因为询问初始给的初值均为 $0$,因此先插入的询问在同一个右端点处的答案不会比后插入的要小。

因此,将询问按左端点排序,每次的操作形如找到一个区间满足区间内的值都在 $[l,r]$ 内,然后集体 $+1$,可以在树状数组上二分实现。

时间复杂度 $O(n\log n)$。

最短路径

Lynkcat Avatar