ABC-283解题报告

发表于 更新于 分类于

比赛传送门

C. Cash Register

题意：给你一个数字串（没有前导零），每次可以敲一个 0∼90\sim 9 的数字以输入，或敲一次 00 键以输入两个 00。问输入这个数字串的最少步骤。

显然遇到两个 00 合并即可。

By SSRS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int N = S.size();
  int ans = N;
  for (int i = 0; i < N - 1; i++){
    if (S[i] == '0' && S[i + 1] == '0'){
      ans--;
      i++;
    }
  }
  cout << ans << endl;
}

D. Scope

题意：有一个合法的括号-小写字母字符串，你需要维护一个集合，任意时刻出现相同元素则不合法。维护过程为：依此扫过每个字符，如果为左括号则不管；为字母则加入集合；为右括号则将它到匹配的左括号之间的字母从集合中删除。

按照题意用栈模拟即可。栈中每个元素代表一层的字母集合，加入左括号则入栈一个空集，加入字母则在栈顶集合插入并检查，加入右括号删除标记并弹栈。

By SSRS

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
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin >> S;
  int N = S.size();
  bool ok = true;
  stack<int> st;
  st.push(-1);
  int A = 0;
  for (int i = 0; i < N; i++){
    if (S[i] == '('){
      st.push(-1);
    } else if (S[i] == ')'){
      while (st.top() != -1){
        A ^= 1 << st.top();
        st.pop();
      }
      st.pop();
    } else {
      int p = S[i] - 'a';
      if ((A >> p & 1) == 1){
        ok = false;
        break;
      }
      A |= 1 << p;
      st.push(p);
    }
  }
  if (ok){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

E. Don’t Isolate Elements

题意：有一个 01 矩阵，每次可以取反一行，问最少多少次操作能使该矩阵没有孤点，或判断无解。

显然可以 DP：f[i][j∈{0,1}][k∈{0,1}]f[i][j\in\{0,1\}][k\in\{0,1\}] 表示当前考虑了前 ii 行，第 i−1i-1 行取反状态为 jj，第 ii 行状态为 kk，且前 i−1i-1 行已经合法（因为后面行无法影响前 i−1i-1 行）的最小操作次数。转移考虑下一行是否能取反即可。

By SSRS

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
#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<int>> A(H, vector<int>(W));
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> A[i][j];
    }
  }
  vector<vector<vector<int>>> dp(H + 1, vector<vector<int>>(2, vector<int>(2, INF)));
  dp[0][0][0] = 0;
  dp[0][0][1] = 1;
  for (int i = 0; i < H; i++){
    for (int j = 0; j < 2; j++){
      for (int k = 0; k < 2; k++){
        for (int l = 0; l < 2; l++){
          bool ok = true;
          for (int y = 0; y < W; y++){
            bool ok2 = false;
            if (i > 0){
              if ((A[i][y] ^ k) == (A[i - 1][y] ^ j)){
                ok2 = true;
              }
            }
            if (i < H - 1){
              if ((A[i][y] ^ k) == (A[i + 1][y] ^ l)){
                ok2 = true;
              }
            }
            if (y > 0){
              if ((A[i][y] ^ k) == (A[i][y - 1] ^ k)){
                ok2 = true;
              }
            }
            if (y < W - 1){
              if ((A[i][y] ^ k) == (A[i][y + 1] ^ k)){
                ok2 = true;
              }
            }
            if (!ok2){
              ok = false;
            }
          }
          if (ok){
            dp[i + 1][k][l] = min(dp[i + 1][k][l], dp[i][j][k] + l);
          }
        }
      }
    }
  }
  int ans = INF;
  for (int i = 0; i < 2; i++){
    for (int j = 0; j < 2; j++){
      ans = min(ans, dp[H][i][j]);
    }
  }
  if (ans == INF){
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
}

还可以预处理行之间的转移情况，优化成 O(1)O(1) 转移，但是预处理为 O(nm)O(nm)，时间复杂度不变。

