Codeforces Round 804

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
D(dp)E(双指针,部分更新,线性筛1/2+1/3+1/4+...)

这次Div2的D,E都不会了

D

https://codeforces.com/contest/1699/problem/D

长度n数组A

每次操作可以删除相邻且不同的两个值, 剩下的拼在一起, 多次操作

要让最终的数组值全部相同,求最大长度

范围

n 5000

2s

256MB

题解

我的思路

如果我们指定哪个值留下来

假设是v

那么 考虑两个v之间的其它值 v …. v

如果其中有值x出现次数超过一半, 那么剩下的必然是x - 非x

否则,如果是奇数个剩下任意一个, 偶数个则全部清除

最后可以得到一个 v 非v v 非v v …

的多段结果

然后我并没有什么办法 处理这个

如果有办法就是n^2 的总复杂度了

题解

首先如果一个数出现次数超过一半,那最终剩下的一定是它,所以这种情况不用猜留哪个

如果整个长度是偶, 且没有数出现次数超过一半,那么可以被完全删除

然后通过O(n^2) 计算所有区间 最多出现的数字,或者全部可消除

啊 我知道啊

dp[i] 表示a[0…i]删除以后 结果包含a[i] 的最大长度

初始化 如果[0..i-1] 能完全删除 dp[i] = 1, 否则 dp[i] = -INF

如果j < i, a[i] == a[j] 且 [j+1..i-1] 能完全删除

dp[i] = max(dp[j]+1)

所以最后就是求所有中的最大的且后缀可删除rm[j..end] == true, 相当于找结果的末尾位置

代码

https://codeforces.com/contest/1699/submission/162852461

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

int a[5010];  // 5000 n^2
bool rm[5010][5010]; // rm[i][j] = [i..j] 完全删除
int dp[5010]; // 前[0..i] 删完剩下 a[i] 的个数

const int INF = 0x3f3f3f3f;

void w(){
  n = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n){
    fill(rm[i],rm[i]+n,false);
    vector<int>cnt(n+1,0); // 次数统计
    int maxc = -1; // 出现最多的
    rep(j,i,n){
      cnt[a[j]]++;
      if(maxc == -1 || cnt[maxc] < cnt[a[j]]) maxc = a[j];
      if((j-i)%2 == 0)continue;
      if(cnt[maxc] <= (j-i+1)/2) rm[i][j] = true;
    }
  }
  rep(i,0,n) dp[i] = (i == 0 || rm[0][i-1]) ? 1: -INF; // 初始化
  int ans = 0;
  rep(i,0,n){
    rep(j,0,i){
      if((i-j)%2==0)continue;
      if(a[i] != a[j]) continue;
      if(j == i-1 || rm[j+1][i-1]) dp[i] = max(dp[i], dp[j]+1);
    }
    if(i == n-1 || rm[i+1][n-1]) ans = max(ans,dp[i]); // 后续可删
  }
  printf("%d\n",ans);
}
 
int main(){
  int t = read();
  while(t--) w();
  return 0;
}

E

给你长度n数组a

每次你可以把任意一个值v=a乘b,拆成a,b,

求 min(max(数组) - min(数组))

范围

n 1e6

ai [1..5e6]

4s

256MB

题解

我的思路

直接想 有点像是说, 能否把每个数拆分进[l..r] 之间

变个方向就是 给定l,求最小的r

那么考虑l的变化

因为任意两个ai,aj的拆分方案互不影响, 考虑单个 v 拆成最小>=l时,最大r的最小值的

显然l增大时,r 非严格单增, 且l <= min(ai)的

而问题是让区间尽量小

区间长度并没有单调性或凹凸性, 想法方向GG

第二个想法是

我直接拆每个数, 去计算每个数的map[间隔] = vector< pair<最小,最大> >

比如 4: [0] = { { 2 , 2 } , { 4 , 4 } }

但不知道怎么拆, dfs暴力?

以及拆分后怎么在不同ai之间组合

题解

和我第一个想法类似但是倒着for最小的因子

因为不同v的拆法互不影响,考虑一个具体的原数组中出现过的 v

若当前最小因子恰好为i, 那么

如果 v不是i的倍数, 则,之前v怎么拆分就怎么拆分

如果 v < i^2, 显然不能拆,如果拆了 另一个因子就会小于i

v >= i^2 且v = ik , 那么会拆成i 和 k, 而对于k可能也有拆的方案

我们直接记录dp[k] = 当前拆分方案中, 最大的因子

有dp[ik] = min(old dp[ik], dp[k]), 其中k >= i

这里要注意的是当一个数v=ik是i的倍数,它按i拆开仅是可能让最大因子更小,而不是一定, 所以要和之前的dp[v] 比较

而最大值, 显然是非严格单调递减, 我们只需要 统计每个值拆分后的最大因子(也是非严格单调递减)出现次数, 就能知道最大值

代码

https://codeforces.com/contest/1699/submission/162860620

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
const int N = 5000000;
bool appear[N+10]; // 在数列中出现过
int mxval[N+10]; // [v] = v当前被拆分出来的更大的因子 , 运算过程中每个值的变化是非严格单调递减
int cnt[N+10]; // 遍历过程中 每个ai拆分后对应最大因子 的 次数统计
int n;
int m;
 
void w(){
  // clear
  fill(appear,appear+m+1,false);
  fill(cnt,cnt+m+1,0);
  fill(mxval,mxval+m+1,0);
 
  n = read();
  m = read();
 
  int mn = m; // 最小
  int mx = 0; // 最大
  rep(i,0,n){
    int x = read();
    appear[x] = true;
    cnt[x] = 1;
    mn = min(mn, x);
    mx = max(mx, x);
  }
  iota(mxval,mxval+mx+1,0); // mxval[i] = i; 默认都未被拆分
  int ptr = mx; // 最大值
  ll ans = mx - mn;
  per(i,1,mx+1){
    for (ll j = i * i; j <= mx; j += i) { // j = i * (k>=i) , j 拆分成 i 和 k, k可能继续能拆
      // 移除原有拆分方案
      if (appear[j]) cnt[mxval[j]]--; // 从真的统计上讲 应该是 [i]--, [mxval[j]]--, 但i <= mxval[j] 所以 这里 中间一段不影响结果
      // 计算新的最优方案
      mxval[j] = min(mxval[j], mxval[j / i]); // i 不一定是最小的, 所以吆喝之前的比较
      // 加入新的拆分方案
      if (appear[j]) cnt[mxval[j]]++;
    }
    while (cnt[ptr] == 0) ptr--;
    if (i <= mn) ans = min(ans, ptr - i); // 最小值为i, 最大值为ptr
  }
  printf("%lld\n",ans);
}
 
int main() {
  int t = read();
  while (t--) w();
}

总结

D

核心其实还是dpi可以和ai挂钩,因为其它什么区间可删除都想到了, 感觉应该还很常见的

E

倒着处理

只更新会影响的部分内容

因为遍历的i就是最小, 所以拆分统计, 不需要统计非最大因子以外的内容, 优化统计

参考

官方