Educational Codeforces Round 55

EDU55E

输入

给你n(1<=n<=500'000)个数字(1<=a[i]<=500'000)和 一个目标值 c(1<=c<=500'000)

要求

任选连续一段加上任意值,使最后的c的出现次数最多,

输出

c最多出现的次数

解法

假设选的区间[l,r]是顶着头,或者 抵着尾的,那么和明显

ans= min(max{[0,i)出现k数字的次数}+[i,n)出现c的次数,max{[i,n)出现k数字的次数}+[0,i)出现c的次数)

用前缀和,可以O(n)做出,问题是无法解决 原数组1 2 1 目标是1的这种,只需要改中间的部分的.

---

想法1是 做分治

f(l,r) = max(fl(l,mid)+fr(mid,r),max(f(l,mid),f(mid,r)))

fl: c...c?...?

fr: ?...?c...c

也就是划分的mid是否 在选取的区间[l,r]内,问题是 看似分治了,但fl(l,mid)+fr(mid,r) 无法处理替换段是一样的情况,如果要处理时间复杂度不会够

---

之后想法是dp

因为可以观察到如果选取的值为v,那么整个数组上统计出现个数的时候采取的是形如

c…cv…vc…c的形状(其中每个形状均可以长度为0),那么也就是可以dp[state][i]来做,state分为第一段 第二段 第三段,

这样看上去是n*m的,但是 实际上当我们走到i的时候,只有a[i]的dp需要更改,所以是O(n)的

---

dp的整理

既然上面也观察到进行到i,只会影响到a[i]相关,那么可以把不同数字的都整合到一起,因为只会有当前a[i]对i位置的进行写和读(==c的会有其它读)

考虑形状

c...c?...?c...c
         i

那么有 ans = max{ [0,i] 中前部分选c后部分选a[i]的最大次数+[i+1,n-1]c出现的次数 }

[0,i]中前部分选c后部分选a[i]的最大次数
= [0,i]中a[i]的次数 + max{[0,j]选c相对于选a[i]的增量} 其中0<=j<=i
= [0,i]中a[i]的次数 + max{[0,j]选c-[0,j]选a[i]} 其中0<=j<=i

至此上面皆可前缀和

i = 1 -> n:
  sumc[i] = sumc[i-1] + (a[i] == c); // 前缀和,求到i个 有多少个c
  sumci[i] = sumci[pre[a[i]]]+1; // 前缀和,求到i个 有多少个a[i]
  maxder[i]=max(maxder[pre[a[i]]],sumc[i-1]-sumv[i]+1); // [0->j] 计算a[i] -> c变化的最大增量
  pre[a[i]]=i; // pre记录a[i]上一次出现的位置
}
ans <- 0;
i = 0 -> n;
  ans=max(ans,maxder[i]+sumci[i]+(sumc[n]-sumc[i])); // 增量+[0,i]中a[i]的个数+[i+1,n-1]中c的个数

代码

code