Educational Codeforces Round 163 (Rated for Div. 2) (A~C)
A题：Special Characters
标签: 暴力枚举（brute force）构造算法（constructive algorithms）
题目大意
- 构造一个字符串含有n个特殊字符
- 如果一个字符与其相邻的一个字符相等，我们就将其称为特殊字符。
思路
- 特殊字符总是两个两个出现，例如 AAABBB 4个特殊字符
- n(n>2)个连续的字符也只有两个特殊字符，构造AABBCCDDEE型字符串即可
AC代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin >> n;
string s = "";
if(n%2) cout << "NO\n";
else
{
cout << "YES\n";
for(int i = 0;i < n;i +=2)
{
if(i%4) cout << "AA";
else cout << "BB";
}
cout << endl;
}
}
int main()
{
int T; cin >> T;
while(T--)
solve();
}
B题：Array Fix
标签: 暴力枚举（brute force）动态规划（dp）贪心策略（greedy）实现问题，编程技巧，模拟（implementation）
题目大意
- 有一个长度为 n 的数组 a，对与a中每个元素 0 ≤ ai ≤ 99
- 可以任意次数对a 中数拆分放在原位，例如：19 拆分为1和9
- 问：能否通过拆分使 a 中元素以非降序排序
思路
- 贪心：如果前面数字能拆则拆，以使前面数字减小
- 判断前面数字能拆，如果十位大于个位不能拆，或十位拆开要小于前面的数不能拆。
- 例如：42 89 判断是否能拆
- 首先42拆开为4 2不是非降序所以不拆，此时89前面为42
- 89拆开8 9，但8 < 42所以不拆
AC代码
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n; cin >> n;
int t = 0, cnt = 0;
for(int i = 1;i <= n; i++)
{
int x; cin >> x;
if((x%10)>=(x/10)&&(x/10)>=t) t = x%10;
else if(x < t)
{
cout << "NO\n";
return;
}
else t = x;
}
cout << "YES\n";
}
int main()
{
int T; cin >> T;
while(T--)
solve();
return 0;
}
C题：Arrow Path
标签: 深度优先搜索及其变种（dfs and similar）图论（graphs）最短路算法（shortest paths）
题目大意
- 有一个网格，由 2 行和 n 列组成。行的编号从从 1 ~ 2 。列的编号 1 ~ n 。网格的每个单元格都包含一个箭头，指向左边或右边。没有箭头指向网格外。
- 从 (1,1)格开始。每隔一秒钟，下面两个动作会相继发生：
- 首先，向左、向右、向下或向上移动(不能试图移动到网格外，也不能跳过移动)；
- 然后，沿着放置在当前单元格中的箭头移动(移动后最终到达的单元格)。
- 判断能否到达 (2, n)单元格。
思路
> >*>*>*> < > *>*>*>* <
- 方法一、如果出现如上中间位置倾斜两点(
>的位置 )同时为<则不可通过
- 例如：(1, 2) 与 (2, 3)、(2, 3)与(1, 4)不能同时是
<- 方法二、bfs或 dfs遍历一遍即可
方法一、AC代码
#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代码
void dfs(int x, int y) {
if (v[x][y]) return ;
v[x][y] = 1;
if (x == 2 && y == n) return ;
for (int k = 1; k <= 4; k++) {
int tx = x + dx[k], ty = y + dy[k];
if (tx <= 0 || tx >= 3 || ty <= 0 || ty >= n + 1) continue;
ty += d[tx][ty];
if (tx <= 0 || tx >= 3 || ty <= 0 || ty >= n + 1) continue;
if (!v[tx][ty]) dfs(tx, ty);
}
}
int main()
{
T = read();
while (T--) {
ans = 0;
n = read();
for (int i = 1; i <= 2; i++) {
scanf("%s", &ch);
for (int j = 0; j < n; j++) {
if (ch[j] == '>') d[i][j + 1] = 1;
else d[i][j + 1] = -1;
v[i][j + 1] = 0;
}
}
dfs(1, 1);
printf(v[2][n] ? "YES\n" : "NO\n");
}
return 0;
}
logo
//へ ／|
// /＼7 ∠＿/
// / │ ／ ／
// │ Z ＿,＜ ／ /`ヽ
// │ ヽ / 〉
// Y ` / /
// ｲ● ､ ● ⊂⊃〈 /
// () へ | ＼〈
// >ｰ ､_ ィ │ ／／
// / へ / ﾉ＜| ＼＼
// ヽ_ﾉ (_／ │／／
// 7 |／
//
/*
__ _,--="=--,_ __
/ \." .-. "./ \
/ ,/ _ : : _ \/` \
\ `| /o\ :_: /o\ |\__/
`-'| :="~` _ `~"=: |
\` (_) `/
.-"-. \ | / .-"-.
.---{ }--| /,.-'-.,\ |--{ }---.
) (_)_)_) \_/`~-===-~`\_/ (_(_(_) (
( )
) (
'---------------------------------------'
*/
