Codeforces 1628C Grid Xor 拼图构型思想
终于坐在div.1的赛场了.最让我难以置信的是,A我一眼没看出可以预处理后缀mex,B我也一眼没看出只需要两个字符串的性质,反而是C被我看了一眼就秒杀了.
题意
一个 n × n n\times n n×n的方阵每个位置有一个数, n n n是偶数.但是我们现在只知道和每个位置相邻的四个位置上的数的异或值,求整个方阵里所有数的异或.
题解
首先我们画图,发现如果选择一个位置,相当于点亮它四周的灯,那我们的目的就是把整个方阵全部点亮,并且每个位置只点一次.那么当我们选择相邻的两个位置的时候,所点亮的位置刚好是不重复的,我们把选择相邻的两个方格所点亮的格子称为一块拼图.那么只要用这样的拼图把整张图完全覆盖就可以了.点亮的过程刚好可以贪心,只要一个位置能和下面的方格或者右边的方格形成一块没有使用过的拼图,我们就直接贪心去拼就可以了.轻松一次通过.
#include<bits/stdc .h> //Ithea Myse Valgulious
const int yuzu=3e5,aoi=1018;
typedef int fuko[yuzu|10];
fuko a;
typedef int yuri[aoi];
yuri vis[aoi],b[aoi];
int main() {
for (int t=read();t--;) {
int n,i,j,ans=0;
read(n);
for (i=0;i<=n; i)
for (j=0;j<=n; j)
vis[i][j]=0;
for (i=1;i<=n; i)
for (j=1;j<=n; j)
b[i][j]=read();
auto lit=[&](int x,int y,int p) {
if (x<0||x>n||y<0||y>n) return 1;
if (p) return vis[x][y]=1;
return vis[x][y]?0:1;
};
auto ck=[&](int x,int y,int p=0) {
return lit(x 1,y,p)&&lit(x-1,y,p)&&lit(x,y 1,p)&&lit(x,y-1,p);
};
for (i=1;i<=n; i) {
for (j=1;j<=n; j) {
if (j<n&&ck(i,j)&&ck(i,j 1)) {
ck(i,j,1),ck(i,j 1,1);
ans^=b[i][j]^b[i][j 1];
}
if (i<n&&ck(i,j)&&ck(i 1,j)) {
ck(i,j,1),ck(i 1,j,1);
ans^=b[i][j]^b[i 1][j];
}
}
}
printf("%d\n",ans);
}
}
谢谢大家.
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhffeeei
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
excel打印预览压线压字怎么办
PHP中文网 06-22