Codeforces Round #575 (Div. 3) E. Connected Component on a Chessboard
2024-10-02 01:39:49
题意：
给你一个黑白相间的1e9*1e9的棋盘，你需要从里面找出来由b个黑色的格子和w个白色的格子组成的连通器(就是你找出来的b+w个格子要连接在一起，不需要成环)。问你可不可以找出来，如果可以就先打印YES，再打印出所有格子的坐标，否则打印出NO。
题解：
如果b和w相等的时候，那么就可以用棋盘的一行来表示。
对于不相等的情况：
如果max(w,b)>min(w,b)*3+1那么这样是找出不来符合条件的连通区域的。
看图中的红色部分你会知道只有这样十十的连接起来才是最大构成情况(这样写代码其实并不麻烦，你不需要一个十一个十的来拼接，可以看一下代码)
就这个十十的拼接可以就是一个十一个十的先拼接，之后多余出来的颜色格子，就用bfs添加到十的周围，但是代码确实太麻烦了
代码：
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 #include<algorithm>
5 #include<map>
6 #include<math.h>
7 using namespace std;
8 typedef long long ll;
9 const int maxn=1e5+5;
10 const int mod=26;
11 const int INF=0x3f3f3f3f;
12 const int block=300;
13 int cnt1=0,cnt2=0;
14 int main()
15 {
16 int t;
17 scanf("%d",&t);
18 while(t--)
19 {
20 int w,b;
21 scanf("%d%d",&b,&w);//b黑色 w白色
22 if(max(w,b)>min(w,b)*3+1)
23 {
24 printf("NO\n");
25 continue;
26 }
27 if(w==b)
28 {
29 printf("YES\n");
30 for(int i=3; i<=w+b+2; ++i)
31 printf("5 %d\n",i);
32 }
33 else if(b<w)
34 {
35 printf("YES\n");
36 w=w-b-1;//将在一行的减掉
37 for(int i=4; i<=b*2+4; i++)
38 {
39 printf("4 %d\n",i);
40 if(w>0 && i&1)
41 {
42 printf("3 %d\n",i);
43 w--;
44 }
45 if(w>0 && i&1 )
46 {
47 printf("5 %d\n",i);
48 w--;
49 }
50 }
51 }
52 else if(b>w)
53 {
54 swap(b,w);
55 printf("YES\n");
56 w=w-b-1;//将在一行的减掉,再对这一行的某些部分添加格子变成十
57 for(int i=4; i<=b*2+4; i++)
58 {
59 printf("3 %d\n",i);
60 if(w>0 && i&1)
61 {
62 printf("2 %d\n",i);
63 w--;
64 }
65 if(w>0 && i&1 )
66 {
67 printf("4 %d\n",i);
68 w--;
69 }
70 }
71 }
72 }
73 return 0;
74 }
最新文章
- 【mysql】mysql 常用建表语句
- javascript 核心语言笔记 4 - 表达式和运算符
- wordpress视频教程
- 转：如何调试PHP的Core之获取基本信息
- 《IO 系统性能》笔记
- HTML 学习笔记 CSS样式（边框）
- NGUI Sprite Type（Simple、Sliced、Tiled、Filed、Advanced）
- Nginx架构的企业级应用
- 94. Binary Tree Inorder Traversal
- Java模块化概念解惑与现状总结
- oracle tkprof 工具详解
- hdu 3926 Hand in Hand
- 【JAVASCRIPT】React学习-JSX 语法
- Angular JS 基础应用--第一篇
- springmvc配置文件配置的事务作用范围
- MVC思想概述
- 苹果ios系统无法通过RD Client连接win10服务器远程错误0x00001307
- js 如何判断数组元素是否存在重复项
- ext.net 实现gridpanel checkbox锁定
- win10虚拟桌面使用方法-提高工作效率