题解：P13343 [EGOI 2025] 一个弦线问题

Doraeman · 2025-07-26 00:00:16 · 题解

感谢来自上一篇题解的大佬 rui_er 的指教！

弦的平行

观察题目给出的两个圆形示例。
在这两个圆形中，所有共 2N 个琴钉连接的 N 条弦线都互相平行。

规律

试试在图中找找规律，可以发现：在这个顺时针均匀编号的圆中，两条弦线的左右端点的编号（设其为第 1 条弦 a_1,b_1，第 2 条弦 a_2,b_2），如果满足 (a_1+b_1)\equiv(a_2+b_2)\pmod{2N}，且 \big((a_1+b_1)\bmod(2N)\big) 为奇数，那么这两条线平行。

注：如果 \big((a_1+b_1)\bmod(2N)\big) 是偶数，就会出现自测样例 4 的情况。
简洁地说，调整后必然会存在恰好 2 条弦，它们各自的两个端点相邻，这时它们各自的端点编号之和就都是奇数，那么其它的也必须是奇数（因为模 2N（偶数）同余）。

表示方法

为了方便表示，规定 F(x,y)=(x+y)\bmod(2N)。

规律应用

此时我们可以设第 i 条弦有一个“弦值” D_i=F(a_i,b_i)。
我们的终极目标就是通过移动弦的端点使所有 D_i 相等（这样它们就都平行了）。

此处用到贪心策略，步骤如下。

1. 求出所有 D_i。
2. 统计这些 D_i 的出现次数。
3. 求出出现次数最多的 D_i，规定这个 D_i 为“最好值”，用 best 记录。 如果出现多个 D_i 出现次数相同且都是最多，那么任意选择 1 个 D_i 作为 best 值。
4. 把其它所有 D_i\not=best 的弦都进行挪动操作，使其符合 D_i=best。这些弦都要挪动恰好一次，所以要最大化 best，这样一来挪动的弦的数量就会尽可能小，即 K 尽可能小。

细节：特殊判断

根据上文内容，所有 D_i 最后都要被调整为奇数，所以 best 也必须是奇数。
那么，对于类似自测样例 4 的情况，所有 D_i 初始都是偶数，就需要特别规定 best 为某个奇数（例如 1）。

求 K 的值

循环检查，从 1 至 N，如果 D_i\not=best，就说明这条弦需要被挪动，K 增加 1。最后求出 K，输出。

求 K 的 50 分代码

注：题目的 SPJ 疑似与题面描述不符，这份代码可能被误判为 0 分（这份部分分代码没有错误，因为它参与到了之后的 AC 代码中）。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int n, maxi;
struct Wire{
    int x, y, sum = 0, id;
}a[N];
map <int, int> p;

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a[i].x >> a[i].y;
        a[i].sum = (a[i].x + a[i].y) % (n*2);
        if(a[i].sum % 2) 
            p[a[i].sum]++,
            maxi = max(maxi, p[a[i].sum]);
        a[i].id = i;
    }

    int best;
    for(int i=0; i<n; i++)
        if(p[a[i].sum] == maxi) 
        best = a[i].sum;
    if(best % 2 == 0) best = 1; // 特判 

    int k = 0;
    for(int i=0; i<n; i++)
        if(a[i].sum != best) k++;
    cout << k;
}

模拟：挪弦与挪弦顺序

这部分内容，要求我们必须要找到正确的挪弦顺序，否则不可能 AC。

规定已知 x 时，x' 能使其满足 F(x,x')=best。
反推可以得到 x'=(best+2N-x)\bmod{(2N)}。

规定 ok(x)=1 表示 x 已经找到了其对应的 x'，ok(x)=0 则表示没有找到。

以下两种顺序被验证是错误的，但这是一种思维的过程。如果各位大佬觉得浪费时间也可以直接跳到结论。

一、先看 a 再看 b

先来考虑一种最简朴的挪动顺序：从 1 到 N 遍历，如果当前的 D_i=best，不用继续考虑。
反之，需要考虑挪动这条弦。

