A~F 个人题解

A

#include <iostream>
using namespace std;

int main() {
  int x;
  cin>>x;
  for (int i=0; i<5; i++)
    cout<<x+i<<' ';
  cout<<'\n';
  
  return 0;
}

B

存在前缀关系的话，必须选择长度最小的k个01串，当且仅当从小到大累加各个长度的01串个数刚好等于k时，这个串就是要找的一个串

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

int main() {
  int n,k;
  cin>>n>>k;
  map<string, int> mp;
  string s;
  while (n--)
    cin>>s, mp[s]++;
  int sum = 0;
  for (auto &[t, v]: mp) {
    sum += v;
    if (sum == k) {
      cout<<t<<'\n';
      return 0;
    }
  }
  cout<<-1<<'\n';
  
  return 0;
}

C

构造即可，剩余奇数个时无解

#include <iostream>
using namespace std;

int main() {
  int n,k;
  cin>>n>>k;
  if ((n-k)%2 != 0) {
    cout<<-1<<'\n';
    return 0;
  }
  for (int i=1; i<=k; i++)
    cout<<i<<' ';
  for (int i=k+1; i<=n; i++)
    cout<<k+1<<' ';
  cout<<'\n';
  
  return 0;
}

D

构造即可，插入到任何位置均可，或时无解

#include <iostream>
using namespace std;

int c[200005], d[200005];

int main() {
  int x,y,n;
  cin>>x>>y>>n;
  for (int i=1; i<=x; i++)
    cin>>c[i];
  for (int i=1; i<=y; i++)
    cin>>d[i];
  if (x+y-1 > n || c[x] != d[y]) {
    cout<<-1<<'\n';
    return 0;
  }
  for (int i=1; i<=x; i++)
    cout<<c[i]<<' ';
  for (int i=y-1; i>=2; i--)
    cout<<d[i]<<' ';
  for (int i=1; i<=n-x-y+1; i++)
    cout<<1<<' ';
  cout<<d[1]<<'\n';
  
  return 0;
}

E

从小到大枚举拼接的位数，取大于等于的最小的那个数，即，如果没超过则找到了一个解

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

int main() {
  int t;
  cin>>t;
  while (t--) {
    int n;
    cin>>n;
    for (long long p=10; ; p*=10) {
      long long q = ceill(sqrtl(n*p));
      if (q*q/p == n) {
        cout<<q*q<<'\n';
        break;
      }
    }
  }
  
  return 0;
}

F

基环树是在有n个节点n-1条边的树上加一条边形成的图，即它有n个节点n条边。基环树的特点是有且仅有一个环。

如果是普通树，两种颜色即可染色。

实际上，要对一棵基环树染色，最多只有环上的一个节点需要被染成第三种颜色；而且是当且仅当这个环的大小为奇数时，才需要将环上的任意一个节点染成第三种颜色。

那么可以直接dfs遍历，当且仅当第一次遍历到已经涂色过的节点时，把它的颜色换成第三种颜色即可。

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

int a[200005];
vector<int> g[200005];
bool found;

void dfs(int u, int f, bool color) {
  if (a[u] == 0) {
    a[u] = color+1;
  } else {
    if (!found && a[u] != color+1)
      found = true, a[u] = 3;
    return;
  }
  for (auto &v: g[u]) {
    if (v == f)
      continue;
    dfs(v, u, !color);
  }
}

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