Educational Codeforces Round 163 (Rated for Div. 2) (A~C)

本文主要是介绍Educational Codeforces Round 163 (Rated for Div. 2) (A~C)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Educational Codeforces Round 163 (Rated for Div. 2) (A~C)

目录：A B 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 ≤ a_i ≤ 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\ |\__/`-'| :="~` _ `~"=: |\`     (_)     `/.-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.)  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				))                                     (
'---------------------------------------'
*/

这篇关于Educational Codeforces Round 163 (Rated for Div. 2) (A~C)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！