YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

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

D https://ac.nowcoder.com/acm/contest/11201/D

总思路没问题, dijkstra不能带log, 2s时间卡时限了

没有log的也800ms, 稍微一个3倍都过不了

所以需要的是点的值要么是初始的要么是推导(当前最大值-定值k)生成的, 双队列+指针实现

没过这题也能+3

代码

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
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

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

int read(){int r; scanf("%d", &r);return r;} // read

int a[500010];
int n,m,k;

bool vis[500010];

const int di[] = {-1,1,0,0,-1,1};
const int dj[] = {0,0,-1,1,1,-1};

vector< array<int,3> > startvij;

ll cost(int diff){
  fill(vis,vis + n*m,false);
  vector< array<int,3> > vp = {}; // 优先队列等含有log的会TLE
  ll sk = 0 ;
  vp = {};
  int i0 = 0;
  int i1 = 0;
  while(i0 < startvij.size() || i1 < vp.size()){
    int v = 0;
    int i = -1;
    int j = -1;
    if(i0 < startvij.size() && i1 < vp.size()){
      if(startvij[i0][0] >= vp[i1][0]){
        v = startvij[i0][0];
        i = startvij[i0][1];
        j = startvij[i0][2];
        i0++;
      }else{
        v = vp[i1][0];
        i = vp[i1][1];
        j = vp[i1][2];
        i1++;
      }
    }else if(i0 < startvij.size()){
      v = startvij[i0][0];
      i = startvij[i0][1];
      j = startvij[i0][2];
      i0++;
    }else {
      v = vp[i1][0];
      i = vp[i1][1];
      j = vp[i1][2];
      i1++;
    }
    if(vis[c(i,j)])continue;
    vis[c(i,j)] = true;
    sk += v - a[c(i,j)];
    rep(w,0,6){
      int ni = i + di[w];
      int nj = j + dj[w];
      if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
      if(a[c(ni,nj)] == -1) continue;
      if(vis[c(ni,nj)]) continue;
      if(v - diff > a[c(ni,nj)]){
        vp.pb({v - diff,ni,nj});
      }
    }
  }
  return sk;
}

