Codeforces Round 932 (Div. 2)
Educational Codeforces Round 163 (Rated for Div. 2)
A题:Special Characters
标签: 暴力枚举(brute force)构造算法(constructive algorithms)
题目大意
- 构造一个字符串含有n个特殊字符
- 如果一个字符与其相邻的一个字符相等,我们就将其称为特殊字符。
思路
- 特殊字符总是两个两个出现,例如 AAABBB 4个特殊字符
- n(n>2)个连续的字符也只有两个特殊字符,构造AABBCCDDEE型字符串即可
AC代码
1 |
|
B题:Array Fix
标签: 暴力枚举(brute force)动态规划(dp)贪心策略(greedy)实现问题,编程技巧,模拟(implementation)
题目大意
- 有一个长度为 n 的数组 a,对与a中每个元素 0 ≤ a
i≤ 99- 可以任意次数对a 中数拆分放在原位,例如:19 拆分为1和9
- 问:能否通过拆分使 a 中元素以非降序排序
思路
- 贪心:如果前面数字能拆则拆,以使前面数字减小
- 判断前面数字能拆,如果十位大于个位不能拆,或十位拆开要小于前面的数不能拆。
- 例如:42 89 判断是否能拆
- 首先42拆开为4 2不是非降序所以不拆,此时89前面为42
- 89拆开8 9,但8 < 42所以不拆
AC代码
1 |
|
C题:Arrow Path
标签: 深度优先搜索及其变种(dfs and similar)图论(graphs)最短路算法(shortest paths)
题目大意
- 有一个网格,由 2 行和 n 列组成。行的编号从从 1 ~ 2 。列的编号 1 ~ n 。网格的每个单元格都包含一个箭头,指向左边或右边。没有箭头指向网格外。
- 从 (1,1)格开始。每隔一秒钟,下面两个动作会相继发生:
- 首先,向左、向右、向下或向上移动(不能试图移动到网格外,也不能跳过移动);
- 然后,沿着放置在当前单元格中的箭头移动(移动后最终到达的单元格)。
判断能否到达 (2, n)单元格。
思路
1
>>> <
*>>> <
1
2
3
4
>- 方法一、如果出现如上中间位置倾斜两点( `>`的位置 )同时为`<`则不可通过
>- - 例如:(1, 2) 与 (2, 3)、(2, 3)与(1, 4)不能同时是`<`
>- 方法二、bfs或 bfs遍历一遍即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
方法一、AC代码
```cpp
#include <iostream>
#include <string>
using namespace std;
void solve()
{
int n;
string s[2];
cin >> n >> s[0] >> s[1];
bool bad = false;
for(int i = 1; i < n; i++)
bad |= (s[(i-1)%2][i] == '<' && s[i%2][i-1] == '<');
cout << (bad? "NO\n":"YES\n");
}
int main(){
int T; cin >> T;
while(T--)
solve();
return 0;
}
方法二、AC代码
1 |
|
logo
1 |
|
1 |
|
Codeforces Round 932 (Div. 2)
https://leaf-domain.gitee.io/2024/03/15/cf-div2-round_163/