队内训练1 牛客多校第六场补题C 构造题(结论题)
题目链接link.
题意:给你一个n,有一个n的完全图。你可以删任意次,每次得删掉一个三角形。一条边只能删一次,删除任意次后需要保证,剩余的边数小于n。输出任意一种符合题意的方案。
这题是一个结论题,知道结论就过的很快。
结论就是删除的三角形的三个顶点编号x,y,z需要满足:
(
x
+
y
+
z
x+y+z%n=0
x+y+z) %
n
=
0
n = 0
n=0
题解就这么一句话,只能说震惊**。
有博弈那味儿了,结论题还是结论题,结论一个比一个简单。
证明我大概想了一个,吃过饭贴一下吧。要赶不上ddl了。
这么简单的代码我都能wa真是怪了
AC代码: 每天一个构造小技巧
#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
int ans1[2000010];
int ans2[2000010];
int ans3[2000010];
int sum=0;
map<pair<int,int>,int> oxy;
int main( )
{
int n;
scanf("%d",&n);
for(int i=1;i<=n/3;i++)
{
for(int j=i+1;j<=n;j++)
{
int k=n-i-j;
if(k>=j+1&&k<=n)
{
ans1[++sum]=i;
ans2[sum]=j;
ans3[sum]=k;
oxy[make_pair(i,j)]=1;
oxy[make_pair(i,k)]=1;
oxy[make_pair(j,k)]=1;
}
//else break;
}
}
//cout<<"哈哈哈哈哈哈哈哈哈哈哈哈哈sum="<<sum<<endl;
for(int i=1;i<=2*n/3;i++)
{
for(int j=i+1;j<=2*n;j++)
{
int k=2*n-i-j;
if(k>=j+1&&k<=n&&
oxy[make_pair(i,j)]+oxy[make_pair(j,k)]+oxy[make_pair(i,k)]==0)
{
ans1[++sum]=i;
ans2[sum]=j;
ans3[sum]=k;
}
//else break;
}
}
printf("%d\n",sum);
for(int i=1;i<=sum;i++)
{
printf("%d %d %d\n",ans1[i],ans2[i],ans3[i]);
}
return 0;
}