Codeforces Round #804 (Div. 2) - A, B, C

https://codeforces.com/contest/1699

---

C. The Third Problem

题意
给定一个 $0$ 到 $n-1$ 的全排列，问一共有多少 $0$ 到 $n-1$ 的全排列和该排列相似？
答案对 1e9+7 取模。

相似定义：如果两个全排列满足下面条件，就说两个这两个全排列相似。

• 对于任意区间 $[l,r](1\le l\le r\le n)$ 都满足：$\mathrm{MEX}([a_l,a_{l+1},\dots ,a_r])=\mathrm{MEX}([b_l,b_{l+1},\dots ,b_r])$

对于一堆数 $c_1,c_2,\dots ,c_k$ 的 $\mathrm{MEX}$ 是指，在集合 $c$ 中第一个未出现的非负整数 $x$。

思路
从 0 到 n-1，一个数一个数的判断，看其能放在哪些位置。所有可能的位置数相乘就是答案。

标记数 x 在原排列中所在位置为 p[x]。

• 首先容易确定，0 和 1 在相似排列中的位置不变，都为 p[0]。设 l 为较左端位置，r 为较右端位置。
• 对于 2：
  1. 如果 p[2] 位于 [l, r] 中，那么 2 可以放在 [l, r] 中的所有空闲位置；
  （2 原来在 [l, r] 中，那么 $\mathrm{MEX}[l,r]$ 就达到 3 了，所以在相似排列中 2 只能放在 [l, r] 中）
  2. 否则，2 只能放在原来位置 p[2]；然后 p[2] 将 l 或者 r 更新；
  （2 原来在 [l, r] 之外，那么 $\mathrm{MEX}[l,r]$ 只能达到 2，2不能在 [l, r] 中；而其位置如果改变的话，会有区间的 MEX 值改变，所以这种情况下 2 的位置不能改变）
• 对于 3：
  1. 如果 p[3] 位于 [l, r] 中，那么 3 可以放在 [l, r] 中的所有空闲位置；
  2. 否则，3 只能放在原来位置 p[3]；然后 p[3] 将 l 或者 r 更新；
• …

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], p[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		for(int i=1;i<=n;i++) cin >> a[i], p[a[i]] = i;
		
		int ans = 1;
		
		int l = min(p[0], p[1]), r = max(p[0], p[1]);
		for(int i=2;i<n;i++)
		{
			if(p[i] > l && p[i] < r)
			{
				ans = ans * (r-l+1 - i) % mod;
			}
			else{
				if(p[i] < l) l = p[i];
				else r = p[i];
			}
		}
		cout << ans << endl;
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

经验
当没有思路的时候应该沉下心来从最初始的情况一点一点往后推，也许推着推着就有思路了。
而不是看着样例胡乱想。。

---

B. Almost Ternary Matrix

题意
构造一个 n*m 的 01 矩阵，使得：

• 对于每个位置，其直接相邻的位置中，恰有两个位置和该位置元素不同。

$2\le n,m\le 50$ 且都为偶数。

思路
这样构造：

6 8
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0
0 1 1 0 0 1 1 0
1 0 0 1 1 0 0 1
1 0 0 1 1 0 0 1
0 1 1 0 0 1 1 0
1
2
3
4
5
6
7

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 210, mod = 1e9+7;
int T, n, m;
int a[N] = {1, 0, 0, 1}, b[N] = {0, 1, 1, 0};
int ans[N][N];

signed main(){
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(i%4 == 1 || i%4 == 0) ans[i][j] = a[j%4];
				else ans[i][j] = b[j%4];
			}
		}
		
		for(int i=1;i<=n;i++){
			for(int j=0;j<m;j++){
				printf("%d ", ans[i][j]);
			}
			printf("\n");
		}
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

A. The Third Three Number Problem

题意
给定一个数 $n$，找到三个数 $a,b,c$ 满足：

• $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$

找不到输出 $-1$。

$1\le n\le 10^9,0\le a,b,c\le 10^9$

思路
由 $a+b=a\oplus b+2\cdot (a$ & $b)$ 可知，$a\oplus b$ 和 $a+b$ 具有相同的奇偶性。
那么 $n=(a\oplus b)+(b\oplus c)+(a\oplus c)$ 就和 $(a+b)+(b+c)+(a+c)=2\cdot (a+b+c)$ 具有相同奇偶性，一定为偶数。

• 当 n 为 奇数时输出 -1。
• 否则 令 $b=c=0$，那么原式变为：$a+a=n$，那么 $a=\frac{n}{2}$。

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n;
		if(n % 2 == 0) cout << n/2 << " " << 0 << " " << 0 << endl;
		else cout << -1 << endl;
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

经验
着重考虑特殊情况。