AtCoder Grand Contest 032-B - Balanced Neighbors （构造）-白红宇

AtCoder Grand Contest 032-B - Balanced Neighbors （构造）

阅读量：5082 次

发布时间：2019-06-13

本文共 2318 字，大约阅读时间需要 7 分钟。

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $700700$ points

Problem Statement

You are given an integer $NN$ . Build an undirected graph with $NN$ vertices with indices $11$ to $NN$ that satisfies the following two conditions:

The graph is simple and connected.

There exists an integer $SS$ such that, for every vertex, the sum of the indices of the vertices adjacent to that vertex is $SS$ .

It can be proved that at least one such graph exists under the constraints of this problem.

Constraints

All values in input are integers.

$3\leqN\leq1003\leqN\leq100$

Input

Input is given from Standard Input in the following format:

NN

Output

In the first line, print the number of edges, $MM$ , in the graph you made. In the $ii$ -th of the following $MM$ lines, print two integers ${aiai}_{iai}$ and ${bibi}_{ibi}$ , representing the endpoints of the $ii$ -th edge.

The output will be judged correct if the graph satisfies the conditions.

Sample Input 1 Copy

Copy

Sample Output 1 Copy

Copy

21 32 3

For every vertex, the sum of the indices of the vertices adjacent to that vertex is $33$ .

题意：

给你一个数字n，

让你构造你简单图（无重边）

要求这个图的每一个节点所连接的节点的id值加起来相等。*（不用加自己的id值）

思路：

显然找规律的构造题。

我们反过来想，先构建一个完全图，设法去掉一些有规律的边，使整个图满足条件。

通过分析可以发现规律。

当n是奇数的时候，

删除i+j=n的边

否则

删除i+j=n+1的边

细节见代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #define ALL(x) (x).begin(), (x).end()#define rt return#define dll(x) scanf("%I64d",&x)#define xll(x) printf("%I64d\n",x)#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
                  
                   #define pll pair
                   
                    #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define db(x) cout<<"== [ "<
                    
                     <<" ] =="<
                     
                      >n; std::vector
                      
                        v; int ans=0; repd(i,1,n) { repd(j,i+1,n) { if(n&1) { if(i+j!=n) { ans++; v.push_back(mp(i,j)); // cout<
                       <<" "<
                        
                         <
                         
                          = '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}