A题 Burenka Plays with Fractions（签到）
给定 2 个分数 \(\dfrac{a}{b},\dfrac{c}{d}\)，现在可以自行进行操作，每次选定一个分数，将其分子或者分母乘上一个数，问至少需要多少次操作才能使得两个分数的值相同？
\(T\leq 10^4,0\leq a,c\leq 10^9,1\leq b,d\leq 10^9\)
对于 \(a,c=0\) 的情况特判一下，省的下面额外处理。
至多只需要两次操作即可（\(\dfrac{a}{b}=\dfrac{ad}{bc}*\dfrac{c}{d}\)），所以我们只需要检查 0，1，2 三种情况即可：
- 0 次操作：两个数的值相同
- 1 次操作：\(ad,bc\) 中有一个是另一个的倍数
- 2 次操作：不存在倍数关系
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL solve() {
LL a, b, c, d;
cin >> a >> b >> c >> d;
if (a == 0) return c != 0;
if (c == 0) return a != 0;
//
LL x = a * d, y = b * c;
if (x == y) return 0;
if (x % y == 0 || y % x == 0) return 1;
return 2;
}
int main() {
int T;
cin >> T;
while (T--) cout << solve() << endl;
return 0;
}
B题 Interesting Sum（思维）
记一个序列的价值为：一个序列的最大值减去最小值。
给定一个长度为 \(n\) 的数组 \(\{a_n\}\)，要求从中选取出一个连续子序列 \([l,r]\)（非空，但是不可以是原数组本身），然后剩下来的那些数重新组成新数列，求出这两个序列的价值和的最大值可能是多少。
\(4\leq n\leq 10^5,1\leq a_i\leq 10^9\)
记整个数组的最大值，次大值，最小值，次小值分别为 \(a,b,c,d\)，那么价值的可能最大值是 \(a+b-c-d\)，而这个值总是能取到的：让这个子序列恰好包含一个大值和小值即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, a[N];
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
cout << a[n] + a[n - 1] - a[1] - a[2] << endl;
}
return 0;
}
C题 Corners（思维）
题意略，建议参照原题面。
答案的上限值是 1 的数量，我们看看啥情况会变得少一些。
注意到，如果存在着两个连续相邻的 0，那么答案就是 1 的数量：因为这保证了每次选定一个 L，都能保证里面有且仅有一个 1。
又因为一次 L 操作后一定会使得图上出现相邻 1，那么我们只需要尽可能减少第一轮消灭的 1 的数量即可：
- 全 1 状态下，一轮至少需要消灭三个
- 一轮只消灭一个，说明有相邻 0 或者对角 0
- 其他情况，一轮都得消灭两个
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
char s[N][N];
bool check(int x, int y) {
if (s[x][y] == '1') return false;
return s[x][y + 1] == '0' || s[x + 1][y] == '0' || s[x + 1][y + 1] == '0' || s[x + 1][y - 1] == '0';
}
int solve() {
memset(s, 0, sizeof(s));
//read
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
//solve
int tot = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (s[i][j] == '1') ++tot;
if (tot == n * m) return tot - 2;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (check(i, j)) return tot;
return tot - 1;
}
int main() {
int T;
scanf("%d", &T);
while (T--) printf("%d\n", solve());
return 0;
}