【2019.7.24 NOIP模拟赛 T1】道路建设（road）（水题）

原题与此题

原题是一道神仙不可做题，两者区别在于，原题不能有重边和自环。

然而，这题可以有重边。。。

于是这题就变成了一道大水题。

此题的解法

考虑如何构造。

对于\(n\le10^4\)的情况：

对于\(n>10^4\)的情况：

边上的权值表示边数。

代码

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

using namespace std;

int n;

int main()

{

	freopen("road.in","r",stdin),freopen("road.out","w",stdout);

	RI i;if(scanf("%d",&n),n<=10000)//对于n<=10000的情况

	{

		for(printf("2 %d\n",n),i=1;i<=n;++i) puts("1 2");//暴力建边

		return 0;

	}

	printf("4 %d\n",10001+n/10000+n%10000);//对于n>10000的情况

	for(i=1;i<=10000;++i) puts("1 2");puts("1 3");//分两组建边

	for(i=1;i<=n/10000;++i) puts("2 4");for(i=1;i<=n%10000;++i) puts("3 4");

	return 0;

}

巴特西

【2019.7.24 NOIP模拟赛 T1】道路建设（road）（水题）

原题与此题

此题的解法

代码

最新文章

热门文章