A. ABC

题目大意

给定一个二进制字符串,如果不含长度大于1的回文子串,就直接输出“YES”
否则就把这个字符串重新排序,
如果重排后可以得到不包含回文子串的字符串的话就输出“YES”
否则输出“NO”

解题思路

可以看到一个特殊的性质,对于长度大于2的二进制字符串,由于只含有0和1,不管怎么排都会构成长度大于1的回文子串
例子:长度为3的二进制字符串001,011,111,110,101,010,101,000..都有回文子串
而对于长度小于等于2的二进制字符串,只有11,00这两种有回文子串

代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    cin >> T;

    while (T--)
    {
        int n;
        string s;
        cin >> n >> s;

        if (n > 2 || s == "11" || s == "00")    puts("NO");
        else puts("YES");
    }
    return 0;
}

C. Strange Test(枚举)

题目大意

给两个数 $a,b$ 你可以执行任意次的以下的三个操作。
[1] $a=a+1$
[2] $b=b+1$
[3] $a=a|b$ (这里的or 为按位或)

问最少多少次的操作,可以使得 $a=b$

解题思路

对于或操作我们有 $a|b >= max(a,b)$(只会让值变大)
题目规定 $a < b$ ,我们发现有两个方式可以使得二者相等
1)先增加 $a$ 的值,然后进行或操作,最后通过增加 $b$ 的值使得二者相等。
2)先增加 $b$ 的值,如果进行或操作,直接使得二者相等。

Code

#include <bits/stdc++.h>
using namespace std;

void solve()
{   
    int a, b;
    cin >> a >> b;

    int res = b - a;
    for (int i = a; i <= b; i++)
        res = min(res, i - a + (i | b) - b + 1);

    for (int i = b; i <= 4 * b; i++)
        if ((i | a) == i) res = min(res, i - b + 1);

    cout << res << endl;
}

int main()
{
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}
上一篇 下一篇