B - AGAGA XOOORRR
2021/4/30 10:55:15
本文主要是介绍B - AGAGA XOOORRR,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
B - AGAGA XOOORRR
原题链接:传送门
人一我十, 人十我百,追逐青春的梦想,怀着自信的心,永不言弃!
题目大意
给定一个长度 n 的数组,你可以对数组进行如下操作:每一次选择两个相邻的数字然后用这两数字的异或值替换这个两个数字,问如果想要保证最后整个数组的元素值都相等且必须保证至少有两个数字。问你是否可以通过若干次操作使得满足以上条件
分析
首先根据异或和的特点,如果整个数组最后都化成某一个数字 x 那么我们对整个序列进行一次异或和之后
- 如果 sum = 0, 说明最终有偶数个 x 则一定可以满足要求
- 如果sum !=0 ,那么sum 一定等于 x 因为 x ^ x = 0, 0 ^ x = x; 故一定可以保证序列中最后有奇数个 x
那么我们从以上两个性质入手
1. 首先我们获取整个序列的异或和, if 异或和 == 0 : yes 2. 否则说明一定有奇数个 sum 我们只需要挨着区间去检查检查一共可以有多少段区间可以构成sum 并且保证每一个区间之构成sum int cnt = 0, ans1 = 0; for(int i = 0; i < n; i ++) { ans1 ^= a[i]; if(ans1 == ans) { ans1 = 0; cnt ++; } } // 判断是否可以恰好组成cnt个 x 并且 cnt要 >= 3 if(ans1 == 0 && cnt >= 3){ cout << "YES" << endl; return; } cout << "NO" << endl;
关键的性质点
对于整个序列的异或之后的结果可能是0,也可能是一个数字
如果是 0 表示序列中最后一定可以化成偶数个相同的数
否则不可以化成 / 可以化成奇数个相同的数并且这个数等于异或和
对于这种只需要判断其是否可以成功或者不可以成功的题目通常需要根据一些良好的性质来判定即可。
AC 代码
AC code
void slove() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i ++)cin >> a[i]; int ans = 0; for(int x : a) ans ^= x; // 说明最后有偶数个一样的数 if(ans == 0) { cout << "YES" << endl; return; } // 否则说明有奇数个一样的数检查是否可以经过 // 一段一段的亦或和令其变成最终的那个数 int cnt = 0, ans1 = 0; for(int i = 0; i < n; i ++) { ans1 ^= a[i]; if(ans1 == ans) { ans1 = 0; cnt ++; } } // 判断是否可以恰好组成cnt个 x 并且 cnt要 >= 3 if(ans1 == 0 && cnt >= 3){ cout << "YES" << endl; return; } cout << "NO" << endl; }
这篇关于B - AGAGA XOOORRR的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)