AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

联合省选2021 完整题解

作者: 作者的头像   whsstory ,  2021-04-22 19:38:46 ,  所有人可见 ,  阅读 898


6


2

联合省选2021 完整题解

详略程度和难度无关。

A卷 Day1T1 卡牌游戏

考虑枚举最小值$minv$($minv$一定是某个$a$或$b$,排序之后枚举即可).此时只需令最大值最小即可(当然要满足$m$的限制)。

为了满足最小值的限制,我们要翻一个前缀$[1,Lt]$.显然$Lt$关于$minv$非严格增。注意特判翻出的$b<minv$的情况。

为了令最大值最小,我们要翻一个后缀$[Rt,n]$.注意$Rt$要满足$m$和$minv$的限制。

考虑比较$[Rt,n]$和$[Rt+1,n]$.前者导致的最大值是$max(Sufmax_{Rt},a_{Rt-1})$,后者导致的最大值是$max(Sufmax_{Rt+1},a_{Rt})$.如果后者更小则增加$Rt$即可(注意同样优时也要增加$Rt$, 因为可能这个函数有一段平的,之后的某个位置才变小)

此外,当$minv$增大时$Rt$的下界会增大,其余不变,因此最优的$Rt$也是非严格增的,在上一个的基础上继续往右走即可。

瓶颈在于排序,为$O(n\log n)$或$O(n)$

My code

A卷 Day1T2 矩阵游戏

首先构造一个符合和的限制但不符合值域限制的矩阵$M$.这是很容易的,钦定第一行与第一列均为0 ,其余便可唯一推出。

考虑能怎样修改使其合法。为了使和的限制不被破坏,一定是若干次(可能为负)以下两种操作:

  • 对某一行,奇数列+1,偶数列-1
  • 对某一列,奇数行+1,偶数行-1

这样就简单了,设第$i$行操作$x_i$次,第$j$列操作$y_j$次,每个位置$(i,j)$的限制形如:
$$ \begin{align} M_{i,j}+x_i+y_j\in[0,10^6]\quad (1,1)\\\\ M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,0)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\\\ M_{i,j}-x_i-y_j\in[0,10^6]\quad (0,0)\\\\ \end{align} $$
$(1,1)$表示$i,j$都为奇数,其余同理。
恭喜,这样是没法做的

接下来是难以想到的操作:将$x_i,y_j$略作修改,具体的,对$i\mod 2=1,x_i:=-x_i$,对$j\mod 2=0,y_j:=-y_j$.这样操作之后,限制形如:
$$ \begin{align} M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,1)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (1,0)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\\\ M_{i,j}-x_i+y_j\in[0,10^6]\quad (0,0)\\\\ \end{align} $$
都是两个变量的差的不等式,可以转化为差分约束模型求解,以$M_{i,j}-x_i+y_j\ge 0$为例:$\Rightarrow y_j+M_{i,j}\ge x_i$,令第$j$列代表的点向第$i$行代表的点连边权为$M_{i,j}$的边。

或者你也可以先猜到是用差分约束,然后把初始形式转化为差分约束的形式。

复杂度即$O(Check_Negative_Ring(n+m,nm))$ 。用spfa/Floyd 实现即可。

My code

A卷D1T3 图函数

考虑有序对$(u,v)$在$G$中产生贡献的条件:存在一个环$R$经过$u,v$且$u$为$R$上编号最小的。

进一步,若求出$T(u,v)$表示所有$R$中边的编号最小值最大的,那么$(u,v)$会对所有$i\le T(u,v)$的$G_i$产生贡献。

考虑如何求$T(u,v)$.

我的做法是,考虑Floyd的过程是加入中转点$k$,且加入$S$中所有点作为中转点后,我们求出的最短距离$dis(u,v)$表示$u$到$v$只经过$S\cup\{u,v\}$中的点的所有路径中边的编号最小值的最大值。

那么,若从大到小加入$k$,此时$(u,v)$的路径上所有点编号都$\ge k$.枚举$v\ge k,T(k,v)=\min(dis(k,v),dis(v,k))$.

时间复杂度$O(n^3)$,但循环展开之后能过!

也有$O(nm)$的做法,大致思路类似。

My code(Floyd)

A卷 Day2T1 宝石

关注$P_i$互不相同 的性质。这个性质指出,如果起点在$u$的子树内且匹配到了$u$且终点为根,那么下一个匹配点是唯一确定的(上一个也是)。因此,下$x$个匹配点也是唯一确定的。预处理每个点往上第一个匹配$P_1$的点$u$,然后可以倍增找出最多能匹配的数量,这样就$O(n\log c)$预处理,$O(\log c)$每次查询的复杂度解决了链上的问题。