先考虑 a，如果 ok(a)=ok(a')=0，就将 a 和 a' 连在一起，并直接考虑下一条弦。

这种考虑顺序被证明是错误的，可以参考第 4 个自测样例。

6
3 9
7 5
10 2
0 6
1 11
8 4

假设这组样例的 best=1，那么这种顺序会导致考虑编号为 5 的弦（1 11）时出现 ok(1)=ok(0)=1,ok(11)=ok(2)=1 的情况，即都已经被连过了，无法继续考虑。

以下是这种考虑顺序对应的代码（为缩短文章长度，仅展示部分代码，不含求 K 部分）。

for(int i=0; i<n; i++){
    if(a[i].sum == best)
        continue;

    // x连接y 变成 x连接xx 或 y连接yy 
    int x = a[i].x, y = a[i].y;
    int xx = (best+n*2 - x) % (n*2),
        yy = (best+n*2 - y) % (n*2);

    if(!ok[xx]){ // 优先考虑：如果x连接xx可以 
        ok[x] = ok[xx] = 1;
        cout << i << ' ' << y << ' ' << xx << '\n';
    }
    else if(!ok[yy]){ // 否则如果y连接yy可以
        ok[y] = ok[yy] = 1;
        cout << i << ' ' << x << ' ' << yy << '\n';
    }
}

如果将这份代码加入求 K 的部分，测试自测样例 4，会得到如下结果。

6
0 9 10
1 5 6
2 10 11
3 6 1
5 4 5

是的，面对编号为 4 的弦出现的前文提到的矛盾情况，我们的考虑顺序无法处理，所以没有输出。

二、dfs 确定连接顺序

开头同理。

在接下来的处理中，首先进入一层 dfs(i)，如果 ok(a_i)=ok({a_i}')=0，可以将它们更新为 1，即连接，并进入下一层 dfs dfs(i+1)。
如果 i=n，输出答案，退出。

如果遇到刚才提到的“都被连接”的问题，再返回（改进部分）。

显然这个写法是正确的，但必然超时。

以下给出 dfs 部分的代码，如果补全可以得到 30 分，其余测试点会超时。

void dfs(int i){
    if(i == n){
        for(int i=1; i<=cnt; i++)
            cout << ans[i].id << ' ' << ans[i].s1 << ' ' << ans[i].s2 << '\n';
        exit(0);
    }
    if(a[i].sum == best)
        dfs(i + 1);

    int x = a[i].x, 
        y = a[i].y;

    int tx = match(x),
        ty = match(y);

    if(!ok[x] && !ok[tx]){
        ok[x] = ok[tx] = 1;
        ans[++cnt].id = i, 
        ans[cnt].s1 = y, ans[cnt].s2 = tx;
        // cout << ans[cnt].id << ' ' << ans[cnt].s1 << ' ' << ans[cnt].s2 << '\n';
        dfs(i + 1);
        ok[x] = ok[tx] = 0;
        --cnt;
    }
    if(!ok[y] && !ok[ty]){
        ok[y] = ok[ty] = 1;
        ans[++cnt].id = i, 
        ans[cnt].s1 = x, ans[cnt].s2 = ty;
        // cout << ans[cnt].id << ' ' << ans[cnt].s1 << ' ' << ans[cnt].s2 << '\n';
        dfs(i + 1);
        ok[y] = ok[ty] = 0;
        --cnt;
    }
    return;
}

三、“集体考虑”（正确顺序）

在尝试了两种错误顺序之后，我们终于迎来了正确的部分。

我们的第 1 种考虑顺序虽然无法 AC，但是可以得到 30 分并通过第 1\sim3 自测点，所以我们不妨来观察第 4 自测点的输出，并分析其考虑顺序。

6
3 6 1
4 1 2
2 2 3
0 3 4
5 4 5
1 5 6

看这个输出，我们可以发现规律：2\sim (K-1) 行中，第 i 行的第三个数等于第 i+1 行的第二个数。

注意：输出的各行顺序是可以调整的，所以我们发现的规律不一定是正确思路。
但这个规律也确实是一个可以尝试并且能够 AC 的代码（经尝试确认）。

AC 思路结论

详细解释这个顺序。

定义“集体”：如果若干条弦只需要相互交换端点位置，就可以让这些弦的 D=best，那么就认为这些弦时一个集体。
显然，总共 K 条 D\not=best 的弦，可以被划分为至少 1 个集体。

解释定义

我将使用自测样例解释“集体”。

自测样例 1,3,4 中，所有 K 根需要被挪动的弦在同一个集体。
自测样例 2 中，如果第 0 根弦不动，那第 1,4 根弦是同一个集体，第 2,3 根弦是同一个集体。此时出现了 2 个集体。

大致思路

从任意一根弦出发，如果这根弦的 D\not=best，就通过挪动，将这根弦以及它的集体全部符合 D=best，然后再去考虑其他集体的其他弦（如果只有 1 个集体，就完成了题目全部要求；如果有多个集体，就要考虑各个集体）。

具体步骤

1. 首先任意考虑一根弦（设其端点为 (a_1,a_2)），调整 a_1 这个端点，让这根弦的端点变成 (a_2,{a_2}')，成功。
2. 如果 {a_2}' 位置原来有一根弦（设其端点为 ({a_2}',a_3)），调整 {a_2}' 这个端点，让这根弦的端点变成 (a_3,{a_3}')，成功。
3. 重复第 2 步，让端点为 ({a_{i-1}}',a_i) 的弦变成 (a_i,{a_i}')，让所有弦都成功。
4. 反之，对应第 2 步，如果 {a_{i-1}}' 挪到的 {a_i}' 位置原来没有弦，就说明不需要再调整 {a_i}' 位置之前连接的弦了，这个循环模拟就暂时中断了，也就是说明这个集体都已经符合 D=best。所以退出当前循环，去寻找下一个集体，即回到第 1 步。

处理集体考虑完毕的情况

观察自测样例 2。

5
0 1
3 2
4 5
6 7
9 8

可以使用 pos(i) 记录第 i 个位置连接的弦的编号。