AGC056A - Three Cells per Row and Column-程序员宅基地

技术标签: 算法  构造  

【题意】

给定一个n*n的矩阵,请构造出一种黑白染色方式,使得每行每列均恰好有3个黑色,且总共的黑色连通块数是n

【分析】

这是一个不是很好想的构造方式,首先考虑n是3的整数倍的情况

直接按照如下方式即可:

 当其不是3的倍数的时候,我们仍然模仿之前的方式,会得到如下的情况,但是这里存在连通块个数变多为n+2个的情况

考虑如何解决这个问题,可以通过交换一些行的方式使得连成黑色的连成一个

发现直接交换第一行和第\lfloor{\frac{n}{3}}\rfloor行就可以减少一个,交换第n-\lfloor{\frac{n}{3}}\rfloor+1行和最后一行又可以减少一个

这样就完成了构造

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector <string> res;
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d",&n);
    int pos=0;
    for(int i=0;i<n;i++)
    {
        string s=string(n,'.');
        pos=i*3;
        for(int j=0;j<3;j++)
            s[(pos+j)%n]='#';
        res.push_back(s);
    }
    // if(n%3) swap(res[1],res[n/3]);
    if(n%3) swap(res[0],res[n/3-1]),swap(res[n-n/3],res[n-1]);
    for(string s : res)
        cout<<s<<endl;
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/andyc_03/article/details/121886347

智能推荐

金融IT行业-程序员宅基地

文章浏览阅读737次。金融IT行业:-行业介绍: 1.金融IT行业:是中国信息化建设中最重要的一个行业,它包括了银行、证券和保险等全部企业IT应用。 2.金融IT人才:是指那些既具备IT专业背景,又有在金融领域工作经历的人士,他们要有IT和金融领域的互通经验。-职位介绍: 1.软件开发工程师 2.软件测试工程师 3.系统集成工程师 4.金融分析工程师 5.管理,销售,实施,客..._金融it行业是做什么的

Blender程序化建模简明教程【PCG】_blender怎么编程-程序员宅基地

文章浏览阅读2.7k次,点赞3次,收藏18次。了解如何定义和创建网格对于在 Blender 中编写几何脚本至关重要。顶点(由 X、Y 和 Z 定义的点)边(由顶点索引定义的线框曲线)面(由顶点索引定义的 3D 表面)在下面这个例子中,我们将定义一个简单的平面来演示顶点和面索引之间的关系。平面将由四个点组成。首先我们定义顶点和面变量……这些被定义为数组。import bpy我们现在需要为网格和场景对象定义变量……我们现在来定义网格的创建位置。我们可以设置要在光标位置创建的网格……现在我们可以创建网格了……import bpy。..._blender怎么编程

机器学习入门总结_自动化机器学习、强化学习、机器学习及服务、sr/语音识别领域的机器学习-程序员宅基地

