CF-737-div2
| 题目 | A | B | C | D | E |
|---|---|---|---|---|---|
| 通过情况 | AC | AC | AC | O | O |
| 难度 | 800 | 1100 | 1700 | 2200 | 2800 |
A. Ezzat and Two Subsequences
题面
略
解法
答案比较显然，只要把最大的取出来单独作为一项就行，证明需要花点功夫。
代码
1 | /* |
B. Moamen and k-subarrays
题面
给定长度为$n$的数列，问是否能分为$k$段后重新组合成为单调递增的数列
解法
样例给的比较有迷惑性，一开始以为只要后一项比前一项小计数器加一即可。正解是要先排序将有连续序号的分为一组。
对于前一种错误解法的hack数据：1
2
31
5 4
2 4 1 3 5
代码
1 | /* |
C. Moamen and XOR
题面
求满足$a_1\&a_2\&…\&a_n\geqslant a_1\oplus a_2\oplus …\oplus a_n$的不同数列数（均小于$2^k$）
解法
本题个人分为、大于和等于两种情况进行讨论
①若要满足$a_1\&a_2\&…\&a_n>a_1\oplus a_2\oplus …\oplus a_n$，那么$n$为偶数且在某一位上是$1$的情况，同时高位取相等，低位任取
②若要满足$a_1\&a_2\&…\&a_n=a_1\oplus a_2\oplus …\oplus a_n$，那么每一位都要满足$n$为奇数且全为$1$，或者含$0$有偶数个$1$,即
$\left( \begin{array}{c}
n\\
0\\
\end{array} \right) +\left( \begin{array}{c}
n\\
2\\
\end{array} \right) +…+\left( \begin{array}{c}
n\\
k\\
\end{array} \right) \,\,, 2k<n$
代码
1 | /* |
D. Ezzat and Grid
题面
给定$n$行长度相等（不超过$10^9$）的01序列，最少删除多少行可以得到相邻行上相同位都有1
解法
这里我们要用到动态规划的思想来分析这个问题:
设$dp_{i,j}$表示在第$i$行第$j$位为$1$的方法数，$C_i$为某行所有$1$的列位置集合：
·$dp_{0,j}=0$
·$dp_{i,j}=1+\max \left\{ dp_{i-1,k} \right\} \,\,, j,k\in C_i$
·$dp_{i,j}=dp_{i-1,j}\,\,, j\notin C_i$
由于实际输入为区间输入，我们使用线段树储存信息
其他技巧：使用离散化压缩空间
代码
（为了学习结构体封装，代码主要参考了题解）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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141/*
* @题目: D. Ezzat and Grid
* @算法: 线段树、DP
* @Author: Blore
* @Language: c++11
* @Date: 2021-08-09 22:26:19
* @LastEditors: Blore
* @LastEditTime: 2021-08-10 16:17:37
*/
using namespace std;
const int inf = 0x7fffffff;
int read()
{
int p = 0, f = 1;
char c = getchar();
while (c < 48 || c > 57)
{
if (c == '-')
f = -1;
c = getchar();
}
while (c >= 48 && c <= 57)
p = (p << 1) + (p << 3) + (c ^ 48), c = getchar();
return p * f;
}
const pair<int, int> NIL = {0, -1};
struct segment_tree
{
int n;
vector<pair<int, int>> tree, lazy;
segment_tree(int n) : n(n)
{
tree = lazy = vector<pair<int, int>>(n << 2, NIL);
}
void pushdown(int rt, int l, int r)
{
if (lazy[rt] == NIL)
return;
tree[rt] = max(tree[rt], lazy[rt]);
if (l != r)
{
lazy[lc] = max(lazy[lc], lazy[rt]);
lazy[rc] = max(lazy[rc], lazy[rt]);
}
lazy[rt] = NIL;
}
void update(int rt, int l, int r, int ql, int qr, pair<int, int> val)
{
pushdown(rt, l, r);
if (qr < l || r < ql)
return;
if (ql <= l && r <= qr)
{
lazy[rt] = max(lazy[rt], val);
pushdown(rt, l, r);
return;
}
update(lc, l, mid, ql, qr, val);
update(rc, mid + 1, r, ql, qr, val);
tree[rt] = max(tree[lc], tree[rc]);
}
pair<int, int> query(int rt, int l, int r, int ql, int qr)
{
pushdown(rt, l, r);
if (qr < l || r < ql)
return NIL;
if (ql <= l && r <= qr)
return tree[rt];
return max(query(lc, l, mid, ql, qr), query(rc, mid + 1, r, ql, qr));
}
void update(int ql, int qr, pair<int, int> val)
{
update(1, 1, n, ql, qr, val);
}
pair<int, int> query(int ql, int qr)
{
return query(1, 1, n, ql, qr);
}
};
int main()
{
int n = read(), m = read();
vector<int> id;
vector<vector<pair<int, int>>> v(n);
rep(i, 1, m)
{
int j = read(), l = read(), r = read();
id.pb(l), id.pb(r);
v[j - 1].pb({l, r});
}
sort(all(id));
id.erase(unique(all(id)), id.end());
rep(i, 0, n - 1)
{
for (auto &it : v[i])
{
it.first = upper_bound(all(id), it.first) - id.begin();
it.second = upper_bound(all(id), it.second) - id.begin();
}
}
segment_tree seg(id.size());
vector<int> prv(n, -1);
rep(i, 0, n - 1)
{
pair<int, int> mx = NIL;
for (auto &it : v[i])
mx = max(mx, seg.query(it.first, it.second));
prv[i] = mx.second;
mx.first++;
mx.second = i;
for (auto &it : v[i])
seg.update(it.first, it.second, mx);
}
pair<int, int> p = seg.query(1, id.size());
vector<bool> vis(n);
int cur = p.second;
while (cur != -1)
{
vis[cur] = 1;
cur = prv[cur];
}
printf("%d\n", n - p.first);
rep(i, 0, n - 1) if (!vis[i]) printf("%d ", i + 1);
return 0;
}
E. Assiut Chess
题面
交互题，国际象棋规则。$8\times 8$棋盘，皇后可以沿八个方向移动任意位，国王只能沿八个方向移动一位。不知道国王的初始位置，每次皇后进行合法移动后，给出国王的移动方向，直到国王无法移动（不超过$130$次交互）
解法
显然我们需要逐步压缩国王的活动空间，不妨按行来压缩。只要保证国王不在下一行就可以移动，具体做法是：
①从左数第1位/第2位向右移动，或者右数第1位/第2位向左移动
②当在某行移动时得到国王向下时，让皇后到下一行
③当在某行移动时得到国王向上时，让皇后重新遍历本行
④当皇后完遍历本行且没有得到上或者下的信息，让皇后到下一行
重复上述步骤即可
（可能由于很难给出国王移动的最优解，实际比赛中只要‘S’型遍历一遍也能AC）
代码
1 | /* |