[CF1023] Codeforces Round #504(Div.1+Div.2)

发表于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1023

我，七夕，掉分

A：两个字符串，其中一个字符串里至多有个“*”表示任何字符都能匹配。问这两个字符串能不能匹配。

从左到右扫两个字符串的相同前缀和后缀，然后看看是不是存在“*”以及两头不相接。据说这题被cha得很厉害啊？

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 300100;
int n, m;
char s[maxn], t[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&m)) {
    scanf("%s%s",s,t);
    if(strcmp(s, t) == 0) {
      printf("YES\n");
      continue;
    }
    int i = 0, j = 0;
    int tot = 0;
    while(s[i] == t[j]) {
      i++,j++;tot++;
    }
    int p = n - 1, q = m - 1;
    while(s[p] == t[q]) {
      p--,q--;tot++;
    }
    if(i == p) {
      if(s[i] == '*' && tot <= m) {
        printf("YES\n");
      }
      else printf("NO\n");
    }
    else {
      printf("NO\n");
    }
  }
  return 0;
}

B：给你两个数$n$和$k$，问你$k$有多少能用不超过$n$的两个不同的数的和来表示，忽略顺序。

设$k=x+y$，要满足$x≤n$、$y≤n$和$x≠y$。我们会发现，需要讨论$k≥2n$、$k≤n$和$n＜k＜2n$三个情况。前两个不必多说，第三个我们也是只需要统计从$\frac{k}{2}$数到$n$有多少个整数就行，因为总有$x＜\frac{k}{2}$和它对应。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
LL n, k;

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%lld%lld",&n,&k)) {
    if(k / 2 >= n) {
      printf("0\n");
      continue;
    }
    if(k <= n) {
      printf("%lld\n", k % 2 == 0 ? k / 2 - 1 : k / 2);
    }
    else {
      printf("%lld\n", n-k/2);
    }
  }
  return 0;
}

C：给定长为$n$的合法括号序列，让你求一个长为$k$的合法括号子序列。

维护每一个下标为$i$的左括号对应的右括号下标$to[i]=j$，然后贪心地从左到右扫符合当前长度条件$k≥to[i]-i+1$的括号序列，每找到一堆符合条件的括号序列要更新$k$和$i$。

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
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
const int maxn = 200200;
int n, k;
int to[maxn];
stack<int> st;
char s[maxn];

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&k)) {
    scanf("%s", s);
    if(n == k) {
      printf("%s\n", s);
      continue;
    }
    while(!st.empty()) st.pop();
    memset(to, 0, sizeof(to));
    for(int i = 0; i < n; i++) {
      if(s[i] == '(') {
        st.push(i);
      }
      else {
        int id = st.top(); st.pop();
        to[i] = id; to[id] = i;
      }
    }
    int tot = k, i = 0;
    vector<pii> pos;
    while(tot) {
      if(to[i] - i + 1 <= tot  && to[i] - i + 1 > 0) {
        tot -= (to[i] - i + 1);
        pos.emplace_back(i, to[i]);
        i = to[i] + 1;
      }
      else i++;
    }
    for(int i = 0; i < pos.size(); i++) {
      for(int j = pos[i].first; j <= pos[i].second; j++) {
        printf("%c", s[j]);
      }
    }
    printf("\n");
  }
  return 0;
}

D：原本有$n$个范围在$[1,q]$的数，定义染色操作$[l_i,r_i]$表示将$[l_i,r_i]$区间内的数字变为$i$，现在给你$n$个染色后的数字作为结果，其中含有数字$0$表示这里可以是任意数字，问你$q$次操作能不能把原本的序列变成这个序列。

考虑到每次染色为一个区间，每个数字$i$仅能染色一次。那么在进行过一次染色操作后，这个区间内的数字必然不能比$i$小。

问题在于如何处理$0$，我们考虑有一个$0$在某个区间$[L,R]$内，且$a_L$与$a_R$相同，$[L,R]$中不存在除了$0$以外小于$a_L$的数字。那么我们可以将这个0置为相邻两侧数字中的任意一个，作为扩展那个数字的区间长度。

因此我们构造时只需要维护每一个数字的最右侧相同的那个数字，整个区间必然会被覆盖一次。然后用线段树维护区间最小值，存在有小于区间端点的数字时必然无法构造。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200200;
int n, q;
int r[maxn];
int a[maxn];

#define lrt rt << 1
#define rrt rt << 1 | 1
int seg[maxn<<2];
void pushup(int rt) {
  seg[rt] = min(seg[lrt], seg[rrt]);
}
void build(int l, int r, int rt) {
  if(l == r) {
    seg[rt] = a[l];
    return;
  }
  int m = (l + r) >> 1;
  build(l,m,lrt);
  build(m+1,r,rrt);
  pushup(rt);
}
int query(int L, int R, int l, int r, int rt) {
  if(L <= l && r <= R) {
    return seg[rt];
  }
  int m = (l + r) >> 1;
  int ret = 0x7f7f7f7f;
  if(m >= L) ret = min(ret, query(L, R, l, m, lrt));
  if(m < R) ret = min(ret, query(L, R, m+1, r, rrt));
  return ret;
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&q)) {
    memset(r, 0, sizeof(r));
    for(int i = 1; i <= n; i++) {
      scanf("%d",&a[i]);
      r[a[i]] = i;
    }
    if(!r[q]) {
      if(!r[0]) {
        printf("NO\n");
        continue;
      }
      else a[r[0]] = q;
    }
    for(int i = 1; i <= n; i++) {
      if(a[i] == 0) a[i] = a[i-1];
    }
    for(int i = n; i >= 1; i--) {
      if(a[i] == 0) a[i] = a[i+1];
    }
    bool ok = 1;
    build(1, n, 1);
    for(int i = 1; i <= n; i++) {
      int tmp;
      if(!r[a[i]]) continue;
      tmp = query(i, r[a[i]], 1, n, 1);
      if(tmp < a[i]) {
        ok = 0;
        break;
      }
    }
    if(ok) {
      printf("YES\n");
      for(int i = 1; i <= n; i++) {
        printf("%d%c", a[i], " \n"[i==n]);
      }
    }
    else printf("NO\n");
  }
  return 0;
}