2021牛客暑期多校训练营6 C题: Delete Edges

C题: Delete Edges

原题链接:https://ac.nowcoder.com/acm/contest/11257/C

题目大意

有一张 n ( n ≤ 2000 ) n(n\le 2000) n(n≤2000) 个点的完全图,你可以进行如下操作:

  1. 每次选取 3 3 3 个不同的点 x , y , z x,y,z x,y,z 构成的环( 3 3 3 边原本存在);
  2. 删除这个环中的边 ( x , y ) ( x , z ) ( y , z ) (x,y)(x,z)(y,z) (x,y)(x,z)(y,z) ;

求一种操作方案,使得若干次操作结束后剩余边数少于 n n n 。

题解

大胆假设,大胆猜测

一张 n n n 个点的完全图有 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)​ 条边,若我们已有一种贪心方案,其对于 n n n 个点的完全图的操作次数为 f ( n ) f(n) f(n) 则其应满足:
n ( n − 1 ) 2 ( 总 边 数 ) − 3 f ( n ) ( 删 去 总 边 数 ) < n ( 目 的 剩 余 边 数 ) − 3 f ( n ) < 2 n − n ( n − 1 ) 2 f ( n ) > n 2 − 3 n 6 \begin{aligned} \frac{n(n-1)}{2}(总边数)-3f(n)(删去总边数)&<n(目的剩余边数)\\ -3f(n)&<\frac{2n-n(n-1)}{2}\\ f(n)&>\frac{n^2-3n}{6} \end{aligned} 2n(n−1)​(总边数)−3f(n)(删去总边数)−3f(n)f(n)​<n(目的剩余边数)<22n−n(n−1)​>6n2−3n​​

然后我们猜测结论并证明(怎么才能在比赛时猜出来?真巧,我也不知道)。
我们假设我们 f ( n ) f(n) f(n) 每次所选的 x , y , z x,y,z x,y,z 满足 x < y < z x<y<z x<y<z , x + y + z ≡ 0   (   m o d     n ) x+y+z\equiv 0\ (\bmod\ n) x+y+z≡0 (mod n) 然后我们构造其递推式。
显然, f ( n ) f(n) f(n) 中的每一种方案都对应了 f ( n + 3 ) f(n+3) f(n+3) 中的一种方案,因为 x + y + z = n x+y+z=n x+y+z=n 可以映射到 ( x + 1 ) + ( y + 1 ) + ( z + 1 ) ≡ 0   (   m o d     n + 3 ) (x+1)+(y+1)+(z+1)\equiv 0\ (\bmod\ n+3) (x+1)+(y+1)+(z+1)≡0 (mod n+3) , x + y + z = 2 n x+y+z=2n x+y+z=2n 可以映射到 ( x + 2 ) + ( y + 2 ) + ( z + 2 ) ≡ 0   (   m o d     n + 3 ) (x+2)+(y+2)+(z+2)\equiv 0\ (\bmod\ n+3) (x+2)+(y+2)+(z+2)≡0 (mod n+3) ,且原 f ( n ) f(n) f(n) 中不存在 x + y + z = 3 n x+y+z=3n x+y+z=3n (即 x = y = z = n x=y=z=n x=y=z=n ,不合法)。
但是注意,此时的 ( x + 1 ) > 1 , ( z + 2 ) < n + 3 (x+1)>1,(z+2)<n+3 (x+1)>1,(z+2)<n+3,即 f ( n + 3 ) f(n+3) f(n+3) 中最小数字( x x x)为 1 1 1 和最大数字( z z z)为 n + 3 n+3 n+3 的情况我们是没有考虑的,我们枚举这些情况:

下表为 x x x 为1时,部分满足条件的 y , z y,z y,z 的对应值(条件: x + y + z = n + 3 x+y+z=n+3 x+y+z=n+3 ):

x 1 1 1 1 1
y 2 3 4 ⌊ n + 2 2 ⌋ \lfloor\frac{n+2}{2}\rfloor ⌊2n+2​⌋(奇 n n n) n 2 \frac{n}{2} 2n​(偶 n n n)
z n n-1 n-2 ⌈ n + 2 2 ⌉ \lceil\frac{n+2}{2}\rceil ⌈2n+2​⌉(奇 n n n) n + 4 2 \frac{n+4}{2} 2n+4​(偶 n n n)

