codeforcesround#804（div.2）A–C

A. The Third Three Number Problem

题意：

给定一个数n，找到三个数a,b,c 使得 a xor b + b xor c + a xor c = n

思路：

一般位运算的A题都是可以直接凑出来的，于是直接寻找特殊值，令 a = b = 0, c = x,运算的结果为2x,所以可以令c = n / 2,因为n为奇数是不能这样得到，猜测n为奇数时不存在，输出-1；证明一下奇数不成立：异或运算的奇偶性与加法的奇偶性相同，所以a xor b + b xor c + a xor c 的奇偶性与a + b + b + c + a + c相同，为偶数，不可能出现奇数。

代码：

#include using namespace std;int t, x;int main () {cin >> t;while (t--) {cin >> x;if ( x % 2 == 0)cout <<"0 0 " <B. Almost Ternary Matrix

题意：

给定n，m，构造一个n行m列的01矩阵，使得每个格子都有且仅有两个数值与自身不同的相邻格。

思路：

一开始想用状压算结果寄了。先看这一个案例，发现如果n=2时可以按这样循环下去10 01 10 ...01 10 01 ...然后n=4时10 01 10 ...01 10 01 ...01 10 01 ...10 01 10 ...如果是方阵，就为一个对称矩阵，行的拓展与列的拓展一样，本质上就是1 00 1和0 11 0的2x2 01矩阵然后可以直接找规律，构造这样一个矩阵：（下标从0开始）j % 4 == 0 || j % 4 == 3 时，每一行为1001 1001 1001... i % 4 == 0 || i % 4 == 3 时为1j % 4 == 1 || j % 4 == 2 时，每一行为0110 0110 0110... i % 4 == 1 || i % 4 == 2 时为1

代码：

#include using namespace std;int t, n, m;int main () {cin >> t;while (t--) {cin >> n >> m;int s[110][110];for (int i = 0; i C. The Third Problem

题意：

给定n，以及一个从0到n-1的全排列，问有多少个0到n-1的全排列与之相似（包含自己）相似的含义是，对于全排列中任意一个区间[l,r],区间的MEX都相同MEX是最小的没有在区间中出现的非负整数

思路：

从0到n-1考虑每一个数能放置的位置，当讨论第i个数时，我们考虑的区间中最有意义的区间是包含0,1，2...i-1从0开始连续到i-1的区间，因为这个区间的MEX最容易随着位置的变化发生改变，如果i在区间内，其MEX为i+1，那么i只能在这个区间中改变位置，否则区间的MEX就会变为i，如果i在区间外，那么i的位置不能改变，因为如果将i与区间的数交换，区间的MEX变化，如果将i与区间外的数交换，同理也会有区间的MEX变化。因此，我们可以逐步维护这个区间并得到答案。一些关于MEX的东西：

https://zhuanlan.zhihu.com/p/448147128

代码：

#include #define ll long longusing namespace std;int t, n;ll a[200010], b[200010], mod = 1000000007;void solve () {cin >> n;for (int i = 1; i > a[i], b[a[i]] = i;ll l = b[0], r = b[0], ans = 1ll;for (int i = 1; i r) r = b[i];else ans = (ans % mod) * (r - l + 1 - i) % mod; }cout <}int main () {cin >> t;while (t--) solve();return 0;}【本文来自：台湾服务器 http://www.558idc.com/tw.html 复制请保留原URL】