题目来源：https://qoj.ac/contest/4128

N 题：New CCPC Rules

题目描述

CCPC最近推出了新规则。
根据新规，对一个特定问题，当以下三种情况任意一种出现，该题分数榜单状态“解冻”。
1. 解出题目的队伍数量大于等于50。 2. 解出题目的队伍数量大于等于总参赛人数的20%（并不一定是整数）。 3. 比赛进入了“分数榜冻结”阶段。具体地，其时间以"HH:MM"格式的字符串表示，表示已过比赛时长；冻结阶段开始于第240分钟。

输入格式：

第一行为整数T，表示测试用例的数量。
接下来的T行每一行包含两个整数n，m和一个字符串，表示总队伍数，解出某题的队伍数量和当前事件。

输出格式：

对每一个测试用例，如果到了解冻状况就输出YES，否则输出NO。

算法思路

显然的，只需要判断三种情况然后做或运算即可。
关于时间的比较，容易发现可以将240分钟转化成字符串"04:00"。
直接将输入时间与冻结时间进行字符串比较是可行的。

参考代码（C++）

#include <bits/stdc++.h>
using namespace std;
void solve() {
  int n, m;
  string time;
  cin >> n >> m >> time;
  if (m >= 50 || n <= 5 * m || time >= "04:00") {
    cout << "YES\n";
    return;
  }
  cout << "NO\n";
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

I 题：Integer Triple

题目描述

给定一个整数 $n$，找到三个整数 $a, b, c$ 满足：
- $|a|, |b|, |c| \le 10^{18}$；
- $n = ab(a + b) + bc(b + c) + ac(a + c)$。

输入格式

输入包含一个整数 $n$（$0 \le n \le 10^{18}$）。

输出格式

如果没有解法，输出 -1；否则输出满足要求的 $a, b, c$。
如果有多种可行答案，输出其中一种。

算法思路

暴力搜索显然不可行，我们首先可以注意到对于任意 $x, y$，$xy(x + y)$ 必然是偶数。
进行构造，令 $a = 1, c = -1$，可化简原方程为 $2b = n$。
因此只要先对 $n$ 的奇偶性进行判断，然后按我们的构造输出即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  ll n;
  cin >> n;
  if (n % 2 == 1) 
    cout << "-1\n";
  else {
    cout << 1 << " " << n / 2 << " " << -1 << '\n';
  }
  return 0;
}

EPS.AC

题目描述

EPS.AC 队有三名成员 Colin、Claris 和 Little_Sheep_Yawn，他们各自将 $n$ 道题按从易到难排序（给出三个 $1 \sim n$ 的排列）。现在要将这 $n$ 道题划分成若干个难度层（从易到难排列），每道题恰好属于一层，每层至少一道题。

对于相邻两层之间的分界线，若某成员眼中「左侧所有题」都排在「右侧所有题」之前，则他支持这条分界线。一条分界线合法当且仅当至少有两名成员支持它。求最多能划分出多少层。

算法思路

关键观察：假设在位置 $i$ 处切一刀（前 $i$ 道题属于左侧，后 $n-i$ 道题属于右侧）。对于某个成员，他支持这条分界线，当且仅当他排名前 $i$ 的题目集合恰好等于左侧所有题的集合。

因此，对于每个 $i$，只需判断三个排列各自的前 $i$ 个元素集合中，是否至少有两个相等。若相等，则这条分界线被至少两人支持，合法。

如何快速判断集合相等：对于两个人 $X$ 和 $Y$，记录 $Y$ 中每个数字的位置 posY[值] = 位置。然后遍历 $X$ 的前 $i$ 个元素，维护这些元素在 $Y$ 中的最大位置 max_pos。如果 max_pos == i，说明 $X$ 的前 $i$ 个元素在 $Y$ 中恰好占据了前 $i$ 个位置，即两个集合完全相同。

对三对成员 $(A,B)$、$(A,C)$、$(B,C)$ 都做一遍，用 cnt[i] 累加分界线 $i$ 被多少对成员支持。最后，cnt[i] >= 1 的分界线就是合法的（因为至少有一对，即至少两个人支持）。答案 = 合法分界线个数 + 1。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> A(n), B(n), C(n);
  for (int i = 0; i < n; i++) cin >> A[i];
  for (int i = 0; i < n; i++) cin >> B[i];
  for (int i = 0; i < n; i++) cin >> C[i];

  vector<int> cnt(n + 1, 0);

  auto check = [&](const vector<int>& X, const vector<int>& Y) {
    vector<int> posY(n + 1);
    for (int i = 0; i < n; i++) posY[Y[i]] = i + 1;
    int max_pos = 0;
    for (int i = 1; i <= n; i++) {
      max_pos = max(max_pos, posY[X[i - 1]]);
      if (max_pos == i) {
        cnt[i]++;
      }
    }
  };

  check(A, B);
  check(A, C);
  check(B, C);

  int ans = 1;
  for (int i = 1; i < n; i++) {
    if (cnt[i] >= 1) ans++;
  }
  cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}

Better Dice

题目描述

给定一个公平六面骰子的六个正整数面值 $a_1, a_2, \dots, a_6$，构造另一个公平六面骰子，面值 $b_1, b_2, \dots, b_6$ 均为正整数，总和恰好为 $k$。两个骰子各掷一次，新骰子点数严格大于原骰子则获胜。要求新骰子至少赢下 $36$ 对点数对中的 $19$ 对（即胜率严格大于 $50\%$）。若存在则输出 YES 和一组构造，否则输出 NO。

算法思路

核心观察：新骰子的每个面值 $b$ 能赢过原骰子的面数，只取决于原骰子中有多少个面严格小于 $b$。

如果某个面值 $b$ 不是 1 也不是 原骰子某面 + 1，将它减小到不超过它的最大候选值，胜场数不变，但总和更小。因此最优解一定在至多 $7$ 个候选值中产生：

$$ \text{cand} = \{1\} \cup \{a_i + 1 \mid i = 1, \dots, 6\} $$

枚举 $6$ 个面值的所有候选组合（最多 $7^6 \approx 1.2 \times 10^5$ 种），对每种组合计算胜利对数。若胜利对数 $\ge 19$ 且总和最小，记录该解。

找到最小可行总和 min_sum 后，若 min_sum > k 则无解；否则将多余的总和 $k - \text{min\_sum}$ 全部加到第一个面上（面值增大只会让胜利数不变或增加），输出 YES 和最终构造。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> a(6);
ll k;
vector<ll> cand;
vector<ll> b(6), best;
ll min_sum = LLONG_MAX;

void dfs(int idx, ll sum) {
  if (sum > k) return;
  if (idx == 6) {
    int win = 0;
    for (ll x : b)
      for (ll y : a)
        if (x > y) win++;
    if (win >= 19 && sum < min_sum) {
      min_sum = sum;
      best = b;
    }
    return;
  }
  for (ll v : cand) {
    b[idx] = v;
    dfs(idx + 1, sum + v);
  }
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);

  for (int i = 0; i < 6; i++) cin >> a[i];
  cin >> k;

  sort(a.begin(), a.end());

  cand.push_back(1);
  for (ll x : a) cand.push_back(x + 1);
  sort(cand.begin(), cand.end());
  cand.erase(unique(cand.begin(), cand.end()), cand.end());

  dfs(0, 0);

  if (best.empty()) {
    cout << "NO\n";
  } else {
    cout << "YES\n";
    best[0] += k - min_sum;
    for (int i = 0; i < 6; i++) {
      cout << best[i] << " \n"[i == 5];
    }
  }
  return 0;
}