CF1927C 题解

yyrwlj · 2024-02-07 21:26:10 · 题解

题意简述

给定两个长度分别为 n 和 m 的序列，分别从两个序列中取出 \frac{k}{2} 个数，是否能使取出的数恰好排列成 1 到 k。

思路

对于 1 到 k 的每一个数，都有三种情况：

1. 两个序列都没有。

2. 两个序列都有。

3. 只有一个序列有。

对于第一种情况，那就肯定无解了。

对于第二种情况，就后考虑，随机应变。

对于第三种情况，因为每个序列要取出 \frac{k}{2} 个数，那么如果必须某个序列的数大于 \frac{k}{2} 个，那么就无解，否则有解。

Code

const int N = 200005;
typedef long long LL;
typedef pair<int, int> PII;
int a[N], b[N];
bool f[N * 2][2];
void work()
{
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for (int i=1;i<=m;i++)
        scanf("%d", &b[i]);
    for (int i=1;i<=k;i++)
        f[i][0] = f[i][1] = 0;
    for (int i=1;i<=n;i++)
        if (a[i] <= k)
            f[a[i]][0] = true;
    for (int i=1;i<=m;i++)
        if (b[i] <= k)
            f[b[i]][1] = true;
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i=1;i<=k;i++)
    {
        if (f[i][0] && f[i][1])
            c3 ++;
        else if (f[i][0])
            c1 ++;
        else if (f[i][1])
            c2 ++;
        else
        {
            puts("NO");
            return;
        }
    }
    int k2 = k / 2;
    if (c1 > k2 || c2 > k2)
        puts("NO");
    else
        puts("YES");
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}