CF2253D
2026-08-08 11:12:21
发布于：广东
13阅读
0回复
0点赞
非常有意思的数学题！
首先也是最重要的转化：我们考虑假设现在是第步，只考虑维度，若我们选择的话，它会在中都会贡献，当从中，贡献范围恰好是，维度同理。
所以题目转化为：从中选若干数相加，为剩余数相加。
既然这样，我们观察到恒成立。
所以贪心来看，我们要求最大的满足。
再看题目要求的与终点的最短距离：
转化：
根据这是一个关于二次函数，对其求导为能求到最小值：
但可能取不到，左右正整数取最优即可，再把的边界判清楚。
最后我们要处理维度选的数和为，维度为。这个我们只考虑维度，从大到小贪心枚举即可，能减就减掉，根据我们第一步讲的，如果当前你选了，相当于你在这个位置上在选择在维度上。
这样我们就做完了。
#include<bits/stdc++.h>
using namespace std;
namespace CZW {
#define endl "\n"
#define vec std::vector
#define pb push_back
#define eb emplace_back
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using lb = long double;
void Main() {
ll x, y;
cin >> x >> y;
ll n = sqrtl(2.0 * (x + y));
while ((n + 1) * (n + 2) / 2 <= x + y) ++n;
while (n * (n + 1) / 2 > x + y) --n;
ll s = n * (n + 1) / 2;
lb pi = (x - y + s) / 2.0;
ll p1 = floor(pi), p2 = ceil(pi);
p1 = max(max(0ll, s - y), min(min(s, x), p1));
p2 = max(max(0ll, s - y), min(min(s, x), p2));
auto get = [&](ll p)->ll{
ll q = s - p;
return (x - p) * (x - p) + (y - q) * (y - q);
};
ll best = p1;
if (get(p2) < get(p1)) best = p2;
vec<char> ans(n + 1, 'Y');
ll cur = best;
for (ll i = n; i >= 1; --i) {
if (cur >= i) {
cur -= i;
ans[n - i + 1] = 'X';
}
}
for (int i = 1; i <= n; ++i) cout << ans[i];
cout << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Test = 1;
cin >> Test;
while (Test--) CZW::Main();
return 0;
}
所以@cjdst和lyy大佬场切太强了，让我们膜拜/bx /bx /bx
有帮助，赞一个