若不考虑 n n n 的奇偶性,共 ⌊ n − 1 2 ⌋ \lfloor\frac{n-1}{2}\rfloor ⌊2n−1​⌋ 组
(注意上表中极限值,若继续枚举则 y > = z y>=z y>=z 不符合定义)

下表为 z z z 为 n + 3 n+3 n+3 时,部分满足条件的 x , y x,y x,y 的对应值(条件: x + y + z = 2 ( n + 3 ) x+y+z=2(n+3) x+y+z=2(n+3) )

z n+3 n+3 n+3 n+3 n+3
x 1 2 3 n + 1 2 \frac{n+1}{2} 2n+1​(奇 n n n) ⌊ n + 3 2 ⌋ \lfloor\frac{n+3}{2}\rfloor ⌊2n+3​⌋(偶 n n n)
y n+2 n+1 n n + 5 2 \frac{n+5}{2} 2n+5​(奇 n n n) ⌈ n + 3 2 ⌉ \lceil\frac{n+3}{2}\rceil ⌈2n+3​⌉(偶 n n n)

若不考虑 n n n 的奇偶性,共 ⌊ n 2 ⌋ + 1 \lfloor\frac{n}{2}\rfloor+1 ⌊2n​⌋+1 组
(注意上表中极限值,若继续枚举则 x > = y x>=y x>=y 不符合定义)

