个人题解

A

#include <iostream>
using namespace std;

int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  cout<<((a==1)+(b==2)+(c==3)+(d==4))<<'\n';
  
  return 0;
}

B

前k个直接输出 后n-k个循环左移一个下标

#include <iostream>
using namespace std;

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

C

贪心 每个数字都尝试让它成为不动点 每个数最多有两个不动点

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

int main() {
  int n,x;
  cin>>n;
  unordered_map<int, int> mp;
  for (int i=1; i<=n*2; i++)
    cin>>x, mp[x]++;
  int ans = 0;
  for (auto &[k, v]: mp)
    if (k <= n)
      ans += min(v, 2);
  cout<<ans<<'\n';
  
  return 0;
}

D

先计算不交换时 不动点个数 记为cnt
则答案要么是cnt+2 要么是cnt+1 要么是cnt
当且仅当两个数交换之后 分别成为新的不动点时 答案为cnt+2
当且仅当两个数交换之后 只有一个成为新的不动点时 答案为cnt+1
否则 答案为cnt
用一个map<int, set<int>>维护所有不动点应为key的位置的实际的数的集合

#include <iostream>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int a[505][505];

int main() {
  int n,m,cnt = 0;
  cin>>n>>m;
  unordered_map<int, unordered_set<int>> mp;
  for (int i=1; i<=n; i++)
    for (int j=1; j<=m; j++)
      cin>>a[i][j], cnt += a[i][j] == min(i, j), mp[min(i,j)].insert(a[i][j]);
  for (auto &[k, st]: mp)
    for (auto &x: st)
      if (x != k && mp.find(x) != mp.end() && mp[x].find(k) != mp[x].end()) {
        cout<<cnt+2<<'\n';
        return 0;
      }
  for (auto &[k, st]: mp)
    for (auto &x: st)
      if (x != k && mp.find(x) != mp.end() && (mp[x].size() >= 2 || mp[x].size() == 1 && *mp[x].begin() != x)) {
        cout<<cnt+1<<'\n';
        return 0;
      }
  cout<<cnt<<'\n';
  
  return 0;
}

E

维护1~n的前缀出现的下标的最小值mn和最大值mx
则该前缀对答案的贡献是C(mn, 1) + C(n-mx+1, 1) = mn*(n-mx+1)

#include <iostream>
using namespace std;

int a[300005], p[300005];

int main() {
  int n;
  cin>>n;
  for (int i=1; i<=n; i++)
    cin>>a[i], p[a[i]] = i;
  int mn = 3e5, mx = 0;
  long long ans = 0;
  for (int i=1; i<=n; i++)
    mn = min(mn, p[i]), mx = max(mx, p[i]), ans += (long long)mn*(n-mx+1);
  cout<<ans<<'\n';
  
  return 0;
}

F

lca
原理跟E题差不多
维护1~n前缀的lca 每次加该前缀的lca节点的深度

#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5+5;

vector<int> g[N];
int dep[N], fath[N], siz[N], son[N], top[N];

void dfs1(int u, int f) {
  dep[u] = dep[f]+1; fath[u] = f; siz[u] = 1; son[u] = 0;
  for (auto &v: g[u]) {
    if (v == f)
      continue;
    dfs1(v, u);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]])
      son[u] = v;
  }
}

void dfs2(int u, int t) {
  top[u] = t;
  if (son[u])
    dfs2(son[u], t);
  for (auto &v: g[u]) {
    if (v == fath[u] || v == son[u])
      continue;
    dfs2(v, v);
  }
}

int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] < dep[top[y]])
      swap(x, y);
    x = fath[top[x]];
  }
  return dep[x] < dep[y] ? x : y;
}

int main() {
  int n,u,v;
  cin>>n;
  for (int i=1; i<=n-1; i++)
    cin>>u>>v, g[u].push_back(v), g[v].push_back(u);
  dfs1(n, 0);
  dfs2(n, n);
  int t = 1;
  long long ans = 0;
  for (int i=1; i<=n; i++)
    t = lca(t, i), ans += dep[t];
  cout<<ans<<'\n';
  
  return 0;
}