Educational Codeforces Round 154 (Rated for Div. 2)（A

这篇具有很好参考价值的文章主要介绍了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\) 个数无序。文章来源地址https://www.toymoban.com/news/detail-691395.html

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;
}

到了这里，关于Educational Codeforces Round 154 (Rated for Div. 2)（A—C）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！