A~E 个人题解

A

#include <iostream>
using namespace std;

int main() {
  string s;
  cin>>s;
  cout<<(s[1] == s[2] ? "Yes" : "No")<<'\n';
  
  return 0;
}

B

用pair存直接排序即可

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  pair<pair<int, int>, int> p[3];
  for (int i=0; i<3; i++)
    cin>>p[i].first.first>>p[i].first.second, p[i].second = i;
  sort(p, p+3);
  cout<<p[1].second+1<<'\n';
  
  return 0;
}

C

将1~(n+1)/2调整为((n+1)/2+1)/2

#include <iostream>
using namespace std;

int main() {
  int n,x;
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>x, cout<<(x <= (n+1)/2 ? ((n+1)/2+1)/2 : x)<<' ';
  cout<<'\n';
  
  return 0;
}

D

dfs维护子树大小
注意根节点没有父节点
注意多组数据记得clear

#include <iostream>
#include <vector>
using namespace std;

vector<int> g[200008];
int siz[200008], cnt, n;

void dfs(int u, int f) {
  siz[u] = 1;
  bool flag = true;
  for (auto &v: g[u]) {
    if (v == f)
      continue;
    dfs(v, u);
    siz[u] += siz[v];
    flag &= siz[v]%2;
  }
  cnt += flag && (u == 1 || (n-siz[u])%2);
}

int main() {
  int t;
  cin>>t;
  while (t--) {
    int u,v;
    cin>>n;
    for (int i=1; i<=n; i++)
      g[i].clear();
    cnt = 0;
    for (int i=1; i<=n-1; i++)
      cin>>u>>v, g[u].push_back(v), g[v].push_back(u);
    dfs(1, 0);
    cout<<cnt<<'\n';
  }
  
  return 0;
}

E

删左边的1，把右边的1变为2，一定不会更亏，否则把左边的1变为2字典序要么不变要么变大

• 如果有偶数个1，直接删前一半的1，后一半的1变为2即可
• 如果有奇数个1，需要额外保留一个1。为了让字典序最小，我们在第一次遇到"12"的时候把这个1保留，此时即为最优，否则如果把这个1删除，字典序会更大，因为2的字典序比1大

#include <iostream>
using namespace std;

int main() {
  string s;
  cin>>s;
  int cnt = 0, n = s.size();
  for (auto &ch: s)
    cnt += ch == '1';
  string t;
  bool flag = false;
  int p = 0;
  for (int i=0; i<n; i++) {
    if (s[i] != '1') {
      t += s[i];
    } else {
      if (p >= (cnt+1)/2)
        t += '2';
      else if (cnt%2 && !flag && (i+1 < n && s[i+1] == '2' || p == cnt/2))
        t += '1', flag = true;
      p++;
    }
  }
  cout<<t<<'\n';
  
  return 0;
}