当前位置 博文首页 > NEFU AB-IN's Blog：2021天梯赛补题
Powered by:NEFU AB_IN
2021天梯赛补题，感觉又挺可惜的，两次打天梯都挺拉胯，这次以为L3挺难，就在L2一直做，可惜最后也没冲到200
ACwing：https://www.acwing.com/problem/content/description/3469/
PTA：https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652362
考察哈希的用法。
由于数据量比较小，可以采用STL暴力过一下。但由于 v e c t o r vector vector没有定义哈希函数，但 v e c t o r vector vector有比较函数，所以就用 m a p map map存一下比较。
两个点注意一下
/*
* @Description: https://blog.csdn.net/qq_45859188
* @Author: NEFU AB_IN
* @version: 1.0
* @Date: 2020-12-10 10:46:04
* @LastEditors: NEFU AB_IN
* @LastEditTime: 2021-05-05 15:32:45
*/
#include<bits/stdc++.h>
using namespace std;
#define SZ(X) ((int)(X).size())
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
map < vector<int> , int > cnt;
vector < pair<int, vector<int> > > ans;
int main()
{
IOS;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
vector <int> line(m);
for(auto& i : line) cin >> i;
cnt[line] ++;
}
for(auto& p : cnt) {
ans.push_back({-p.second, p.first});
}
sort(ans.begin(), ans.end());
cout << SZ(cnt) << endl;
for(auto& p : ans){
cout << -p.first;
for(auto i : p.second) cout << " " << i;
cout << endl;
}
return 0;
}
如果不用负数这种奇技淫巧的话，就需要结构体排序，由于 v e c t o r vector vector是无序容器，所以需要在排序时，将 c m p cmp cmp函数对象放入即可
/*
* @Description: https://blog.csdn.net/qq_45859188
* @Author: NEFU AB_IN
* @version: 1.0
* @Date: 2021-05-10 19:25:00
* @LastEditors: NEFU AB_IN
* @LastEditTime: 2021-05-10 19:31:45
*/
#include<bits/stdc++.h>
using namespace std;
#define SZ(X) ((int)(X).size())
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
struct cmp{ //自定义vector排序
bool operator() (const pair<int,vector<int> >&a, const pair<int,vector<int> >&b) const{
if(a.first != b.first)
return a.first > b.first;
else return a.second < b.second;
}
};
map < vector<int> , int > cnt;
vector < pair<int, vector<int> > > ans;
int main()
{
IOS;
int n, m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
vector <int> line(m);
for(auto& i : line) cin >> i;
cnt[line] ++;
}
for(auto& p : cnt) {
ans.push_back({p.second, p.first});
}
sort(ans.begin(), ans.end(), cmp());
cout << SZ(cnt) << endl;
for(auto& p : ans){
cout << p.first;
for(auto i : p.second) cout << " " << i;
cout << endl;
}
return 0;
}
而像 p r i o r i t y _ q u e u e priority\_queue priority_queue, s e t set set 这种有序容器，内部就定义了 c o m p a r e compare compare函数进行了排序
比如 s e t set set对应基于二叉树实现从小到大排序，而 p r i o r i t y _ q u e u e priority\_queue priority_queue默认大根堆（从大到小排序）
如何改写呢？
由于是有序容器，所以在构造函数时就应该将比较函数
c
m
p
cmp
cmp放入
对于 s e t set set
struct cmp{
bool operator() (const int &a, const int &b){
return a > b;
}
};
set <int, cmp> s;
结构体排序的话，只需要改改参数就好了。
例子
/*
* @Description: https://blog.csdn.net/qq_45859188
* @Author: NEFU AB_IN
* @version: 1.0
* @Date: 2020-12-10 10:46:04
* @LastEditors: NEFU AB_IN
* @LastEditTime: 2021-05-10 20:26:07
*/
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define SZ(X) ((int)(X).size())
#define MP make_pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
