首页 > 其他分享 >2.4 響け恋の歌 ——ARC古报 104~106

2.4 響け恋の歌 ——ARC古报 104~106

时间:2024-02-05 23:11:08浏览次数:31  
标签:二分 连通 sum 古报 奇偶性 先手 枚举 ARC 106

本来想一次放五场的,但是感觉实在是太多了,题解写起来很累,就改为三场了。以后没活了就写这个。ARC 多的是,所以近阶段就不会没活啦!

ARC104

D Multiset Mean

对于 \(x\),我们只需要求出 \([0,x-1]\) 的元素组合的背包,以及 \([1,n-x]\) 的元素组合的背包,然后再做点乘即可。

做背包的时候,注意可以使用前缀和优化让其达到 \(O(n^4)\)。

E Random LIS

枚举最终形成的序列的排列,以及元素是否相等。我们可以一开始把值域拆成 \(O(n)\) 个段,然后再在内层算出 LIS 后,枚举每个元素处于哪个段。段内方案数是简单的组合数。

复杂度能过。

F Visibility Sequence

我们考虑在已经确定了 \(p\) 的情况下,可以贪心地尽可能使 \(a\) 小地填数。考虑 DP:\(f(l,r,x)\) 表示考虑 \([l,r]\),贪心方案中 \(a[l,r]\) 最大值最小是 \(x\),的方案数。

由于 \(x\) 是 \(O(n)\) 的,所以转移直接枚举最后一个 \(p=-1\) 的位置即可,然后前缀和优化。

ARC105

避雷:这场一整个垃圾场,慎做。

D Let's Play Nim

我们发现第二个游戏的先手有巨大优势。仔细想一下,如果 Nim 的先手是后手那么一定赢,否则除非后手可以与先手做对称玩法(即出现次数均为偶数),否则也是必赢。

E Keep Graph Disconnected

我们考虑最后一定是两个连通块然后看这两个连通块中的未连边的奇偶性。我们设这两个连通块的大小为 \(x,y\)。如果 \(n=x+y\) 是奇数,那么 \(xy\) 一定是奇数,于是 \(x,y\) 是多少都不会影响谁胜谁负。

然后我们看初始 \(x_0,y_0\)。如果 \(x_0,y_0\) 不同奇偶,那么一定存在其余奇块。于是先手可以选择是否改变奇偶性,然后后面后手每走一步,先手就可以根据情况来进行操作。否则我们就再看看一开始局面的 \(x_0y_0\) 的奇偶性判断胜负,因为胜者也总能根据情况进行维持操作。

F Lights Out on Connected Graph

容易发现图合法当且仅当其是连通二分图。我们枚举点集及其染色得到任意二分图及其染色的组合的数量。然后我们在对其做容斥,得到连通二分图及其染色的组合的数量。由于连通二分图数染色数是 \(2\),所以直接除以二就行了。复杂度 \(O(3^n)\)。

ARC106

D Powers

\(\sum_{l,r}(a_l+a_r)^{k}=\sum_{i} \binom{k}{i}\sum_{l,r} a_l^ia_r^{k-i}\)。预处理一下 \(\sum a_i^j\) 即可。

E Medals

我们先进行一个二分,然后就发现是一个匹配问题。

注意到 \(n\le 18\),于是直接进行一个 Hall 定理。

F Figures

考虑 Prufer 序列。于是答案就是

\[\begin{aligned} & [z^{n-2}] (n-2)!\prod_u \sum_i \frac{z^{i}d_i^{\underline{i+1}}}{i!}\\ =& (n-2)!\binom{\sum (d_i-1)}{n-2}\prod d_u \end{aligned} \]

标签:二分,连通,sum,古报,奇偶性,先手,枚举,ARC,106
From: https://www.cnblogs.com/TetrisCandy/p/18008989

