The 2026 ICPC Latin America Championship(2026 拉丁美洲决赛)-Gym-106416——K. Kitten Greetings(傻逼题面,对常数要求比较高,1e7 的数据下,确实普通的vec 套 vec 存图力不从心了) · znzryb
## 题目大意
**题目描述**
给定二维平面上的 $N$ 只猫的坐标,保证没有任何两只猫的 $X$ 坐标相同,也没有任何两只猫的 $Y$ 坐标相同。
你需要设计一条符合以下规则的回路(包含 $m$ 个步骤,问候 $m$ 只不同的猫):
1. 选择一个起点 $(x_0, y_0)$,并面向四个基本方向(东、南、西、北)之一。
1. 在第 $i$ 步($1 \le i \le m$)中:
- 选择一个距离 $k_i > 0$,沿着当前方向直线前进 $k_i$ 的距离,此时必须恰好停在一只**之前从未问候过**的猫的位置。
- 问候这只猫。
- 不改变方向,继续直线前进 $k_i$ 的距离,到达点 $(x_i, y_i)$。
- 左转或右转 90 度,面向一个新的基本方向。
1. 完成所有 $m$ 步后,必须回到起点 $(x_0, y_0)$,并且面向初始方向。
整条路线的总长度为 $\sum_{i=1}^{m} 2k_i$。如果 $m=0$,则路线长度为 $0$。
请计算并输出符合上述规则的路线的**最大总长度**。
(注:由于猫的 $X$ 和 $Y$ 坐标互不相同,平面上任意水平或垂直的直线上最多只有一只猫。因此题目等价于:在平面上寻找一个边平行于坐标轴且边数偶数的闭合多边形,该多边形的每一条边的中点都恰好是一只猫,求该多边形的最大周长。)
**输入格式**
第一行包含一个整数 $N$($1 \le N \le 4000$),表示猫的数量。
接下来 $N$ 行,每行包含两个整数 $X$ 和 $Y$($-10^8 \le X, Y \le 10^8$),表示一只猫的坐标。
保证没有任何两只猫的 $X$ 坐标相同,也没有任何两只猫的 $Y$ 坐标相同。
**输出格式**
输出一个整数,表示符合条件的路线的最大总长度。
**样例 1**
**输入**
```
5
1 2
2 1
0 0
-1 -2
-2 -1
```
**输出**
```
0
```
**样例 1 解释**
虽然存在一条长度为 16 且经过所有猫的回路,但它不符合规则,因为沿途位于 $(0,0)$ 的猫会被问候两次,而题目要求每次经过的猫都必须是之前未曾问候过的。
**样例 2**
**输入**
```
6
4 0
0 4
2 -1
-1 2
-4 3
3 -4
```
**输出**
```
32
```
**样例 2 解释**
存在一条长度为 32 的路线,可以完美经过并问候所有 6 只猫。每只猫都恰好位于路线某条直线段的正中点。
**样例 3**
**输入**
```
7
2 1
0 -1
5 5
3 0
4 4
6 2
1 -2
```
**输出**
```
24
```
**样例 3 解释**
在给定的 $N=7$ 只猫中,可以选择其中的 $m=6$ 只猫构成一条合法的路线,其能达到的最大长度为 24。

## 思路讲解
这个数据是 $O(n^2)$ 的。
这个还是非常适合图论建模的。