int main(){
  n = read();
  m = read();
  k = read();

  rep(i,0,n){
    rep(j,0,m){
      a[c(i,j)] = read();
      if(a[c(i,j)] != -1) startvij.pb({a[c(i,j)],i,j});
    }
  }
  sort(startvij.begin(), startvij.end(), greater<array<int,3>>());

  int l = 0;
  int r = 1000;
  int ans = 1000;
  while(l <= r){
    int mid = (l+r)/2;
    if(cost(mid) <= k){
      ans = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
  cout<<ans<<endl;
  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 4.1k 所需閱讀時間 ≈ 14 分鐘
C(反向dijkstra)D(DP,数学,贡献)E(标记,延后处理,贪心,树状数组)F(0/1串,数学)

D

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

给你一个排列

问多少个子区间 可以表示成 增序列和减序列合成的, 称作Decinc

范围

n 2e5

2s

512MB

题解

我的思路

如果是判断一个是否合法

考虑

inc[i] 表示i在增序列, 减序列的最大值

dec[i] 表示i在减序列, 增序列的最小值

然后dp一下O(n) 就做了

然后这里考虑有没有办法转移

因为如果[i..j] 是decinc的,那么它的所有子区间也是

考虑有没有办法dp然后做转移, 发现并没有办法转移

题解

AmShZ

一样的, 但是说是可以证明均摊更新是常数倍?

对于给定i, 找最大的j, 使得 j < i, a[j] > a[j+1]

注意到a[j],a[j+1] 不会都在增序列里,必定一个在减序列里

情况1 a[j+1] 在增序列的话 => a[j] 在减序列

情况2 a[j+1] 在减序列

且因为它是最大的j, 所以a[j] > a[j+1], 且a[j+1] < a[j+2] < a[j+3] < ... < a[i]

inc[i] = a[j](情况1) or a[j+1](情况2) or 0

而对于inc[i]初始化是是inf, 而对于a[j+1]..a[i]这一段都是inf

所以每个位置的值只会有4种情况

dec对称关系同理

换句话说

l从大到小,

每轮从小到大, 如果更新才会去算下一个位置, 否则提前退出

这里还有一点是就是 运算时,当给定l的时候, dp[i]仅依赖于dp[i-1]和a[i], 所以说如果dp[i]没有更新,则i以后的也不会更新, 所以更新的一定是连续的区间

所以sum 遍历 = sum 更新次数 = sum变化次数 = O(n)

Koosha_Mv

一个由升序和降序列合成的序列,当且仅当它不含 3412 也不含 2143

显然包含则不满足

怎么证明不满足一定包含这样的呢

回到dp的过程, 如果刚好在i不满足,

那么, 如果 a[i-1] < a[i], (a[i-1] > a[i] 对称同理

显然a[i-1] 在增序列不合法, (如果a[i-1] 在增序列有合法方案,那么把a[i]放到增序列即可

a[i-1]在减序列, 且 增序列最小值 > a[i]

所以 存在a[j] > a[i] > a[i-1], j < i-1

所以原序列是由

增序列 ..... a[j] 和 减序列.... a[i-1]合成的

因为a[j] 是满足的最小的a[j]

也就是, a[j] 不能放进减序列里(如果可以则能得到更小的增序列值

那么 不妨设下标 w(可能不存在) < j < k ,且 a[k] 在减序列中, a[w] 在减数列中

那么a[j] < a[k] (j k i-1 i => 3 4 1 2) 或 a[j] > a[w](a[j] 左侧至少一个

考虑把a[j]左侧分成三部分讨论, 大于a[j]的, a[i]到a[j]之间的, 小于a[i]的

如果a[i]到a[j]之间存在(3 4 1 2)`, 否则完全不存在, 且 小于a[i] 至少一个

如果大于a[j]的存在,则一定全属于减序列

如果小于a[i]的有不只1个, 那么一旦有其中两个递减 => (? ? j i) => (2 1 4 3) 即它的对称状态

小于a[i]的一定是升序列

总上可以重组 升序列a[j] 左侧,小于a[i], 包含a[w] .... a[j], 降序列a[j]左侧大于a[j]...a[j]右侧原减序列

注意到这样重组以后, a[j] 可以被放入减序列, 而增序列最小值将不再是a[j]

性质充要得证

如何实现

注意到3412和2143是对称的,所以a[i] = n+1-a[i] ,再跑一次3412就行

那么如何计算3412

考虑计算的结果是对于当前位置i作为3,min_r[i]表示最近的2让3412出现

给定3以后,4要是最近的,如果有2,那么1是离2最近的

所以先预处理每个位置后面和它最近的比它大的,以及每个位置前面最近的比它小的的位置

但是记录并不是[3]->4, [2] -> 1

考虑反着来4-> array{3}, 1->array{2}

为什么要这么样做呢,因为除了大小关系还有顺序,1 需要在4的右侧

那么我们倒着遍历4的位置

我们可以用fenwick记录i右侧, (1,2) 存在的[值]->2的坐标

这样我们对于每个3, 去fenwick上查, 值 < 3的值中存在的最大坐标, 就算出答案了

代码

https://codeforces.com/contest/1693/submission/160996027

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
#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 = 2e5 + 10;

int n;
int a[N]; // 数组
int inc0[N]; // a[i] 在增数组时, 减数组的最大值
int dec0[N]; // a[i] 在减数组时, 增数组的最小值
int f[N]; // f[i] = 该轮次的计算中,当前点i到 以l为起点的终点 的距离
ll ans;

void udec0(int i){
  if (n >= i){
    // 就硬算
    int inc1 = max( (dec0[i - 1] < a[i]?a[i - 1]:0), (a[i - 1] < a[i] ? inc0[i - 1]: 0));
    int dec1 = min( (a[i] < inc0[i - 1]?a[i - 1]:n+1), (a[i] < a[i - 1] ? dec0[i - 1]: n+1));
    if (!(inc1 == inc0[i] && dec1 == dec0[i])){ // 更新的一定是连续的区间, sum(遍历) = sum(更新) = sum(变化)
      inc0[i] = inc1;
      dec0[i] = dec1;
      f[i] = 0; // 结束点 距离为0
      if (dec1 <= n || inc1) udec0(i+1);
    }
  }
  f[i - 1] = f[i] + 1; // 到结束点距离+1
}

int main(){
  n = read();
  rep(i,1,n+1) a[i] = read();
  per(i,1,n+1) { // 倒序l
    inc0[i] = n + 1;
    dec0[i] = 0;
    udec0(i + 1);
    ans += f[i];
  }
  printf("%lld\n", ans);
  return 0;
}

3412,2143的

https://codeforces.com/contest/1693/submission/161132167

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
#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 = 2e5 + 10;


int INF = 0x3f3f3f3f;

// 前缀最小值fenwick
struct Fenwick {
  const int n;
  vector<int> a;
  Fenwick(int n) : n(n), a(n, INF) {}
  // 支持 [0..n) 更新最大值
  void setMin(int x, int v) {
    for (int i = x + 1; i <= n; i += i & -i) a[i - 1] = min(a[i - 1], v);
  }
  // 获得 [0,x) 最大值
  int get(int x) {
    int ans = INF;
    for (int i = x; i > 0; i -= i & -i) ans = min(ans, a[i - 1]);
    return ans;
  }
};


int n;
int a[N]; // 数组
int min_r[N];
ll ans;
stack <int> sk;
vector <int> vec[2][N];

// 如果指定3和2的位置,所以你需要的是3后面最近的4, 和2前面最近的1
void find_3412(){
  Fenwick f(n+10); // 下标是值, 前缀表示小于某个值的出现的最小坐标
  rep(i,0,2) fill(vec[i]+1,vec[i]+n+1,vector<int>());

  // vec[0][i] = vector<int> {j,...}, 表示 j 前面最近的比j小的是i, sk中保留单增的值对应的下标
  sk = {};
  rep(i,1,n+1) {
    while (!sk.empty() && a[i] < a[sk.top()]) sk.pop();
    if (!sk.empty()) vec[0][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做一边, sk中保持值单调递减, vec[1][i] = {j...} , j后面最近的比a[j]大的是a[i]
  sk = {};
  per(i,1,n+1) {
    while (!sk.empty() && a[sk.top()] < a[i]) sk.pop();
    if (!sk.empty()) vec[1][sk.top()].push_back(i);
    sk.push(i);
  }
  // 倒着做
  per(i,1,n+1){
    // f在遍历过程中,存的是(1,2) 的下标都>=i, 然后[2的值] = 位置
    // i=>1, ind=>2
    for (auto ind : vec[0][i]) f.setMin(a[ind], ind); // (i,ind) 构成增序列
    // 这次就是 i=>4, ind => 3, 因为如果确定了3,那么4就最近最好, 所以查询的是(1,2)位置在(以后,且值小于3的,结束位置的最小值),
    // 这里遍历过程之所以i=>4 而不是3,主要因为 保证(1,2)在当前位置右侧
    for (auto ind : vec[1][i]) min_r[ind] = min(min_r[ind], f.get(a[ind]));
    // 得到的是min_r[3的位置] = 最近的2的位置能构成3 4 1 2
    // 在反转过程中 min_r 直接取min,而f是清空
  }
}

int main(){
  n = read();
  INF = n+1;
  rep(i,1,n+1) a[i] = read();
  fill(min_r, min_r + n + 2, INF);
  find_3412();
  rep(i,1,n+1) a[i] = n + 1 - a[i]; // 做对称, 因为对称不影响答案, 而3412和2143是对称的
  find_3412();
  per(i,1,n+1) {
    min_r[i] = min(min_r[i], min_r[i + 1]);
    ans += min_r[i] - i;
  }
  printf("%lld\n", ans);
  return 0;
}

E

题目

https://codeforces.com/contest/1693/problem/E

n+2 长度数组a

首尾元素值为0

最小操作次数让 所有值 = 0

每次操作可以任选以下一种

  1. 最左的最大值=它的左侧的最大值
  2. 最右的最大值=它的右侧的最大值

范围

n 2e5

2s

256mb

题解

我的思路

值挺友好,给你的是[0,n]的范围,(就算很大也可以手动离散

没思路了

ecnerwala

官方的代码实在太长了

ecnerwala 有个超短的代码

https://codeforces.com/contest/1693/submission/160890042

有点延后判断, 贪心选最小值的意味

1
2
3
4
5
6
7
8
9
10
11
12
0 1 4 2 4 0 2 0
. . . . . . . . // 初始
. . ? . ? . . . // 最大的标记为?, 贡献 +2, 意义是第一轮处理2个

. . . x x x x . // 准备处理2的也就是x覆盖区间的, 把区间左侧问号标成 <(表示这个?位置的值比当前小,和左侧的最值相等, 右侧标成 > (同理
. . < . ? . . . // 标记
. . < ? ? . ? . // 对2处理, 贡献 +3

. . ? > > . > . // 同理对于1, 但注意到 1右侧的 < 会变成? 因为
. ? ? > > . > . // 贡献+2

// 0 不需要处理

总贡献是2+3+2 = 7

样例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0 1 3 5 4 2 0
. . . . . . .

. . . ? . . . // +1

. . . < . . . // 
. . . < ? . . // +1

. . . ? > . . //
. . ? ? > . . // +2

. . < < ? . . //
. . < < ? ? . // +2

. . ? ? > > . //
. ? ? ? . . . // +3

1+1+2+2+3 = 9

再补充一个例子 1 2 3

1
2
3
4
5
6
7
8
9
10
0 1 2 3 0
. . . . .

. . . ? . // +1

. . . > . // 
. . ? > . // +1

. . > > . // 
. ? > > . // +1

1+1+1 = 3

总的来说, 每轮最大值,确定覆盖区间

区间左侧:

1
2
? 变 <
> 变?

区间内部

1
2
< 变 ?
> 变 ?

区间右侧

1
2
? 变 >
< 变 ?

最后最大值的所有点都是? , 统计?个数即可

实现

并不需要真的像上面思路那样维护4种 . , ? , > , <的状态

发现其实只需要统计?的个数

那么?个数有多少呢

区间内,所有大于它的都变成了问号, 所以区间内就是大于它的个数

区间左侧, 可能有 >,?,<

但 注意到一旦出现 > ,说明上一轮 > 的左侧有?, 如果出现 < 说明上一轮右侧有 ?

引理, 每轮结束后 除开.的情况,剩下的一定是 < ? > 形状的

归纳法可证明

因此, 你需要统计的是

  1. 相交关系
1
2
3
4
5
    ?   ?      // 上一轮结果
<  [l...r] >   // 上一轮结果
     [l...r]   // 本轮
      ?   ?    // 本轮
   < [l...r]>  // 结果
  1. 非相交关系
1
2
3
4
5
    ?   ?                 // 上一轮结果
<  [l...r] >              // 上一轮结果
                [l...r]   // 本轮
                 ?   ?    // 本轮
        < [l      ...r]>  // 结果

有

1
2
newl = min(l, lastr)
newr = max(r, lastl)

区间统计点 = 前缀差 = 树状数组维护

代码

ecnerwaia https://codeforces.com/contest/1693/submission/160890042

基于修改+注释+自己格式+bit改为fenwick: https://codeforces.com/contest/1693/submission/161139663

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
#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;)
 
ll read(){ll r;scanf("%lld",&r);return r;} // read
 
int main() {
  int n = read();
  vector<vector<int> > idxs(n+1); // [值] = 下标数组
  rep(i,1,n+1) idxs[read()].push_back(i);
 
  vector<int> fenwick(n); // 树状数组, 大于等于当前的点记为1
 
  ll ans = 0;
  int lo = 1, hi = n + 1; // 左闭右开, [lo,hi)
  per(v, 1, n+1) { // 从大到小
    if (idxs[v].empty()) continue; // 忽略不存在的值
    // 本轮全为问号的范围
    std::tie(lo, hi) = make_pair(
        min(idxs[v].front(), hi),
        max(idxs[v].back()+1, lo)
    );
 
    // 本轮点 树状数组上标记为1,
    for (int a : idxs[v]) {
      for (; a <= n; a += (a&-a)) fenwick[a-1]++;
    }
    // 区间 [lo, hi) = pre[hi-1] - pre[lo-1]
    for (int a = hi-1; a; a -= (a&-a)) ans += fenwick[a-1];
    for (int a = lo-1; a; a -= (a&-a)) ans -= fenwick[a-1];
  }
  printf("%lld\n", ans);
  return 0;
}

F

https://codeforces.com/contest/1693/problem/F

0/1 字符串 S

每次选择一段 sort, 代价 |cnt(1) - cnt(0)| + 1

求最小总代价,让整个S有序

范围

n 2e5

题解

我的想法

假设最后一次操作了 [l..r]

那么说明 操作之前, [0..l-1] 和目标一样[r+1..n-1] 和目标一样

并且[l..r]中的1和0的个数尽可能的靠近

题解

结论: 只对0和1个数相等的进行排序

证明:

若最优方案中, 对[l,r]排序,且区间中,0比1多d个(d > 0), 代价d+1

如果l上是0, 只需要对[l+1,r]排序,代价为d, 且效果相同, 所以l上一定是1

确定区间左端点,右端点增加时,0和1的差的变化为+1/-1

因此必然存在k < r, 区间 [l,k] 的0和1的个数相等

排序[l,k],代价1, 再排序 [l+1,r] 代价 = d, 总代价 = d+1

所以任何一个0比1多排序, 可以拆成 (0和1相等的排序,代价1) + (0和1的差更小,更短,比原来代价更小的排序)

对于1比0多的情况, 对称关系同理可证

得证

问题变成如何选尽量少的0和1相等区间排序

把0换为-1

又变成经典的,前缀和2维图形化了, 每次选择的是等高的点, 让等高点之间变成 V字形

假设1比-1多,那么也就是结束点比起点高, 如果最后一段是从一个和起点相等的值 一直+1达到 结束点的,那么 把起点和这个值的区间处理即可

所以就是让最后一个连续+1 到的结束点 的那一串尽量长

我们记录达到每个值的首先出现的点, 只考虑(>=0的部分) 显然随着值越大,下标大,( 因为是从0涨过来的

而我们对末端的操作不会改变这个首次出现的位置

贪就完了

-1 比 1多 对称处理即可, 这里只要方案数不要操作细节,(所以还可以把 1变-1,0变1,并旋转字符串)

样例输入1的最后一个数据

这个和上面假设相反, 那就是 把头部可达的值的最小值的最后出现位置之间做区间处理

当然也可以双指针, (总代价移动是线性的

代码

https://codeforces.com/contest/1693/submission/162002156

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;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;} // read

char s[200010];
int pre[200010]; // 前缀和
int pos[200010]; // 首次出现的位置

int w(){
  int n = read();
  fill(pos,pos+n+1,-1);
  scanf("%s",s);
  int cnt[] = {0,0};
  rep(i,0,n) cnt[s[i] == '1'] ++;
  if(cnt[0] > cnt[1]) { // 保证 个数1 > 个数0
    swap(cnt[0],cnt[1]);
    rep(i,0,n) s[i] = (1 - (s[i] - '0')) + '0';
    rep(i,0,n/2) swap(s[i],s[n-1-i]);
  }
  int d = cnt[1] - cnt[0];
  rep(i,0,n) pre[i+1] = pre[i] + (s[i] == '0'? -1 : 1);
  rep(i,0,n+1){
    if(pre[i] < 0) continue;
    if(pos[pre[i]] != -1) continue;
    pos[pre[i]] = i;
  }
  int minv = d; // 倒着最小能连续到达的值
  per(i,-cnt[0],d+1){
    if(pre[n - (d-i)] != i) break;
    minv = i;
  }
  int ans = 0;
  while(minv + cnt[0] > 0){ // 已经完成排序
    if(minv < 0) return ans + 1; // 和l=0配
    ans ++ ;
    minv -= ((n-(d-minv))/*r*/-pos[minv]/*l*/)/2; // [l..r]
  }
  return ans;
}

int main(){
  int t = read();
  while(t--) printf("%d\n",w());
  return 0;
}

总结

C

Dijkstra 性质还是不够熟啊

D

直接的dp能想到,也在想转移,倒是转移也可以倒着做, 而且需要推导这个变化的条件,从而得到必定是区间变化,有遍历次数=变化次数=可能次数

另一个方案, 我有大的方向, 说看能不能找不成立的,但是没有得到3412/2143, 一个是这个充要真不知道比赛能不能快速证明,

再就是3412, 就算我知道了, 也不知道怎么去算, 这个按中间位置做遍历, 预处理 两头算是又学了一手

E

总觉得好像见过类似的标记处理, 这里是标记+延后+贪心

哦 像python里的 a,b= b,a+b 可以写成 std::tie(a,b) = make_pair(b,a+b)

原来树状数组还有bit和fenwick写法区别

bit版本的是 a|=a+1

fenwick的是 a+=(a&-a)

逻辑上 bit版本,统计的是末尾连续1的所有子集或上高位1的信息

而fenwick是当前结束向前(a&-a)长度的信息

F

敢于去猜让解答变容易的特殊情况,并证明它

经典的0/1区间个数相等处理, 变成-1,1 和二维图

参考

官方

ecnerwala E

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
F(2-sat)

我的第二次 2-SAT 练习

题目

https://codeforces.com/contest/1697/problem/F

给你m个限制, 分别可能是

  1. $a_i \neq x$
  2. $a_i+a_j \ge x$
  3. $a_i+a_j \le x$

请构造一个满足限制的长n的数组a, 且每个元素在$[1,k]$之间

范围

n 2e4

m 2e4

k 10

2s

512MB

题解

我的思路

一眼2-sat,写过但不熟, 来看看题解如何建立图的

tourist ,jiangly也是拖的板子, XD, 看来我要好好准备板子了?

题解

一个值拆成2k个点

分别是$\le 1,\le 2,\cdots,\le k,>1,>2,\cdots,>k$

其中$\le i, > i$ 是一个互补对

$(i,v,0) = a_i \le v$

$(i,v,1) = a_i > v$

因为2-sat 就是每个点选或不选 0/1, 而上面的两个必定一个满足一个不满足

$(i,v,0) \to (i,v+1,0)$ 不等式关系

$(i,v,1) \to (i,v-1,1)$ 不等式关系 (可以由上面自动建立对称关系

$(i,v,1) \to (i+1,v,1)$ 非严格单增

$(i,x,0) \to (i,x-1,0)$, $a_i \ne x$

$(i,x-1,1) \to (i,x,1)$, $a_i \ne x$ (可以由上面自动建立对称关系

$(i,v,1) \to (j,x-a_i-1,0)$, $a_i + a_j \le x$, 轮换$i,j$

$(i,v,0) \to (j,x-a_i-1,1)$, $a_i + a_j \ge x$, 轮换$i,j$

对于限制必定不合法的$(i,v,x)$ , 建立 $(i,v,x) \to (i,v,x\oplus 1)$

2-sat 的选择

之前有个问题, 我一直没想太通, 现在有点思路了

假设我们完成建边和tarjan的部分

如下, 这样那怎么顺序选都没问题

1
2
a0 <-> b0
a1 <-> b1

而对于这种, 你是不能去选b1/c1 的,而这也是Tarjan 不会处理的,因为tarjan只是合并联通块, 这种还算有答案

1
2
3
a0 <-> b0
b1 <-> c1
c1 -> a0

这种是没有答案, 而且tarjan 的时候是判断不了的

1
2
3
a0<->b0
b1<->c1
c0<->a1

那么两个办法我想的

方法一

如果我们要加 $a[x] \to b[y]$

考虑 如果 $b[y\oplus 1]$ ,那么a不能选x, 所以同时会产生$b[y\oplus 1] \to a[x\oplus1]$

这个好处是,本身可以利用tarjan

方法二

在tarjan处理完scc后, 对scc的每个点的反点做并查集, 缺点是还要跑并查集

等价性 一个奇怪的视角可以证明就是 这些操作是对称性的, 比如方法一里面每次都是对称加的边, 而方法二,不妨设scc 中的反点个数比它大,那么scc必定会合其它scc连接,最终所有并查集完成后, scc和scc反点的scc个数相等

这两个任选一种以后, 最后对scc/并查集 做原图的反向边 做倒序拓扑选择,必定有解?

再看上面的 3个例子

第一个不变

1
2
a0 <-> b0
a1 <-> b1

第二个变成如下,你需要反向拓扑选择

1
2
3
a0 <-> b0 <-> c0
a1 <-> b1 <-> c1
c1 -> a0

第三个则全部连到一个并查集里了, 直接确定不合法了

第三个是限制的不可选状态

比如 $(i,x)$ 不可选, 之前的办法是做一个 失败的节点,让它和这个节点双向连通

而现在发现其实$(i,x) \to (i,x\oplus 1)$, 因为这样如果选$(i,x)$自动造成矛盾

注意区别是不可选还是选了一定满足

代码

我先自己写了个twosat的板子,下次也可以用

https://codeforces.com/contest/1697/submission/160657743

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#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

class TwoSat{
  vector<int> low; // 能达到的最小的点
  vector<int> dfn; // tarjan 用的深搜访问次序标识
  stack<int> stk; // tarjan 用的stk
  vector<int> res; // tarjan 结果
  vector<vector<int> > p; // 所有点
  int n;
  void scc(int v) {
    static int id = 0;
    low[v] = dfn[v] = id++;
    stk.push(v);
    for(auto w:p[v]){
      if(dfn[w] == -1){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(res[w] == -1){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  TwoSat(int SZ):n(SZ){ // 点范围[0..SZ-1]
    low = vector<int>(2*n,-1);
    dfn = vector<int>(2*n,-1);
    stk = {};
    res = vector<int> (2*n,-1);
    p = vector<vector<int> >(2*n);
  }

  bool calc(vector<bool> & ans){
    rep(i,0,2*n) if(res[i] == -1) scc(i);
    // rep(i,0,2*n) printf("scc[%lld] = %d\n",i,res[i]);
    rep(i,0,n) if(res[i*2] == res[i*2+1]) return false; // 同一个块的真假都在一个scc里
    vector<int> revscc(2*n); // 互斥scc
    rep(i,0,n) {
      revscc[res[i*2]] = res[i*2+1];
      revscc[res[i*2+1]] = res[i*2];
    }
    vector<set<int> > scc2scc(2*n);
    unordered_map<int,int> degree; // scc入度
    unordered_map<int,bool> scctf; // scc 真假
    rep(i,0,2*n) { // 跨scc的反向边, 做拓扑选择
      degree[res[i]] = 0;
      for(auto j:p[i]){ // i -> j
        if(res[i] == res[j]) continue;
        scc2scc[res[j]].insert(res[i]);
      }
    }
    for(auto s:scc2scc){
      for(auto t:s) degree[t]++;
    }
    vector<int> d0; // 入度为0
    for(auto [v,d]: degree) if(!d) d0.pb(v);
    rep(i,0,d0.size()) {
      if(!scctf.count(d0[i])){ // 没有选择过
        // printf("pick %d, unpick %d\n",d0[i],revscc[d0[i]]);
        scctf[d0[i]] = true;
        scctf[revscc[d0[i]]] = false;
      }
      for(auto item:scc2scc[d0[i]]) { // 更新入度排序
        if(!(--degree[item])) d0.pb(item);
      }
    }
    ans = vector<bool>(n);
    rep(i,0,n) ans[i] = scctf[res[i*2+1]];
    return true;
  }
  void p2(pair<int,bool> pi, pair<int,bool> pj){ // {i,true/false} -> {j,true/false}
    auto [i,bi] = pi;
    auto [j,bj] = pj;
    // printf("(%d,%d) -> (%d,%d)\n",i,(int)bi,j,(int)bj);
    // printf("(%d,%d) -> (%d,%d) (auto\n",j,(int)bj^1,i,(int)bi^1);
    assert(i >= 0 && i < n);
    assert(j >= 0 && j < n);
    p[2*i+bi].pb(2*j+bj);
    p[2*j+(!bj)].pb(2*i+(!bi)); // 自动建立逻辑边
  }
};


int n;
int m;
int k;

int c(int i,int j){
  return i*k+j;
}

void w(){
  n = read();
  m = read();
  k = read();
  TwoSat ts(n*k);
  // a[i][j=0..k-1] => i*k+j
  // false : <= j+1
  // true  : >  j+1
  // 不等式关系
  rep(i,0,n){
    rep(j,0,k-1){
      ts.p2({c(i,j),0},{c(i,j+1),0}); // 自动建立反向边 ts.p2({c(i,j+1),1},{c(i,j),1});
    }
    ts.p2({c(i,k-1),1},{c(i,k-1),0}); // 不能选 > k
  }
  // 非严格单增
  rep(i,0,n-1){
    rep(j,0,k){
      ts.p2({c(i,j),1},{c(i+1,j),1});
    }
  }

  while(m--){
    int op = read();
    int i = read()-1;
    if(op == 1){
      int x = read()-1;
      if(x){
        ts.p2({c(i,x),0},{c(i,x-1),0});
        // ts.p2({c(i,x-1),1},{c(i,x),1}); // 对称自动
      }else{
        ts.p2({c(i,x),0},{c(i,x),1}); // 输入的原始 x = 1 的时候, 不能选 <= 1
      }
    }else if(op == 2){
      int j = read() - 1;
      int x = read(); // a[i] + a[j] <= x , a[i] > v : a[j] <= x-a[i] < x-v, a[j] < x-v-1
      rep(v,1,k+1){
        int v2 = x - v - 1;
        if(v2 >= 1 && v2 <= k){
          ts.p2({c(i,v-1),1},{c(j,v2-1),0});
          // ts.p2({c(j,v-1),1},{c(i,v2-1),0}); // 对称自动建立
        }else if(v2<1){ // 不可选的v , ( v2 > k 说明一定满足
          ts.p2({c(i,v-1),1},{c(i,v-1),0});
          ts.p2({c(j,v-1),1},{c(j,v-1),0});
        }
      }
    }else if(op == 3){
      int j = read() - 1;
      int x = read(); // a[i] + a[j] >= x, a[i] <= v : a[j] >= x - a[i] >= x - v > x - v - 1
      rep(v,1,k+1){
        int v2 = x - v - 1;
        if(v2 >= 1 && v2 <= k){
          ts.p2({c(i,v-1),0},{c(j,v2-1),1});
          // ts.p2({c(j,v-1),0},{c(i,v2-1),1}); // 对称自动建立
        }else if(v2 > k){ // 不可选的v, (v2 < 1 是一定满足
          ts.p2({c(i,v-1),0},{c(i,v-1),1});
          ts.p2({c(j,v-1),0},{c(j,v-1),1});
        }
      }
    }
  }
  vector<bool> ans;
  vector<int> a(n);
  if(!ts.calc(ans)){
    printf("-1\n");
  }else{
    rep(i,0,n){
      rep(j,0,k){
        if(!ans[i*k+j]){
          a[i] = j+1;
          break;
        }
      }
    }
    rep(i,0,n) printf("%d%c",a[i]," \n"[i==n-1]);
  }
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

总结

这里的问题就是说 选则一个范围的值,怎么变成2-sat需要的 真/假

这里的办法是拆成大于小于

当然从逻辑上 用 $= v$ 和$\ne v$ 也可以, 但是这样的问题是, 在做上面的和的不等式的关系时, 边的量就很大了, 不是k条边了

之前2-sat 还有点问题,缺少了一些反向的连接,和缩点后的反向拓扑序选择

准备准备2sat的板子了

参考

官方

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

G(倍增)

G

题目

https://atcoder.jp/contests/abc254/tasks_print

n个楼, 每个楼高都是1..1e9

有m个电梯, 每个电梯在一个楼里,负责[li,ri] 之间

可以允许这个楼里, [li,ri] 范围中的移动

跨楼同楼层移动代价1

同楼电梯内移动,代价 高度差

q个询问, ai楼bi层 到 ci楼di层最小代价, 或它们不可达

范围

n 2e5

m 2e5

q 2e5

6s

1024mb

题解

我的思路

显然 同楼层答案是1或0

不同楼层,只会单调移动,不会先上再下这种, 答案 = 距离+跨楼数, 需要最小化跨楼数

而每次移动贪心距离, 这样模拟可做, 但是复杂度无法接受

显然同楼的重叠电梯可以合并

官方

显然上下还满足对称性, 那么只考虑从下向上

合并同楼重叠电梯(这样做了以后剩下的线段就不用考虑属于哪个楼了? 因为是一旦重叠肯定不重楼

如果 ai楼内bi移动到最高位置, ci 楼内 di 移动到最低位置, 合法提前输出

dp[i][j] 当前建筑第i层,用j个电梯后最高能到达的楼层

考虑 离散+倍增

代码

我写的按右断点跳右端点的map不知道为什么WA了除了测试点, 调了七八个小时,atcoder还没数据, 放弃了

下面是一个别人的代码,我改了部分格式,靠清理了一些线段,保持左右端点都严格单调递增, 然后用线段跳线段来做的, 我觉得完全一样啊, 吐了, 搞不动了,心态炸了

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;

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

int read(){int r;scanf("%d",&r);return r;} // read

vector<array<int,2> > ilr[200010];
vector<array<int, 2>> segs;
vector<vector<int>> jump;

int N;
int lg = 20;

int n, m, q;

int query(){
  int i0, f0, i1, f1;
  i0 = read() - 1;
  f0 = read();
  i1 = read() - 1;
  f1 = read();

  if(f0 == f1) return i0 != i1;

  if (f0 > f1) {
    swap(i0, i1);
    swap(f0, f1);
  }

  int ans = f1 - f0;
  auto it =
    lower_bound(ilr[i0].begin(), ilr[i0].end(), array<int, 2>{f0 + 1, -1});
  if (it != ilr[i0].begin()) f0 = max(f0,(*--it)[1]);

  it = lower_bound(ilr[i1].begin(), ilr[i1].end(), array<int, 2>{f1 + 1, -1});
  if (it != ilr[i1].begin()) {
    it--;
    if (f1 <= (*it)[1]) {
      f1 = (*it)[0];
    }
  }

  if (f0 >= f1) return ans + (i0 != i1);
  // 跳到一个右端点 保证f0 是右端点
  ans++;
  int idx = lower_bound(segs.begin(), segs.end(), array<int, 2>{f0 + 1, -1}) - segs.begin();
  // 未被覆盖到
  if (!idx) return -1;
  idx--;
  if (f0 > segs[idx][1]) return -1;
  if (segs[idx][1] >= f1) return ans + 1;
  if (segs[jump[idx][lg]][1] < f1) return -1;
  per(k,0,lg+1){
    if (segs[jump[idx][k]][1] >= f1) continue;
    idx = jump[idx][k];
    ans += 1 << k;
  }
  idx = jump[idx][0];
  return ans + 2;
}

int main() {
  n = read();
  m = read();
  q = read();
  rep(i,0,m){
    int a, b, c;
    a = read() - 1;
    b = read();
    c = read();
    ilr[a].push_back({b, c});
  }
  // 每组内部 排序 与 合并
  rep(i,0,n){
    sort(ilr[i].begin(), ilr[i].end());
    vector<array<int, 2>> temp;
    for (auto [l, r] : ilr[i]) {
      if (!temp.empty() && l <= temp.back()[1]) {
        temp.back()[1] = max(temp.back()[1], r);
      } else {
        temp.push_back({l, r});
      }
    }
    ilr[i] = temp;
    for (auto s : temp) segs.push_back(s);
  }

  sort(segs.begin(), segs.end());

  vector<array<int, 2>> temp;
  for (auto [l, r] : segs) {
    if (!temp.empty() && r <= temp.back()[1]) { //
      continue;
    }
    if (!temp.empty() && l == temp.back()[0]) {
      temp.pop_back();
    }
    temp.push_back({l, r});
  }
  segs = temp;

  N = segs.size();
  jump = vector<vector<int>>(N, vector<int>(lg + 1));

  // jump[段id][pwr] = 段id
  for (int i = 0, j = 0; i < N; i++) {
    while (j + 1 < N && segs[j + 1][0] <= segs[i][1]) {
      j++;
    }
    jump[i][0] = j;
  }
  rep(j,0,lg){
    rep(i,0,N){
      jump[i][j + 1] = jump[jump[i][j]][j];
    }
  }


  while(q--) printf("%d\n", query());
  return 0;
}

我的代码 不知道WA在哪里了

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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,m,q;

vector<pair<int,int> > ilr[200010]; // 每个楼

vector<pair<int,int> > segs; // 所有楼
vector<int> maxr = {0}; // 前缀 最大r
map<int,vector<int>> jump = {}; // jump[结束位置][2**i次跳跃] = 最高位置

const int lg = 20;

int query(){
  int i0 = read();
  int f0 = read();
  int i1 = read();
  int f1 = read();
  // 同楼层
  if(f0 == f1) return i0 != i1;

  // 从低到高 f0 < f1
  if(f0 > f1){
    swap(i0,i1);
    swap(f0,f1);
  }
  int ans = f1-f0;

  // 注意不在区间的情况不会跳
  int itr0 = lower_bound(ilr[i0].begin(),ilr[i0].end(),make_pair(f0+1,-1)) - ilr[i0].begin();
  if(itr0 > 0) f0 = max(f0, ilr[i0][itr0-1].second);

  int itr1 = lower_bound(ilr[i1].begin(),ilr[i1].end(),make_pair(f1+1,-1)) - ilr[i1].begin();
  if(itr1 > 0 && ilr[i1][itr1-1].second >= f1) f1 = ilr[i1][itr1-1].first;

  if(f1 <= f0) return ans + (i0 != i1);

  // next0 可能不是某个右端点, 不可能一次跳到, 否则 perv1 <= next0, 所以直接贪心去最大可达右端点
  // 跳一次 保证f0 是右端点
  int idx = lower_bound(segs.begin(),segs.end(),make_pair(f0+1,-1)) - segs.begin();
  if(idx == 0 || maxr[idx] < f0) return -1; // 未被覆盖到
  f0 = maxr[idx]; // 当不可达时可能是比它小的右端点, 但是不影响结果逻辑
  ans ++;
  if(f1 <= f0) return ans + 1;

  // ? 需要吗 TODO
  // if(!h.count(f0)) return -1;

  if(jump[f0][lg] < f1) return -1;

  per(pwr,0,lg+1){
    if(jump[f0][pwr] >= f1) continue;
    f0 = jump[f0][pwr];
    ans += (1<<(pwr));
  }
  assert(f0 < f1 && jump[f0][0] >= f1);
  // printf("%d\n",ans+1 +1); // 分别是跳到比f1 大的和跳到恰好f1
  return ans + 2; // 分别是跳到比f1 大的和跳到恰好f1
}

int main(){
  n = read();
  m = read();
  q = read();
  rep(i,0,m) {
    // 注意g++ 函数处理顺序问题
    // ilr[read()].pb(make_pair(read(),read()));
    int pos = read();
    int l = read();
    int r = read();
    ilr[pos].pb({l,r});
  }
  // 合并同楼 重叠
  rep(i,1,n+1){
    sort(ilr[i].begin(),ilr[i].end());
    vector<pair<int,int> > tmp = {}; // 合并辅助
    for(auto [l,r]: ilr[i]){
      if(tmp.size() == 0 || l > tmp.back().second){ // 不连续 [l0,r0] .. [l1..r1]
        tmp.pb({l,r});
      }else{
        tmp.back().second = r;
      }
    }
    ilr[i] = tmp;
    for(auto o:tmp) segs.pb(o);
  }
  sort(segs.begin(),segs.end()); // 所有楼的
  for(auto item:segs) maxr.pb(max(maxr.back(), item.second));
  // 倍增
  for(auto item:segs){
    auto r = item.second;
    if(jump.count(r)) continue;
    jump[r] = vector<int>(lg+1,r);
    // [...r] [r+1...
    int idx = lower_bound(segs.begin(),segs.end(),make_pair(r+1,-1)) - segs.begin();
    jump[r][0] = maxr[idx]; // 初始化跳2^0 = 1次
  }
  rep(pwr,1,lg+1){
    for(auto item:segs){ // 会重复计算,不影响
      auto r = item.second;
      jump[r][pwr] = jump[jump[r][pwr-1]][pwr-1];
    }
  }

  while(q--) printf("%d\n", query());
  return 0;
}

总结

G

倍增, 编码速度也是问题, 写几个小时还在wa,哎

参考

官方题解 https://atcoder.jp/contests/abc254/editorial

發表於 更新於 分類於 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失败一个重大阻碍

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

参考

官方

0%