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

A. Prime Deletion

题意：给定一个包含1到9的字符串，要求删除最多7个字符，是否可以表示为一个质数。

思路：暴力枚举所有的两位数即可。

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N = 100010;
typedef pair<int, int> pll;
int prime[N], cnt;
bool st[N];
 
int get_prime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])prime[cnt++] = i;
        for (int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0)break;
        }
    }
    return cnt;
}
void solve()
{
    string arr;
    cin >> arr;
    for(int i = 0; i < arr.size(); i++)
        for (int j = i + 1; j < arr.size(); j++)
        {
            int num = (arr[i] - '0') * 10 + arr[j] - '0';
            if (!st[num])
            {
                cout << num << endl;
                return;
            }
        }
    
}
signed main()
{
    int t;
    cin >> t;
    get_prime(100);
    //t = 1;
    while (t--)
    {
        solve();
    }
}

B. Two Binary Strings

题意：给定两个0开头，1结尾，只包含01的字符串，可以对两个字符串进行任意次如下操作：选定两个相同的字符，将两者之间的所有字符都变为这个字符。问是否可以使两个字符串相同。

思路：如果能找到一个位置使得在这个位置上，两个字符串都为1，且左边为0，那么就可以做到。

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
const int N = 100010;
typedef pair<int, int> pll;
int prime[N], cnt;
bool st[N];
void solve()
{
    string a, b;
    cin >> a >> b;
    for (int i = 1; i < a.size(); i++)
    {
        if (a[i] == b[i] && a[i] == '1' && (a[i - 1] == b[i - 1] && a[i - 1] == '0'))
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
signed main()
{
    int t;
    cin >> t;
    //get_prime(100);
    //t = 1;
    while (t--)
    {
        solve();
    }
}

C. Queries for the Array

题意：给定一个字符串，”+“代表向空数组中加入一个数，”-“代表删除空数组最后一个数，”1“表示查询数组此时为一个非递减序列（有序），”0“表示数组此时不为一个非递减序列（无序）。问给出的字符串是否合法。

思路：记录三种状态，总长度n，初始为0；最小min_s，初始为1；最小无序长度min_ns，初始为0；一共四种情况：

a[i] == "+"：只会影响len，len++，min_s和min_ns都不会变化。

a[i] == "-"：首先len要减一，如果min_s >= len的话，min_s需要更新，min_s = min(min_s, len);如果min_ns此时大于len的话，在len的范围里无法判断是否无序，则min_ns = 0。

a[i] == "1"：如果此时min_ns != 0，说明序列此时一定不是有序，输出NO；如果min_ns == 0，则更新min_s，min_s = len。

a[i] == "0":如果此时len < 2或min_s == len，则序列一定有序，输出NO；否则可能成立，更新min_ns，如果min_ns此时为0，则min_ns = len，否则min_ns = min（min_ns， len）。

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
typedef pair<int, int> pll;
void solve()
{
    string arr;
    cin >> arr;
    
    int len = 0, min_s = 1, min_ns = 0;
    for (int i = 0; i <= arr.size(); i++)
    {
        len += (arr[i] == '+');
        if (arr[i] == '-')
        {
            len--;
            min_s = min(min_s, len);
            if (min_ns > len)min_ns = 0;
        }
        else if (arr[i] == '1')
        {
            if (min_ns != 0)
            {
                cout << "NO" << endl;
                return;
            }
            min_s = len;
        }
        else if (arr[i] == '0')
        {
            if (len < 2 || min_s == len)
            {
                cout << "NO" << endl;
                return;
            }
            if (min_ns == 0)
            {
                min_ns = len;
            }
            else min_ns = min(min_ns, len);
        }
    }
    cout << "YES" << endl;
}
signed main()
{
    int t;
    cin >> t;
    //get_prime(100);
    //t = 1;
    while (t--)
    {
        solve();
    }
}