Educational Codeforces Round 105 题解报告

【解题报告】Educational Codeforces Round 105 | ABC

A：ABC String
B：Berland Crossword
C：1D Sokoban

A：ABC String |思维

• 题意
  给定一串由’A’,‘B’,'C’组成的字符串，每个字母可选择变成”(“或”)“，是否存在能变成正则表达式的情况。
• 思路
  首先可以确定头和尾的字母一定不相同并且变成的括号相反，所以不是头和尾的那个字母就有两种变化情况，正确的情况是变化后两种括号数量相等。然后从左到右遍历，每一个出现的")"符号一定在前面有“(”符号相匹配，用两个sum更新两种符号出现的数量判断即可。

#include 
using namespace std;
#define qc ios::sync_with_stdio(0);
int book[51];int main() {qc;cin.tie(0);string s;int t;cin >> t;while (t--) {cin >> s;int n = s.length();if (s[0] == s[n - 1]) {cout << "NO" << endl;continue;}char a = s[0], b = s[n - 1];char c;for (int i = 0; i < n; i++) {if (s[i] != a && s[i] != b) {c = s[i];break;}}int aa = 0, bb = 0, cc = 0;for (int i = 0; i < n; i++) {if (s[i] == a)aa++;else if (s[i] == b)bb++;else if (s[i] == c)cc++;}if (aa + cc != bb && bb + cc != aa) {cout << "NO" << endl;continue;}if (aa < bb) {for (int i = 0; i < n; i++)if (s[i] == c)s[i] = a;}if (bb < aa) {for (int i = 0; i < n; i++)if (s[i] == c)s[i] = b;}int aaa = 0, bbb = 0;int flag = 0;for (int i = 0; i < n && flag == 0; i++) {if (s[i] == a) {aaa++;}if (s[i] == b) {bbb++;if (bbb > aaa) {flag = 1;break;}}}if (flag == 1)cout << "NO" << endl;elsecout << "YES" << endl;}
}

B：Berland Crossword|枚举，思维

• 题意
  给定一个n*n的空白矩阵，同时给你首行末行，首列末列的黑格子数，你可以选择任意方格染成黑色，是否存在某种操作使得结果满足所给条件。

• 思路
  可以发现影响其余行列的格子只有两个端点，所以对于黑格子数k 如果k=n，说明当前行（列）格子全部染黑，所以与其相接的两列（行）至少存在的黑格子数(设为sum1)+1，两列（行）总共的黑格子数(设为sum2)+2。
  如果k=n-1，说明与其相接的两列（行）会有一列（行）至少存在的黑格子数+1，两列（行）总共的黑格子数+1。
  将行（列）统计完毕后再去判断相接的两列（行）是否满足单列（行）k>=sum1，是否满足两列（行）的k1+k2>=sum2。
  （以上是一种思维的解题方法，还可以枚举四个端点黑格子数的情况进行判断，一共是2^4次循环）

• 思路1代码

#include 
using namespace std;
#define qc ios::sync_with_stdio(0);
int a[6];
int n;int can(int a, int b, int c, int d) {int flag = 0;int sum2 = 0;int sum1 = 0;if (a == n) {sum1++;sum2 += 2;} else if (a == n - 1)sum2++;if (c == n) {sum1++;sum2 += 2;} else if (c == n - 1)sum2++;if (b + d < sum2)flag = 1;if (b < sum1 || d < sum1)flag = 1;return flag;
}int main() {qc;cin.tie(0);int t;cin >> t;int  u, r, d, l;while (t--) {int ans = 0;cin >> n >> u >> r >> d >> l;if (can(u, r, d, l) == 1)ans = 1;if (can(r, d, l, u) == 1)ans = 1;if (ans)cout << "NO" << endl;elsecout << "YES" << endl;}
}

• 思路2代码

#include 
using namespace std;
#define qc ios::sync_with_stdio(0);
int a[6];int main() {qc;cin.tie(0);int t;cin >> t;while (t--) {int n;int u, r, d, l;int ans = 1;cin >> n >> u >> r >> d >> l;for (int i1 = 0; i1 <= 1 && ans; i1++)for (int i2 = 0; i2 <= 1 && ans; i2++)for (int i3 = 0; i3 <= 1 && ans; i3++)for (int i4 = 0; i4 <= 1 && ans; i4++)if (u >= i1 + i2 && r >= i2 + i3 && d >= i3 + i4 && l >= i4 + i1) {if (n - (2 - i1 - i2) >= u && n - (2 - i2 - i3) >= r && n - (2 - i3 - i4) >= d && n - (2 - i4 - i1) >= l)ans = 0;}if (ans)cout << "NO\n";if (!ans)cout << "YES\n";}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！