博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CodeForces1208C
阅读量:5290 次
发布时间:2019-06-14

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

CodeForces1208C

常见的构造题,这题的要求就给我一种疯狂暗示你按位构造的感觉,所以我一开始就疯狂尝试按位构造,但是...这时,\(dalao\)画了一张这样的图给我:

\[\begin{array}{llll}{0} & {0} & {1} & {1} \\ {0} & {0} & {1} & {1} \\ {2} & {2} & {3} & {3} \\ {2} & {2} & {3} & {3}\end{array}\]

然后你发现你就把它分\(4\)份考虑就行了.

上面那个图的来源是这个亚子的:

你考虑使得每一行每一列的数字异或起来都为\(0\),就可以自然的构造出这样一组答案.

\(dalao\)鄙视之后,我就羞愧得不能自己.按位考虑个\(JB\)啊,这样构造就完了.

但是题目要求每个数字出现且仅出现一次啊,这怎么办啊?

其实也不难,你考虑,如果我们按照这种\(0,1,2,3\)的顺序填充,那么最后填成这个亚子,一定是合法的,那么我们接下来要考虑怎么把这些多出来的数字变成不重复的题目要求的数字.

考虑异或的性质: \(a \: xor b = ( a + c ) \: xor ( b + c )\)

所以我们每次填充的时候把\(0,1,2,3\)改成对应的数字加\(4\)的倍数就行了.

因为给定的\(n\)一定是\(4\)的倍数,所以这样做一定可以.

为什么一定要是\(4\)的倍数呢?

因为这样我们才能构造出像上面那样的基本图,使得每个数字在每一行每一列都出现了偶数次.

\(Code:\)

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)#define per(i,a,b) for (int i = a ; i >= b ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
#define int long long#define pb push_back using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;} const int N = 1e3 + 100 ; int n , e[N][N] , tot ; signed main (int argc , char * argv[] ) { n = rint () ; tot = 0 ; rep ( i , 1 , n / 2 ) rep ( j , 1 , n / 2 ) { e[i][j] = ( tot << 2 ) ; e[i+n/2][j] = 1 + ( tot << 2 ) ; e[i][j+n/2] = 2 + ( tot << 2 ) ; e[i+n/2][j+n/2] = 3 + ( tot << 2 ) ; ++ tot ; } rep ( i , 1 , n ) { rep ( j , 1 , n ) printf ("%I64d " , e[i][j] ) ; putchar(10) ; } return 0 ;}

转载于:https://www.cnblogs.com/Equinox-Flower/p/11447260.html

你可能感兴趣的文章
SQL:获取语句执行时间2
查看>>
html学习第一天笔记——第六章节
查看>>
2018.10.25 atcoder Leftmost Ball(计数dp+组合数学)
查看>>
使用uiautomator 截图
查看>>
前端:background 设置
查看>>
Spring MVC的异常统一处理方法
查看>>
近日梦回
查看>>
表单验证 Validator v1.05
查看>>
马利筋
查看>>
js基础——幕布
查看>>
多项式求逆
查看>>
dubbo的服务发现和注册如何实现
查看>>
docker 不同版本 添加--insecure-registry
查看>>
并发编程中的Callable,Future,FitureTask
查看>>
Java反射机制
查看>>
Oracle EBS AP更新供应商地址
查看>>
Perl语言入门笔记 第十章 其他控制结构(unless,until,elsif,for,last,next,redo,and,or)
查看>>
phpunit.xml
查看>>
php实现工厂模式
查看>>
ubuntu 安装maven提示出错 The program &#39;mvn&#39; can be found in the following packages
查看>>