链接：https://ac.nowcoder.com/acm/contest/120563
题目按照通过人数降序排序。
A – 宙天
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
ll x;
cin >> x;
for (int i = 1; i <= x; ++i)
{
if (x == i * (i + 1))
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}G – スピカの天秤
算法：
贪心，排序。
思路：
令 \(sum1\) 表示数组 \(a\) 的和，\(sum2\) 表示数组 \(b\) 的和。
当 \( sum1 = sum2 \) 时，随机在 \( a \) 或 \( b \) 里面拿走任意一个都可以改变状态，因此答案为 \( 1 \)；
当 \( sum1 > sum2 \) 时，需要将状态改变至 \( sum1 = sum2 \) 或者 \( sum1 < sum2 \)，所有需要移除 \( a \) 数组中的一些砝码，贪心的从最大的开始移除即可，直至状态改变。
\( sum1 < sum2 \) 时，同理。
关键代码：
void miyan()
{
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto &x : a)
cin >> x;
for (auto &x : b)
cin >> x;
ranges::sort(a);
ranges::sort(b);
ll sum1 = accumulate(all(a), 0ll);
ll sum2 = accumulate(all(b), 0ll);
if (sum1 == sum2)
{
cout << 1 << endl;
}
else if (sum1 > sum2)
{
ll ans = 0;
for (int i = n - 1; i >= 0; --i)
{
++ans;
sum1 -= a[i];
if (sum1 <= sum2)
{
cout << ans << endl;
break;
}
}
}
else
{
ll ans = 0;
for (int i = m - 1; i >= 0; --i)
{
++ans;
sum2 -= b[i];
if (sum2 <= sum1)
{
cout << ans << endl;
break;
}
}
}
}B – Random
算法：
\(gcd\)，随机数据。
思路：
由于数据是随机生成，在 \(n\) 较大时全是奇数的概率非常低（证明略），可得任意取一些数字与剩余的全部数字全互质的概率非常非常低。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
for (int i = 0; i < min(n, 201); ++i)
{
for (int j = 0; j < n; ++j)
{
if (i == j)
continue;
if (gcd(a[i], a[j]) != 1)
{
cout << a[i] << ' ' << a[j] << endl;
return;
}
}
}
cout << -1 << endl;
}J – Branch of Faith
算法：
完全二叉树的性质。
思路：
在完全二叉树中深度为 \(d\) 的节点编号范围为 \([2^d, 2^{d + 1} – 1]\)。
注意：\(log2()\) 函数返回的是浮点数，可能会存在精度问题，可以使用 \(\text{__lg()}\) 函数（其返回整数）替代。
关键代码：
void miyan()
{
ll n, q;
cin >> n >> q;
ll lgn = __lg(n);
while (q--)
{
ll x;
cin >> x;
ll dep = __lg(x);
ll L = 1ll << dep;
ll R = 0;
if (dep == lgn)
R = n;
else
R = (1ll << (dep + 1)) - 1;
cout << R - L + 1 << endl;
}
}H – Tic Tac DREAMIN’
算法：
计算几何。
思路：
卡精度，太恶心了。
已知三角形三个顶点坐标 \((x1, y1), (x2, y2), (x3, y3)\)，可得面积公式：
\(S=\frac{1}{2}|x1(y2−y3)+x2(y3−y1)+x3(y1−y2)|\)
已知 \(y3 = 0\)，那么公式可化简为：
\(S=\frac{1}{2}|x1y2-x2y1+x3(y1−y2)|\)
继续简化（题目要求输出任意一个，那么直接将绝对值化简，取正）：
\(x3 = \frac{2S – x_1y_2 + x_2y_1}{y_1 – y_2}\)
题目给定 \((x1, y1), (x2, y2), S = 2\)：
- 当 \(y1 = y2\) 时，\(x3\) 只与 \((x1, y1), (x2, y2)\) 有关，因此只有 \(x_1y_2 + x_2y_1\) 与 \(2S\) 相等时才存在解。
- 否则，直接将点代入公式求得 \(x3\) 即可。
记得判断精度误差。
关键代码：
using ld = long double;
ld eps = 1e-7;
void miyan()
{
ld x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 == x2 && y1 == y2)
{
cout << "no answer" << endl;
return;
}
if (y1 == y2)
{
ld S = fabsl(x1 * y2 - x2 * y1);
if (fabsl(S - 4.0L) > eps)
printf("no answer\n");
else
printf("114514\n");
return;
}
ld p = 4.0L - x1 * y2 + x2 * y1;
ld q = y1 - y2;
ld X = p / q;
printf("%.10Lf\n", X);
}F – Energy Synergy Matrix
算法：
博弈论。
思路：
最优策略：
- 小红：阻止小紫制造更多的拐角；
- 小紫：制造更多的拐角。
手玩找一下规律即可。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 始 | 紫 | 红 | 紫 | |||||||||||
| 红 | 紫 | 红 |
关键代码：
void miyan()
{
ll n;
cin >> n;
ll t = n / 5;
cout << n - 1 + t << endl;
}C – Inverted World
算法：
贪心。
思路：
容易想到满足要求的子序列只有两种可能，\(a = 0101…, b = 1010…\)。
分别求一下将 \(s\) 转换为 \(a\) 和 \(b\) 的操作次数，求最小值即可：
- 发现在 \(s\) 中如果 \(s_i = t_i\)（\(t_i\) 为 \(a_i\) 或者 \(b_i\)），那么 \(s_i\) 是不用操作的，操作之后答案只会变大或者不变；
- 定义 \(need\) 为 \(s_i \neq t_i\) 的字符集合，需要操作的就是 \(need\) 整个集合，由于每次只能选择一个交替串（相邻两个位置不相同的字符串），那么问题就转换为了 \(need\) 可以拆解出最少的交替子序列的个数；
求最小交替子序列：
- 定义 \(cnt0\) 为当前以 \(0\) 结尾的子序列数量，\(cnt1\) 为当前以 \(1\) 结尾的子序列数量；
- 对于 \(t_i\)，如果 \(t_i = 0\)，那么就将其接到以 \(1\) 结尾的子序列后面，执行 \(cnt1 := cnt1 – 1, cnt0 := cnt0 + 1\)，反之亦然。
关键代码：
void miyan()
{
int n;
string s;
cin >> n >> s;
string a, b;
for (int i = 0; i < n; ++i)
{
a += '0' + (i & 1);
b += '0' + ((i + 1) & 1);
}
if (s == a || s == b)
{
cout << 0 << endl;
return;
}
auto get = [&](string s, string t) -> ll
{
string need;
for (int i = 0; i < n; ++i)
if (s[i] != t[i])
need.push_back(s[i]);
ll cnt0 = 0, cnt1 = 0;
for (auto c : need)
{
if (c == '0')
{
if (cnt1 > 0)
{
cnt1--;
cnt0++;
}
else
cnt0++;
}
else
{
if (cnt0 > 0)
{
cnt0--;
cnt1++;
}
else
cnt1++;
}
}
return cnt0 + cnt1;
};
cout << min(get(s, a), get(s, b)) << endl;
}
