比赛链接

A - Garland

大意：给你一个可能没补完的排列，让你把剩下的数填上，使得奇偶不同的相邻数目最少。
思路：直接上 d p dp dp,表示第 i i i个，有 j j j个 1 1 1， k k k个 0 0 0，第 i i i个是 0 / 1 0/1 0/1的最小答案。
枚举 1 − n 1-n 1−n分情况转移即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int f[111][111][111][2];
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> v(n + 1), b(2, 0), len(2, 0);
  int l = n / 2;
  int r = n / 2;
  if (n & 1)
    l++;
  b[0] = r;
  b[1] = l;
  for (int i = 1; i <= n; i++) {
    cin >> v[i];
  }
  memset(f, 0x3f3f3f, sizeof f);
  f[0][0][0][1] = f[0][0][0][0] = 0;
  for (int i = 1; i <= n; i++) {
    if (v[i]) {
      for (int j = len[0]; j <= b[0]; j++) {
        if (i - 1 - j < len[1])
          break;
        if (i - 1 - j > b[1])
          continue;
        if (v[i] % 2 == 0) {
          if (j + 1 > b[0])
            continue;
          f[i][j + 1][i - j - 1][0] =
              min(f[i][j + 1][i - j - 1][0], f[i - 1][j][i - j - 1][0]);
          f[i][j + 1][i - j - 1][0] =
              min(f[i][j + 1][i - j - 1][0], f[i - 1][j][i - j - 1][1] + 1);
        } else {
          if (i - j > b[1])
            continue;
          f[i][j][i - j][1] = min(f[i][j][i - j][1], f[i - 1][j][i - j - 1][1]);
          f[i][j][i - j][1] =
              min(f[i][j][i - j][1], f[i - 1][j][i - j - 1][0] + 1);
        }
      }
      len[v[i] % 2]++;
    } else {
      for (int j = len[0]; j <= b[0]; j++) {
        if (i - 1 - j < len[1])
          break;
        if (i - 1 - j > b[1])
          continue;
 
        if (j + 1 <= b[0]) {
          f[i][j + 1][i - j - 1][0] =
              min(f[i][j + 1][i - j - 1][0], f[i - 1][j][i - j - 1][0]);
          f[i][j + 1][i - j - 1][0] =
              min(f[i][j + 1][i - j - 1][0], f[i - 1][j][i - j - 1][1] + 1);
        }
        if (i - j <= b[1]) {
 
          f[i][j][i - j][1] = min(f[i][j][i - j][1], f[i - 1][j][i - j - 1][1]);
          f[i][j][i - j][1] =
              min(f[i][j][i - j][1], f[i - 1][j][i - j - 1][0] + 1);
        }
      }
    }
  }
  cout << min(f[n][b[0]][b[1]][1], f[n][b[0]][b[1]][0]) << endl;
  return 0;
}

B - Numbers on Tree

大意：给你一颗有根树，和儿子节点的 c s o n c_{son} cson​严格小于当前节点的 c f a c_{fa} cfa​的节点个数
让你构造一组合法的 c c c数组，或者不存在合法的情况输出 N O NO NO。
思路：不合法的情况显然是 c i ≤ s z i c_i \leq sz_i ci​≤szi​。
从根开始dfs处理每个节点，构造 c i = m i n ( k t h ) , （ 1 − n 没 用 过 的 第 k 小 元 素 ) c_i=min(k_{th}),（1-n没用过的第k小元素) ci​=min(kth​),（1−n没用过的第k小元素),即可。由于 n n n不大，直接暴力即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n, r, c[N], sz[N];
vector<int> v[N];
int vis[N], ans[N];
void dfs(int now) {
  sz[now] = 1;
  int y = 0, res = 0;
  while (1) {
    if (!vis[y + 1]) {
      y++;
      if (res == c[now]) {
        ans[now] = y;
        vis[y] = 1;
        break;
      }
      res++;
    } else
      y++;
  }
  for (auto k : v[now]) {
    dfs(k);
    sz[now] += sz[k];
  }
  if (sz[now] <= c[now]) {
    cout << "NO\n";
    exit(0);
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    int x;
    cin >> x >> c[i];
    if (!x)
      r = i;
    v[x].pb(i);
  }
  dfs(r);
  cout << "YES\n";
  for (int i = 1; i <= n; i++)
    cout << ans[i] << ' ';
  return 0;
}

