\(\texttt{E F}\) 忘（不）记（会）写了。

A Yet Another Dividing into Teams 题解

题目大意

有一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)，将他们分为若干组，使得每一组没有两个数的差为 \(1\)，使分的组数尽可能少。

解题思路

排完序后对于任意 \(1\le i< n\) 均有 \(a_i\) 与 \(a_{i+1}\) 最接近，所以若存在 \(a_{i+1}-a_i=1\) 则必定要分成两组，否则一组。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while(t--) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    int ans = 1;
    sort(a + 1, a + n + 1);
    for(int i = 2; i <= n; i++) {
      if(a[i - 1] + 1 == a[i]) {
        ans = 2;
        break;
      }
    }
    cout << ans << "\n";
  }
  return 0;
}

B1 & B2 Books Exchange 题解

题目大意

有 \(n\) 个小朋友每人手里有一本书，给定一个排列 \(a\)，表示每一轮第 \(i\) 个小朋友会把书给 \(a_i\)。求每个小朋友的书会在几轮后回到自己手里。

解题思路

暴搜寻找即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 205;
int t, n, a[N];
inline int dfs(int cur, int x, int y) {
  if(y == x && cur != 0) {
    return cur;
  }
  return dfs(cur + 1, a[x], y);
}
int main() {
  ios::sync_woth_stdio(0);
  cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while(t--) {
    cin >> n;
    for(int i = 1; i <= n; i++) {
      cin >> a[i];
    }
    for(int i = 1; i <= n; i++) {
      cout << dfs(0, i, i) << " ";
    }
    cout << "\n";
  }
  return 0;
}

C1 & C2 Good Numbers 题解

题目大意

给定 \(n\)，求不小于 \(n\) 的最小数 \(x\)，使得 \(x\) 可以分解成不同的 \(3\) 的幂之和。其中 \(C2\) 的数据规模更大。

解题思路

我们只需要算出 \(3^i\) 的前缀和 \(s_i\)，然后从大到小判断是否要选 \(3^i\) 作为 \(x\) 的一部分，如果 已选数字之和加上 \(s_{i-1}\le x\) 那么说明当前 \(3^i\) 不用选。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
int n, ans, sum[105], a[105];
inline int solve(long long x) {
  int ans = 0;
  for(int i = 38; i >= 1; i--) {
    if(ans + sum[i - 1] >= x) {
      continue;
    } else {
      ans += a[i];
    }
  }
  if(ans < x) {
    ans += 1;
  }
  return ans;
}
signed main() {
  sum[0] = 1;
  a[0] = 1;
  long long cnt = 3;
  for(int i = 1; i <= 100 && sum[i - 1] <= INF; i++) {
    sum[i] = sum[i - 1] + cnt;
    a[i] = cnt;
    cnt *= 3;
  }
  int t;
  cin >> t;
  while(t--) {
    cin >> n;
    cout << solve(n) << "\n";
  }
  return 0;
}

D1 & D2 Too Many Segments 题解

题目大意

给定 \(n\) 个区间，要求删除最少数量的区间，使得每个点被覆盖的次数不超过 \(k\)，求方案。

解题思路

我们首先要做的事情就是能够计算出当前点 \(x\) 处被几条线段覆盖的问题。我们需要先将所有线段按左端点排序，用差分维护线段结束，然后枚举每条线段，每枚举一个线段我们就让 \(cnt+1\)， 表示当前点 a[i].l 有 \(cnt\) 个线段覆盖，同时 sum[a[i].r]--，表示线段在 a[i].r 在这里结束。当我们在判断当前点 a[i].l 被几条线段覆盖时，还需要去掉右端点已经小于 a[i].l 的线段，这样就得到了当前点 a[i].l 有 \(cnt\) 个线段覆盖。然后判断 \(cnt>k\)，如果 \(cnt>k\) 说明需要去掉线段，我们优先去掉右端点最大的线段。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k;
int sum[N], cnt, pos;
vector<int> ans;
priority_queue<pair<int, int> > p;
struct node {
  int l, r, id;
} a[N];
inline bool cmp(node x, node y) {
  if(x.l == y.l) {
    return x.r > y.r;
  }
  return x.l < y.l;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++) {
    cin >> a[i].l >> a[i].r;
    a[i].id = i;
  }
  sort(a + 1, a + 1 + n, cmp);
  for(int i = 1; i <= n; i++) {
    p.push(make_pair(a[i].r, a[i].id));
    cnt++;
    sum[a[i].r]--;
    while(pos < a[i].l) {
      cnt = cnt + sum[pos];
      pos++;
    }
    if(a[i].l != a[i + 1].l) {
      while(cnt > k) {
        while(!p.empty() && p.top().first < a[i].l) {
          p.pop();
        }
        ans.push_back(p.top().second);
        sum[p.top().first]++;
        p.pop();
        cnt--;
      }
    }
  }
  cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
  return 0;
}