[ 算法竞赛进阶指南 0x40 ] 杂谈

持续跟新

并查集

[NOI2015]程序自动分析
在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设x1,x2,x3…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2,x2=x3,x3=x4,x4≠x1，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

数据标识码在int范围内 <=1e9 显然离散化

先处理相等部分因相等关系他们可以传递
最后看不相等在里面冲突

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;

const int maxn =2e6+5;
int n, m;

int pre[maxn];

void init(int n){
    for(int i=1;i<=n;i++) pre[i]=i;
}

int finds(int x){
    return pre[x]!=x?pre[x]=finds(pre[x]):x;
}

void unions(int x,int y){
    x=finds(x),y=finds(y);
    pre[x]=y;
}

signed main() {
    fastio;
    int t;
    cin>>t;
    while(t--){
        int cnt=0;
        cin>>n;	
        init(n*2);
        int x,y,d;
        map<int,int> id;
        vector<pair<int,int> >b;
        while(n--){
            cin>>x>>y>>d;
            if(!id[x]) id[x]=++cnt;
            if(!id[y]) id[y]=++cnt;
            if(d==1){
                unions(id[x],id[y]);
            }else{
                b.push_back(make_pair(id[x],id[y]));
            }
        }
        int f=1;
        for(int i=0;i<b.size();i++){
            if(finds(b[i].first)==finds(b[i].second)){
                cout<<"NO"<<endl;
                f=0;
                break;
            } 
        }
        if(f){
            cout<<"YES"<<endl;
        }
    }
    return 0;
}

NOI2002 银河系英雄传说

带权并查集（根搭积木很像）：
对于每个点，分别记录所属链的头结点、该点到头结点的距离以及它所在集合的大小。
每次合并将y接在x的尾部，改变y头的权值和所属链的头结点，同时改变x的尾节点。
注意：每次查找的时候也要维护每个节点的权值。
每次查询时计算两点的权值差。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=30000+10;

int pre[maxn],siz[maxn],d[maxn];

void init(int n){
	for(int i=1;i<maxn;i++){
		pre[i]=i,siz[i]=1,d[i]=0;
	}
}

int finds(int x){
	if(x==pre[x]) return x;
	int rt=finds(pre[x]);
	d[x]+=d[pre[x]];
	return pre[x]=rt;
}

void unions(int x,int y){
	x=finds(x),y=finds(y);
	pre[x]=y;
	d[x]+=siz[y];
	siz[y]+=siz[x];
}

int main() {
	int n;
	cin>>n;
	init(n);
	for(int i=1;i<=n;i++){
		string cmd;
		int x,y;
		cin>>cmd>>x>>y;
		if(cmd[0]=='M'){
			unions(x,y);
		}else{
			if(finds(x)!=finds(y)) cout<<-1<<endl;
			else cout<<abs(d[x]-d[y])-1<<endl;
		}
	}
	return 0;
}

树状数组练习

楼兰图腾 统计凹凸个数

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];
int L[maxn],R[maxn];
int l[maxn],r[maxn];

signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
	}
	add(a[1],1);
	for(int i=2;i<n;i++){
		add(a[i],1);
		l[i]=ask(n)-ask(a[i]);
		L[i]=ask(a[i]-1);
	}
	memset(c,0,sizeof c);
	add(a[n],1);
	for(int i=n-1;i>1;i--){
		add(a[i],1);
		R[i]=ask(a[i]-1);
		r[i]=ask(n)-ask(a[i]);
	}
	ll rs=0,res=0;
	for(int i=2;i<n;i++){
		rs+=1ll*l[i]*r[i];
		res+=1ll*L[i]*R[i]; 
	}
	cout<<rs<<" "<<res<<endl;
	return 0;
}

线段树
Can you answer on these queries III

单独杂谈外链： https://blog.csdn.net/qq_40831340/article/details/90726050
关于这个线段树的相似的题

#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(false);cin.tie(0)
const int maxn = 5e5+10;
int n, m;

int sum[maxn << 2], lmax[maxn << 2], rmax[maxn << 2], lrmax[maxn << 2];

void push_up(int rt) {
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	lmax[rt] = max(lmax[rt << 1], sum[rt << 1] + lmax[rt << 1 | 1]);
	rmax[rt] = max(rmax[rt << 1 | 1], sum[rt << 1 | 1] + rmax[rt << 1]);
	lrmax[rt] = max( max(lrmax[rt << 1], lrmax[rt << 1 | 1]), rmax[rt << 1] + lmax[rt << 1 | 1]);
}

