AGC021到030

AGC021到AGC030题解合集

AGC的题面一般都不难懂,就不给出翻译了

0/10

AGC021

AGC021C - Tiling 讨论特判题,不想做

AGC021D - Reversed LCS

请先思考后再展开

考虑到$val(T,T’)=max\ {dp[1..i][i+1..n]*2,dp[1..i-1][i+1..n]*2+1}$,即dp到重叠后乘二就行了,所以可以独立决策,$dp(1..i,j..n,cnt)$即可,$O(n^3)$

1
2
3
4
5
6
fo(i,0,n) fd(j,n+1,i+1) fo(cnt,0,K)
{
chmax(dp[i+1][j][cnt],dp[i][j][cnt]);chmax(dp[i][j-1][cnt],dp[i][j][cnt]);
chmax(dp[i+1][j-1][cnt+(str[i+1]!=str[j-1])],dp[i][j][cnt]+1);
}
int ans=0;fo(i,0,n) fo(cnt,0,K) chmax(ans,dp[i][i+1][cnt]*2),chmax(ans,dp[i][i+2][cnt]*2+1);write(ans);

upd:发现其实我没意识到其本质是求最长回文子序列……

AGC028

AGC028E - High Elements code

请先思考后再展开

为了方便我的实现改为考虑更小的元素;设E集合为全局的前缀最小值

考虑逐位确定,那么我们需要判断的就是可行性

$设前面i个已经填完,前面的mi_0,mi_1,前面的长度c_0,c_1,后面的前缀最小值个数cnt$

对于两个集合只考虑下降部分,因为其他数总是至少有一种让它没用的分配方案(每个数丢到左边第一个更小的数所在集合即可)

将元素分为来自E的A类、其他B类,那么能等效地转化为至少一个集合的下降是只有A类的(设为集合0)

$c_0+cnt-a=c_1+a+b即2a+b=c_0-c_1+cnt$ 即要求存在一个「开头<mx,满足权值(A贡献2,B贡献1)为定值」的下降序列

因为一定能$a–$,所以对于某个奇偶性求最长的即可,考虑一个维护前缀max的支持撤销树状数组,询问也是前缀

从后往前插入元素来维护$f(num)$表示以num为开头的最长下降子序列,插入就是一个链修改,因为端点一直往后移动,这种东西是可以撤回的

时空复杂度 $O(nlogn)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/919438ff.html
转载请注明出处,谢谢!