By CQ0x3F

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
const int _ = 1e3 + 10;
bool a[_][_], b[_][2][2], l[2], r[2], tmp;
int n, m, k, f[_][2][2], ans;
inline void cmin(int& a, int b) {
    if (a > b) a = b;
}
int main() {
    read(n);
    read(m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            read(k);
            a[i][j] = k;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (((j == 1 || a[i][j] != a[i][j-1])) && ((j == m || a[i][j] != a[i][j+1]))) {
                if (i == 1) {
                    l[a[i][j] ^ a[i+1][j]] = true;
                } else if (i == n) {
                    r[a[i][j] ^ a[i-1][j]] = true;
                } else {
                    b[i][a[i][j] ^ a[i-1][j]][a[i][j] ^ a[i+1][j]] = true;
                }
            }
        }
    }
    memset(f, 0x3F, sizeof(f));
    for (int x = 0; x <= 1; x++) {
        for (int y = 0; y <= 1; y++) {
            tmp = true;
            for (int p = 0; p <= 1; p++) {
                if (l[p] && (!((x ^ y) == p))) tmp = false;
            }
            if (tmp) f[2][x][y] = (x + y);
        }
    }
    for (int i = 2; i < n; i++) {
        for (int x = 0; x <= 1; x++) {
            for (int y = 0; y <= 1; y++) {
                for (int z = 0; z <= 1; z++) {
                    if (f[i][x][y] != 0x3F3F3F3F) {
                        tmp = true;
                        for (int p = 0; p <= 1; p++) {
                            for (int q = 0; q <= 1; q++) {
                                if (b[i][p][q] && (!(((x ^ y) == p) || ((y ^ z) == q)))) tmp = false;
                            }
                        }
                        if (tmp) cmin(f[i+1][y][z], f[i][x][y] + z);
                    }
                }
            }
        }
    }
    ans = 0x3F3F3F3F;
    for (int x = 0; x <= 1; x++) {
        for (int y = 0; y <= 1; y++) {
            tmp = true;
            for (int p = 0; p <= 1; p++) {
                if (r[p] && (!((x ^ y) == p))) tmp = false;
            }
            if (tmp) cmin(ans, f[n][x][y]);
        }
    }
    if (ans == 0x3F3F3F3F) ans = -1;
    write(ans);
    return 0;
}

F. Permutation Distance

题意：给你一个排列 pp，对每个位置 ii 求 min⁡j≠i(∣pi−pj∣+∣i−j∣)。\min\limits_{j\ne i}(|p_i-p_j|+|i-j|)。

显然可以正反扫两遍（或直接反转数组）分别处理 j<ij<i 和 j>ij>i 的情况。这里只考虑 j<ij<i。

在 j<ij<i 时，有 pj<pip_j<p_i 和 pj>pip_j>p_i 两种情况，对于前者，贡献为 (pi+i)−(pj+j)(p_i+i)-(p_j+j)，显然要让 pj+jp_j+j 尽可能大；对于后者，贡献为 (pj−j)−(pi−i)(p_j-j)-(p_i-i)，显然要让 pj−jp_j-j 尽可能小。于是，维护两个线段树/树状数组，区间下标为 pip_i，值分别为 pj+jp_j+j 和 pj−jp_j-j，分别维护区间最大值和区间最小值即可。

