A - The Third Three Number 问题
Problem - A - Codeforces
题意
给你一个整数 $n$，请输出三个数 $a, b, c$ 满足 $(a\oplus b) + (a\oplus c) + (b\oplus c) = n$。
题解
考虑异或的性质 $(x\oplus x)=0,(x\oplus 0) = x$。
则很快可以得到若 $a=x,b=x,c=0$ 的情况下，原式的结果即为 $2x$。
那么直接输出 n/2 n/2 0 即可。
但是上述结论很显然只对于偶数成立，在样例中 $n$ 为奇数的只有一个，表现为无解。那么是否能证明所有的奇数都能证明无解呢？
对于二进制的末位进行考虑。发现不论是 $1,1,1$、$1,1,0$、$1,0,0$、$0,0,0$ 最后的末位之和都是偶数，也就是说，如果是奇数的 $n$，是永远不可能找到一个合法的 $a,b,c$ 来表示的。证毕。
B - Almost Ternary Matrix
Problem - B - Codeforces
题意
构造一个 $n\times m$ 的矩阵，满足要求：对于矩阵上任意一个点，其正上下左右都恰好有两个点的颜色与其相同。保证 $n,m$ 均为偶数。
题解
构造题不要被样例迷惑了qwq
不难想到答案矩阵由下面的子矩阵填充而成：
那么就结束了。
C - The Third 问题
Problem - C - Codeforces
题意
定义两个相似的序列 $a, b$：$\forall 1\le l \le r\le n, \operatorname{MEX}(a_l,\cdots ,a_r)=\operatorname{MEX}(b_l,\cdots ,b_r)$。
现在给定长度为 $n$ 的序列 $a$，问有多少与其相似的序列 $b$。
题解
显然 $0,1$ 的位置不变。对于一个大于 $1$ 的 $k$。我们可以分两种情况讨论：
- $k$ 在所有小于他的数之间
- $k$ 在所有小于他的数之外
这样分是有道理的。因为如果 $k$ 在所有小于他的数直接间，那么这一段数的 $\operatorname{mex}$ 是不变的，可以随便放。而如果在之外，就只有一个选择。
代码
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
int n;
int a[N];
int pos[N];
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) {
read(a[i]);
pos[a[i]] = i;
}
}
inline void Work() {
int l = pos[0], r = pos[0];
ll ans = 1;
for(int i = 1; i < n; i++) {
if(pos[i] < l) l = pos[i];
else if(pos[i] > r) r = pos[i];
else ans = (ans * (r - l + 1 - i)) % P;
}
printf("%lld\n", ans);
}
int main() {
int T = read();
while(T--) {
Input();
Work();
}
return 0;
}
|
D - Almost Triple Deletions
Problem - D - Codeforces
题意
对于一个序列 $a$，可以执行若干次如下操作：删去任意相邻的，不同的元素 $a_i,a_{i+1}$。问执行若干次操作使得剩余的部分留下相同数字，问这些相同的数字最长的长度是多少？
题解
考虑DP，设状态为 $dp[i]$ 表示将区间 $[1,i]$ 删掉只剩下 $a[i]$ 这类数字的最大长度，则有式子：
考虑答案。很显然 $dp[n]$ 是不正确的。所以设置通配符 $a[n+1]$，这样就可以快速综合所有答案。
接下来考虑 $Check$ 的条件。
很显然，如果一段序列能被删去，需要满足如下条件：
- 长度偶数
- 众数出现次数小于等于一半
然后还有条件，$a[i] = a[j]$ 因为删去这一段我们是要把 $a[i],a[j]$ 接在一起的。还有我们要保证 $dp[j]$ 有解，不然是不可以转移的。
代码
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int > pii;
typedef unsigned long long ull;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 5010;
int n;
int a[N];
int cnt[N];
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) {
read(a[i]);
}
}
int dp[N];
inline void Work() {
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n + 1; i++) {
for(int j = 1; j <= n; j++) cnt[j] = 0;
int mx = 0;
for(int j = i - 1; j >= 0; j--) {
if( !(a[i] != a[j] && i != n + 1 && j != 0) &&
!(i % 2 == j % 2) && !(mx * 2 > i - j - 1) &&
!(dp[j] == 0 && j != 0)) {
dp[i] = max(dp[i], dp[j] + 1);
}
mx = max(mx, ++cnt[a[j]]);
}
}
printf("%d\n", dp[n + 1] - 1);
}
int main() {
int T = read();
while(T--) {
Input();
Work();
}
return 0;
}
|
E - Three Days Grace
Problem - E - Codeforces
题意
你可以把序列 $a$ 中的任意一个数拆成两个数相乘，问进行若干次拆数后序列的极差最小值是多少？
题解
我不会做。
