传送门:Dashboard - Codeforces Round 950 (Div. 3) - Codeforces
B. Choosing Cubes(排序)
Dmitry has n cubes, numbered from left to right from 1 to n. The cube with index f is his favorite.
Dmitry threw all the cubes on the table, and the i-th cube showed the value ai (1≤ai≤100). After that, he arranged the cubes in non-increasing order of their values, from largest to smallest. If two cubes show the same value, they can go in any order.
After sorting, Dmitry removed the first k cubes. Then he became interested in whether he removed his favorite cube (note that its position could have changed after sorting).
For example, if n=5, f=2, a=[4,3,3,2,3] (the favorite cube is highlighted in green), and k=2, the following could have happened:
- After sorting a=[4,3,3,3,2], since the favorite cube ended up in the second position, it will be removed.
- After sorting a=[4,3,3,3,2], since the favorite cube ended up in the third position, it will not be removed.
Input
The first line contains an integer t (1≤t≤1000) — the number of test cases. Then follow the descriptions of the test cases.
The first line of each test case description contains three integers n, f, and k (1≤f,k≤n≤100) — the number of cubes, the index of Dmitry's favorite cube, and the number of removed cubes, respectively.
The second line of each test case description contains nn integers ai (1≤ai≤100) — the values shown on the cubes.
Output
For each test case, output one line — "YES" if the cube will be removed in all cases, "NO" if it will not be removed in any case, "MAYBE" if it may be either removed or left.
You can output the answer in any case. For example, the strings "YES", "nO", "mAyBe" will be accepted as answers.
题意翻译
Dimtry 有 n 个立方体，第 i 个立方体的价值为 ai，他最喜欢第 f 个立方体。
接下来 Dimtry 会把立方体按 a 从大到小排序（价值相同的立方体顺序任意），使得排完序后 a 单调不增，并且拿走此时的前 k 个立方体。
现在给定 n,f,k,{a1,a2,⋯ ,an}（保证 1≤f,k≤n≤100,1≤ai≤100），试判断 Dimtry 喜欢的（即原来的第 f 个）立方体是否会被拿走。
如果在所有情况下都会被拿走，输出“YES”。
如果在所有情况下都不会被拿走，输出“NO”。
如果在所有情况下，有可能被拿走，有可能不被拿走，输出“MAYBE”。
本题单个测试点存在多组测试数据，保证测试数据组数 t 不超过 1000。
输入输出样例
输入 #1复制
12 5 2 2 4 3 3 2 3 5 5 3 4 2 1 3 5 5 5 2 5 2 4 1 3 5 5 5 1 2 5 4 3 5 5 4 3 1 2 4 5 5 5 5 4 3 2 1 5 6 5 3 1 2 3 1 2 3 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 42 5 2 3 2 2 1 1 2 2 1 1 2 1 5 3 1 3 3 2 3 2
输出 #1复制
MAYBE YES NO YES YES YES MAYBE MAYBE YES YES YES NO
思路
一般这种输出yes、no、maybe只有三种格式的其实不需要考虑所有的情况，只需要考虑好判断的情况就行了，就比如这道题我们只判断yes和no的情况剩下的就都是maybe了
题目的意思很明确了就是问能不能拿到a[f].定义x = a[f],把a数组降序排序，如果a[k] < a[f],那么一定能拿到，如果a[k] > a[f] 或者a[k] == a[f] 并且a[k + 1] < a[f]那么就一定拿不到，剩余的情况就输出maybe即可
代码
#include <iostream>
#include <algorithm>using namespace std;const int N = 110;
int a[N];int t;
int n,f,k;bool cmp(int A,int B){return A > B;
}void solve()
{cin >> n >> f >> k;for(int i = 1;i <= n;i ++) cin >> a[i];int x = a[f];sort(a + 1, a + n + 1, cmp);if(a[k] > x) cout << "No" << endl;else if(a[k] < x || (a[k] == x && a[k + 1] < x) || k == n) cout << "Yes" << endl;else cout << "Maybe" << endl;
}int main()
{cin >> t;while(t --){solve();}return 0;
}C. Sofia and the Lost Operations （思维题）
Sofia had an array of n integers a1,a2,…,an. 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 〈cj,dj〉 and means that the element of the array with index cj should be assigned the value dj, i.e., perform the assignment acj=dj. After applying all modification operations sequentially, Sofia discarded the resulting array.
Recently, you found an array of n integers b1,b2,…,bn. You are interested in whether this array is Sofia's array. You know the values of the original array, as well as the values d1,d2,…,dm. The values c1,c2,…,cm turned out to be lost.
Is there a sequence c1,c2,…,cm such that the sequential application of modification operations 〈c1,d1,〉,〈c2,d2,〉,…,〈cm,dm〉 to the array a1,a2,…,an transforms it into the array b1,b2,…,bn?
Input
The first line contains an integer t (1≤t≤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≤n≤2⋅10^5) — the size of the array.
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9) — the elements of the original array.
The third line of each test case contains n integers b1,b2,…,bn (1≤bi≤10^9) — the elements of the found array.
The fourth line contains an integer m (1≤m≤2⋅10^5) — the number of modification operations.
The fifth line contains m integers d1,d2,…,dm(1≤dj≤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⋅10^5, similarly the sum of the values of m for all test cases does not exceed 2⋅10^5.
Output
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 c1,c2,…,cm, 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).
题意翻译
索菲亚有一个包含n 个整数的数组a[1],a[2],…,a[n]。有一天她对这个数组感到厌倦，于是决定顺序地对其应用m 个修改操作。
每个修改操作由一对数字〈cj,dj〉 描述，意味着数组中索引为c[j]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"都将被视为肯定答案）。
输入输出样例
输入 #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不同的元素记录下来，如果d当中没有可替补的或者替补数量不够的，那么就一定不成立。那这道题的难点就是边界的考虑了，也就是d数组的最后一个值。一定要联想到最后一个因为最后一个之后就不会在替换了，也就是说最后一个值必须是有效值，否则替换之后变成无效值了，而且之后也没有值在替换他。
条件都总结清楚了，代码实现一下就行
代码
#include <iostream>
#include <algorithm>
#include <map>#define ll long longusing namespace std;const int N = 2e5 + 10;
int a[N],b[N],d[N];int t;
int n,m;void solve()
{map<int,int> st,mp,mp1;cin >> n;for(int i = 0;i < n;i ++) cin >> a[i];for(int i = 0;i < n;i ++){cin >> b[i];mp1[b[i]] ++;if(a[i] == b[i]) continue;st[b[i]] ++;}cin >> m;for(int i = 0;i < m;i ++){cin >> d[i];mp[d[i]] ++;}bool check = true;for(auto [x,y] : st){if(mp.find(x) == mp.end() || mp[x] < y){check = false;break;}}int x = d[m - 1];if(!check || mp1.find(x) == mp1.end()){cout << "No" << endl;return;}cout << "Yes" << endl;
}int main()
{cin >> t;while(t --){solve();}return 0;
}E. Permutation of Rows and Columns（思维题）
You have been given a matrix aa of size n by m, containing a permutation of integers from 1 to n⋅m.
A permutation of n integers is an array containing all numbers from 1 to n exactly once. For example, the arrays [1], [2,1,3] ,[5,4,3,2,1] are permutations, while the arrays[1,1],[100], [1,2,4,5] are not.
A matrix contains a permutation if, when all its elements are written out, the resulting array is a permutation. Matrices [[1,2],[3,4]], [[1]], [[1,5,3],[2,6,4]]contain permutations, while matrices [[2]], [[1,1],[2,2]], [[1,2],[100,200]] do not.
You can perform one of the following two actions in one operation:
- choose columns cc and dd (1≤c,d≤m, c≠d) and swap these columns;
- choose rows cc and dd (1≤c,d≤n, c≠d) and swap these rows.
You can perform any number of operations.
You are given the original matrix aa and the matrix bb. Your task is to determine whether it is possible to transform matrix aa into matrix bb using the given operations.
Input
The first line contains an integer t (1≤t≤10^4) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case description contains 2 integers n and m (1≤n,m≤n⋅m≤2⋅10^5) — the sizes of the matrix.
The next n lines contain m integers aij each (1≤aij≤n⋅m). It is guaranteed that matrix a is a permutation.
The next n lines contain m integers bij each (1≤bij≤n⋅m). It is guaranteed that matrix b is a permutation.
It is guaranteed that the sum of the values n⋅mn⋅m for all test cases does not exceed 2⋅10^5
Output
For each test case, output "YES" if the second matrix can be obtained from the first, and "NO" otherwise.
You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.
题意翻译
给你 1 个 n×m 矩阵，里面元素构成排列，你可以交换任意一列任意一行，求任意次操作后两个矩阵能否相同。
输入输出样例
输入 #1复制
7 1 1 1 1 2 2 1 2 3 4 4 3 2 1 2 2 1 2 3 4 4 3 1 2 3 4 1 5 9 6 12 10 4 8 7 11 3 2 1 5 9 6 12 10 4 8 7 11 3 2 3 3 1 5 9 6 4 2 3 8 7 9 5 1 2 4 6 7 8 3 2 3 1 2 6 5 4 3 6 1 2 3 4 5 1 5 5 1 2 3 4 4 2 5 1 3
输出 #1复制
YES YES NO YES YES NO YES
思路
这种题目想到就想到了，想不到就想不到，所以要多刷题。开始的时候确实不知道要怎么做，一般拿到判断的题目不要从小的方面判断，去从小的方面找规律推出全局的规律。这道题的规律就是，把行列存哈希表，如果行列没有不一样的元素说明一定能成立
代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>using namespace std;int t;
int n,m;void solve()
{cin >> n >> m;vector<vector<int>> a(n,vector<int>(m,0));vector<vector<int>> b(n,vector<int>(m,0));for(int i = 0;i < n;i ++){for(int j = 0;j < m;j ++){cin >> a[i][j];}}for(int i = 0;i < n;i ++){for(int j = 0;j < m;j ++){cin >> b[i][j];}}map<vector<int>,int> row1,row2,col1,col2;for(int i = 0;i < n;i ++){vector<int> A(a[i].begin(),a[i].end());vector<int> B(b[i].begin(),b[i].end());sort(A.begin(),A.end());sort(B.begin(),B.end());row1[A] ++, row2[B] ++;}for(int i = 0;i < m;i ++){vector<int> A,B;for(int j = 0;j < n;j ++){A.push_back(a[j][i]);B.push_back(b[j][i]);}sort(A.begin(),A.end());sort(B.begin(),B.end());col1[A] ++, col2[B] ++;}bool check = true;for(auto [arr,w] : row1){if(row2[arr] != w){check = false;break;}}if(!check){cout << "No" << endl;return;}for(auto [arr,w] : col1){if(col2[arr] != w){check = false;break;}}if(check) cout << "Yes" << endl;else cout << "No" << endl;
}int main()
{cin >> t;while(t --){solve();}return 0;
}加油
![[C语言] 函数详解：库函数与自定义函数](https://img-blog.csdnimg.cn/img_convert/8b4bf585a78633e1f1f035d523c9e3fd.png)
![鸢尾花书实践和知识记录[6-23数据聚类]](https://i-blog.csdnimg.cn/direct/799c591eb6d6439eab893d1943ce3def.png)