文章浏览阅读1.3k次,点赞4次,收藏15次。目录机器学习入门概述总结前言:1、机器学习的定义2、机器学习的领域3、机器学习算法类型(1)监督学习(Supervised Learning)(2)无监督学习(Unsupervised Learning)(4)半监督学习(Semi-supervised Learning)(5)强化学习(Reinforcement Learning)(6)遗传算法(Genet..._自动化机器学习、强化学习、机器学习及服务、sr/语音识别领域的机器学习

iframe父页面vue、html与子页面html事件相互调用_vue iframe调用子页面方法-程序员宅基地

文章浏览阅读2.4k次,点赞2次,收藏4次。一. html页面中引入的iframe标签 <iframe id="menuframe" name="menuframe" src="modal.html" frameborder="no" style="width:100%;height:100%></;"iframe> 父html中调用子iframe html 中的事件通过contentwindow属性,其中..._vue iframe调用子页面方法

java 数据库 update 变量_Java 使用executeUpdate向数据库中创建表格-程序员宅基地

文章浏览阅读168次。Java 使用executeUpdate向数据库中创建表格一、创建mysql.ini文件,配置如下这样以后修改数据库的配置直接在mysql.ini文件中修改。二、编写代码initParam方法: 获得mysql.ini中的数据createTale方法: 连接数据库,并且executeUpdate执行sql语句。此例的sql文件为创建表语句。main方法: 传入Sql语句。注意事项:传入的Sql语句..._java中怎样用update语句在数据库表格里添加一行

动态渲染页面爬取(Python 网络爬虫) ---Selenium的使用-程序员宅基地

文章浏览阅读489次。Selenium 的使用Selenium 是一个自动化测试工具,利用它可以驱动浏览器执行特定的动作,如点击、下拉等操作,同时还可以获取浏览器当前呈现的页面的源代码,做到可见即可爬。对于一些JavaScript 动态渲染的页面来说,此种抓取方式非常有效。好处:不用再分析网站复杂的通信流程了坏处:效率低一般用在登录环节。1、准备工作安装Chrome浏览器配置..._anwang-apk.x101.cyou

随便推点

NYOJ448. 寻找最大数(贪心)_第1行:一个正整数t,表示测试次数 以下t行,每行输入:type n [beg,end) : n个数-程序员宅基地

文章浏览阅读306次。寻找最大数时间限制:1000 ms | 内存限制:65535 KB难度:2描述请在整数 n 中删除m个数字, 使得余下的数字按原次序组成的新数最大,比如当n=92081346718538,m=10时,则新的最大数是9888 输入第一行输入一个正整数T,表示有T组测试数据每组测试数据占一行,每行有两个数n,m(n可能是一个很_第1行:一个正整数t,表示测试次数 以下t行,每行输入:type n [beg,end) : n个数据(

【程序23】 题目:求1+2!+3!+...+20!的和 Note:数据类型需注意,对比区分_编程求 1!+2!+3!+……+20! 的值。(20分,程序错误一处扣2分,结果错误扣5分)注意:根-程序员宅基地

文章浏览阅读304次。Note: double有效位只有52位,剩余位数用于符号位和指数位,大概能精确表示16位十进制数,20的阶乘需要19位十进制数表示出来,double就无法精确表示了。 --摘自论坛中的解释(对应的数据类型不同,导致输出精度有些许误差,现整理如下,供参考讨论,欢迎大佬指正,必将虚心学习。)#include<stdio.h>int main(){ int i; long l..._编程求 1!+2!+3!+……+20! 的值。(20分,程序错误一处扣2分,结果错误扣5分)注意:根据题目,考虑所定义的各个变量应该为何种类型。

北京联通dns服务器位置,全国联通DNS服务器地址-程序员宅基地

文章浏览阅读6.4k次。《全国联通DNS服务器地址》由会员分享,可在线阅读,更多相关《全国联通DNS服务器地址(5页珍藏版)》请在人人文库网上搜索。1、全国联通服务器DNS首尾地址124.161.97.234124.161.97.234四川省 联通DNS服务器124.161.97.238124.161.97.238四川省 联通DNS服务器124.161.97.242124.161.97.242四川省 联通DNS服务器20..._北京联通dns

leetcode 735[medium]---Asteroid Collision_leetcode,正数在前面,负数在后面-程序员宅基地

文章浏览阅读201次。难度:mediumWe are given an array asteroids of integers representing asteroids in a row.For each asteroid, the absolute value represents its size, and the sign represents its direction (posit_leetcode,正数在前面,负数在后面

ORACLE 11G DG打补丁详细步骤-程序员宅基地

文章浏览阅读1.1k次。主库操作如下: 1下载并上传包 p17836989_112000_Linux-x86-64和p24732075_112040_Linux-x86-64 特别注意事项: ..._dg主库打补丁

C# - Lock 锁浅析_c# 锁函数-程序员宅基地

文章浏览阅读2.5k次。一. 为什么要lock,lock了什么?当我们使用线程的时候,效率最高的方式当然是异步,即各个线程同时运行,其间不相互依赖和等待。但当不同的线程都需要访问某个资源的时候,就需要同步机制了,也就是说当对同一个资源进行读写的时候,我们要使该资源在同一时刻只能被一个线程操作,以确保每个操作都是有效即时的,也即保证其操作的原子性。lock是C#中最常用的同步方式,格式为lock(objectA){codeB} 。lock(objectA){codeB} 看似简单,实际上有三个意思,这对于适当地使用它至关重要:_c# 锁函数

推荐文章

热门文章

相关标签