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

2024-03-16 19:52

本文主要是介绍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 ≤ 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)格开始。每隔一秒钟,下面两个动作会相继发生:
    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)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816556

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

CSS实现DIV三角形

本文内容收集来自网络 #triangle-up {width: 0;height: 0;border-left: 50px solid transparent;border-right: 50px solid transparent;border-bottom: 100px solid red;} #triangle-down {width: 0;height: 0;bor

创建一个大的DIV,里面的包含两个DIV是可以自由移动

创建一个大的DIV,里面的包含两个DIV是可以自由移动 <body>         <div style="position: relative; background:#DDF8CF;line-height: 50px"> <div style="text-align: center; width: 100%;padding-top: 0px;"><h3>定&nbsp;位&nbsp;

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

CF#271 (Div. 2) D.(dp)

D. Flowers time limit per test 1.5 seconds memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/474/problem/D We s

CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

B. Candy Boxes time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output 题目链接: http://codeforces.com/contest/488/problem/B There