A. Shovels and Swords
波利卡普玩的是一款著名的电脑游戏（名字就不提了）。在这个游戏中，他可以制作两种工具–铲子和剑。制作一把铲子，波利卡普需要花费两根棍子和一颗钻石；制作一把剑，波利卡普需要花费两颗钻石和一根棍子。
每种工具可以卖到正好一颗绿宝石。如果波利卡普有 $a$ 根木棍和 $b$ 颗钻石，他能赚到多少颗绿宝石？
大概思路
按照官方题解说的，答案应该满足以下三个性质：
- $ans \le a$
- $ans \le b$
- $ans \le \frac{a+b}{3}$
被这题硬控半小时，最后没办法乱蒙了一个纸上不知道哪个角落推出来的关系时，然后1A过了
参考代码
void solve() {
int a, b;
std::cin >> a >> b;
if (a > b) std::swap(a, b);
if (a * 2 <= b) {
std::cout << a << "\n";
return;
} else {
int y = (2 * b - a) / 3;
a -= y;
b -= 2 * y;
int ans = y;
ans += std::min(b, a / 2);
std::cout << ans << "\n";
}
}
官方题解：
void solve() {
int a, b;
std::cin >> a >> b;
std::cout << std::min(std::min(a, b), (a + b) / 3) << "\n";
}
B. Shuffle
你有一个全为0的数组，第x个位置为1，进行q次操作，每次操作可在给出的区间内任选两个数，交换它们的位置。问操作结束后共有多少种可能的数组。（两数组不同当且仅当存在一个i，$a_i \ne a_i’$）
大概思路
直接贪心地维护一个区间，每次操作时，判断区间是否相交，若相交则更新所维护的区间的边界。
一开始读错题了，我还以为区间操作顺序可打乱，研究了半小时怎么处理含x的区间并的长度
参考代码
void solve(){
i64 n, x, m;
std::cin >> n >> x >> m;
i64 L = x, R = x;
auto insect = [&](i64 l, i64 r) {
return std::max(R, r) - std::min(L, l) + 1 < (R - L + 1) + (r - l + 1);
};
while (m--) {
i64 l, r;
std::cin >> l >> r;
if (insect(l, r)) {
L = std::min(L, l);
R = std::max(R, r);
}
}
std::cout << R - L + 1 << "\n";
}
C. Palindromic Paths
给你一个01矩阵，让你可能少地修改，使得任意从(1, 1)到(n, m)的转移路径都为回文路径（只能向下或向右走）
大概思路
根据题目和样例，可以靠直觉知道这个矩阵最后的形式应该有某种对称性。
考虑样例给出的合法矩阵：
$\begin{pmatrix} 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 0 & 1 \end{pmatrix}$
从起点和终点开始推，易知，只要满足如下条件，该矩阵就是一个合法的01矩阵：
$\begin{pmatrix} \color{#ff0000}{1} & \color{#ffaa00}{0} & \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#666666}{1} & \color{#00ff00}{1} & \color{#ffff00}{1}\\ \color{#ffaa00}{0} & \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#666666}{0} & \color{#00ff00}{1} & \color{#ffff00}{1} & \color{#ffaa00}{0}\\ \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#666666}{1} & \color{#00ff00}{1} & \color{#ffff00}{1} & \color{#ffaa00}{0} & \color{#ff0000}{1} \end{pmatrix}$
相同颜色的数必须全部相同（灰色部分不需要管，因为它是路径中心）
$\begin{pmatrix} \color{#ff0000}{1} & \color{#ffaa00}{0} & \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#00ff00}{1} & \color{#ffff00}{1}\\ \color{#ffaa00}{0} & \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#00ff00}{1} & \color{#ffff00}{1} & \color{#ffaa00}{0}\\ \color{#ffff00}{1} & \color{#00ff00}{1} & \color{#00ff00}{1} & \color{#ffff00}{1} & \color{#ffaa00}{0} & \color{#ff0000}{1} \end{pmatrix}$
而这种情况是没有所谓的路径中心的，所以要注意分奇偶特判一下
参考代码
void solve(){
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> a(std::min(n, m) + 1, std::vector<int>(std::max(n, m) + 1));
if (n > m) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> a[j][i];
}
}
std::swap(n, m);
} else {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
std::cin >> a[i][j];
}
}
}
int ans = 0;
for (int j = 1; j <= n + (m - 1 - n) / 2 - (n == m); j++) {
int sum = 0, L = 0, R = 0;
for (int i = 1; i <= n && j - i + 1 >= 1; i++) {
sum++;
L += a[i][j - i + 1];
R += a[n - i + 1][m - (j - i + 1) + 1];
}
if (L == R && (L == 0 || L == sum)) {
continue;
} else {
ans += std::min(L + R, 2 * sum - L - R);
}
}
std::cout << ans << "\n";
}
D. Two Divisors
给你n个数，对于每个数$a_i$，找到它的一对约数$d_1 > 1$, $d_2 > 1$，满足$\gcd(d_1 + d_2, a_i) = 1$，如果不存在，输出-1。（$2 \le a_i \le 10^7$）
大概思路
超级水题，为什么他放在D题啊，我觉得放B题都没问题的
一眼就看到1e7这个数据范围，没记错的话，我板子里那个筛子的上限就是1e7。
直接分类讨论即可：
- 当 $a_i$ 为质数时，不存在符合题意的约数对。
- 当 $a_i$ 为某个质数的幂时，显然不行，因为这样加出来的gcd必为那个质数。
- 当 $a_i$ 由两个以上的本质不同的质数构成时，显然可以。若 $a_i = \prod p_i^{c_i}$，直接取 $a_i$ 的最小质因数 $p$，以及 $\frac{a_i}{p^{c}} $ 即可。
参考代码
struct Sieve {
std::vector<int> mpf; // minimum prime factor
std::vector<int> prime;
Sieve(int n) : mpf(n) {
for (int i = 2; i < n; i++) {
if (mpf[i] == 0) {
prime.push_back(i);
mpf[i] = i;
}
for (int j = 0; j < prime.size() and i * prime[j] < n; j++) {
mpf[i * prime[j]] = prime[j];
if (prime[j] == mpf[i])
break;
}
}
}
// get all factors
std::vector<int> getDiv(int x) const {
std::vector<int> _div(1, 1);
while (x > 1) {
int d = mpf[x];
int l = 0, r = _div.size();
while (x % d == 0) {
for (int k = l; k < r; k++) {
_div.push_back(_div[k] * d);
}
x /= d;
l = r, r = _div.size();
}
}
return _div;
}
};
Sieve si(1e7 + 1);
void solve(){
//std::cout << "ok";
int n;
std::cin >> n;
std::vector<std::pair<int, int>> ans(n);
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (si.mpf[x] == x) {
ans[i] = {-1, -1};
} else {
int z = si.mpf[x];
while (x != 1 && x % z == 0) {
x /= z;
//std::cout << x << "\n";
}
if (x == 1) {
ans[i] = {-1, -1};
} else {
ans[i] = {z, x};
}
}
}
for (auto &[x, y] : ans) {
std::cout << x << " ";
}
std::cout << "\n";
for (auto &[x, y] : ans) {
std::cout << y << " ";
}
}