• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1365B 题解

开发技术 开发技术 1周前 (05-04) 11次浏览

Luogu-CF1365B

题意分析

通过模拟样例,发现只要 (b) 中同时出现 (0)(1),就可以实现在 (n) 次成功交换到位。

所以,我们只对 (b) 只为 (0) 或只为 (1) 时的情况考虑。

很容易发现,此时是不能交换的。那么当且仅当此时的 (a_i) 满足不下降才符合题目要求。

所以,根据以上性质进行特判,即可通过此题。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;

ll n, T, m;
ll a[10000], b[10000];
bool ok1, ok0;

void Clear() //初始化,清空
{
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    ok1 = 0;
    ok0 = 0;
}

bool check() //判断 b[i] 全是1 或 全是0
{
    if (ok1 == 0 && ok0 == 1)
        return 1;
    if (ok1 == 1 && ok0 == 0)
        return 1;
    return 0;
}

int main()
{
    T = read();
    while (T--)
    {
        Clear();
        n = read();
        for (int i = 1; i <= n; ++i)
            a[i] = read();

        for (int i = 1; i <= n; ++i)
        {
            ll x = read();
            b[i] = x;
            if (x == 0) ok0 = 1; 
            if (x == 1) ok1 = 1;
        }
        
        if (check()) //判断b 全是0 或 全是1 
        {
            bool ook = 0;
            for (int i = 1; i < n; ++i)
            {
                if (a[i] > a[i + 1]) //判断 a序列 是否不下降
                {
                    ook = 1;
                    break;
                }
            }
            if (ook == 1)
                puts("No");
            else
                puts("Yes");
        }
        else
            puts("Yes");
    }
}

程序员灯塔
转载请注明原文链接:CF1365B 题解
喜欢 (0)