祝各位 CSP2025 RP++！
在 的时候，我偶然看见有一篇帖子 https://ykj.cpolar.cn/article/7186。
于是我打算写一波题解。
解题思路呢
首先，分讨。假设我们从 中选出的数为 ， 中选的数为 。
- ，显然 都最小时是最优的，于是乎答案就是 。
- ，显然答案为 。
- ，显然答案为负数，那么在 最小时， 最大时有最大值。
- ，显然答案为 。
- ，显然答案为 。
- ，显然答案为 。
- ，显然答案为负数，那么在 最大时， 最小时有最大值。
- ，显然答案为 。
- ，显然 都最大时是最优的，于是乎答案就是 。
于是我们就尤拉肥肠暴戾的代码，但是显然由于人类智慧，写出来的代码可以疯狂精简，最后也并不复杂。
显然 as a test question creator，并没有想到会因为高精度的问题使得两年以来 besides me 居然无人通过。
于是乎橙题 黄题。
__int128 a[100010], b[100010];
inline __int128 read() {
__int128 x = 0;
int w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-')
w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void write(__int128 x) {
if (x < 0) {
putchar('-');
x = -x;
}
static int sta[40];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + '0');
}
int main() {
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0;
for (int i = 1; i <= n; i++) {
if (a[i] < 0)
ans1++;
else if (a[i] == 0)
ans2++;
if (b[i] < 0)
ans3++;
else if (!b[i])
ans4++;
}
__int128 res1 = -1e30, res2 = -1e30;
for (int i = 1; i <= n; i++) {
if (a[i] < 0) {
res1 = a[i];
break;
}
}
for (int i = 1; i <= n; i++) {
if (b[i] < 0) {
res2 = b[i];
break;
}
}
if (ans1 + ans2 == n && ans3 + ans4 == n) {
write(res1 * res2);
return 0;
}
__int128 res5 = -1e30, res6 = -1e30;
for (int i = n; i >= 1; i--) {
if (res5 == -1e30 && a[i] > 0)
res5 = a[i];
if (res6 == -1e30 && b[i] > 0)
res6 = b[i];
}
if (res5 != -1e30 && res6 != -1e30) {
if (res1 != -1e30 && res2 != -1e30)
write(max(res5 * res6, res1 * res2));
else
write(res5 * res6);
return 0;
}
res5 = -1e30, res6 = -1e30;
for (int i = n; i >= 1; i--) {
if (res5 == -1e30 && a[i] < 0)
res5 = a[i];
if (b[i] >= 0)
res6 = b[i];
}
__int128 res7 = -1e30, res8 = -1e30;
for (int i = n; i >= 1; i--) {
if (a[i] >= 0)
res7 = a[i];
if (res8 == -1e30 && b[i] < 0)
res8 = b[i];
}
if (res5 != -1e30 && res6 != -1e30)
write(res5 * res6);
else
write(res7 * res8);
关于 __int128
由于不能直接 cin 或 cout，所以需要手写快读快写，显然 bd 一大堆，AI 也是可以解释清楚的。
但是需要注意的是：__int128 不在 C++ 标准中！不在 namespace std 中！ 位 GCC 可直接使用。小熊猫 C++ 似乎也不支持。
共 1 条回复
QAQ