首页 > 其他分享 >ARC100

ARC100

时间:2023-10-25 12:22:08浏览次数:30  
标签:好子 ARC100 序列 mathcal 考虑 underline

A

直接 \(a_i\gets a_i-i\) 做中位数就行。

B

这我都不会???

不能嗯二分答案。考虑相当于枚举三个数 \(i<j<k\) 算 \(s_i,s_j-s_i,s_k-s_j,s_n-s_k\),然后枚举 \(j\),显然 \(i,k\) 的最优决策点是单调的。直接双指针啊啊。

C

做一个高维前缀最大值 / 次大值。

D

不错的题?

考虑 \(k-\) 子序列出现过这个条件太烂,我们一般都是用全部答案减去一个 \(k-\) 好子序列都没有的情况。

全部答案的话,从 \(A\) 起点的方向考虑可以得出是 \(k^{n-m}(n-m+1)\)。

然后考虑不合法的情况。分三种:

  • \(A\) 中含 \(k-\) 好子序列:显然全都合法不用管。
  • \(A\) 中不含 \(k-\) 好子序列,而且有重复元素出现:此时我们需要左边和右边都没有 \(k-\) 好子序列。先考虑全局的情况。我们设 \(f_{i,j}\) 表示 \(i\) 个数,最后一个段长为 \(j\) 的方案数。转移就是 \(f_{i,j}\times (k-j)\to f_{i+1,j+1},f_{i,j}\to f_{i+1,p}(p\in [1,j])\)。前缀和维护可以 \(\mathcal O(nk)\) 计算。回到原问题,我们假设左右的最长连续不重段长度为 \(lef,rig\),那么分别做一次,初始化 \(f_{0,lef}=1\),右边是类似的。中间做一个卷积合并即可。
  • \(A\) 中不含 \(k-\) 好子序列,并且没有重复元素:这个时候我们统计全局每个不含 \(k-\) 好序列中的 \(m-\) 好序列个数,最后再除去 \(k^{\underline m}\),大概理解一下,这 \(A_1\sim A_m\) 并没有什么特殊的,和其它的 \(m\) 元组出现的系数一样,都是 \(k^{\underline m}\) 所以除去就好了。计算的话,大概还是那样,不过要开一个 \(g\) 数组,一边做着和 \(f\) 形式一样的转移,一边每次加上 \(f_i\) 中 \(\ge m\) 的下标元素。

时间复杂度 \(\mathcal O(nk)\)。最后一步讨论和第一步按位置拆贡献的思想非常棒。

标签:好子,ARC100,序列,mathcal,考虑,underline
From: https://www.cnblogs.com/Royaka/p/17786884.html

相关文章

  • AT_arc100_b 题解
    题意这道题是让我们把一段区间分成四个不为空的连续子序列,并算出每个区间的和,最后用四个和的最大值减去最小值,算出最终答案。分析大家首先想到的肯定是暴力法用三个循环枚举四个区间,对于每一个区间,在单独算和,这样的时间复杂度$O(n^4)$,肯定会超时。现在我们进行优化:最后求和的......
  • [ARC100E] Or Plus Max
    原题链接不难发现我们可以处理出每个状态所有子集中\(a_i\)的最大值和次大值,用一个pair<int,int>维护,跑一遍\(\text{SOSDP}\),这时每个状态的权值就是最大值加次大值,最终输出的每一个答案都是一个前缀最大值。点击查看代码#include<bits/stdc++.h>#defineFL(i,a,b)f......
  • Atcoder ARC100D Equal Cut
    发现是\(3\)个断点且数据范围的\(n\le2\times10^5\),根据2022CSP-SA留下的心理阴影不难想到可以枚举中间的那个点的同时移动左右两个端点。考虑如何移动,已知现在在枚举中间的断点\(i\),则现在被分为了两部分\(1\simi\)和\(i\simn\),因为要使极差最小,那就先可以让每一......
  • ARC100F口胡
    写一篇自己能看得懂的题解。。。。。。先考虑一个正难则反,用\(a\)序列出现过的次数减去在不好的序列里面的出现次数。前者显然是\(k^{n-m}(n-m+1)\),考虑后者的答案。......
  • ARC100E口胡
    垃圾\(O(3^n)\)做法/kk对于每个\(k\)分别计算答案,注意到\(i\)一定是\(k\)的子集所以先枚举一个\(i\),此时\(j\)应该是被钦定\(i\)为\(1\)的部分为\(0\),剩......