CodeChef June Div1 Prefix Suffix Distinct(数学)

發表於 更新於 分類於 Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

主要问题不在算法,在自己写bug

题目

https://www.codechef.com/submit-v2/PRFSUFDSTNCT

一个数组, 的前缀i个数,不重复的数值个数为pi

后缀i到结束,不重复的数值个数为si

给你p和s,问是否存在数组满足, 返回是否即可

范围

n 1e5

1s

题解

我的思路

首先最直接的,

p[0] = s[n-1] = 1

p[n-1] = s[0]

然后 p的增量为0/1,s的增量为0/-1

再因为每个值至少贡献1次

所以如果p[i] + s[i+1] == p[n-1], 那么说明 i 和i+1 可以切开,并且这位置p增量为1,s增量为-1

对于切开后的每一段 找到变化的位置(增量为1/-1)的位置

分别跑后缀的前缀 应该小于等于前缀(与前缀首个的差)

和 前缀的后缀 应该小于等于后缀(与后缀最后一个的差)

官方

反而没有切割的操作,上面几个倒是有

官方 判断了个a[i]+b[i] <= a[n-1] 跟我切割操作有点像,但是 不是错位的判断

原理和我那个也是类似,所有数贡献一次,左右统计的第i个两侧都有贡献,所以至少是a[n-1]+1

–

分析的是同一位的(p[i]-p[i-1],s[i]-s[i+1]) 的四种情况

1,1 原数组中唯一的值, 不需要额外判断, 甚至可以考虑原数组删除它

0,1 和 1,0 是对称的, 如果全部都是这两个

那么1,0 的出现意味着 右侧会有一个0,1 也就是从后缀上这个数首次出现的

可以看成1,0左括号,0,1右括号做括号匹配, 但不完全是相邻位置的, 如 (()), 可以1和3,2和4配

0,0 说明没有变化,应该被包含在某个值中, 如果记作.

那么(.)(.)是好的, 而().(),0,0无值可选

如此检查

(.)(.) 如

1
2
p 111222
s 222111

正好一个答案是111222

().()如

1
2
11122
22111

再换句 (, 上面+1, 右括号下面后一个-1, 所以考虑上下的总和变化, 出现问题就是 a[i]+b[i] <= a[n-1]

看了一下应该是有真的代码被我判否了, 因为我把答案逻辑塞到我代码后面return false也不对

最后发现是因为我代码 if 的l和r复制漏改了

代码

按照我的逻辑AC的代码

https://www.codechef.com/viewsolution/66653363

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#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
ll p[100010]; // a 前缀 [..i] 不同的个数
ll s[100010]; // a 后缀 [i..] 不同的个数

bool p0[100010];
bool p1[100010];
// 只用 yes or no
int n;

// 保证范围 单增 单减 , 跨度 0/1
bool check(int l,int r){
  // [st..en]
  if(l > 0 && p[l] != p[l-1]+1) return false;
  if(r < n - 1 && p[r] != p[r+1]-1) return false;

  if(l > 0 && s[l] != s[l-1]-1) return false;
  if(r < n - 1 && s[r] != s[r+1]+1) return false; // 这里写成l了

  if(p[r] - p[l] != s[l] - s[r])return false;

  // 计算变化的点
  rep(i,l,r+1){
    if(i == r || p[i] != p[i+1]){
      p0[i] = true;
    }
  }
  rep(i,l,r+1){
    if(i == l || s[i] != s[i-1]){
      p1[i] = true;
    }
  }

  // 跑前缀 <= 前缀
  {
    int cur = 0;
    rep(i,l,r+1){
      cur += p1[i];
      if( cur > p[i] - p[l]+1) return false;
    }
  }
  {
    int cur = 0;
    per(i,l,r+1){
      cur += p0[i];
      if( cur > s[i] - s[r]+1) return false;
    }
  }

  return true;
}

bool w(){
  // 清空
  n = read();
  fill(p0,p0+n,0);
  fill(p1,p1+n,0);
  rep(i,0,n) p[i] = read();
  rep(i,0,n) s[i] = read();
  // p [n-1] 不同的总数
  if(p[n-1] != s[0]) return false;
  if(p[0] != s[n-1]) return false;
  if(p[0] != 1) return false;
  // 跨度 0/1
  rep(i,1,n)if(p[i] < p[i-1] || p[i] > p[i-1] + 1)return false;
  rep(i,1,n)if(s[i] > s[i-1] || s[i] < s[i-1] - 1)return false;
  int itr = 0;
  rep(i,0,n-1){
    if(p[i] + s[i+1] == p[n-1]){
      if(!check(itr,i)) return false;
      itr = i+1;
    }else if(p[i] + s[i+1] < p[n-1]){
      // ???
      return false;
    }
  }
  return check(itr,n-1);
}

int main(){
  int t = read();
  while(t--) printf("%s\n",w()?"YES":"NO");
  return 0;
}

总结

BUG 是我AC失败一个重大阻碍

题解的转化我也是没想到的学习了

参考

官方