By SSRS

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
#include <bits/stdc++.h>
using namespace std;
const int INF = 10000000;
template <typename T>
struct segment_tree{
  int N;
  vector<T> ST;
  function<T(T, T)> f;
  T E;
  segment_tree(int n, function<T(T, T)> f, T E): f(f), E(E){
    N = 1;
    while (N < n){
      N *= 2;
    }
    ST = vector<T>(N * 2 - 1, E);
  }
  T operator [](int k){
    return ST[N - 1 + k];
  }
  void update(int k, T x){
    k += N - 1;
    ST[k] = x;
    while (k > 0){
      k = (k - 1) / 2;
      ST[k] = f(ST[k * 2 + 1], ST[k * 2 + 2]);
    }
  }
  T query(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return E;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return f(query(L, R, i * 2 + 1, l, m), query(L, R, i * 2 + 2, m, r));
    }
  }
  T query(int L, int R){
    return query(L, R, 0, 0, N);
  }
};
int main(){
  int N;
  cin >> N;
  vector<int> P(N);
  for (int i = 0; i < N; i++){
    cin >> P[i];
    P[i]--;
  }
  function<int(int, int)> mn = [](int a, int b){
    return min(a, b);
  };
  vector<int> ans(N, INF);
  segment_tree<int> ST1(N, mn, INF), ST2(N, mn, INF);
  for (int i = 0; i < N; i++){
    ans[i] = min(ans[i], (i + P[i]) + ST1.query(0, P[i]));
    ans[i] = min(ans[i], (i - P[i]) + ST2.query(P[i] + 1, N));
    ST1.update(P[i], -i - P[i]);
    ST2.update(P[i], -i + P[i]);
  }
  segment_tree<int> ST3(N, mn, INF), ST4(N, mn, INF);
  for (int i = N - 1; i >= 0; i--){
    ans[i] = min(ans[i], (-i + P[i]) + ST3.query(0, P[i]));
    ans[i] = min(ans[i], (-i - P[i]) + ST4.query(P[i] + 1, N));
    ST3.update(P[i], i - P[i]);
    ST4.update(P[i], i + P[i]);
  }
  for (int i = 0; i < N; i++){
    cout << ans[i];
    if (i < N - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

除了可以分别处理这些情况外，还可以在一个线段树内维护着四个信息，简化代码。

By kotatsugame

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
#include<iostream>
#include<atcoder/segtree>
using namespace std;
struct dat{
    int pmx,pmn,mmx,mmn;
};
dat op(dat l,dat r)
{
    l.pmx=max(l.pmx,r.pmx);
    l.pmn=min(l.pmn,r.pmn);
    l.mmx=max(l.mmx,r.mmx);
    l.mmn=min(l.mmn,r.mmn);
    return l;
}
dat e(){return dat{-(int)1e9,(int)1e9,-(int)1e9,(int)1e9};}
int N,P[2<<17];
int main()
{
    cin>>N;
    for(int i=0;i<N;i++)cin>>P[i],P[i]--;
    atcoder::segtree<dat,op,e>L(N),R(N);
    for(int i=0;i<N;i++)R.set(P[i],dat{i+P[i],i+P[i],i-P[i],i-P[i]});
    for(int i=0;i<N;i++)
    {
        R.set(P[i],e());
        int ans=1e9;
        ans=min(ans,i+P[i]-L.prod(0,P[i]).pmx);
        ans=min(ans,R.prod(P[i]+1,N).pmn-(i+P[i]));
        ans=min(ans,i-P[i]-L.prod(P[i]+1,N).mmx);
        ans=min(ans,R.prod(0,P[i]).mmn-(i-P[i]));
        cout<<ans<<(i+1==N?"\n":" ");
        L.set(P[i],dat{i+P[i],i+P[i],i-P[i],i-P[i]});
    }
}

如果是分类讨论处理，还可以用 for 循环两次，在循环的开头/结尾处反转信息。

By IH19980412

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
void solve(){
    int n;cin>>n;
    vc<int>ans(n+1, 1e18);
    vc<int>p(n+1);
    repn(i,n)cin>>p[i];
    rep(_, 2){
        segtree<decltype(f), decltype(e)>sm((1<<18), f, e);
        segtree<decltype(f), decltype(e)>bg((1<<18), f, e);
        repn(i,n){
            int d = sm.query(1, p[i]);
            d = p[i]+i-d;

            int e = bg.query(p[i], n);
            e = -p[i]+i-e;

            chmin(d, e);
            if(!_) chmin(ans[i], d);
            else chmin(ans[n+1-i], d);

            sm.update(p[i], p[i]+i, true);
            bg.update(p[i], -p[i]+i, true);
        }
        repn(i,n){
            if(i >= n+1-i) break;
            swap(p[i], p[n+1-i]);
        }
    }
    repn(i,n) o(ans[i]);
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);
    int t; t = 1; //cin >> t;
    while(t--) solve();
}

这道题还有一个非常“暴力”的做法，即对于每个位置，从近到远枚举选的元素，如果当前下标的差已经超过了当前的最优解则 break 掉（最优性剪枝）。不是很会证复杂度，可以手玩几组数据感性理解。

By lvkaiyi0811

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define _ 200005
ll n,s,a[_],i,j;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++){
        for(s=n,j=1;j<s;j++){
            if(i+j<=n)s=min(s,j+abs(a[i]-a[i+j]));
            if(i-j>=1)s=min(s,j+abs(a[i]-a[i-j]));
        }
        cout<<s<<' ';
    }
}