void update(int L, int l, int r, int rt, int c) {
	if(l == r) {
		lrmax[rt] = lmax[rt] = rmax[rt] = sum[rt] = c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

//int query(int L, int R, int l, int r, int rt) {
// if(L <= l && r <= R) {
// return lrmax[rt];
// }
// int mid = l + r >> 1;
// int res = -0x3f3f3f3f;
// if(L <= mid) res = max(res, query(L, R, l, mid, rt << 1));
// if(R > mid) res = max(res, query(L, R, mid + 1, r, rt << 1 | 1));
// return res;
//}

struct node {
	int sum;
	int lmax, rmax, lrmax;
};

node query(int L, int R, int l, int r, int rt) {
	if(L <= l && r <= R) {
		return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
	}
	//if(l == r) return node {sum[rt], lmax[rt], rmax[rt], lrmax[rt]};
	int mid = l + r >> 1;
	if (R <= mid) return query(L, R, l, mid, rt << 1);
	else if (L > mid) return query(L, R, mid + 1, r, rt << 1 | 1);
	else {
		node res;
		node re1 = query (L, R, l, mid, rt << 1);
		node re2 = query (L, R, mid + 1, r, rt << 1 | 1);
		res.sum = re1.sum + re2.sum;
		res.lmax = max(re1.lmax, re1.sum + re2.lmax);
		res.rmax = max(re2.rmax, re2.sum + re1.rmax);
		res.lrmax = max( max(re1.lrmax, re2.lrmax), re1.rmax + re2.lmax);
		return res;
	}
}

int main() {
	fastio;
	cin >> n >> m;
	int k;
	for(int i = 1; i <= n; i ++) {
		cin >> k;
		update(i, 1, n, 1, k);
	}
	while(m--) {
		int cmd, x ,y;
		cin >> cmd >> x >> y;
		if(cmd == 1) {
			if(x > y) swap (x, y);
			cout << query(x, y, 1, n, 1).lrmax << endl;
		} else {
			update(x, 1, n, 1, y);
		}
	}
	return 0;
}

维护差分变成区间修改单点查
这样不能直接修改某区间变成b 复杂度有点搞人

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=2*1e5+10;

int c[maxn];
int n;
int lowbit(int x) {
	return x&(-x);
}

int ask(int x) {
	int res=0;
	for(; x; x-=x&(-x)) res+=c[x];
	return res;
}

void add(int x,int y) {
	for(; x<=n; x+=x&(-x)) {
		c[x]+=y;
	}
}

int a[maxn];

signed main() {
	int m;
	cin>>n>>m;
	string cmd;
	int l,r,d;
	
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=1;i<=m;i++){
		cin>>cmd;
		if(cmd[0]=='Q'){
			cin>>l;
			cout<<ask(l)+a[l]<<endl;
		}else{
			cin>>l>>r>>d;
			add(l,d);
			add(r+1,-d);
		}
	}
	return 0;
}

poj lost cows
这题说什么二分树状数组什么的完全没有看懂。。。
书堆大法好啊
反正都是倒着找 k大而且这个k大不能与后面重复倒着删就好了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fir first
#define sec second
const int maxn=1e5+10;

int siz[maxn];
int s[maxn][3];
int w[maxn],pos[maxn];
int tot;

void up(int i) {
	siz[i]=siz[s[i][0]]+siz[s[i][1]]+1;
}

void spin(int &i,int p) {
	int t=s[i][p];
	s[i][p]=s[t][!p],s[t][!p]=i,up(i),up(t),i=t;
}

void ins(int x,int &i) {
	if(!i) {
		i=++tot,siz[i]=1,w[i]=x,pos[i]=rand();
		return;
	}
	siz[i]++;
	if(x<=w[i]) {
		ins(x,s[i][0]);
		if(pos[s[i][0]]<pos[i])spin(i,0);
	} else {
		ins(x,s[i][1]);
		if(pos[s[i][1]]<pos[i])spin(i,1);
	}
}

void del(int x,int &i) {
	if(w[i]==x) {
		if(s[i][0]*s[i][1]==0) {
			i=s[i][0]+s[i][1];
			return;
		}
		if(pos[s[i][0]]>pos[s[i][1]]) {
			spin(i,1);
			del(x,s[i][0]);
		} else {
			spin(i,0);
			del(x,s[i][1]);
		}
	} else if(w[i]>x)del(x,s[i][0]);
	else del(x,s[i][1]);
	up(i);
}

int find(int x,int i) {
	if(!i)return 1;
	if(w[i]>=x)return find(x,s[i][0]);
	return find(x,s[i][1])+siz[s[i][0]]+1;
}

int ask(int x,int i) {
	if(siz[s[i][0]]==x-1)return w[i];
	if(siz[s[i][0]]>=x)return ask(x,s[i][0]);
	return ask(x-siz[s[i][0]]-1,s[i][1]);
}

int ans[maxn];
int a[maxn];
signed main() {
	int n;
	cin>>n;
	int root=0;

	ins(1,root);
	for(int i=2; i<=n; i++) cin>>a[i],ins(i,root),a[i]++;


	for(int i=n; i>1; i--) {
		ans[i]=ask(a[i],root);
		del(ans[i],root);
	}

	cout<<ask(1,root)<<endl;
	for(int i=2; i<=n; i++) {
		cout<<ans[i]<<endl;
	}
	return 0;
}

这里在补个权值线段树水果区的代码orz

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
using namespace std;

const int maxn = 1e5 + 5;

int n, m;

int b[maxn << 2];

void push_up(int rt) {
	b[rt] = b[rt << 1] + b[rt << 1 | 1] ;
}

void update(int L, int l, int r, int rt, int c) {
	if(l == r) {
		b[rt] += c;
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update(L, l, mid, rt << 1, c);
	else update(L, mid + 1, r, rt << 1 | 1, c);
	push_up(rt);
}

void query(int L, int l, int r, int rt) {
	if(l == r) {
		cout << l << " " << b[rt] << endl; 
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) query(L, l, mid, rt << 1);
	else query(L, mid + 1, r, rt << 1 | 1);
}

int find_k(int l, int r, int rt, int k) {
	if(l == r) {
		return l;
	}
	int mid = l + r >> 1;
	if(k <= b[rt << 1]) return find_k(l, mid, rt << 1, k);
	else return find_k(mid + 1, r, rt << 1 | 1, k - b[rt << 1]);
}

int a[maxn];
int ans[maxn];
int main() {
	fastio;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		update(i, 1, n, 1, 1);
	}
	
	for(int i = 2; i <= n; i ++) {
		cin >> a[i];
	}
	a[1] = 0;
	int k = n;
	for(int i = n; i >= 1; i --) {
		ans[i] = find_k(1, n, 1, a[i] + 1);
	// cout << find_k(1, n, 1, a[i] + 1) << endl;
	// cout << "\\\\" << ans[i] << endl;
		update(ans[i], 1, n, 1, -1);
	// query(ans[i], 1, n, 1);
	}
	
	for(int i = 1; i <= n; i ++)
		cout << ans[i] << endl; 
	
	return 0;
}

全部评论

推荐最新楼层

11-24 08:35

湖南大学 Java

华为实习一月体验

首先，工位超大，双屏办公。再说伙食，真的很好吃，很对我的胃口。公司凝聚力很强，很团结。团队氛围也特别好，大家都很有活力也很专业，互相帮助。加班的话，也是有的，具体看项目和工作的进度。园区环境很漂亮，设施这些应该算顶配了，显得时候下来散散步很舒服

italentmailsys：你是说那个没有绿豆的绿豆汤吗

华为工作强度 838人发布

点赞评论收藏

不愿透露姓名的神秘牛友

昨天 12:39

华为工作体验

首先，工作强度嘛，因人而异。研发的基本上都是9-11-5的节奏，确实是最累的岗位，但转岗机会也多，激励措施还不错。我咋采购部，相比下来还算轻松。再说说工作氛围，我在不同的小组待过，整体感觉还不错。大部分同事都很和气，大家一起努力，甩锅的现象少。入职培训NEO做得很不错，培训结束后会有导师带你4-6个月，考核也很严格，基本上都能顺利转正。考核压力嘛，确实不小。每半年一次，强制比例分布，13-14级的校招员工升级速度相对快，但供应链的名额少于研发。绩效决定了在华为的发展，大家都很看重KPI，内卷和心理压力也是常态。

华为工作强度 838人发布

点赞评论收藏

10-16 12:29

携程_移动安全研发

转正了呀

Yushuu：你的确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆

点赞评论收藏