Educational Codeforces Round 154 (Rated for Div. 2)（A—C）
A. Prime Deletion
思路：
从1到9，每个数后面都可以加一个数构成一个含有两个数的质数，只需要从s[1]~s[9]中找到一个数与s[0]构成质数即可
代码实现
/*******************************
| Author: CHC
| Problem: A. Prime Deletion
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/A
| When: 2023-08-31 22:55:13
|
| Memory: 512 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[11] = {0, 13, 23, 31, 41, 53, 61, 71, 83, 97};
void solve()
{
string s;
cin >> s;
for (int i = 1; i < 10; i++)
if (s[0] - '0' == i) {cout << a[i] << endl; break;}
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
B. Two Binary Strings
思路：
观察样例即可发现两个字符串只要在相同位置都有01存在就能成功实现转换后两个字符串相等
代码实现
/*******************************
| Author: CHC
| Problem: B. Two Binary Strings
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/B
| When: 2023-09-02 10:10:12
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
string a, b;
cin >> a >> b;
for (int i = 1; i < a.size(); i++)
{
if (a[i - 1] == '0' && a[i] == '1' && b[i - 1] == a[i - 1] && b[i] == a[i])
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}
C. Queries for the Array
思路
可以先假设字符串是可以成立的，那么接下来就判断它什么时间是不会成立就行了。
只有尾部增删操作，可以用 \(sum\) 记录当前整数的个数,用 \(s1\) 记录当前 \(s1\) 个数有序(这里用有序代表"\(a_1≤⋯≤a_n\)")，用 \(s2\) 记录当前 \(s2\) 个数无序。
s[i] == 1但前面有无序时(s2 ≤ sum)不会成立，具体看代码s[i] == 0但前面有无序时(s1 ≥ sum)不会成立，具体看代码
代码实现
/*******************************
| Author: CHC
| Problem: C. Queries for the Array
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/C
| When: 2023-08-31 23:25:51
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9
void solve()
{
string s;
cin >> s;
int sum = 0, s1 = 1, s2 = INF;//sum记录当前整数个数，s1记录前s1个数递增，s2记录前s2个数不满足递增条件
for (char c : s) {
if (c == '+') sum++;
else if (c == '-') {
sum--;
if (sum > 0 && s1 > sum) s1 = sum;//前sum个数递增
if (s2 > sum) s2 = INF;//不能判断前s2-1个整数的无序性，s2赋值为INF
}
//两种判断“NO”的情况
else if (c == '1') {
if (s2 <= sum) { cout << "NO\n"; return; }//c==1但前面有无序时
s1 = max(s1, sum);//否则更新s1
}
else {
if (s1 >= sum) { cout << "NO\n"; return; }//c==0但前sum个数都是有序时
s2 = min(s2, sum);//否则更新s2
}
}
cout << "YES\n";
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}