CF1481C Fence Painting

Fence Painting - 洛谷

题目描述

You finally woke up after this crazy dream and decided to walk around to clear your head. Outside you saw your house's fence — so plain and boring, that you'd like to repaint it.

You have a fence consisting of nn planks, where the ii -th plank has the color a_iai​ . You want to repaint the fence in such a way that the ii -th plank has the color b_ibi​ .

You've invited mm painters for this purpose. The jj -th painter will arrive at the moment jj and will recolor exactly one plank to color c_jcj​ . For each painter you can choose which plank to recolor, but you can't turn them down, i. e. each painter has to color exactly one plank.

Can you get the coloring bb you want? If it's possible, print for each painter which plank he must paint.

输入格式

The first line contains one integer tt ( 1 \le t \le 10^41≤t≤104 ) — the number of test cases. Then tt test cases follow.

The first line of each test case contains two integers nn and mm ( 1 \le n, m \le 10^51≤n,m≤105 ) — the number of planks in the fence and the number of painters.

The second line of each test case contains nn integers a_1, a_2, \dots, a_na1​,a2​,…,an​ ( 1 \le a_i \le n1≤ai​≤n ) — the initial colors of the fence.

The third line of each test case contains nn integers b_1, b_2, \dots, b_nb1​,b2​,…,bn​ ( 1 \le b_i \le n1≤bi​≤n ) — the desired colors of the fence.

The fourth line of each test case contains mm integers c_1, c_2, \dots, c_mc1​,c2​,…,cm​ ( 1 \le c_j \le n1≤cj​≤n ) — the colors painters have.

It's guaranteed that the sum of nn doesn't exceed 10^5105 and the sum of mm doesn't exceed 10^5105 over all test cases.

输出格式

For each test case, output "NO" if it is impossible to achieve the coloring bb .

Otherwise, print "YES" and mm integers x_1, x_2, \dots, x_mx1​,x2​,…,xm​ , where x_jxj​ is the index of plank the jj -th painter should paint.

You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" are all recognized as positive answer).

 每个木匠必须涂一块而且必须按照来的顺序涂。

对于每一块木板，我们只需要倒着遍历木匠，来找到使得ai变成bi的ci,对于ai==bi的可以先不做考虑，这样做是为了让更多ai!=bi的有机会转变成bi,是一种贪心的思想。

在遍历的过程中，我们给木匠打上标记

00000id10000id20000id3 像这样的，在第一个到标记id1的木匠，全涂id1的木板，涂id1之后到涂id2的木匠，全涂id2的木板，这样就避免了乱涂导致的混乱。反正最后我们会变成id，那么之前涂的什么也就无所谓了。

这样做是不够的，第一种情况，全部ai==bi,但是我们还必须把每个木匠都给用上，而且最后一个木匠用完之后再无更改机会，也就是最后一个木匠必须有一个对应的bi,我们找到这个bi所在的i,那么1-m个木匠全涂i就OK了，否则无解

第二种情况，我们找着找着，发现ai!=bi的时候，我们再也找不到一个没被标记的ci==bi，这样也是无解

第三种情况，也是坑点，那就是根据最后一个木匠的特殊性（无法再更改）也就是还要特判一下最后一个木匠是不是已经被标记了，如果没有，随便找一个bi==c[m]即可，否则无解

第四种情况，皆大欢喜，按照我们原来的思路模拟即可

# include<iostream>
# include<set>
# include<algorithm>
# include<cstring>

using namespace std;

typedef long long int ll;

int a[100000+10],b[100000+10];
int c[100000+10];
int id[100000+10];

int main ()
{

    //倒着找  ，找到第一个bi

    //


    int t;

    cin>>t;

    while(t--)
    {
        int n,m;

        cin>>n>>m;

        memset(id,0,sizeof(id));


        for(int i=1; i<=n; i++)
        {
            cin>>a[i];

        }
        for(int i=1; i<=n; i++)
        {
            cin>>b[i];

        }

        for(int i=1; i<=m; i++)
        {
            cin>>c[i];

        }
        int flag=0;

        int check=0;


        for(int i=1; i<=n; i++)
        {
            if(a[i]==b[i])
                continue;

            flag=1;

            check=0;

            for(int j=m; j>=1; j--)
            {
                if(id[j]==0&&c[j]==b[i])
                {
                    id[j]=i;

                    check=1;

                    break;

                }
            }

            if(check==0)
            {

                flag=-1;

                break;

            }

        }

        if(flag==-1)
        {
            cout<<"No"<<'\n';

        }
        else if(flag==0)
        {
            flag=0;

            int ans=0;
            for(int i=1; i<=n; i++)
            {
                if(c[m]==b[i])
                {
                    flag=1;

                    ans=i;

                    break;

                }
            }

            if(!flag)
            {
                cout<<"No"<<'\n';

            }
            else
            {
                cout<<"YES"<<'\n';

                for(int i=1; i<=m; i++)
                {
                    cout<<ans<<" ";

                }

                cout<<'\n';

            }
        }
        else
        {

            if(id[m]==0)
            {

                for(int i=1; i<=n; i++)
                {
                    if(c[m]==b[i])
                    {

                        id[m]=i;

                        break;

                    }
                }

                if(id[m]==0)
                {
                    cout<<"No"<<endl;

                    continue;

                }
            }

            int pre=1;

            cout<<"YES"<<'\n';

            for(int i=1; i<=m; i++)
            {
                if(id[i])
                {
                    for(int j=pre; j<=i; j++)
                    {
                        cout<<id[i]<<" ";

                    }

                    pre=i+1;
                }
            }

            cout<<endl;
        }
    }

    return 0;

}