Atcoder abc313
https://atcoder.jp/contests/abc313
F - Flip Machines
n张卡,正面ai,背面bi,初始都是正面
m个机器,对应卡xj,yj,!!xj可能等于yj
如果一个机器启动 则1/2几率 翻转卡xj,否则翻转卡yj
启动机器的集合任意选择
问 所有的 启动机器的集合 的方案中 卡的和
的期望值最大是多少
n 40
ai,bi [1,1e4]
m 1e5
2s
1024mb
我的思路
显然是个概率论的题
n 比较小,m中等,ai,bi中等
1 | 卡 a1 a2 a3 |
从频次的角度来看, 如果涉及到翻转,那么该位置的期望贡献就是 (a[i]+b[i])/2
如果不涉及翻转 那么期望贡献就是 a[i]
所以选取的集合 就算再多,也只和被激活的那些有关,和一个位置被选了几次无关
所以问题可以变为,基础 = sum ai,
di = (b[i]-a[i])/2
有一堆激活的pair可以任意选,
问 最大 di和为多少
把di 按照正(>=0),负(<0)分类
如果有 (+,+)的di pair则一定选, 如果有(-,-)一定不选
那么剩下的就是 (+,-)的
而这类如果 其中的+已经选了 则一定不选
所以变成了, 未被选的+,所有-
和很多(+,-)的问题
那么显然 至少一侧的个数 <= n/2 = 20
这就很像bitset了
如果 所有-的个数 <= n/2 那最简单, 就是贪心选掉所有(+,-)有-被选的正的里面的
如果 所有+的个数 <= n/2???
1 | (a0 10,b0 -5) |
只能说 最终被选的 -的个数肯定 <= n/2, 因为每个(+,-) 最多选一次
n-正 个中 选 <=正的方案数? 这有多大?
正=20时 2^20
正=19时 $2^{21}-\binom{21}{21}-\binom{21}{20}$
正=18时 $2^{22}-\binom{22}{22}-\binom{22}{21}-\binom{22}{20}-\binom{22}{19}$
1 | def binom(n,m): |
看输出 感觉 还是2s过不了
1 | 1 40 |
题解
几乎一样的处理题意
也是 如果暴力 枚举 更劣的点, 那么贪心连接边 则 O(n 2^|劣|)
然后就是 我上面自己没想到的 优势一半的 个数<=n/2时
处理方式是 bitdp
dp[i][mask] =
前i个劣势状态的所有方案中,优势选择的情况为mask的最优代价和
然后我漏考虑了xj=yj, 这种的话 就是100% 选择更优的就行了
G - Redistribution of Piles
a[n] \in[0,1e9]
n 2e5
每次二选一,做任意次
- 所有石头 > 1,减去1个, bag+=对应的值
- bag-=N, 所有+=1
问可以得到的数组的方案数 mod 998244353
2s
1024mb
我的思路
不知道怎么牵连这个变化值进来
比如我想把一个地方垒得很高,
那么先清空,然后不断所有+1
然后把不是目标位置的都清除
再所有+1, 如此反复直到 挖完后bag中个数< N
然后对于单点来说, 变小总是可以的
变大都需要一次全+1
如果把它们按照目标从小到大排列
那么每次除了最大的全部删除,所有+1,这样直到最大的达到目标
然后问题到次大的,还是除了次大了 前面的所有删除,最大的-1, 然后所有加1
所以其实像是在 最大的完成时 是 (n-1) + 最大 <= all
次大的是 (n-1) + 次大 <= all - (最大-1)
所以从大到小排 需要 (n-1) + 目标 <= all - sum (比他大 - 1)
比它小的个数 + 目标 <= all - sum 比他大
这里 比他大 如果大小相等 则比较index
那么问题是
- 这样的方案数如何算
- 有没有一种方案 是这样的操作无法达到的
想法是
- 如果 所有放完以后剩余remain >= n-1,那么所有位置随便放,就是个球插板法
- 如果所有放完以后剩余remain < n-1, 似乎只需要 0的个数 <= remain 即可,这样的状态都可达
- 这样操作无法达到的,显然也属于 剩余的 < n-1里的,因为 >= n-1剩余的 所有状态都可达,并且0的个数 > remain,
1 | 0 0 0 0 1 1 1 1 2 2 2 2 ... |
如何处理 remain < 0 的个数
且 remain < n-1
如果执行过一次所有+1
,那么每变成一个0,至少remain+1, 所以这种状态一定是 未执行过所有+1
所以 这种状态就是直接减
dp[i][j][k] =
前i个有j个0, k个remain是否能达成
然而这$O(N^3)$的样子
其实同理,如果在指定0的时候 是从正的下降,那0个数
增长是大于等于 remain的,所以一定有一些0是来自原本的0,那么对于下降的来说就是使用一次初始的0,所以可以优化成
所以dp[i][z] =
前i个剩余未使用0的方案数
dp[i][z] = dp[i-1][z] + dp[i-1][z+1] + dp[i-1][z+2] ..
, 一个是转移的值 大于等于增长+inc
, 其次 当 转移值 用尽 a[i]
,只需要+(a[i]-1)
然而还是$O(N^2)$, 转移倍率复杂度可以用区间和 优化成O(1)
这里可以拆的是, 指定一些非0的位置为0, 让dp转移始终 +增长量
问题变成,有n-(所有变成0)
个 a[i]-1
的球 的盒子 从中取不多于 count(zero) - sum(a[指定0]-1) > 0
个球的方案数
如何快速求?生成方程?
题解
读错题了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
读成 任意位置减去任意个了
那 这原题意就是 所有 -=1, bag+=count 或者, bag-=n, 所有+=1
那么第二个操作 显然是后置的, 否则 状态->操作2->操作1->状态
state -> k操作1 -> q操作2
满足 $\sum \min(k,a[i]) \ge q\cdot n$
$a[i]_{new} = a[i]-\min(k,a[i])+q$
然而这样的话 k的取值不会少
同样的观察,至少一个变成0以后,才会考虑使用q
$\min(a[i]) < k \le \max(a[i])$,随着k增加,$\sum \min(k,a[i])$ 有n段斜率
观察 最大的是 a[i]-k+q
,而最小的是q
,所以 不同的(k,q)
对应不同的方案(满足上述限制)
1 | f(k,q) |
感觉需要从n段斜率下手
1 | ans += min(a[i])+1 只用操作1 且操作1 >=min(a[i]) |
要转化也是
1 | for slope in n-1..1: |
需要floor_sum即可(atcoder库里有, abc283也有floor_sum)
代码
https://atcoder.jp/contests/abc313/submissions/49534183
1 |
|
Ex - Group Photo
第一排a[n],第二排b[n+1],所有数字两两不同
每排内可以随意换位置
目标
1 | a1 < b1 |
问 有多少第一排的所有重排列n!的方案mod 998244353,满足可以通过重排列第二排 来满足上述目标
n 5000
ai,bi 1e9
2s
1024mb
我的思路
题意简化就是每个bi要么大于ai,要么大于a[i-1]
这个or给我看傻了
如果是 没有这个or的情况,就是对应大于的话,那就是无脑的 的排序一一对应
而如果排序一一对应是可行的话,其实N!所有方案都可行
然后这里N给到5000的意思是要N^2吗
那对于一个给定的a[i]方案,如何判断它是否有对应的bi方案呢
那还是继承上面的贪心的想法,从最大的ai向下考虑,如果当前没有放置,则放置最大的bi到它对应位置???
然而似乎是不行的例如 这样也是一个方案
1 | 1 100 99 2 |
那么类似的,就是放置到它正下方或者+1的位置
不太行
那么就ai从小到大
对于最小的ai,需要bi,bi+1都比它大,而且一定取最小的两个bi
1 | .........ai.......... |
而且关心的是bi是否合法,所以这两个bi就不用考虑了,剩下的 ai和 bi都是n-1个
1 | [........] [..........] |
那么次小的a[i-1]
一样的,如果是对应两个位置就是最小的两个bi,如果对应1个位置就是最小的1个bi
1 | b = sorted(b) |
也就是 checkcount[i] = 2 - int(a[i-1] < a[i]) - int(a[i+1] < a[i])
然后 sorted(b) 按照 sorted(a)的checkcount每次检验对应大小
dp[i][cnt] =
a的前i个,已经检验的b的个数为cnt
dp[i][cnt] = dp[i-1][cnt-0/cnt-1/cnt-2] ???
转移条件呢
首先 cnt-2/-1/-0的发生需要满足bi和ai的大小关系
其次,注意到 当 -2时 意味着 ai中产生了一个不连通的新块(block+1)
-1时意味着某个块 增加了一个元素(block)
-0时意味着合并了两个块(block - 1)
由此得到 校验个数变化 = block变化+1
操作次数 x 校验个数变化 = 操作次数 x (block变化+1)
block个数 = 校验个 - 操作次数
ans = block个数=0
所以转移为
1 | for i in 1..n : # 1-index a,b |
答案
ans = dp[n][n+1]
似乎就过了
参考
https://atcoder.jp/contests/abc313/editorial
总结
F: 真不应该啊,都分析到那个地方了,最后的bitdp应该也很自然就能想到
G: 和F差不多啊,甚至需要floor_sum(第二次遇到)比F难,虽然是我读错题了艹,不过这两道题从难度上,自己都应该能过
Ex: 感觉甚至比F,G还简单,也没想很久
这期如果不考虑时间,应该自己能ak