CodeForces CF1980C Sofia and the Lost Operations 题解
嗨嗨，又来了啊，蒟蒻再来一篇题解
Sofia and the Lost Operations
题面翻译
索菲亚有一个包含$n$
个整数的数组$a[1],a[2],…,a[n]$
。有一天她对这个数组感到厌倦，于是决定顺序地对其应用$m$
个修改操作。
每个修改操作由一对数字$⟨cj,dj⟩$
描述，意味着数组中索引为$c[j]$
的元素应该被赋值为$d[j]$
，即执行赋值$a[c[j]]=d[j]$
。在所有修改操作顺序应用后，索菲亚丢弃了结果数组。
最近，你找到了一个包含$n$
个整数的数组$b[1],b[2],…,b[n]$
。你想知道这个数组是否是索菲亚的数组。你知道原始数组的值，以及值$d[1],d[2],…,d[m]$
。值$c[1],c[2],…,c[m]$
被证明丢失了。
是否存在一个序列$c[1],c[2],…,c[m]$
，使得将修改操作顺序应用到数组$a[1],a[2],…,a[n]$
上$⟨c[1],d[1],⟩,⟨c[2],d[2],⟩,…,⟨c[m],d[m]⟩$
，将其转换为数组$b[1],b[2],…,b[n]$
？
输入
第一行包含一个整数$t$
（$1≤t≤10^4$
）— 测试用例的数量。
然后是每个测试用例的描述。
每个测试用例的第一行包含一个整数$n$
（$1≤n≤2⋅10^5$
）— 数组的大小。
每个测试用例的第二行包含n
个整数$a[1],a[2],…,a[n]$
（$1≤ai≤10^9$
）— 原始数组的元素。
每个测试用例的第三行包含$n$
个整数$b[1],b[2],…,b[n]$
（$1≤bi≤10^9$
）— 找到的数组的元素。
第四行包含一个整数$m$
（$1≤m≤2⋅10^5$
）— 修改操作的数量。
第五行包含$m$
个整数$d[1],d[2],…,d[m]$
（$1≤dj≤10^9$
）— 每个修改操作的保留值。
保证所有测试用例的$n$
值的总和不超过$2⋅10^5$
，同样保证所有测试用例的$m$
值的总和不超过$2⋅10^5$
。
输出
输出 $t$
行，每行是对应测试用例的答案。作为答案，如果存在一个合适的序列$c[1],c[2],…,c[m]$
，则输出"YES"，否则输出"NO"。
你可以以任何形式输出答案（例如，字符串"yEs"、"yes"、"Yes"和"YES"都将被视为肯定答案）。
题目描述
Sofia had an array of $ n $ integers $ a_1, a_2, \ldots, a_n $ . One day she got bored with it, so she decided to sequentially apply $ m $ modification operations to it.
Each modification operation is described by a pair of numbers $ \langle c_j, d_j \rangle $ and means that the element of the array with index $ c_j $ should be assigned the value $ d_j $ , i.e., perform the assignment $ a_{c_j} = d_j $ . After applying all modification operations sequentially, Sofia discarded the resulting array.
Recently, you found an array of $ n $ integers $ b_1, b_2, \ldots, b_n $ . You are interested in whether this array is Sofia's array. You know the values of the original array, as well as the values $ d_1, d_2, \ldots, d_m $ . The values $ c_1, c_2, \ldots, c_m $ turned out to be lost.
Is there a sequence $ c_1, c_2, \ldots, c_m $ such that the sequential application of modification operations $ \langle c_1, d_1, \rangle, \langle c_2, d_2, \rangle, \ldots, \langle c_m, d_m \rangle $ to the array $ a_1, a_2, \ldots, a_n $ transforms it into the array $ b_1, b_2, \ldots, b_n $ ?
输入格式
The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.
Then follow the descriptions of the test cases.
The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of the array.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the original array.
The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 10^9 $ ) — the elements of the found array.
The fourth line contains an integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of modification operations.
The fifth line contains $ m $ integers $ d_1, d_2, \ldots, d_m $ ( $ 1 \le d_j \le 10^9 $ ) — the preserved value for each modification operation.
It is guaranteed that the sum of the values of $ n $ for all test cases does not exceed $ 2 \cdot 10^5 $ , similarly the sum of the values of $ m $ for all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
Output $ t $ lines, each of which is the answer to the corresponding test case. As an answer, output "YES" if there exists a suitable sequence $ c_1, c_2, \ldots, c_m $ , and "NO" otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
样例 #1
样例输入 #1
7
3
1 2 1
1 3 2
4
1 3 1 2
4
1 2 3 5
2 1 3 5
2
2 3
5
7 6 1 10 10
3 6 1 11 11
3
4 3 11
4
3 1 7 8
2 2 7 10
5
10 3 2 2 1
5
5 7 1 7 9
4 10 1 2 9
8
1 1 9 8 7 2 10 4
4
1000000000 203 203 203
203 1000000000 203 1000000000
2
203 1000000000
1
1
1
5
1 3 4 5 1
样例输出 #1
YES
NO
NO
NO
YES
NO
YES
思路如下
结合数据输入，其实就是两个数组之间的比较问题。设第一个获取的数组是A，第二个数组是B，后续对A经过n次操作，看最终能否使“A==B”。
首先我们要将俩个数组扫一遍，对于修改操作，一共n次，可以对A数组的任意位置进行修改，也就是说，假设A数组为1,2,3,4
B数组为1,2,5,4，修改次数为2，内容是1,5,我们可以在A数组的三号位置连续修改两次，将不需要的1通过5覆盖。也就是说在n>=差异数的情况下，只需要保证所有需要修改的地方我们都有值与之对应即可。
也就是说在n>=差异数的情况下，只需要保证所有需要修改的地方我们都有值与之对应即可。
当然，题目中还有其他条件，操作要按其所给的顺序修改。
我们可以采取这种方式，将A录入数组中，在B数组录入的同时进行比对，如果A[i]!=B[i],那么我们让need[B[i]]++,什么意思呢，A与B在i = n的情况下，同一位置但数据不匹配，那么我们就需要一个值等同于此位置上的B的值，来对A进行修改，我们采用哈希存储所需的值和B数组本身。同时将B的值录入set容器中，set容器自排序无重复，后边可以作为检索哈希表的索引。
后续计算如下，我们也将改动数列按顺序录入哈希表中，并且记录最后一次的值为target便于比对。
最后，计算输出为YES or NO
对B的set容器进行遍历
如果(got[key] >= need[key])，那么a与b相差n个该元素，但我们拥有的>=n，所以该位置需计数，计入操作次数sum中，如果sum<=k(可操作次数)，并且target存在B数组中damn_b[target]>0即可输出YES，但是如若任意条件不符合，即为NO
最终代码如下，希望各位大佬可以给我讲讲怎么优化一下，本蒟蒻还是菜=w=，最后居然TLE了。。。。。。
代码如下
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
vector<int>nima;
map<long long, int>damn_a;
map<long long, int>damn_b;
map<long long, int>need;
set<long long>b;//set容器存储B的所有数据，作为索引，（需要降重，所以选择set）
long long int t;
long long int k;
map<long long,int> got;
vector<long long>A(1e5+3);
vector<long long>B(1e5+3);
int fu = 0;
int main() {
cin >> t;
while (t--) {
//置空
vector<long long>(1e5+3).swap(A);
vector<long long>(1e5+3).swap(B);
b.clear();
need.clear();
got.clear();
need.clear();
damn_b.clear();
int sum = 0;
int n;
cin >> n;
int target = 0;
//懒得合并 就拆开写循环吧
//A B数组是有位置顺序的
for (int i = 1; i <= n; i++)
cin >> A[i];
for (int i = 1; i <= n; i++) {//这里需要考虑B的顺序
cin >> B[i];
damn_b[B[i]]++;
if (A[i] != B[i]) //A与B相对位置元素不一致
need[B[i]]++; //对A而言,该位置所需的B元素数量++,得到a与b相差的对应元素数量
b.insert(B[i]);//以所需的相对元素做索引，查询数量
}
int damn = B[n];
cin >> k;//可更改的次数
int p = k;
while (p--) {
long long int temp;
cin >> temp;
if (p == 1)
target = p;//记录最后一次的值 用于验证
got[temp]++; //所拥有的，修改工具
}
for (int key : b)//遍历B数组
{
if (got[key] >= need[key]) //对于该元素，a与b相差n个该元素，但我们拥有的>=n，所以该位置需计数;
{
sum += need[key];
continue;
}
else//缺少，直接NO
{
cout << "NO" << endl;
fu = 1;
break;
}
}
if (fu != 1)
{
if (sum > k)//如果需要更改次数>可更改次数
cout << "NO" << endl;
else
{
if (damn_b[target])//如果target存在于B序列中
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
fu = 0;
}
}