题目链接:https://codeforces.com/contest/1504/problem/B

题目大意

有$0$和$1$组成的序列、每次可以选中前$k$个数字反转(但要求前k个数字一半是$0$一半是$1$),问$A$能否转换到$B$

题目解析

可以探究到,我们只需要依次判断最后的数字能不能被修改。因为如果不能修改,再怎么修改也修改也不能使序列变成$B$。所以我们只需要统计$0$、$1$的个数根据题目要求模拟。最终得到答案。时间复杂度$O(Tn)$

Code:

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ios ios::sync_with_stdio(false);
#define CF true
 
using namespace std;
 
const int N = 1e5 + 5;
int a[N], n, m, T;
 
int main()
{
    #ifdef CF
        cin >> T;
        while (T -- )
        {
    #endif
            int len;
            cin >> len;
            int zero = 0, one = 0;
            string str, strb;
            cin >> str >> strb;
            int k = 0;
            for(int i = 0; i < len; i ++ )
            {
                str[i] -= '0';
                if (str[i] == 0)
                {
                    zero ++;
                }
                else
                {
                    one ++;
                }
            }
            bool flag = false;
            for (int i = len - 1; i >= 0; i -- )
            {
                int ts = (str[i] + k) % 2;
                if (ts != strb[i] - '0')
                {
                    if (zero == one)
                    {
                        k ++;
                    }
                    else
                    {
                        flag = true;
                        break;
                    }
                }
                ts = (str[i] + k) % 2;
                if (ts == 0)
                {
                    zero --;
                }
                else
                {
                    one --;
                }
            }
            if (flag)
            {
                cout << "NO";
            }
            else
            {
                cout << "YES";
            }
            cout << endl;
    #ifdef CF
        }
    #endif
    return 0;
}

后记:

好久都没写过题解、博客了。最近事情太多了....也不保证啥时候能再写.....另外,博客主题短期内也不太想修改...懒得折腾了....

Last modification:April 5th, 2021 at 04:57 pm
End.