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

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

原题题解：https://ac.nowcoder.com/acm/contest/11257/C

题目大意

给定一个有$n(3\le n\le 2000)$个点的完全图,j节点编号从$1$到$n$，你可以多次删除图上的边，每次选择三个节点$x,y,z$,其中$(x,y)$$(x,z)$$(y,z)$并未被删除，然后删除这三条边。
求使得剩余边数小于$n$的删边方案。

解题思路

做题胆要大，什么结论都往上套
首先，证明当$x+y+z\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$且$x<y<z$时删边不会重复。
当$x+y+z=n$时$(x+1)+(y+1)+(z+1)=n+3$

一共有$?\frac{n?1}{2}?$个。
当$x+y+z=2n$时$(x+1)+(y+1)+(z+1)=2(n+3)$，而当$z=n+2$时，

共有$?\frac{n}{2}?+1$个。
得出递推式
$$\begin{array}{rl}f(n+3)& =f(n)+?\frac{n?1}{2}?+?\frac{n}{2}?+1\\ & =f(n)+\{\begin{array}{rcl}& \frac{n?1}{2}+\frac{n?1}{2}+1& (n\%2==1)\\ & \frac{n}{2}+\frac{n?2}{2}+1& (n\%2==0)\end{array}\\ & =f(n)+n\end{array}$$
之后枚举$x,y$,算出$z$,可AC。

拓展时间

本题范围不大，但如果达到$10^9$,暴力就肯定超时，以下是两种解法。

矩阵快速幂

我们老师说：大部分线性变换都可以用矩阵快速幂来做
首先写出矩阵$$?\begin{array}{c}f(n)\\ f(n?1)\\ f(n?2)\\ n?2\\ 1\end{array}?$$
写出等式
$$?\begin{array}{c}f(n+1)\\ f(n)\\ f(n?1)\\ n?1\\ 1\end{array}?=?\begin{array}{ccccccc}& 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{array}??\begin{array}{c}f(n)\\ f(n?1)\\ f(n?2)\\ n?2\\ 1\end{array}?$$
最后矩阵快速幂求得方案数。

数学

我们由上得知$$\begin{array}{rl}\frac{n(n?1)}{2}?2f(n)& <n\\ 3f(n)& >\frac{n(n?1)}{2}?n\\ f(n)& >\frac{n(n?3)}{6}\end{array}$$
当$n\mathrm{m}\mathrm{o}\mathrm{d}3=0$：
$$f(3)+3=f(6),f(6)+6=f(9),f(9)+9=f(12)\dots$$
可知为等差数列。
可得当$n\mathrm{m}\mathrm{o}\mathrm{d}3=0$：
$$f(n)=\frac{(n^2?3n+3)(n?1)}{6}+1$$
其它情况亦可推出。
写出通项式：
$$f(n)=\{\begin{array}{rcl}\frac{n^2?3n+3}{6}& >\frac{n(n?3)}{6}& (n\%3==0)\\ \frac{n^2?3n+3}{6}& >\frac{n(n?3)}{6}& (n\%3!=0)\end{array}$$

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,ans=0;cin>>n;if(n%3==0)ans=n*n-3*n+6;elseans=n*n-3*n+2;ans/=6;cout<<ans<<'\n';for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
    int k=(2*n-i-j)%n;if(j<k)cout<<i+1<<' '<<j+1<<' '<<k+1<<'\n';}}
}