codeforces 1438D,思路非常非常巧妙的构造题
大家好,欢迎来到codeforces专题。
今天选择的问题是contest1438的D题,全场通过人数为1325人。一般在codeforces当中千人通过的题难度都不算太高,但是这题有点例外,虽然没有涉及一点高深的算法,但是想要自己做出来还是有点难度的。
题目链接:https://codeforces.com/contest/1438/problem/D
废话不多说了,我们直接来看题。
题意
给定一个拥有n()个正整数的数组,然后我们队数组当中的元素进行一种神奇的异或操作。
操作如下,我们选择三个不同的下标i、j、k。对a[i]
,a[j]
,a[k]
这三个元素执行异或操作,即。之后这三个数分别赋值成这个异或之后的结果。
现在我们想要在n步这样的神奇异或操作之内让数组当中的所有元素全部相等,请问这一点是否可能呢?首先输出YES或NO,表示是否有解。如果有解输出需要操作的步数,以及对应选择的元素下标。
样例
在第一个样例当中,4、1、7的异或结果为2,所以通过这样一步操作之后,即可以满足所有元素全部均等。
题解
我一开始的时候惯性思维,既然是异或运算,那么肯定要从二进制下手。一个数组当中的所有元素均等,其实就等价于它们在每一个二进制位上也等相等,同为0或者是同为1。于是我就一直在思考怎么来针对每一个二进制位来进行判断和选择,不知不觉就走进了死胡同,因为这些二进制位之间彼此影响, 我们很难一位一位地梳理清楚。
我之所以走进死胡同是因为被题目当中的一个条件给欺骗了,这个条件就是最多n个操作步骤的限制。我们直观上都会觉得这是一个非常严苛的要求,所以会期望想到一个完美的解法,可以用最少的步骤解开这个问题。
但实际上这个n足够大,足够一些看起来非常笨的方法也能AC。不得不说这也是很多题目当中惯用的思维陷阱,考验的就是选手的胆量和经验。
异或的性质
首先我们来分析一下异或运算,这题当中并没有对异或做什么特殊的处理。唯一不同的地方就是,我们是对三个数进行异或。我们从最基础的01二进制位来分析,3个数做异或只有四种情况。000、010、011和111,我们发现其中000和011的结果都是0,010和111的结果是1。因为异或相同为0,不同为1的计算特性,会导致相同的数被消除。
比如我们计算的三个数是[a,b,b]
那么最后的结果是a,我们可以利用这一点来做文章。想起来或许有些复杂,但是说穿了真的一文不值。
我们假设n=7,这7个数分别是[a,b,c,d,e,f,g]
。首先我们对前三个数进行异或操作,这样我们会得到:[h,h,h,d,e,f,g]
,接着我们选择第3、4、5位的元素操作,得到:[h,h,j,j,j,f,g]
。我们继续选择第5、6、7位的元素进行操作,得到[h,h,j,j,k,k,k]
。
到这里其实已经有点眉目了,因为[a,b,b]
的操作结果是a,我们剩下要做的就是继续选择,把除了k之外其他的元素全部消除。
我们继续选择第3、4、5位的元素操作,得到[h,h,k,k,k,k,k]
,同理我们最后选择第1、2、3位的元素操作,这样整个数组当中的元素都变成了k。到这里,我们一共进行了5次,也就是n-2次操作,完全没有超过题目的限制。
但是这里有一个小问题,这个方案之所以可行是有前提的。它最大的前提就是n是奇数。如果n是偶数,就会最后剩下一个元素,这个应该怎么解决呢?
偶数的情况
偶数的情况我们光想是很难想出办法来的,因为我们解决不了最后多余一个元素的问题。
这里需要用到一个关键性的推论,这个推论非常隐蔽,真的不容易想到。我们假设,当n为偶数时,那么无论我们对这n个元素如何操作,这个异或得到的k保持不变。
这个结论是从哪里来的?其实也是从异或的性质当中来的。我们对三个数做异或,从具体某一个二进制位来分析。我们会发现我们的操作不会改变整体这n个bit的奇偶性。对于异或操作而言,两两相消,最后的结果只和奇偶性相关。最终的结果只和这个奇偶性相关。
从这一点出发,我们进一步可以得到如果,那么一定无解。
这个结论其实也很简单,因为我们已经知道了,无论我们如何操作也不会改变这个k值。由于n是偶数,所以如果n个数完全相等的话,那么它们的异或值一定等于0,所以k不等于0的时候,一定无解。
当k等于0的时候怎么办呢?其实非常简单,我们只需要抛弃掉最后一个元素,把之前的n-1个元素按照上面n为奇数时的操作全部操作相等即可。这样一番操作之后,数组会变成这样[a,a,a,a...a,b]
。前面n-1个a的异或值为a,而整体n个数的异或值为0,所以可以得到a=b。那么我们就完成了整个操作。
整个思路有了之后,代码实现就太简单了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#define rep(i,a,b) for (int i=a;i<b;i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
const int N=100050;
const long long Mod=1000000007;
using namespace std;
int a[N];
int main() {
int n, x;
scanf("%d", &n);
rep(i, 0, n) {
scanf("%d", a + i);
}
// 如果n为奇数,一定有解
if (n % 2) {
puts("YES");
printf("%d\n", n-2);
for (int i = 0; i + 2 < n; i+=2) {
printf("%d %d %d\n", i+1, i+2, i+3);
}
for (int i = n-3; i - 2 >= 0; i-=2) {
printf("%d %d %d\n", i+1, i, i-1);
}
}else {
// 如果n为偶数,判断整个数组的异或值是否为0
x = 0;
rep(i, 0, n) x ^= a[i];
if (x > 0) {
puts("NO");
}else {
n --;
puts("YES");
printf("%d\n", n-2);
for (int i = 0; i + 2 < n; i+=2) {
printf("%d %d %d\n", i+1, i+2, i+3);
}
for (int i = n-3; i - 2 >= 0; i-=2) {
printf("%d %d %d\n", i+1, i, i-1);
}
}
}
return 0;
}
到这里,今天这道题就做完了,怎么样,今天的题目还挺有意思吧。讲道理把算法讲出来之后非常简单,几乎没有难度,但是如果让我们自己思考,会变得非常难,我们很难从当中整理出思绪来。思路巧妙有趣这也是codeforces题目的最大魅力所在,希望大家都能体会到算法的乐趣。
今天的文章就到这里,衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话,请来一个三连支持吧~(点赞、关注、转发)
最新文章
- DB2 常用命令小结
- python学习笔记之常用模块(第五天)
- django with mysql (part-1)
- linux系统字符集
- 即使连网了ping也会失败
- 转 用 AXIOM 促进 XML 处理
- eclipse 或MyEclipse将工程进行移动的时候会对@Override报错的处理方法
- form 表单练习
- java ssh
- 【百度地图API】今日小年大进步,齐头共进贺佳节——API优化升级上线,不再增加内存消耗
- Uploadify 上传后的文件删除,上传队列无法更新问题
- grid栅格布局
- Hive 本地调试方法
- js 连接mqtt
- [小结]InnoDB体系结构及工作原理
- java从request中获取GET和POST请求参数
- CentOS 安装Python3、pip3
- Page11:状态反馈、输出反馈的概念及性能比较,极点配置的基本概念、意义及其算法[Linear System Theory]
- 百练-16年9月推免-C题-图像旋转
- 基于select类型多路IO复用,实现简单socket并发
热门文章
- Golang 实现 Redis(8): TCC分布式事务
- UnityEditorWindow做一个TimeLine的滑动块
- go语言数据类型值--整型和浮点型
- 第11.14节 正则表达式转义符和Python转义符相同引发问题的解决办法
- PyQt学习随笔:使用PyCharm+PyQt开发遇到的坑
- 大数据技术体系 &;&; NoSQL数据库的基本原理
- 实验吧bypass the upload
- pandas 处理缺失值(连续值取平均,离散值fillna";<;unk>;";)
- Docker 命令自动补全?要的
- 【WC2014】紫荆花之恋(替罪羊重构点分树 &; 平衡树)