Educational Codeforces Round 154 (Rated for Div. 2)（A—D）
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;
}
D. Sorting By Multiplication
思路
- 观察发现，每遇到一个\(a_i≥a_{i-1}\) 都可以取\(1\)~\(i\) 取\((a_l,a_r)*x\) 使得前\(i\)个数变成负数且单调递减，同理每遇到一个\(a_i≥a_{i+1}\) 都可以取\(1\)~\(i+1\) 取\((a_l,a_r)*x\) 使得前\(i+1\)个数变成正数且单调递增
- 无论开始是怎样的数组，后来都会变成前缀是负数(单调递减)，后缀是正数(单调递增) 注：前缀和后缀个数都有可能为0
- 从前到后扫一遍求前缀需要改变的个数，用一个数组记录下。然后从后往前扫一遍求后缀需要改变的个数，
- 最后求出每个\(i\)对应的前缀和后缀的和的最小值即可(注：无前缀时不需要把前缀*(-1)，不用+1)
具体看代码实现过程
代码实现
/*******************************
| Author: CHC
| Problem: D. Sorting By Multiplication
| Contest: Codeforces - Educational Codeforces Round 154 (Rated for Div. 2)
| URL: https://codeforces.com/contest/1861/problem/D
| When: 2023-09-04 17:47:30
|
| Memory: 256 MB
| Time: 2000 ms
*******************************/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
//让最后的数组形式变为前缀为负数(单调递减)+后缀为正数(单调递增)
vector<int> b(n + 2, 0);//前缀需要改变的
vector<int> c(n + 2, 0);//后缀需要改变的
for (int i = 1; i <= n; i++) cin >> a[i];
//前缀严格递减需要改变的
for (int i = 2; i <= n; i++)
b[i] += b[i - 1] + (a[i - 1] <= a[i]);
//后缀严格递增需要改变的
for (int i = n - 1; i >= 1; i--)
c[i] += c[i + 1] + (a[i] >= a[i + 1]);
//前缀最后需要*(-1)把前缀变为递增的，当后缀需要改变的最小时且不需要前缀(i!=1)时，不用再*(-1)，不需要+1
int res = 1e9 + 5;
for (int i = 1; i <= n + 1; i++)
res = min(res, b[i - 1] + c[i] + (i != 1));
cout << res << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}