ARC219 A
出处：ARC219 A
题目大意：给定 $N$ 个互不相同的字符串 $S_1,\dots,S_N$，每个字符串长度为 $M$，且均由 ‘0’ 和 ‘1’ 组成。请判断是否存在一个长度为 $M$ 且由 ‘0’ 和 ‘1’ 组成的字符串 $T$，满足如下条件，并在存在时构造出一个例子。
数据范围：$1 \leq N \leq 2 \times 10^4$，$1 \leq M \leq 100$，$|S_i| = M$。
思路：
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
| struct Node {
int son[2];
Node() { son[0] = son[1] = -1; }
};
void solve() {
int n, m;
cin >> n >> m;
vector<string> ma(n);
map<string, int> ma2;
vector<Node> tree(1);
rep(i, 0, n - 1) {
cin >> ma[i];
ma2[ma[i]]++;
int cur = 0;
for (char c : ma[i]) {
int b = c - '0';
if (tree[cur].son[b] == -1) {
tree[cur].son[b] = sz(tree);
tree.emplace_back();
}
cur = tree[cur].son[b];
}
}
if (m <= 30 && sz(ma2) == (1 << m)) {
cout << "No" << endl;
return;
}
cout << "Yes" << endl;
string res;
bool flag = false;
auto dfs = [&](this auto&& dfs, int x, int cnt) -> void {
if (flag) return;
if (cnt == m) return;
rep(i, 0, 1) {
if (flag) return;
if (tree[x].son[i] == -1) {
res.push_back(char('0' + i));
while (sz(res) < m) {
res.push_back('0');
}
flag = true;
return;
}
res.push_back(char('0' + i));
dfs(tree[x].son[i], cnt + 1);
if (flag) return;
res.pop_back();
}
};
dfs(0, 0);
rep(i, 0, m - 1) { res[i] = (res[i] == '0') ? '1' : '0'; }
cout << res << endl;
return;
}
|
ARC219 B
出处：ARC219 B
题目大意：给定一个整数 $N$ 和一个排列 $P=(P_1,P_2,\ldots,P_N)$，其中 $P$ 是 $1,2,\ldots,N$ 的一个排列。对任意排列 $Q=(Q_1,Q_2,\ldots,Q_N)$，定义 $Q'=(Q_1',Q_2',\ldots,Q_N')$ 为通过如下操作恰好一次后能够获得的字典序最小的排列： - 选择一对整数 $(l,r)$，满足 $1\le l\le r\le N$，将 $Q_l,Q_{l+1},\ldots,Q_r$ 这一段翻转。更具体地，即将 $Q$ 变为 $(Q_1,Q_2,\ldots,Q_{l-1},Q_r,Q_{r-1},\ldots,Q_l,Q_{r+1},Q_{r+2},\ldots,Q_N)$。
数据范围：$1\le T$，$1\le N\le 5\times 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| const ll MOD = 998244353;
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
ll tem = 0;
rep(i, 0, n - 1) {
if (a[i] != i + 1) break;
tem = (tem + (n - 1 - i) + MOD) % MOD;
}
bool flag = true;
rep(i, 0, n - 1) {
if (a[i] != i + 1) {
flag = false;
break;
}
}
cout << (tem + flag) % MOD << endl;
return;
}
|
ARC219 C
出处：ARC219 C
题目大意：注意：本题与问题 G 的设定几乎相同，题目陈述的不同之处以红色粗体标出。 有一个由 $H$ 行 $W$ 列组成的地下公寓。第 $i$ 行第 $j$ 列的格子表示为格子 $(i, j)$。地下公寓的入口在格子 $(1,1)$。地下公寓内有 $N$ 扇门。第 $k$ 扇门位于格子 $(A_k, B_k)$。在地下公寓内，推销员可以按照任意顺序、任意多次执行以下两种移动方式： - 他可以从当前格子水平移动到邻近的格子（左或右移动一格），该操作花费 $1$。- 如果他当前所在的格子在第 $1$ 列或第 $W$ 列，可以乘电梯垂直移动到相邻的格子（向上或向下移动一格），该操作的花费是**$\mathbf{0}$**。
数据范围：$1 \leq H \leq 10^9$，$2 \leq W \leq 10^9$，$1 \leq N \leq 3 \times 10^5$，$1 \leq A_k \leq H$，$1 \leq B_k \leq W$。
思路：
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
| const ll MOD = 998244353;
void solve() {
ll h, w;
cin >> h >> w;
int n;
cin >> n;
vector<pll> ma(n);
map<ll, vl> ma2;
rep(i, 0, n - 1) {
cin >> ma[i].first >> ma[i].second;
ma2[ma[i].first].push_back(ma[i].second);
}
ll tem = 0;
for (auto& [x, y] : ma2) {
ranges::sort(y);
y.erase(unique(all(y)), y.end());
tem += 2 * (y[sz(y) - 1] - 1);
}
vl dp(3, LLONG_MAX / 3);
dp[0] = 0;
for (auto& [x, y] : ma2) {
int m = sz(y);
vl pre(m + 1);
ll tem2 = LLONG_MAX / 3;
tem2 = min(tem2, 2 * (y[m - 1] - 1));
tem2 = min(tem2, 2 * (w - y[0]));
rep(i, 0, m - 2) { tem2 = min(tem2, 2 * (y[i] - 1) + 2 * (w - y[i + 1])); }
vl ndp(3, LLONG_MAX / 3);
rep(i, 0, 2) {
if (dp[i] == LLONG_MAX / 3) continue;
ndp[i] = min(ndp[i], dp[i] + tem2);
}
if (dp[0] < LLONG_MAX / 3) {
ndp[1] = min(ndp[1], dp[0] + w - 1);
}
if (dp[1] < LLONG_MAX / 3) {
ndp[2] = min(ndp[2], dp[1] + w - 1);
}
if (dp[2] < LLONG_MAX / 3) {
ndp[1] = min(ndp[1], dp[2] + w - 1);
}
dp = ndp;
}
cout << min({dp[0] + 2 * (w - 1), dp[1] + w - 1, dp[2], tem}) << endl;
return;
}
|
ARC219 D
出处：ARC219 D
题目大意：有一个 $N \times N$ 的网格。第 $i$ 行从上往下，第 $j$ 列从左往右的格子记作格子 $(i, j)$。格子 $(i, j)$ 初始包含 $A_{i, j}$ 颗石子。Alice 和 Bob 用这个网格玩如下游戏。- 由 Alice 先手，两人轮流操作。- 每一回合，当前玩家选择一个格子，并把其中至少 $1$，至多 $K$ 颗石子一起移动到相邻的上方或左方的格子。具体分为以下几步： 1. 选择一个包含至少 $1$ 颗石子的 $(i, j)$ 格子。不能选择 $(1, 1)$。2. 设该格子当前有 $c$ 颗石子，选择一个整数 $x$，满足 $1 \le x \le \min(c, K)$。
数据范围：$1\le T$，$2\le N\le 100$，$1\le K\le 10^9$，$0\le A_{i,j}\le 10^9$，$\sum N^2 \le 3\times 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void solve() {
ll n, k;
cin >> n >> k;
vvl ma(n, vl(n));
rep(i, 0, n - 1) { rep(j, 0, n - 1) cin >> ma[i][j]; }
int tem = 0;
rep(i, 0, n - 1) {
rep(j, 0, n - 1) {
if ((i + j) % 2 == 0) continue;
tem ^= ma[i][j] % (k + 1);
}
}
if (tem != 0)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
return;
}
|
ARC219 E
出处：ARC219 E
题目大意：有一个形状为 $2H \times 2W$ 的蛋糕，蛋糕每个格子用 $(i,j)$ 表示，其中 $i$ 表示从上往下的第 $i$ 行，$j$ 表示从左往右的第 $j$ 列。如果 $S_{i,j}=$ ‘o’，则 $(i,j)$ 位置上有一颗草莓；如果 $S_{i,j}=$ ‘x’，则该格没有草莓。保证恰好有 $2HW$ 个格子上有草莓。请将蛋糕的每个格子分配到 A、B 两个区域中，分配需要满足如下所有要求： - 任意一个格子必须且仅属于 A、B 两个区域之一。- 区域 A、B 都是连通的。即，对任何属于同一区域中的两个格子，可以只经过与该区域内的相邻格子（共享边）多次移动，从其中一个格子移动到另一个格子。
数据范围：$1 \leq T$，$1 \leq H \leq W$，$H \times W \leq 10^6$，$S_{i,j}=$，$\sum H \times W \leq 10^6$。
思路：
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
| void solve() {
ll h, w;
cin >> h >> w;
vector<string> ma(2 * h);
rep(i, 0, 2 * h - 1) cin >> ma[i];
vvi res(2 * h, vi(2 * w));
vector<pii> tem;
rep(i, 0, 2 * h - 1) tem.emplace_back(i, 0);
rep(i, 1, 2 * w - 1) tem.emplace_back(2 * h - 1, i);
frep(i, 2 * h - 2, 0) tem.emplace_back(i, 2 * w - 1);
frep(i, 2 * w - 2, 1) {
if ((2 * w - 1 - i) % 2) {
rep(j, 0, 2 * h - 2) tem.emplace_back(j, i);
} else {
frep(j, 2 * h - 2, 0) tem.emplace_back(j, i);
}
}
int tem2 = 0;
int l, r;
rep(i, 0, 4 * h * w - 1) {
tem2 += (ma[tem[i].first][tem[i].second] == 'o');
if (i < 2 * h * w - 1) continue;
if (tem2 == h * w) {
r = i, l = i - 2 * h * w + 1;
break;
}
tem2 -= (ma[tem[i - 2 * h * w + 1].first][tem[i - 2 * h * w + 1].second] == 'o');
}
rep(i, l, r) res[tem[i].first][tem[i].second] = 1;
rep(i, 0, 2 * h - 1) {
rep(j, 0, 2 * w - 1) cout << (res[i][j] ? 'A' : 'B');
cout << endl;
}
return;
}
|