相关文章

  • [ARC135D] Add to Square 题解
    题目链接点击打开链接题目解法很牛的题!!!先考虑一步很牛的转化:把矩阵黑白染色,且\(i+j\)为奇数的位置的值取反,每次操作变为左上右下\(+v\),左下右上\(-v\)这样有啥好处?操作不会使行和列的和改变考虑答案的下界显然是:\(\max\{\)行的绝对值之和,列的绝对值之和\(\}\)这里给出......
  • eviacam在Arch/Manjaro Linux下的安装
    安装base-devel安装编译工具,默认的依赖里没有编译工具sudoyay-Sbase-devel如果安装编译工具,会报类似下面的错误:安装eviacamyay-Seviacam这里主要是用AUR的方式来顺便把依赖安装了,也可以手动安装依赖,然后Clone源码这一步会报类似下面的错误:根据错误提示修......
  • Proxmox 7.4 使用vgpu_unlock,为GTX1060开启vGPU支持
    本文在2021年发布的博客《Proxmox5.4使用vgpu_unlock,为GTX1060开启vGPU支持》,介绍了ProxmoxVE5.4上部署vGPUunlock的操作步骤。 后续有发布了在 ProxmoxVE7.x上支持vGPU的博客《Proxmox7.2部署DoraCloud桌面云,支持vGPU》,实现了通过3个脚本完成vGPU的配置。 ......
  • 题解 ARC171D【Rolling Hash】
    来补题了。昨天赛时想法是对的,代码写错了,没调过太可惜了。显然\(P>n\)时必定有解。设前缀\([1,i]\)的哈希值为\(s_i\),显然\([l,r]\)的哈希值不为\(0\)的充要条件是\(s_{l-1}\nes_r\)。建立一个点的编号为\(0\simn\)的图,对于每个输入的区间\([l,r]\),连接一条边......
  • 题解 ARC171C【Swap on Tree】
    每棵子树内只可能有至多一个外来的数,且外来的数是多少并不影响方案数,因此考虑设\(f_{u,i,0/1}\)表示考虑以\(u\)为根的子树,与\(u\)相连的所有边中断了\(i\)条,且\(u\)与其父亲之间的边有没有断的方案数。设\(g_{u,c}=\sumf_{u,i,c}\)。每个节点的初始状态是\(f_{u,0,......
  • 题解 ARC171B【Chmax】
    考察题面中的操作究竟做了什么,不难发现其实是将所有满足\(P_i>i\)的\(i\toP_i\)连边,得到若干条链,然后\(B_i\)即为\(i\)所在链的最后一个节点。显然,存在\(A_i<i\)时无解,存在\(A_i\nei\)但\(A_j=i\)时也无解。否则,每个\(A_i\nei\)的位置填的数都唯一确定......
  • [ARC162D] Smallest Vertices 题解
    题目链接点击打开链接题目解法这种树的形态计数题首先可以想到\(prufer\)序列计数,如果没有任何限制,那么方案数为\(\prod\frac{(n-2)!}{deg_i}\),其中\(deg_1=d_1-1,deg_i=d_i(2\lei\len)\)对于每个点分开求贡献考虑这个式子只和点的个数和子树内的\(\sumdeg\)有关......
  • Arct房屋设计网的设计与实现代码
      <headerid="sticky-header">  <divclass="cc-header-area">  <divclass="container-fluid">   <divclass="row">   <divclass="main-wrapper">    <navclass=&q......
  • [ARC171B] Chmax
    [ARC171B]ChmaxSolution首先可以发现相同\(a_{i}\)的元素可以形成一条链。问题很容易转化为:给定若干线段\([l_{i},r_{i}]\),要求\(i\)能连向\(j\)当且仅当\(l_{j}<r_{i}\),求生成环集的数量。容易发现两个点之间至少有一条边,当且仅当两线段不交时,左侧线段无法连向右......
  • 二分查找BinarySearch
    二分查找法首先,整个数组必须有序,通常为递增。将数组中间数字与被比较元素比较相等即目标元素为被比较元素中间元素大于目标元素,意味着中间元素右边的所有元素均大于目标元素,排除中间元素小于目标元素,意味着中间元素左边的所有元素均小于目标元素,排除当数组元......