文章目錄
- 前言
- 一、題目
- 英文原題
- 中文翻譯
- 輸入樣例
- 輸出樣例
- 二、解題思路
- 三、代碼
- 總結
前言
之前從沒有過要寫博客的想法，覺得會寫博客的都是大佬，自己的水平還是太菜，這個學期末和大佬們一起學習寫大作業肝課設，他們也不止一次的建議我可以試著寫博客，明天就是大年三十了，想著新的一年要有新氣象，所以打算在今天寫下第一篇博客，就像大佬說的，萬事開頭難，寫了總比沒寫好，正好最近為了實作元旦那天立下的flag，打了CF刷了題，這道Fence Painting我前前后后也改了差不多兩個晚上才AC，總共提交了差不多20次左右，答案錯誤，超時，超記憶體都出來了，所以記錄一下我對這道題的解法，就當做筆記了，
一、題目
英文原題
time limit per test：2 seconds
memory limit per test：256 megabytes
input：standard input
output：standard output
You have a fence consisting of n planks, where the i-th plank has the color ai. You want to repaint the fence in such a way that the i-th plank has the color bi.
You’ve invited m painters for this purpose. The j-th painter will arrive at the moment j and will recolor exactly one plank to color cj. 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 b you want? If it’s possible, print for each painter which plank he must paint.
Input
The first line contains one integer t (1≤t≤104) — the number of test cases. Then t test cases follow.
The first line of each test case contains two integers n and m (1≤n,m≤105) — the number of planks in the fence and the number of painters.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤n) — the initial colors of the fence.
The third line of each test case contains n integers b1,b2,…,bn (1≤bi≤n) — the desired colors of the fence.
The fourth line of each test case contains m integers c1,c2,…,cm (1≤cj≤n) — the colors painters have.
It’s guaranteed that the sum of n doesn’t exceed 105 and the sum of m doesn’t exceed 105 over all test cases.
Output
For each test case, output “NO” if it is impossible to achieve the coloring b.
Otherwise, print “YES” and m integers x1,x2,…,xm, where xj is the index of plank the j-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).
中文翻譯
（百度直接翻譯的有些地方的表述有點問題，所以稍微把翻譯不對或者不通順的地方自己修改了一下，但是因為我的六級到現在也還沒過（捂臉），所以有不通順的地方大家可以看看英文原文）
在做了這個瘋狂的夢之后，你終于醒了過來，決定四處走走，清醒一下頭腦，在外面你看到了你家的籬笆——如此樸素乏味，以至于你想重新粉刷一下，
你有一個由n塊木板組成的圍欄，其中第i塊木板的顏色是ai，你想重新粉刷籬笆，使第i塊木板的顏色為bi，
你為此邀請了m個畫家，第j個油漆工將在第j時刻到達，并將給正好一塊木板重新著色為cj，對于每個畫家你可以選擇哪個木板重新著色，但你不能拒絕他們，即每個畫家只能給一塊木板涂色，
你能得到你想要的顏色嗎？如果可能的話，為每個畫家列印他必須畫的木板，
輸入
第一行包含一個整數t（1≤t≤104）-測驗用例數，接著是t測驗用例，
每個測驗用例的第一行包含兩個整數n和m（1≤n，m≤105）-圍欄中木板的數量和油漆工的數量，
每個測驗用例的第二行包含n個整數a1，a2，…，an（1≤ai≤n）-圍欄的初始顏色，
每個測驗用例的第三行包含n個整數b1，b2，…，bn（1≤bi≤n）-柵欄的所需顏色，
每個測驗用例的第四行包含m個整數c1，c2，…，cm（1≤cj≤n）-畫家擁有的顏色，
在所有測驗用例中，保證n的和不超過105，m的和不超過105，
輸出
對于每個測驗用例，如果無法實作著色b，則輸出“NO”，
否則，列印“是”和m整數x1，x2，…，xm，其中xj是第j位畫家應該繪制的木板的索引，
您可以在任何情況下列印每個字母（例如，字串“yEs”、“yEs”、“yEs”和“yEs”都被認為是肯定答案），
輸入樣例
6
1 1
1
1
1
5 2
1 2 2 1 1
1 2 2 1 1
1 2
3 3
2 2 2
2 2 2
2 3 2
10 5
7 3 2 1 7 9 4 2 7 9
9 9 2 1 4 9 4 2 3 9
9 9 7 4 3
5 2
1 2 2 1 1
1 2 2 1 1
3 3
6 4
3 4 2 4 1 2
2 3 1 3 1 1
2 2 3 4
輸出樣例
YES
1
YES
2 2
YES
1 1 1
YES
2 1 9 5 9
NO
NO
二、解題思路
打比賽的時候思路比較亂，想到一點補一點，所以后來補題的時候重新理了一下思路，
首先先判斷是否需要改變顏色，即木板原來的顏色與最終的顏色是否有不一樣的地方，若有，flag1=1，并判斷油漆工是否有需要的顏色，若有，則flag2=1，例如：木板原來的顏色a為1，1，2，3，4；需要的顏色b為1，1，2，3，5；油漆工所持顏色c為1，2，4；則沒有所需要的顏色5，故不可能有解決方案，則flag2=0，注意這里不僅要判斷是否有需要的顏色，還需要判斷油漆工所持顏色的數量，因為每個油漆工只能給一塊木板著色，所以若有多塊需要修改為某種顏色的木板，則油漆工所持該顏色需達到指定數量才可以，例如：木板原來的顏色a為1，1，2，3，4；需要的顏色b為1，1，5，3，5；油漆工所持顏色c為1，2，5；因為只有一個油漆工有顏色5，但有兩塊木板需涂色為顏色5，所以該情況下沒有解決方案，
若所有需要修改顏色的木板都有油漆工持有對應顏色，則接著判斷每個油漆工所持顏色的用途，用途有兩種情況：一是用來改色，二是可有可無，即最好沒有，若是第一種用來改色的情況，則直接涂在需要修改顏色的木板上就行了，若是第二種情況，首先判斷是否有與油漆工所持顏色相同顏色的木板，若有，則直接涂在對應顏色的木板上，flag4=1,涂過之后木板的顏色不變；若沒有，則flag4=0,需要再次判斷涂上錯誤的顏色之后有沒有正確的顏色可覆寫掉錯誤的顏色，例如：某塊木板x原來的顏色為1，需修改為2，某油漆工有顏色3，若該油漆工到達的順序在持有顏色2的油漆工之前，則可先在x木板上涂上顏色3，等持有顏色2的油漆工到達可用顏色2覆寫顏色3，這樣對最終的結果就沒有影響了，若有可覆寫的顏色，則flag5=1;若沒有正確的顏色可覆寫，則flag5=0,沒有解決方案，
以上就是需要修改顏色的情況，若不需要修改顏色，則flag1=0，不需要修改顏色的情況比較簡單，我們只需要判斷油漆工涂色后是否可以維持原樣，具體做法與需要修改顏色的情況中對于油漆工的顏色用途為可有可無的情況做法一致，因為對于不需要修改顏色的情況來說，所有顏色都是可有可無的，
以下是我改掉WA后的代碼，答案是對了，但是在第四個測驗點超時了
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
int a[100005]={0};
int b[100005]={0};
int c[100005]={0};
int d[100005]={0};
int main()
{
int t,n,m;
int k=0;
int i,j,p;
int x,y;
int flag=1;
int flag1=0;
int flag2=0;
int flag3=0;
int flag4=0;
int flag5=0;
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d %d",&n,&m);
flag=1;
flag1=0;
flag2=0;
flag3=0;
flag4=0;
flag5=0;
for(j=0;j<n;j++){
scanf("%d",&a[j]);
}
for(j=0;j<n;j++){
scanf("%d",&b[j]);
}
for(j=0;j<m;j++){
scanf("%d",&c[j]);
d[j]=0;
}
for(j=0;j<n;j++){
if(a[j]!=b[j]){
flag1=1;
flag2=0;
for(k=0;k<m;k++){
if(c[k]==b[j]&&d[k]==0){
flag2=1;
d[k]=j+1;
break;
}
}
if(flag2==0){
flag=0;
break;
}
}
}
for(k=0;k<m;k++){
if(d[k]==0){
for(j=0;j<n;j++){
if(b[j]==c[k]){
d[k]=j+1;
break;
}
}
}
}
if(flag1==0){
for(k=0;k<m;k++){
for(j=0;j<n;j++){
if(c[k]==b[j]){
d[k]=j+1;
break;
}
}
}
for(k=0;k<m;k++){
if(d[k]==0){
flag5=0;
for(j=k+1;j<m;j++){
if(d[j]!=0){
flag5=1;
d[k]=d[j];
break;
}
}
if(flag5==0){
flag=0;
break;
}
}
}
}else{
for(k=0;k<m;k++){
if(d[k]==0){
flag4=0;
for(j=0;j<n;j++){
if(c[k]==b[j]){
flag4=1;
d[k]=j+1;
break;
}
}
if(flag4==0){
flag5=0;
for(j=k+1;j<m;j++){
if(d[j]!=0){
flag5=1;
d[k]=d[j];
break;
}
}
if(flag5==0){
flag=0;
break;
}
}
}
}
}
if(flag==0){
printf("NO");
}else{
printf("YES\n");
printf("%d",d[0]);
for(k=1;k<m;k++){
printf(" %d",d[k]);
}
}
printf("\n");
}
return 0;
}
里面有很多地方用到了雙重回圈，時間復雜度大概是O(nm)，所以出現超時也在意料之中，
但是我太菜了（捂臉），只會用空間換時間，也正是因為用空間換時間所以后來試出了超出記憶體的答案，但總歸最后終于AC了，真的感動，
優化的方法添加了三個陣列e,f,g(當時懶得想命名了所以先用efg了)，e是一個二維陣列，e[i][j]代表油漆工擁有顏色的所在位置，i代表顏色，j代表是第幾個該顏色，例如：油漆工所持顏色為1,1,2,3,4,5，則e[1][0]=0,e[1][1]=1,e[2][0]=2,e[3][0]=3,e[4][0]=4,e[5][0]=5，f[i]代表油漆工所持顏色i的數量，以上例子中，f[1]=2,f[2]=1,f[3]=1,f[4]=1,f[5]=1，g[i]代表木板所需顏色即陣列b中每種顏色出現的最后一個位置，例如：陣列b為1，1，2，3，4，2，則g[1]=1,g[2]=5,g[3]=3,g[4]=4，
有了這三個陣列后，有些原本需要雙重回圈判斷的地方現在只需要一重回圈就可以得出結果，這樣就大大節省了時間，
在優化了一半的時候先提交了一次，沒想到居然過了，后來把需要優化的地方都改了之后差不多快了10倍，但是不得不說記憶體消耗真的太大了（捂臉）
三、代碼
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
int a[100001]={0};//木板原來的顏色
int b[100001]={0};//木板最終的顏色
int c[100001]={0};//油漆工所持顏色
int d[100001]={0};//油漆工涂色位置
int e[100001][501];//油漆工有的顏色所在位置
int f[100001]={0};//油漆工擁有的每種顏色數量
int g[100001]={0};//最終每種顏色出現的最后一個位置
int main()
{
int t,n,m;
int i,j,k;
int flag=1;//是否有解決方案（默認有）
int flag1=0;//判斷是否需要涂色
int flag2=0;//若需要改色，判斷油漆工是否有需要的顏色
//int flag3=0;//不需要了，忽略就好
int flag4=0;//判斷木板最終的顏色中是否有木板顏色與油漆工所持顏色相同
int flag5=0;//判斷木板涂上顏色后是否有正確顏色可覆寫
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d %d",&n,&m);
flag=1;
flag1=0;
flag2=0;
//flag3=0;
flag4=0;
flag5=0;
for(j=0;j<n;j++){
scanf("%d",&a[j]);
g[j]=-1;
}
g[n]=-1;
for(j=0;j<n;j++){
scanf("%d",&b[j]);
g[b[j]]=j;
}
for(j=0;j<m;j++){
scanf("%d",&c[j]);
d[j]=0;
e[c[j]][f[c[j]]]=j;
f[c[j]]++;
}
for(j=0;j<n;j++){
if(a[j]!=b[j]){//現有與預期不一樣
flag1=1;//需要改色
flag2=0;//默認油漆工沒有需要顏色
if(f[b[j]]>0){//油漆工有顏色
for(k=0;k<f[b[j]];k++){
if(d[e[b[j]][k]]==0){//該顏色還未使用
flag2=1;
d[e[b[j]][k]]=j+1;
break;
}
}
}
if(flag2==0){
flag=0;
break;
}
}
}
if(flag!=0){
for(k=0;k<m;k++){//保證每個木板有的顏色都被用到
if(d[k]==0){//如果有木板需要的顏色但還未用到
if(g[c[k]]!=-1){
d[k]=g[c[k]]+1;
}
}
}
if(flag1==0){//不需要改色
for(k=0;k<m;k++){
if(g[c[k]]!=-1){
d[k]=g[c[k]]+1;
}
}
for(k=0;k<m;k++){
if(d[k]==0){//若有油漆工還未涂色（有不是木板所需顏色）
flag5=0;
for(j=k+1;j<m;j++){
if(d[j]!=0){//若在該油漆工之后有可覆寫的顏色
flag5=1;
d[k]=d[j];
break;
}
}
if(flag5==0){
flag=0;
break;
}
}
}
}else{//需要改色
for(k=0;k<m;k++){
if(d[k]==0){//可有可無的顏色
flag4=0;
if(g[c[k]]!=-1){
flag4=1;
d[k]=g[c[k]]+1;
}
if(flag4==0){//沒有木板顏色與之相同
flag5=0;
for(j=k+1;j<m;j++){
if(d[j]!=0){//在其后有顏色可覆寫
flag5=1;
d[k]=d[j];
break;
}
}
if(flag5==0){
flag=0;
break;
}
}
}
}
}
}
if(flag==0){
printf("NO");
}else{
printf("YES\n");
printf("%d",d[0]);
for(k=1;k<m;k++){
printf(" %d",d[k]);
}
}
printf("\n");
for(j=0;j<m;j++){
f[c[j]]=0;
}
}
return 0;
}
總結
寫到這里已經過了0點了，總的來說這個方法感覺沒有很好，但至少能過當時真的就很開心，特別是在看到一個又一個Wrong answer，Time limit exceeded，Memory limit exceeded甚至還有不知道為啥的Compilation error之后，綠色的AC真的可以算得上是驚喜了，其實這個方法還是有bug，比如說當每個油漆工所持單個顏色的個數超過500就會出問題，因為e陣列只定義到e[100001][501]，再大的話就會超記憶體了，然后編碼習慣方面也有很大改進的空間，有些細節說不定可以再簡化改進一下，還沒有去看CF上其他大佬們的代碼，等有時間去看看有沒有其他更好的解題方法，這篇博客就當是磕了兩個晚上的一個記錄吧，最后給大家拜個早年，新年快樂！！新的一年沖沖沖！！
最后的最后，附上我多達21次的提交記錄（捂臉），其中有幾次提交是為了看樣例的輸入資料，改bug真的心態要崩了
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258994.html
標籤：其他