【51nod1804】小C的多边形

  • 本文为博主原创，未经许可不得转载

首先我们发现所以三角形的边权之和是$\frac{3n(n+1)}{2}$

那么每个三角形的边权之和就是$\frac{3(n+1)}{2}$

显然，n必须是奇数时才有解

我们采用这样的方法构造：先给内部的边钦定权值

每隔一条边权值相差1

然后根据总权值计算外边的边权

人生第一道自己yy出来的构造题，好开心啊

吐槽一下：为什么cout比printf快

我用printf居然超时了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000100
using namespace std;
int cnt,a[MAXN],b[MAXN];
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	int n; scanf("%d\n",&n); n--;
	if(n%2==0)  {puts("0");  return 0;}
	for(int i=1;i<=n;i+=2) b[i]=++cnt;
	for(int i=2;i<=n;i+=2) b[i]=++cnt;
	b[n+1]=b[1]; int sum=(n+1)*3/2;
	for(int i=1;i<=n;++i) a[i]=sum-b[i]-b[i+1];
	for(int i=1;i<=n;++i) cout<<a[i]<<' '; cout<<endl;
	for(int i=1;i<=n;++i) cout<<b[i]<<' '; cout<<endl;
	return 0;
}

本文标题:【51nod1804】小C的多边形

文章作者:chty

发布时间:2017年05月26日 - 20时59分

最后更新:2018年03月02日 - 17时28分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,