备孕百度之星-9月19日
记了一下prime、kruskal模板，学了并查集
prinme（力扣 1584）
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
//来背prime板子喽
int n = points.size();
int g[1005][1005], dis[1005], vis[1005];
for(int i = 0; i < points.size(); i++)
for(int j = 0; j < points.size(); j++)
g[i][j] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
int res = 0;
for(int i = 0; i < points.size(); i++){//选n个点
int t = -1;
for(int j = 0; j < n; j++)
if(!vis[j] && (t == -1 || dis[t] > dis[j])) t = j;
if(i != 0) res += dis[t];
vis[t] = 1;
for(int j = 0; j < n; j++)
if(!vis[j]) dis[j] = min(dis[j], g[t][j]);
}
return res;
}
};
kruskal（poj 1287）
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10005;
struct node {
int x, y, z;
bool operator<(node &t)const{
return z < t.z;
}
}edge[N];
int fu[N];
int Find(int x){
if(x == fu[x]) return x;
return fu[x] = Find(fu[x]);
}
int main(){
int n, m;
while(cin >> n, n){
cin >> m;
for(int i = 1; i <= m; i++)
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].z);
sort(edge+1, edge+1+m);
for(int i = 1; i <= n; i++) fu[i] = i;
int ans = 0;
for(int i = 0; i <= m; i++){
int x = Find(edge[i].x);
int y = Find(edge[i].y);
if(x == y) continue;
fu[x] = y;
ans += edge[i].z;
}
printf("%d\n", ans);
}
}
二者选择的区别在于图是稠密还是稀疏
并查集（NOI2015/洛谷R125165595）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;
const int N = 1000005;
int fa[N];
ll ii[N], jj[N];
int Find(int x){
if(fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
int main(){
int n, T;
cin >> T;
while(T-- > 0){
cin >> n;
for(int i = 1; i <= n; i++) fa[i] = i;
// memset(ii, 0, sizeof(ii));
// memset(jj, 0, sizeof(jj));
unordered_map<ll, int> map;
int ind = 1;//第一个ll用1
int index = 0;
string res = "YES";
for(int i = 0; i < n; i++){
ll x,y,e;
cin >> x >> y >> e;
if(e == 0){//验证
ii[index] = x;
jj[index++] = y;
}else{//并查集
if(map.find(x) == map.end()) map[x] = ind++;
if(map.find(y) == map.end()) map[y] = ind++;
int i_ind = map[x];
int j_ind = map[y];
fa[Find(i_ind)] = Find(j_ind);//并
}
}
for(int i = 0; i < index; i++){
if(ii[i] == jj[i]) {
res = "NO";
break;
}
if(map.find(ii[i]) != map.end() && map.find(jj[i]) != map.end() && Find(map[ii[i]]) == Find(map[jj[i]])){
res = "NO";
break;
}
}
cout << res << endl;
}
}
被N的范围卡了40min，0的个数数错了
c++的优先队列（poj1456）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
struct fuc{
bool operator()(pair<int, int> p1, pair<int, int> p2){
return p1.first > p2.first;
}
};
bool cmp(pair<int, int> a, pair<int, int> b){
return a.second < b.second;
}
int main(){
int n;
while(cin >> n){
int cur = 0;
long res = 0;
vector<pair<int, int> > v;
for(int i = 0; i < n; i++){
int x, y;
cin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end(), cmp);
priority_queue<pair<int, int>, vector<pair<int, int> >, fuc> q;
for(int i = 0; i < v.size(); i++){
if(q.size() < v[i].second){
q.push(v[i]);
res += v[i].first;
}else{
if(q.top().first < v[i].first){
res -= q.top().first;
q.pop();
q.push(v[i]);
res += v[i].first;
}
}
}
cout << res << endl;
}
}
重点学一下比较器的写法。 无意间发现，poj的c++竟然不支持unordered_map的头文件。G++的提交不能出现错误的>>。 也就是vector<pair<int, int>> 这样写是不对的，要在>>中间加空格。
再来复习STL
一些函数：
计算公约数cout << __gcd(12,44) << endl;
统计二进制中存在几个1
cout << __builtin_popcountll(21);
定义类型名称
typedef long long ll;
初始化数组内容全是0：
int a[10];
memset(a, 0, sizeof(a))
因为memeset按字节进行赋值，所以不能赋值其他整数（字符可以通用）
计算vector的数组和：
accumulate(ans.begin(),ans.end(), 0ll)；
双端队列的使用：
deque<TreeNode*> q;
q.push_front(t);
q.push_back(t);
q.pop_front();
q.pop_back();
q.size();
q.empty();
数字转字符串：
to_string(val)
字符转数字：
char - '0'
unordered_set的使用：
unordered_set<int> s;
s.insert(1);//插入
s.erase(1);//清除
s.find(1)；//查找，会返回指针，判断指针是不是end()
s.find(1) == s.end() ? 不存在 ： 存在
s.size()；//集合大小
unordered_map的使用：
unordered_map<int, string> mp;/*insert插入*/
//1：借助pair构造函数
pair<int, string> kv(1, "one");
mp.insert(kv);
//2：借助pair构造匿名对象插入
mp.insert(pair<int, string>(2, "two"));
//3：调用make_pair函数模板插入
mp.insert(make_pair(3, "three"));
//4：使用[]运算符重载函数进行插入
mp[4] = "four";
//4：使用{}
mp.insert({ 5, "five" });
//2：范围forfor (auto e : mp)
{
cout << e.first << ":" << e.second << " ";
}
erase函数可以传入指针或者值。
比较器：（类似java，都是传一个函数）
数组：
sort(a,a+n,cmp);bool cmp(int a, int b){
return num1[a] == num1[b] ?num2[a] < num2[b] : num1[a] < num1[b];
}
vector：
vector<vector<int>> b;
sort(b.begin(), b.end(), cmp);
bool cmp(vector<int> a, vector<int> b){
return a[0] - b[0];
}
运算符优先级：
'==' 大于 '&'优先队列：
priority_queue<int> q;
q.empty();
q.push(0);
q.top();
q.pop();//返回数值
vector<vector<int>> g(numCourses);//这样使用要提前分配好空间
long long类型的绝对值：
使用llabs(ll a);
可以直接用{a，b}构造一个vector<int>
结构体的比较器：
例如kurskal的边：
struct node{
int x, y, z;
bool operator<(const node &t) const{
return z < t.z;
}
}
priority_queue重写比较器：
struct fuc{bool operator()(pair<int, int> p1, pair<int, int> p2){
return p1.first > p2.first;
}
};
priority_queue<pair<int, int>, vector<pair<int, int> > ,fuc> q;
bitset的使用：
bitset<100> s;//其实还是可以看成是一个数字cout << s[5] << endl;
s.set();
s >>= 10;
cout << s[5] << endl;
unique去重函数：
vector<int> a;
int m = unique(a.begin(), a.end()) - a.begin();//返回去重后的个数
二分查找：
lower_bound(a, a+n, x)；//找大于等于x的数
upper_bound(a, a+n, x)；//找小于等于x的数
360集团公司福利 197人发布