这个上面的是不难看出的。
## AC代码
AC
[https://codeforces.com/gym/106416/submission/368359863](https://codeforces.com/gym/106416/submission/368359863)
::: 源代码
```cpp
// teamname: Gospel_rock
/**
* Problem: K. Kitten Greetings
* Contest: The 2026 ICPC Latin America Championship
* Judge: Codeforces
* URL: https://codeforces.com/gym/106416/problem/K
* Created: 2026-03-27 00:05:52
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct X_y {
ll x, y;
ll id;
};
bool cmpx(const X_y &a, const X_y &b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmpy(const X_y &a, const X_y &b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
// 以后从低位到高位写
// 这样子映射,要求 a,b 是 0-based,即范围是 [0,N)
// 注意,这里的 type 的意思是说这个节点想要后续的点是 横边 还是 竖边?
ll gen_id(ll a, ll b, ll type, ll N) {
return type * N * N + b * N + a;
}
auto gen_graph(vector<X_y> &xyx_ls, vector<X_y> &xyy_ls, ll N) {
sort(all(xyx_ls), cmpx);
sort(all(xyy_ls), cmpy);
vector<int> g(2 * N * N + 2, -1);
for (int i = 0; i < N; ++i) {
auto [xb,yb,idb] = xyx_ls[i];
for (int j = 0; j < N; ++j) {
if (j == i) continue;
auto [xa,ya,ida] = xyx_ls[j];
ll targetx = 2 * xb - xa;
auto it = lower_bound(all(xyx_ls), X_y{targetx, -INF, 0}, cmpx);
if (it == xyx_ls.end() || it->x != targetx) {
continue;
}
auto [xc,yc,idc] = *it;
ll u = gen_id(ida, idb, 0, N), v = gen_id(idb, idc, 1, N);
g[u] = v;
}
}
for (int i = 0; i < N; ++i) {
auto [xb,yb,idb] = xyy_ls[i];
for (int j = 0; j < N; ++j) {
if (j == i) continue;
auto [xa,ya,ida] = xyy_ls[j];
ll targety = 2 * yb - ya;
auto it = lower_bound(all(xyy_ls), X_y{-INF, targety, 0}, cmpy);
if (it == xyy_ls.end() || it->y != targety) {
continue;
}
auto [xc,yc,idc] = *it;
ll u = gen_id(ida, idb, 1, N), v = gen_id(idb, idc, 0, N);
g[u] = v;
}
}
return g;
}
vector<ll> get_info_from_u(ll u, ll N) {
vector<ll> res;
while (u) {
res.push_back(u % N);
u /= N;
}
res.resize(2);
return res;
}
void push_node(ll u, queue<ll> &q, auto &vis, vector<int> &cat_vis, ll N, bool is_start) {
q.push(u);
vis[u] = true;
vector<ll> t = get_info_from_u(u, N);
if (is_start) {
cat_vis.push_back(t[0]);
}
cat_vis.push_back(t[1]);
}
ll get_dis(const X_y &a, const X_y &b) {
ll res = abs(a.x - b.x) + abs(b.y - a.y);
return res;
}
ll get_dis_from_id_ls(const vector<int> &cat_vis, const auto &xy_id_ls) {
ll sz = SZ(cat_vis);
ll res = 0;
for (int i = 0; i < sz; ++i) {
res += get_dis(xy_id_ls[cat_vis[i % sz]], xy_id_ls[cat_vis[(i + 1) % sz]]);
}
return res;
}
// 注意,我们虽然叫图论建模,但是这个图是非常简单的,其实就是一条链,或者一个环。
ll bfs(const auto &g, auto &vis, ll start, ll N, const auto &xy_id_ls) {
queue<ll> q;
vector<int> cat_vis;
// ll cat_start;
ll res = 0;
push_node(start, q, vis, cat_vis, N, true);
while (!q.empty()) {
ll u = q.front();
q.pop();
for (auto to: g[u]) {
if (vis[to]) {
// assert(0);
continue;
}
push_node(to, q, vis, cat_vis, N, false);
}
}
if (SZ(cat_vis) <= 1) {
return 0;
}
if (cat_vis.back() == cat_vis.front()) {
vector<int> uni_cat = cat_vis;
sort(all(uni_cat));
uni_cat.resize(unique(all(uni_cat)) - uni_cat.begin());
if (SZ(uni_cat) == SZ(cat_vis) - 1) {
#ifdef LOCAL
debug1d(cat_vis);
#endif
return get_dis_from_id_ls(cat_vis, xy_id_ls);
}
}
return 0;
}
ll gen_ans(const vector<int> &g, ll N, const vector<X_y> &xy_id_ls) {
static bitset<2 * 4000 * 4000 + 2> vis;
vis.reset();
ll ans = 0;
for (int i = 0; i < 2 * N * N; ++i) {
if (vis[i]) continue;
vis[i] = 1;
if (g[i] == -1) continue;
// 沿链前进
vector<int> chain;
chain.push_back(i);
int cur = g[i];
while (cur != -1 && !vis[cur]) {
vis[cur] = 1;
chain.push_back(cur);
cur = g[cur];
}
if (cur == -1) continue;
int cs = -1;
for (int j = 0; j < (int)chain.size(); j++) {
if (chain[j] == cur) { cs = j; break; }
}
if (cs == -1) continue;
// 提取环上的猫
vector<int> cat_vis;
for (int j = cs; j < (int)chain.size(); j++) {
int a = chain[j] % N, b = (chain[j] / N) % N;
if (j == cs) cat_vis.push_back(a);
cat_vis.push_back(b);
}
if (SZ(cat_vis) <= 1) continue;
if (cat_vis.front() != cat_vis.back()) continue;
vector<int> uni_cat = cat_vis;
sort(all(uni_cat));
uni_cat.resize(unique(all(uni_cat)) - uni_cat.begin());
if (SZ(uni_cat) == SZ(cat_vis) - 1) {
ans = max(ans, get_dis_from_id_ls(cat_vis, xy_id_ls));
}
}
return ans;
}
void Solve() {
ll N;
cin >> N;
vector<X_y> xyx_ls(N);
for (int i = 0; i < N; ++i) {
cin >> xyx_ls[i].x >> xyx_ls[i].y;
xyx_ls[i].id = i;
}
vector<X_y> xy_id_ls = xyx_ls;
auto xyy_ls = xyx_ls;
auto g = gen_graph(xyx_ls, xyy_ls, N);
cout << gen_ans(g, N, xy_id_ls) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
// cin >> lT;
// for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
*/
```
:::
我的 TLE 代码(应该没什么问题,但是这个题目对常数要求比较高)
::: TLE 代码
```cpp
// teamname: Gospel_rock
/**
* Problem: K. Kitten Greetings
* Contest: The 2026 ICPC Latin America Championship
* Judge: Codeforces
* URL: https://codeforces.com/gym/106416/problem/K
* Created: 2026-03-27 00:05:52
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);
ll lT, testcase;
/*
*
*/
struct X_y {
ll x, y;
ll id;
};
bool cmpx(const X_y &a, const X_y &b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmpy(const X_y &a, const X_y &b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
// 以后从低位到高位写
// 这样子映射,要求 a,b 是 0-based,即范围是 [0,N)
// 注意,这里的 type 的意思是说这个节点想要后续的点是 横边 还是 竖边?
ll gen_id(ll a, ll b, ll type, ll N) {
return type * N * N + b * N + a;
}
auto gen_graph(vector<X_y> &xyx_ls, vector<X_y> &xyy_ls, ll N) {
sort(all(xyx_ls), cmpx);
sort(all(xyy_ls), cmpy);
vector<vector<int> > g(2 * N * N + 2);
for (int i = 0; i < N; ++i) {
auto [xb,yb,idb] = xyx_ls[i];
for (int j = 0; j < N; ++j) {
if (j == i) continue;
auto [xa,ya,ida] = xyx_ls[j];
ll targetx = 2 * xb - xa;
auto it = lower_bound(all(xyx_ls), X_y{targetx, -INF, 0}, cmpx);
if (it == xyx_ls.end() || it->x != targetx) {
continue;
}
auto [xc,yc,idc] = *it;
// 填写 type0 是 {ida to idb} 节点是想要 横边,所以就是 0
ll u = gen_id(ida, idb, 0, N), v = gen_id(idb, idc, 1, N);
g[u].push_back(v);
// g[v].push_back(u);
}
}
for (int i = 0; i < N; ++i) {
auto [xb,yb,idb] = xyy_ls[i];
for (int j = 0; j < N; ++j) {
if (j == i) continue;
auto [xa,ya,ida] = xyy_ls[j];
ll targety = 2 * yb - ya;
auto it = lower_bound(all(xyy_ls), X_y{-INF, targety, 0}, cmpy);
if (it == xyy_ls.end() || it->y != targety) {
continue;
}
auto [xc,yc,idc] = *it;
ll u = gen_id(ida, idb, 1, N), v = gen_id(idb, idc, 0, N);
g[u].push_back(v);
// g[v].push_back(u);
}
}
return g;
}
vector<ll> get_info_from_u(ll u, ll N) {
vector<ll> res;
while (u) {
res.push_back(u % N);
u /= N;
}
res.resize(2);
return res;
}
void push_node(ll u, queue<ll> &q, auto &vis, vector<int> &cat_vis, ll N, bool is_start) {
q.push(u);
vis[u] = true;
vector<ll> t = get_info_from_u(u, N);
if (is_start) {
cat_vis.push_back(t[0]);
}
cat_vis.push_back(t[1]);
}
ll get_dis(const X_y &a, const X_y &b) {
ll res = abs(a.x - b.x) + abs(b.y - a.y);
return res;
}
ll get_dis_from_id_ls(const vector<int> &cat_vis, const auto &xy_id_ls) {
ll sz = SZ(cat_vis);
ll res = 0;
for (int i = 0; i < sz; ++i) {
res += get_dis(xy_id_ls[cat_vis[i % sz]], xy_id_ls[cat_vis[(i + 1) % sz]]);
}
return res;
}
// 注意,我们虽然叫图论建模,但是这个图是非常简单的,其实就是一条链,或者一个环。
ll bfs(const auto &g, auto &vis, ll start, ll N, const auto &xy_id_ls) {
queue<ll> q;
vector<int> cat_vis;
// ll cat_start;
ll res = 0;
push_node(start, q, vis, cat_vis, N, true);
while (!q.empty()) {
ll u = q.front();
q.pop();
for (auto to: g[u]) {
if (vis[to]) {
// assert(0);
continue;
}
push_node(to, q, vis, cat_vis, N, false);
}
}
if (SZ(cat_vis) <= 1) {
return 0;
}
if (cat_vis.back() == cat_vis.front()) {
vector<int> uni_cat = cat_vis;
sort(all(uni_cat));
uni_cat.resize(unique(all(uni_cat)) - uni_cat.begin());
if (SZ(uni_cat) == SZ(cat_vis) - 1) {
#ifdef LOCAL
debug1d(cat_vis);
#endif
return get_dis_from_id_ls(cat_vis, xy_id_ls);
}
}
return 0;
}
ll gen_ans(const auto &g, ll N, const auto &xy_id_ls) {
// vector<char> vis(2 * N * N + 2);
bitset<2 * 4000 * 4000 + 2> vis;
ll ans = 0;
for (int i = 0; i < 2 * N * N; ++i) {
if (vis[i]) {
continue;
}
ans = max(ans, bfs(g, vis, i, N, xy_id_ls));
}
return ans;
}
void Solve() {
ll N;
cin >> N;
vector<X_y> xyx_ls(N);
for (int i = 0; i < N; ++i) {
cin >> xyx_ls[i].x >> xyx_ls[i].y;
xyx_ls[i].id = i;
}
vector<X_y> xy_id_ls = xyx_ls;
auto xyy_ls = xyx_ls;
auto g = gen_graph(xyx_ls, xyy_ls, N);
cout << gen_ans(g, N, xy_id_ls) << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流,方便我们调试
#endif
// cin >> lT;
// for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程(WA,TLE,MLE……)