C - Madhouse (Hard version)

简单版本直接查询 [ 1 , n ] , [ 2 , n ] [1,n],[2,n] [1,n],[2,n]通过两个回答的差别直接求出n个前缀即可。
困难版本需要查询三次 [ 1 , n / 2 ] , [ 2 , n / 2 ] , [ 1 , n ] [1,n/2],[2,n/2],[1,n] [1,n/2],[2,n/2],[1,n]，前两次求出前一半的答案。
有一个小 t r i c k trick trick，设 c n t i , x cnt_{i,x} cnti,x​为最后一次询问的回答中，长度为i的所有串中x字符出现的个数，
那么 c n t i + 1 , x − c n t i , x cnt_{i+1,x}-cnt_{i,x} cnti+1,x​−cnti,x​就应该等于 i + 1 i+1 i+1到 n − i n-i n−i中字符 x x x出现的个数（需满足 i + 1 ≤ n − i i+1\leq n-i i+1≤n−i）
然后你就可以通过这个条件来确定后一半字符串的所有前缀了，就是胡乱模拟即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int cnt[26], sum[26][111];
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  if (n <= 3) {
    string ans = "";
    for (int i = 1; i <= n; i++) {
      cout << "? " << i << ' ' << i << endl;
      string x;
      cin >> x;
      ans += x;
    }
    return cout << "! " << ans << endl, 0;
  }
  multiset<string> v[101], q[101];
  int f = n;
  n /= 2;
  cout << "? " << 1 << ' ' << n << endl;
  for (int i = 1; i <= (1 + n) * n / 2; i++) {
    string x;
    cin >> x;
    sort(x.begin(), x.end());
    if (n == 1)
      return cout << "! " << x << endl, 0;
    v[x.size()].insert(x);
  }
  cout << "? " << 2 << ' ' << n << endl;
  for (int i = 1; i <= (n - 1) * n / 2; i++) {
    string x;
    cin >> x;
    sort(x.begin(), x.end());
    auto f = v[x.size()].find(x);
    v[x.size()].erase(f);
  }
  string ans = "";
  for (int i = 1; i <= n; i++) {
    string f = *v[i].begin();
    for (auto k : f)
      cnt[k - 'a']++;
    for (auto k : ans)
      cnt[k - 'a']--;
    for (int j = 0; j < 26; j++) {
      if (cnt[j]) {
        ans += j + 'a';
        cnt[j] = 0;
      }
    }
  }
  string half = ans; //前一半
  cout << "? " << 1 << ' ' << f << endl;
  for (int i = 1; i <= f * (f + 1) / 2; i++) {
    string x;
    cin >> x;
    for (auto k : x) {
      sum[k - 'a'][x.size()]++;
    }
  }
  vector<int> tmp(26, 0);
  for (int j = 0; j < n; j++) {
    tmp[ans[j] - 'a']++;
  }
  for (int i = n; i >= 1; i--) {
    if (f - i < i + 1)
      continue;
    for (int j = 0; j < 26; j++) {
      int l = 0;
      for (int k = i + 1; k < f - i; k++) {
        l += (ans[k - 1] - 'a' == j);
      }
      if (sum[j][i + 1] - sum[j][i] > l) {
        ans += j + 'a';
        break;
      }
    }
  }
  vector<int> last(26, 0);
  for (int i = 0; i < ans.size(); i++)
    last[ans[i] - 'a']++;
  for (int i = 0; i < 26; i++) {
    if (sum[i][f] != last[i]) {
      ans += i + 'a';
      break;
    }
  }
  cout << "! " << ans << endl;
  return 0;
}