Fence Painting
题意
按顺序使用c 数组中的元素 将 a数组 变成 b 数组 问是否可能，若可能 输出c 中每个元素应该放在a 中的哪个位置
思路
先找到哪些元素需要修改存在q 里
对于c中最后一个元素c[m] 有以下三种情况
1.需要修改的数中有c[m]
2.需要修改的数中没有c[m] 但是不需要修改的数中有c[m]
3.b中没有 c[m]
用 las 表示c[m] 应该修改b 中的哪一个数字的下标
对于 1 直接令las=q[c[m]].back() 即可
对于 2 在 b bb 中找到一个c[m] 对应的下标即可
对于 3 肯定无解 因为c[m] 是最后一个修改的
对于1、2 按顺序遍历c 在q 中找到应该修改哪个位置 如果存在c[i] 不在q 中 那么直接让他先修改c 中最后一个数需要修改的位置 即las 反正最后会被覆盖
然后遍历判断一下q 中改被修改的数是否都被修改了 最后输出答案即可
代码
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 998244353 #define endl '\n' using namespace std; typedef long long LL; typedef pair<int, int>PII; const int N = 100100; int n, m; int a[N], b[N], c[N]; // a -> b by c vector<int>q[N]; void solve() { cin >> n >> m; for (int i = 1; i <= n; ++i)q[i].clear(); for (int i = 1; i <= n; ++i)scanf("%d", a + i); for (int i = 1; i <= n; ++i) { scanf("%d", b + i); if (b[i] != a[i]) { q[b[i]].push_back(i); //找到每一个颜色需要修改的位置 } } for (int i = 1; i <= m; ++i)scanf("%d", c + i); int las = -1; if (q[c[m]].size()) { las = q[c[m]].back(); q[c[m]].pop_back(); } else { for (int i = 1; i <= n; ++i) { if (b[i] == c[m]) { las = i; break; } } } if (las == -1) { puts("NO"); return; } vector<int>res(m); res[m - 1] = las; for (int i = 1; i < m; ++i) { if (q[c[i]].size()) { res[i - 1] = q[c[i]].back(); q[c[i]].pop_back(); } else res[i - 1] = las; } for (int i = 1; i <= n; ++i) { if (q[i].size()) { puts("NO"); return; } } puts("YES"); for (int i = 1; i <= m; ++i) { printf("%d%c", res[i - 1], i == m ? '\n' : ' '); } } int main() { int t; cin >> t; while (t--) solve(); return 0; }