对于一般情况,$s\rightarrow LCA$的部分同样可以这样处理,记匹配到$p$。对于$LCA\rightarrow t$的部分,考虑二分答案。设当前要判断能否匹配$[p+1,k]$ .先离线求解$t$往上第一个匹配$P_k$的点,然后同样倍增(这个倍增是倍增前驱)找出最多能匹配的位置$q$,若$q\le p+1$即可。

预处理$O(n\log c)$,$O(\log^2 c)$每次查询。

My code

A卷 Day2T2 滚榜

先考虑暴力枚举所有排列。我们可以考虑贪心,最小化封榜后过题数$t$:若$t(t\le m)$可行,那么一定可以让最后一队再过$m-t$题,这样仍可行。这样是$O(n!n)$的

优化也很显然,考虑状压DP。

暴力是,$f(S,i,w,sum)$表示用了集合$S$,最后一个是$i$,$i$额外过了$w$题,$S$额外过题数和为$sum$.

这样是$O(2^nn^2m^2)$,不太行。

按照套路,$w$是没用的,我们直接费用提前计算,就是说加入一个$j$,若$j$至少要过$x$题,那么之后共有$(n-|S|)$个人要因为$j$再过$x$题。

这样就是$O(2^nn^2m)$了,空间$O(2^nnm)$.

实际上,$\sum_i\binom{n}{i}i(n-i)=2^{n-2}n(n-1)$,计算量至多159744000,是合理的
My code

A卷Day2T3 支配

先求支配树$DT$。

当然可以用polylog的方法,但没必要,枚举删掉点$u$再从1开始bfs,走不到的就受$u$支配,这样就能$O(n(n+m))$求出每个点的支配集;又由于$fa_u$的受支配集大小恰为$u$的受支配集大小减1,就可以$O(n(n+m))$求出$DT$。

考虑一个点$u$,$DT$上父亲为$fa$,受支配集$D_u$变化仅当$D_{fa}$改变或$fa$不再支配$u$.这个等价于若$fa$不再支配$u$,则$u$子树中所有点受支配集都改变。

所以只需判断$fa$是否仍然支配$u$.

记新加入的边为$(x,y)$,那么$fa$不再支配当且$u$仅当原图存在$1\rightarrow x$和$y\rightarrow u$的路径且均不经过$fa$(注意$x,y\ne fa$)。

存在$1\rightarrow x$不经过$fa$显然仅当$fa$不支配$x$.考虑预处理$f(i,j)$表示在不经过$fa_i$的情况下$j$能否到达$i$.那么存在$y\rightarrow u$仅当$f(u,y)=1$.直接在反图上从$i$开始bfs即可预处理好。

询问时候枚举所有$u$判断即可。

总复杂度$O(n(n+m+Q))$

可能轻微卡常,但这些技巧显然省选选手都能掌握。

My code

B卷 数对

枚举$i$的所有倍数的复杂度是$O(A/i)$,去重之后复杂度是$O(\sum_i A/i)=O(A\log A)$.

B卷 取模

我居然这种题都不会了。。。

考虑暴力枚举$k$. 令$b_i=a_i\mod a_k$,就是找一对$b_i+b_j$最大,贡献$(b_i+b_j)\mod a_k$,或找一对$b_i+b_j<a_k$,贡献$b_i+b_j$.将$b$排序后双指针即可。复杂度$O(n^2\log n)$.

然而只要加上两个优化,当$a_k$小于当前答案时直接结束,则不同的有效$a_k$至多$O(\log A)$个。

证明也很容易:记最终答案为$ans$.$a_k$之后两个不同的数为$a_{k+1},a_{k+2}$
$$ (a_{k+1}+a_{k+2})\mod a_k\le ans\\\\ \Rightarrow a_{k+1}+a_{k+2}-a_k\le ans\\\\ \Rightarrow (a_{k+1}-ans)+(a_{k+2}-ans)\le a_k-ans $$
所以数列$f_i=a_i-ans$是至少是斐波那契级别增长,因此不同的有效$k$至多$O(\log A)$个。

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

My code

4 评论


用户头像
CCCkk   2022-07-31 19:24         踩      回复

%%%

用户头像
CCCkk   2022-07-31 19:26         踩      回复

NOI加油


用户头像
changle_cyx   2021-05-07 17:36         踩      回复

Day2T2 的时间复杂度有点问题吧,应该还是 $O(2^nn^2m)$ 的。

$$ \sum_{i=0}^{n} \binom{n}{i}i(n-i)=2^{n-2}(n-1) n $$

用户头像
whsstory   2021-05-07 19:05         踩      回复

哦是的,吸收一下就行,不过$2^{n-2}n(n-1)m\le 159744000$ 也是合理的


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息