2025ICPC沈阳区域赛 K题

https://qoj.ac/contest/2641/problem/14950

题目概述

平面上有 \(n\) 只青蛙（编号 \(1\) 到 \(n\)），初始坐标互不相同。外部刺激会触发连锁跳跃反应：

• 当青蛙 \(i\) 受到刺激，它会选择跳过另一只青蛙 \(j\)，并精准落在以 \(j\) 为中心的对称点上。
• 跳跃完成后，青蛙 \(j\) 成为下一只唯一受到刺激的青蛙。
• 连锁反应在某只青蛙选择原地不动时结束。

题目给出了所有青蛙的初始坐标、最终坐标以及第一只被刺激的青蛙编号 \(s\)，求最后一只被刺激的青蛙编号 \(t\)。

---

思路

面对这道题，如果顺着题目的描述去思考，就会想到模拟，但这肯定不行。

模拟的死胡同

最直观的想法是写代码去模拟青蛙跳来跳去。但很快会发现两个无法逾越的鸿沟：

• 信息缺失：题目只给了开头和结尾，根本没有给中间具体的跳跃顺序（谁跳了谁）。
• 复杂度超标：跳跃次数高达 \(2 \times 10^5\)，即便知道顺序，高频的坐标更新和追踪也极易超时。
• 结论：必须跳出局部细节，从宏观寻找规律。

Hint 1 : 从局部变化观察全局属性

既然不能盯着每一步怎么跳，我们就需要寻找一个“全局属性”。在涉及大量坐标移动的题目中，最容易想到的全局属性就是“所有人坐标的总和”。

我们先看最基本的数学规则：青蛙 \(A\) 跳过青蛙 \(B\) 落地到对称点。
根据平面几何的中点公式（对称中心点坐标是两端点坐标的平均值）：

\[\frac{A_{\text{旧}} + A_{\text{新}}}{2} = B \implies A_{\text{旧}} + A_{\text{新}} = 2 \times B \]

我们可以推导出 \(A\) 跳跃后的新坐标公式：

\[A_{\text{新}} = 2 \times B - A_{\text{旧}} \]

接下来，我们观察这一次跳跃对全场坐标总和（设为 \(Sum\)）带来了什么影响？
因为整场只有青蛙 \(A\) 动了，其他青蛙都没动，所以：

\[\text{新总和} = \text{旧总和} - A_{\text{旧}} + A_{\text{新}} \]

把上面推导出的 \(A_{\text{新}}\) 代入进来：

\[\text{新总和} = \text{旧总和} - A_{\text{旧}} + (2 \times B - A_{\text{旧}}) \]

\[\text{新总和} = \text{旧总和} - 2 \times A_{\text{旧}} + 2 \times B \]

Hint2 : 移项,分类配对

盯着上面这个公式：\(\text{新总和} = \text{旧总和} - 2 \times A_{\text{旧}} + 2 \times B\)。
搞算法和数学有一个常用技巧 —— 配对，把属于“跳跃前”的变量移到等号一边，把属于“跳跃后”的变量移到另一边。

我们将 \(2 \times B\) 移到左边：

\[\text{新总和} - 2 \times B = \text{旧总和} - 2 \times A_{\text{旧}} \]

这时候，奇迹出现了：

• 等号右边是：跳跃前的坐标总和 \(- 2 \times\) 跳跃前受刺激的青蛙坐标 (\(A\))
• 等号左边是：跳跃后的坐标总和 \(- 2 \times\) 跳跃后受刺激的青蛙坐标 (\(B\))

我们发现等号左边和等号右边的共同点都是 坐标的总和 - 当前受到刺激的青蛙坐标

这说明了什么？无论青蛙怎么乱跳，这个组合计算出来的数值在全过程中是绝对绝对不会变的！ 这就是整个系统的“不变量”（守恒量）。

---

算法设计与求解步骤

既然找到了这个永恒不变的总和，我们就可以直接绕过中间几十万步复杂的跳跃过程，直接连线开局与结局：

1. 计算初始常数 \(K\)：
   利用初始状态所有青蛙的坐标，算出初始总和 \(Sum_{\text{start}}\)。已知第一只被刺激的青蛙是 \(s\)，其初始坐标为 \(P_s\)。

\[K = Sum_{\text{start}} - 2 \times P_s \]

2. 利用最终状态列方程：
   算结局时所有青蛙的最终坐标总和 \(Sum_{\text{end}}\)。设最后一只被刺激的青蛙最终坐标为 \(Q_t\)。由于不变量守恒：

\[Sum_{\text{end}} - 2 \times Q_t = K \]

3. 一元一次方程求解 \(Q_t\)：

\[2 \times Q_t = Sum_{\text{end}} - K \implies Q_t = \frac{Sum_{\text{end}} - K}{2} \]

4. 全场搜寻目标：
   算出了最后一只青蛙的具体坐标 \(Q_t\) 后，在最终的青蛙队伍里挨个比对，看谁刚好站在这，谁就是我们要找的青蛙 \(t\)。

---

C++ 代码实现

//
// Created by awake on 2026/5/17.
//
#include <bits/stdc++.h>
using namespace std;// clang-format off
struct { auto operator()(auto &i) { cin >> i; } } IN; // NOLINT
struct { auto operator()(auto &i) { cout << i << ' '; } } OUT; // NOLINT
// clang-format on
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)// NOLINT
#define int long long
using pii = pair<int, int>; //NOLINT
using ll = long long;       //NOLINT
template <typename T>
using vec = vector<T>; //NOLINT#define endl '\n'void solve()
{int n, s;cin >> n >> s;vec<pii> P;vec<pii> Q;pii sum1 = {0, 0};pii sum2 = {0, 0};pii st = {0, 0};for (int i = 1; i <= n; i++){int px, py, qx, qy;cin >> px >> py >> qx >> qy;P.emplace_back(px, py);Q.emplace_back(qx, qy);sum1.first += px;sum1.second += py;sum2.first += qx;sum2.second += qy;if (i == s){st.first += px;st.second += py;}}int Kx = sum1.first - 2 * st.first;int Ky = sum1.second - 2 * st.second;int enx = (sum2.first - Kx) / 2;int eny = (sum2.second - Ky) / 2;for (int i = 0; i < n; i++){if (Q[i].first == enx && Q[i].second == eny){cout << (i + 1) << endl;return;}}
}signed main()
{IOS;int T = 1;// cin >> T;while (T--)solve();return 0;
}

tag说明

数学 : 解题的核心过程是代数公式的列举、移项、合并同类项，最终化简出一个优雅的等式。
不变量：本题最精准的方法论标签。面对复杂多变的过程，寻找“总量不变”或“特定代数和不变”的属性，是算法竞赛中非常经典的一类套路。
几何 ：利用了基础的“中心对称 / 点对称”的几何性质（中点公式）。不过它对几何知识的考察非常浅。