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

感谢来自上一篇题解的大佬 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$ 相等（这样它们就都平行了）。

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

求出所有 $D_i$ 。
统计这些 $D_i$ 的出现次数。
求出出现次数最多的 $D_i$ ，规定这个 $D_i$ 为“最好值”，用 $best$ 记录。如果出现多个 $D_i$ 出现次数相同且都是最多，那么任意选择 $1$ 个 $D_i$ 作为 $best$ 值。
把其它所有 $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 代码中）。

CPP

#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

个自测样例。

CPP

假设这组样例的

best=1

，那么这种顺序会导致考虑编号为

5

的弦（1 11）时出现

ok(1)=ok(0)=1,ok(11)=ok(2)=1

的情况，即都已经被连过了，无法继续考虑。

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

K

部分）。

CPP

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

，会得到如下结果。

CPP

是的，面对编号为

4

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

二、dfs 确定连接顺序

开头同理。

在接下来的处理中，首先进入一层 dfs(i)，如果

ok(a_i)=ok({a_i}')=0

，可以将它们更新为

1

，即连接，并进入下一层 dfs dfs(i+1)。
如果

i=n

，输出答案，退出。

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

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

以下给出 dfs 部分的代码，如果补全可以得到

30

分，其余测试点会超时。

CPP

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

自测点的输出，并分析其考虑顺序。

CPP

看这个输出，我们可以发现规律： $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

个集体，就完成了题目全部要求；如果有多个集体，就要考虑各个集体）。

具体步骤

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

处理集体考虑完毕的情况

观察自测样例

2

。

CPP

可以使用

pos(i)

记录第

i

个位置连接的弦的编号。

pos(i)=-1

表示这个位置不连接任何弦。

按照思路

best=1\ or\ 3\ or\ 5\ or\ 7\ or\ 9

。不妨设

best=7

。
如果按照刚才提到的顺序，模拟其过程。

a_1 = 0, a_2 = 1\\ \therefore pos(a_1) = -1

{a_2}' = 6, a_3 = 7\\ \therefore pos({a_2}') = pos(a_2)\\

{a_3}' = 0, a_4 = 1\\ \therefore pos({a_3}') = -1

最后得到：

pos({a_3}')=-1

说明

{a_3}'

现在不连接任何弦，无需继续考虑。
也说明这个集体已经全部符合 $D=best$ ，退出循环，去考虑下一个集体。对于本测试点，所有集合都考虑完毕。

现在，我们只需要将刚才这个循环模拟、判断集体是否考虑完毕的过程编写成代码就可以了。

代码

CPP

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

int n, maxi, k, best, a[N][2], d[N];
map <int, int> t, pos;
map <int, bool> ok;

int match(int x){ // 已知x, 求x' 
	return (best + n*2 - x) % (n*2);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        int x, y; cin >> x >> y;
        a[i][0] = x, a[i][1] = y;
        pos[x] = pos[y] = i; // 所在绳子的编号 
        
        d[i] = (x + y) % (n*2); 
        if(d[i] % 2) 
            t[d[i]]++,
            maxi = max(maxi, t[d[i]]);
    }
    
    for(int i=0; i<n; i++){
    	if(t[d[i]] == maxi) 
			best = d[i];
    }
	if(best % 2 == 0) best = 1;

    for(int i=0; i<n; i++)
        if(d[i] != best) k++;
        else ok[i] = 1;
    cout << k << '\n';

    // 这部分很复杂, 很重要
    for(int i=0; i<n; i++){
    	if(!ok[i]){ // 如果第i根绳子及其集体没有被考虑. 
    		 int s = i, o = 0;
    		 // 接下来一直考虑第s根绳子. 
    		 while(1){ // 集体考虑完毕时退出.
    		 	int u = a[s][o];
    		 	int v = match(u);
    		 	int s2 = pos[v]; // v原来在s2绳子上
    		 	// 第s1根绳子的非u端连到v上去.
    		 	cout << s << ' ' << a[s][o^1] << ' ' << v << '\n';
    		 	ok[s] = 1; // u所在的s绳子ok了. 
    		 	
    		 	pos[v] = s; // v点现在和u都在s上, u <-> v.
    		 	pos[a[s][o^1]] = -1; // u所在的s绳子的原端点o^1现在没有绳子.
    		 	
    		 	// v点原来没有任何绳子, 当前集体考虑完毕, 结束.
    		 	if(s2 == -1) break; 
    		 	
    		 	s = s2; // v原来在s2绳子上, 现在去继续考虑s2.
    		 	if(a[s2][0] == v) o = 1;
    		 	if(a[s2][1] == v) o = 0; // else.
			 }
		}
    }
    return 0;
}

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

文章操作

弦的平行

规律

表示方法

规律应用

细节：特殊判断

求 $K$ 的值

求 $K$ 的 $50$ 分代码

模拟：挪弦与挪弦顺序

一、先看 $a$ 再看 $b$

二、dfs 确定连接顺序

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

AC 思路结论

解释定义

大致思路

具体步骤

处理集体考虑完毕的情况

代码

相关推荐

评论

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

文章操作

弦的平行

规律

表示方法

规律应用

细节：特殊判断

求 KKK 的值

求 KKK 的 505050 分代码

模拟：挪弦与挪弦顺序

一、先看 aaa 再看 bbb

二、dfs 确定连接顺序

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

AC 思路结论

解释定义

大致思路

具体步骤

处理集体考虑完毕的情况

代码

相关推荐

评论

求 $K$ 的值

求 $K$ 的 $50$ 分代码

一、先看 $a$ 再看 $b$