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

我，七夕，掉分

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

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

#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}$ 和它对应。

#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$ 。

#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置为相邻两侧数字中的任意一个，作为扩展那个数字的区间长度。

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

#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;
}