C题: Delete Edges
原题链接:https://ac.nowcoder.com/acm/contest/11257/C
题目大意
有一张 n ( n ≤ 2000 ) n(n\le 2000) n(n≤2000) 个点的完全图，你可以进行如下操作:
- 每次选取 3 3 3 个不同的点 x , y , z x,y,z x,y,z 构成的环( 3 3 3 边原本存在);
- 删除这个环中的边 ( 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(合并)
因为转移式不方便直接使用，我们有以下两种思路:
- 采用矩阵快速幂对线代进行加速
- 转化为通项式
在文末简单介绍了矩阵快速幂的方式，如有需要可参考
因为题目数据范围 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⟶+3f(6)=4⟶+6f(9)=10⟶+9f(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−3n=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⟶+4f(7)=5⟶+7f(10)=12⟶+10f(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⟶+5f(8)=7⟶+8f(11)=15⟶+11f(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⎦⎥⎥⎥⎥⎤