博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF976D. Degree Set
阅读量:6613 次
发布时间:2019-06-24

本文共 1085 字,大约阅读时间需要 3 分钟。

题目大意:

给你一个长度为 $n$ 的正整数序列 $d\_1, d\_2, ......, d\_n$ ( $d\_1 < d\_2 < ...... < d\_n$ )。要求你构造一个满足以下条件的无向图:

1. 有恰好 $d_n + 1$ 个点;

2. 没有自环;
3. 没有重边;
4. 总边数不超过 $10^6$ ;
5. 它的度数集合等于 $d$ 。

点从 $1$ 标号至 $d_n + 1$ 。

图的度数序列是一个长度与图的点数相同的数组 $a$ ,其中 $a_i$ 是第 $i$ 个顶点的度数(与其相邻的顶点数)。

图的度数集合是度数序列排序后去重的结果。

保证有解,要求输出符合条件的图。

思路:

对于对于前 $d[1]$ 个点向所有点连接一条边于是现在当前局面里有 $d[1]$ 个点为度数 $d[n]$ ,其余点度数为 $d[1]$ ,所以我们对于度数为 $d[n]$ 的 $d[1]$ 个点不再进行操作,对于度数为 $d[n]$ 的 $d[n]-d[n-1]$ 个点也不再操作。那么问题就转化成子问题,构造 $(d[2]-d[1],d[3]-d[1],......,d[n-1]-d[1])$ 的子问题。

以下代码:

#include
#define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=1e6+5;int n,tot,cnt,d[N];struct node{ int x,y;}t[N];il int read(){ int x,f=1;char ch; _(!)ch=='-'?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x;}il void ins(int x,int y){ t[++tot]=(node){x,y};}int main(){ n=read(); for(int i=1;i<=n;i++)d[i]=read(); int L=1,R=d[n]+1; for(int i=1,j=n;i<=(n>>1);i++,j--){ for(int k=1;k<=d[i];k++)for(int l=L;l
View Code

 

转载于:https://www.cnblogs.com/Jessie-/p/10527906.html

你可能感兴趣的文章
Java AES算法和UNIX下openssl之间的加解密
查看>>
我的友情链接
查看>>
基于vCenter/ESXi平台CentOS 6.8系统虚拟机Oracle 12c RAC双节点数据库集群搭建
查看>>
HashMap要点
查看>>
CentOS 7输入startx无法启动图形化界面
查看>>
#51CTO学院四周年# 终于在这里遇到你
查看>>
2018-4-10
查看>>
Linux配置raid1+0阵列磁盘
查看>>
百度首次公布云业务收入,同比增长超100%,跻身国内第三
查看>>
iOS之UI--CAShapeLayer
查看>>
Java学习笔记 1—命名规则、数据类型、运算符
查看>>
7个python案例中的数据思维
查看>>
蛋花花分析人工智能就业前景究竟如何
查看>>
FusionCharts入门教程,使用指南
查看>>
我的友情链接
查看>>
数组的一些方法
查看>>
关于MFC中WM_MOUSEHOVER和WM_MOUSELEAVE消息的使用
查看>>
我的友情链接
查看>>
linux下查看nginx,apache,mysql,php的编译参数[转]
查看>>
Android掌中游斗地主游戏源码完整版
查看>>