综上所述, f ( n ) f(n) f(n) 转移式如下:
f ( n + 3 ) = f ( n ) + ⌊ n − 1 2 ⌋ + ⌊ n 2 ⌋ + 1 f ( n + 3 ) = f ( n ) + n + { n − 1 2 + n − 1 2 + 1 ( 奇 n ) n − 2 2 + n 2 + 1 ( 偶 n ) f ( n + 3 ) = f ( n ) + n ( 合 并 ) \begin{aligned} f(n+3)&=f(n)+\lfloor\frac{n-1}{2}\rfloor+\lfloor\frac{n}{2}\rfloor+1\\ f(n+3)&=f(n)+n+\left\{ \begin{array}{rcl} \frac{n-1}{2}+\frac{n-1}{2}+1(奇n)&\\ \\ \frac{n-2}{2}+\frac{n}{2}+1(偶n)&\\ \end{array} \right.\\ f(n+3)&=f(n)+n(合并) \end{aligned} f(n+3)f(n+3)f(n+3)​=f(n)+⌊2n−1​⌋+⌊2n​⌋+1=f(n)+n+⎩⎨⎧​2n−1​+2n−1​+1(奇n)2n−2​+2n​+1(偶n)​​=f(n)+n(合并)​

因为转移式不方便直接使用,我们有以下两种思路:

  1. 采用矩阵快速幂对线代进行加速
  2. 转化为通项式

在文末简单介绍了矩阵快速幂的方式,如有需要可参考

因为题目数据范围 n ≤ 2000 n\le 2000 n≤2000 ,矩阵快速幂效果并不显著,没有必要,在此讲述通项式转化法:

若 n n n 为 3 3 3 的倍数,观察:
f ( 3 ) = 1 ⟶ + 3 f ( 6 ) = 4 ⟶ + 6 f ( 9 ) = 10 ⟶ + 9 f ( 12 ) = 19 ⟶ + 12 . . . f(3)=1\stackrel{+3}{\longrightarrow}f(6)=4\stackrel{+6}{\longrightarrow}f(9)=10\stackrel{+9}{\longrightarrow}f(12)=19\stackrel{+12}{\longrightarrow}... f(3)=1⟶+3​f(6)=4⟶+6​f(9)=10⟶+9​f(12)=19⟶+12​...

易发现 f ( n ) f(n) f(n) 为 f ( 3 ) = 1 f(3)=1 f(3)=1 加上等差数列 3 , 6 , 9 , . . . , n − 3 3,6,9,...,{n-3} 3,6,9,...,n−3 ,通项式如下:
f ( n ) = 1 + n − 3 3 n 2 = n 2 − 3 n + 6 6 f(n)=1+\frac{\frac{n-3}{3}n}{2}=\frac{n^2-3n+6}{6} f(n)=1+23n−3​n​=6n2−3n+6​

若 n % 3 = 1 n\%3=1 n%3=1 ,观察:
f ( 4 ) = 1 ⟶ + 4 f ( 7 ) = 5 ⟶ + 7 f ( 10 ) = 12 ⟶ + 10 f ( 13 ) = 22 ⟶ + 13 . . . f(4)=1\stackrel{+4}{\longrightarrow}f(7)=5\stackrel{+7}{\longrightarrow}f(10)=12\stackrel{+10}{\longrightarrow}f(13)=22\stackrel{+13}{\longrightarrow}... f(4)=1⟶+4​f(7)=5⟶+7​f(10)=12⟶+10​f(13)=22⟶+13​...

易发现 f ( n ) f(n) f(n) 为 f ( 4 ) = 1 f(4)=1 f(4)=1 加上等差数列 4 , 7 , 10 , . . . , n − 3 4,7,10,...,n-3 4,7,10,...,n−3 ,通项式如下:
f ( n ) = 1 + n − 4 3 ( n + 1 ) 2 = n 2 − 3 n + 2 6 f(n)=1+\frac{\frac{n-4}{3}(n+1)}{2}=\frac{n^2-3n+2}{6} f(n)=1+23n−4​(n+1)​=6n2−3n+2​

若 n % 3 = 2 n\%3=2 n%3=2 ,观察:
f ( 5 ) = 2 ⟶ + 5 f ( 8 ) = 7 ⟶ + 8 f ( 11 ) = 15 ⟶ + 11 f ( 14 ) = 26 ⟶ + 14 . . . f(5)=2\stackrel{+5}{\longrightarrow}f(8)=7\stackrel{+8}{\longrightarrow}f(11)=15\stackrel{+11}{\longrightarrow}f(14)=26\stackrel{+14}{\longrightarrow}... f(5)=2⟶+5​f(8)=7⟶+8​f(11)=15⟶+11​f(14)=26⟶+14​...

易发现 f ( n ) f(n) f(n) 为 f ( 5 ) = 2 f(5)=2 f(5)=2 加上等差数列 5 , 8 , 11 , . . . , n − 3 5,8,11,...,n-3 5,8,11,...,n−3 ,通项式如下:
f ( n ) = 2 + n − 5 3 ( n + 2 ) 2 = n 2 − 3 n + 2 6 f(n)=2+\frac{\frac{n-5}{3}(n+2)}{2}=\frac{n^2-3n+2}{6} f(n)=2+23n−5​(n+2)​=6n2−3n+2​

合并后如下:
f ( n ) = { n 2 − 3 n + 6 6 ( n % 3 = 0 ) n 2 − 3 n + 2 6 ( b % 3 = 1 ) n 2 − 3 n + 2 6 ( b % 3 = 2 ) = { n 2 − 3 n + 6 6 > n 2 − 3 n 6 ( n % 3 = 0 ) n 2 − 3 n + 2 6 > n 2 − 3 n 6 ( n % 3 ! = 0 ) \begin{aligned} f(n)&=\left\{ \begin{array}{rcl} \frac{n^2-3n+6}{6}(n\%3=0)\\ \\ \frac{n^2-3n+2}{6}(b\%3=1)\\ \\ \frac{n^2-3n+2}{6}(b\%3=2) \end{array} \right.\\ &=\left\{ \begin{array}{rcl} \frac{n^2-3n+6}{6}>\frac{n^2-3n}{6}(n\%3=0)\\ \\ \frac{n^2-3n+2}{6}>\frac{n^2-3n}{6}(n\%3!=0)\\ \end{array} \right. \end{aligned} f(n)​=⎩⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎧​6n2−3n+6​(n%3=0)6n2−3n+2​(b%3=1)6n2−3n+2​(b%3=2)​=⎩⎨⎧​6n2−3n+6​>6n2−3n​(n%3=0)6n2−3n+2​>6n2−3n​(n%3!=0)​​

显然,该方案满足第一部分推算出的要求,合理。
输出方案时,枚举 x , y x,y x,y ,然后计算输出对应的 z z z 即可。

参考代码

#include<bits/stdc++.h>
#define For(i,n,m) for(int i=n;i<=m;i++)
using namespace std;

int n;

int main()
{
	std::ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	if(n==3){
		puts("1");
		puts("1 2 3");
	}
	else{
		printf("%d\n",n%3?(n*n-3*n+2)/6:(n*n-3*n+6)/6)//方案总操作数
		int k;
		For(i,1,n){
			For(j,i+1,n){
				k=(2*n-i-j-1)%n+1;//和为n或2n(3n需i=j=k=n,不合法),最大2n,减法计算后取模即可。注意先-1再+1,使得1<=k<=n
				if(k>j)printf("%d %d %d\n",i,j,k);//若k<j为非法方案则不输出
			}
		}
	}
	return 0;
}

附:矩阵快速幂计算方案操作数

我们首先设原矩阵为 [ f ( n ) f ( n − 1 ) f ( n − 2 ) ] \begin{bmatrix}f(n)\\f(n-1)\\f(n-2)\end{bmatrix} ⎣⎡​f(n)f(n−1)f(n−2)​⎦⎤​ ,目标矩阵为 [ f ( n + 1 ) f ( n ) f ( n − 1 ) ] \begin{bmatrix}f(n+1)\\f(n)\\f(n-1)\end{bmatrix} ⎣⎡​f(n+1)f(n)f(n−1)​⎦⎤​ 初步操作式为:
[ f ( n + 1 ) f ( n ) f ( n − 1 ) ] = [ ?   ?   ? ?   ?   ? ?   ?   ? ] [ f ( n ) f ( n − 1 ) f ( n − 2 ) ] \begin{bmatrix}f(n+1)\\f(n)\\f(n-1)\end{bmatrix}=\begin{bmatrix}?\ ?\ ?\\?\ ?\ ?\\?\ ?\ ?\end{bmatrix}\begin{bmatrix}f(n)\\f(n-1)\\f(n-2)\end{bmatrix} ⎣⎡​f(n+1)f(n)f(n−1)​⎦⎤​=⎣⎡​? ? ?? ? ?? ? ?​⎦⎤​⎣⎡​f(n)f(n−1)f(n−2)​⎦⎤​

倒推出 ? ? ? 部分,发现计算 f ( n + 1 ) = f ( n − 2 ) + n − 2 f(n+1)=f(n-2)+n-2 f(n+1)=f(n−2)+n−2 需要常数 n − 2 n-2 n−2 ,添加一项:
[ f ( n + 1 ) f ( n ) f ( n − 1 ) n − 1 ] = [ 0   0   1   1 1   0   0   0 0   1   0   0 ?   ?   ?   ? ] [ f ( n ) f ( n − 1 ) f ( n − 2 ) n − 2 ] \begin{bmatrix}f(n+1)\\f(n)\\f(n-1)\\n-1\end{bmatrix}=\begin{bmatrix}0\ 0\ 1\ 1\\1\ 0\ 0\ 0\\0\ 1\ 0\ 0\\ ?\ ?\ ?\ ?\end{bmatrix}\begin{bmatrix}f(n)\\f(n-1)\\f(n-2)\\n-2\end{bmatrix} ⎣⎢⎢⎡​f(n+1)f(n)f(n−1)n−1​⎦⎥⎥⎤​=⎣⎢⎢⎡​0 0 1 11 0 0 00 1 0 0? ? ? ?​⎦⎥⎥⎤​⎣⎢⎢⎡​f(n)f(n−1)f(n−2)n−2​⎦⎥⎥⎤​

发现此时需更新 n − 2 n-2 n−2 为 n − 1 ( n − 2 + 1 ) n-1(n-2+1) n−1(n−2+1) ,再添加一个常数项 1 1 1 ,得最终转移式:
[ f ( n + 1 ) f ( n ) f ( n − 1 ) n − 1 1 ] = [ 0   0   1   1   0 1   0   0   0   0 0   1   0   0   0 0   0   0   1   1 0   0   0   0   1 ] [ f ( n ) f ( n − 1 ) f ( n − 2 ) n − 2 1 ] \begin{bmatrix}f(n+1)\\f(n)\\f(n-1)\\n-1\\1\end{bmatrix}=\begin{bmatrix}0\ 0\ 1\ 1\ 0\\1\ 0\ 0\ 0\ 0\\0\ 1\ 0\ 0\ 0\\ 0\ 0\ 0\ 1\ 1\\0\ 0\ 0\ 0\ 1\end{bmatrix}\begin{bmatrix}f(n)\\f(n-1)\\f(n-2)\\n-2\\1\end{bmatrix} ⎣⎢⎢⎢⎢⎡​f(n+1)f(n)f(n−1)n−11​⎦⎥⎥⎥⎥⎤​=⎣⎢⎢⎢⎢⎡​0 0 1 1 01 0 0 0 00 1 0 0 00 0 0 1 10 0 0 0 1​⎦⎥⎥⎥⎥⎤​⎣⎢⎢⎢⎢⎡​f(n)f(n−1)f(n−2)n−21​⎦⎥⎥⎥⎥⎤​

上一篇:递归_青蛙跳台阶(进阶版)


下一篇:数学表达式3