首页 > 其他分享 >20240913 ARC104

20240913 ARC104

时间:2024-11-08 15:18:53浏览次数:1  
标签:背包 20240913 ARC104 独立 区间 dp

20240913 ARC104

感觉后四题价值都很高,dp 还是弱项,待加强。

A Plus Minus

水,略。

B DNA Sequence

只有对应的两种字符数量相等才能满足条件,直接 \(O(n^2)\) 枚举子串可过。用 unordered_map 开桶能做到 \(O(n)\)。

C Fair Elevator

赛时没想到 dp,乱搞做法差 1 个点就过了。

考虑 dp,设 \(f_i\) 表示前 \(i\) 个位置能否完成分配。转移时枚举一个独立的区间 \([j,i]\),判断这个区间是否可行并转移。

考虑如何判断一个独立区间是否合法。不妨设这个区间内没有独立的区间,否则可以从另一个状态转移。注意到所有的 \([a_i,b_i]\) 间不存在包含关系,所以这个独立区间内的所有区间一定两两相交。于是这个独立区间会是这样:\(\{a_{i_1},a_{i_2},...,a_{i_m},b_{i_1},b_{i_2},...,b_{i,m}\}\)。根据这个性质判断就好。

似乎可以搜,但要剪枝。

D Multiset Mean

遗憾的,赛时连第一层转化都没想到,乱七八糟想,浪费很多时间。又 get 一种多重背包优化。

先考虑对于每个平均值 \(x\) 单独求解。将每个数的价值减去 \(x\),那么问题转化为选出一些数使和为 0。显然可以多重背包求,但是 \(O(n^4k)\)。

再次转化,和为 0 也就是说正数和与负数和的绝对值相等。又注意到可选的正数和负数都是一段连续的数,于是可以预处理 \(f_{i,j}\) 表示选 \([1,i]\) 的数,每个数最多 \(k\) 个,和为 \(j\) 的方案数。这里的多重背包可以用前缀和优化,是 \(O(n^3k)\) 的。那么答案为 \(c_x=(k+1)\sum_{i=0}^{\frac {kn(n+1)}{2}} f_{x-1,i}f_{n-x,i}-1\)。

标签:背包,20240913,ARC104,独立,区间,dp
From: https://www.cnblogs.com/luyuyang/p/18535159

相关文章

  • 20240913 随机训练
    GYM105293C题目描述有\(N\)个怪物排成一排,第\(i\)个怪物的血量为\(h_i\)。当一个怪物的血量\(h_i\le0\)时,则它死亡。你可以进行以下操作:选择一个正整数\(x\)。找到第一个\(h_i\gex\)的\(i\),并令\(h_i\leftarrowh_i-x\)。如果该次操作没有影响到任何怪物,......
  • 20240913_155935 mysql 触发器
    建表需求创建一个日志表记录teacher表的操作日志情况增删改的相关信息要保存起来方便定期查看明确字段表名:log_info列信息idactioninfotime创建表格CREATETABLElog_info( idINTPRIMARYKEYAUTO_INCREMENT, action_nameVARCHAR(11), infoVARCHAR(111), act_......
  • [ARC104D] Multiset Mean
    考虑计算和为\(x\)的方案时,把所有的数减去\(x\),dp出和等于\(0\)的。减去后数被分为三段,小于\(0\),等于\(0\)和大于\(0\)。其中等于\(0\)的直接乘上即可,对于正负,上下都是对称的,直接dp出\(f_{i,j}\)表示用了前\(i\)个数和为\(j\)的方案书,使用前缀和优化,最后......
  • [ARC104E] Random LIS
    题意:数列每个数是在\([1,a_i]\)上均匀随机分布的整数,求其最长上升子序列长度的期望,\(n\le6\)。发现\(n\)很小,考虑\(O(n^n)\)枚举所有数的偏序关系,然后设\(h_i=\min_{rk_j=i}a_j\),\(m=\max_{i=1}^nrk_i\),这样问题就能转化为数列每个数是\([1_i,h_i]\)上均匀随机分布......
  • [ARC104F] Visibility Sequence 题解
    题意对于一个长度为\(N\)的序列\(H\),可以通过如下方式构造一个序列\(P\):若存在\(j\in\left[1,i\right)\),使得\(H_j>H_i\),则\(P_i=\max\limits_{j\in\left[1,i\right)\landH_j>H_i}j\),否则\(P_i=-1\)。给定一个长度为\(N\)的序列\(X\),求所有满足如......
  • [ARC104E] Random LIS 题解
    题意给定一个长度为\(N\)的序列\(A\),按照下列方式生成一个长度为\(N\)的序列\(X\):\(\foralli\in[1,n]\),\(X_i\)在\([1,A_i]\)中的整数中均匀随机生成。求其最长上升子序列长度的期望,对\(10^9+7\)取模。\(1\leN\le6,1\leA_i\le10^9\)。题解由于\(N\)......
  • [ARC104B] DNA Sequence 题解
    题意对于一个只含有A,C,T,G的字符串\(s\),定义其为匹配的当且仅当其中A的数量和T的数量相等,C的数量和G的数量相等。给定一个长度为\(N\)的字符串\(S\),求其有多少个非空子串是匹配的。\(1\leN\le5000\)。题解\(\mathcal{O}(N)\)做法。首先考虑如果字符集只有......
  • [ARC104D] Multiset Mean 题解
    题意给定\(N,K\)和\(M\)。对于每个大小在\([1,N]\)中的\(x\),求每个元素大小在\([1,N]\)中,平均数为\(x\)且相同元素不超过\(K\)个的可重集的数量,对\(M\)取模。\(1\leN,K\le100\),\(M\)为质数。题解发现对于\(x\),若存在一个合法的集合\(S\),那么有\[\sum\li......
  • [ARC104C] Fair Elevator 题解
    题意有\(N\)个区间\([a_i,b_i](a_i<b_i)\),都是\([1,2n]\)内的整数且互不相同(\(a_i\neb_j,a_i\nea_j,b_i\neb_j\))。现在给定一些\(a\)和\(b\)的值,剩下不知道的用\(-1\)表示。问是否存在一种替换掉\(-1\)的方案,使得:若两个区间有交,那么它们长度相等。即\(\forall......
  • 题解 ARC104F
    前言在这里首先感谢一下题解区的FZzzz,本人的题解思路主要是基于他并给出了自己的理解。如非特殊说明,本题解中的数学符号原则上与题目中一致。题目分析需要转化的喵喵题。我们需要把原问题转化成一个图论计数问题,然后剩下的就很好办了。好,首先让我们修改一下题目的要求,将不......