并查集加速区间修改例题
admin
|
|
329
|
算法知识总结

968 字
|
20 分钟

E – Packing Under Range Regulations

题目描述：

n个球，每个球只能放在[l,r]的任意一个盒子中，每个盒子只能放一个球，问这n个球能不能都放进盒子里

思路：

贪心 + 并查集优化

先放 r 小的，如果 r 相同就放 l 小的

难点是优化找的这个过程，这里可以用并查集来优化，fa[x] 表示从 x 开始后的第一个没有放过物品的盒子，这样可能快速获得放的位置

板子：

int fa[MAX];
int getfa(int x){
 return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
//仅更新区间中满足条件的第一个点
for(int i = l; i <= r ;i = getfa(i + 1)){
 if(){
     //按题意更新  
 		fa[i] = getfa(i + 1);//更新fa数组
				break;//因为只更新一个点所以直接break
		}
}

但这个题比较恶心的就是l,r的范围是1e9，所以不能用数组，得离散化，也就是用unordered_map来映射(map也可以，但是会慢)

unordered_map <int,int> fa;
int getfa(int x)
{
	return !fa.count(x) ? x : fa[x] = getfa(fa[x]);
}

for(int i = 1; i <= n; ++i){
 x = getfa(tr[i].l);
 if(x > tr[i].r){
     cout<<"No\n";//在该区间的点都修改过了就说明该球放不下
     return;
 }
 fa[x] = x + 1;
}

 

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int l, r;
string s, t;
struct ran{
    int l, r;
}tr[MAX];

bool cmp(ran a, ran b){
    if(a.r != b.r)return a.r < b.r;
    else return a.l < b.l;
}

unordered_map<int, int>fa;
int getfa(int x){
    return !fa.count(x) ? x : fa[x] = getfa(fa[x]);
}


void work(){
    fa.clear();
    cin>>n;
    for(int i = 1; i <= n; ++i){
        cin>>tr[i].l>>tr[i].r;
    }
    sort(tr + 1, tr + 1 + n, cmp);
    for(int i = 1; i <= n; ++i){
        x = getfa(tr[i].l);
        if(x > tr[i].r){
            cout<<"No\n";
            return;
        }
        fa[x] = x + 1;
    }
    cout<<"Yes\n";
}

int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
    }
    return 0;
}

D – Linear Probing

题目描述：

N = 220,

Q次操作，输入op和x

  • op=1，如果trx%n=-1，就将这个点的值更新成x，否则就给x+1，直到找到第一个是-1的
  • op=2，输出tr[x%n]

思路：

可以看作是一个势能只有1的区间修改+单点查询

我们要做的就是去优化找第一个是-1的点即可

还是用上面的并查集来优化，如果这个点已经用过了就把fa[i] = getfa(i + 1); 合并掉他

注意取模即可

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 2000000 + 50
int n, m, k, op;
ll x, y, z;
int l, r;
string s, t;
ll tr[MAX];

ll fa[MAX];
ll getfa(ll x){
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}

void work(){
    n = (int)pow(2, 20);
    for(int i = 0; i <= n; ++i)fa[i] = i;
    mem(tr, -1);
    cin>>m;
    while (m--) {
        cin>>op>>x;
        if(op == 1){
            for(ll i = x % n; ;i = getfa(i + 1)){
                i %= n;
                if(tr[i] == -1){
                    tr[i] = x;
                    fa[i] = getfa(i + 1);
                    break;
                }
            }
        }
        else cout<<tr[x % n]<<endl;
    }

}

int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

Supermarket

题目描述

每个商品都有一个截止时间，在截止时间之前卖出去就可以获得对应的价值，否则就得不到对应的价值，问该如何安排才能获得最大价值

思路：

贪心 + 并查集优化

将价值从高到低排序，优先考虑价值大的商品，价值相同的时候就按截止时间靠前的放前面

对于一个商品要被卖掉，肯定是越晚被卖掉越好，因为可以给前面留出时间，给价值赶不上他且时间在他之间的

比如 100 2 和 99 1这两个物品

我们就应该把100安排在2的时间，把99安排在1的时间

所以对于一个商品，我们要从他的截止时间往前找，可以放的下就放，放不了就不行

这个查找的过程就可以用并查集优化

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
//#include<unordered_map>
using namespace std;

//#pragma GCC optimize("Ofast")
//#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
typedef  long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
int l, r;
string s, t;

struct ran{
    int l, val;
}tr[MAX];
bool cmp(ran a, ran b){
    if(a.val != b.val)return a.val > b.val;
    else return a.l < b.l;
}
int fa[MAX];
int getfa(int x){
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
void work(){
    while(cin>>n){
        for(int i = 1; i <= 10000; ++i)fa[i] = i;
        for(int i = 1; i <= n; ++i)cin>>tr[i].val>>tr[i].l;
        sort(tr + 1, tr + 1 + n, cmp);
        ll ans = 0;
        for(int i = 1; i <= n; ++i){
            x = getfa(tr[i].l);
            if(x < 1)continue;
            ans += tr[i].val;
            fa[x] = getfa(x - 1);
        }
        cout<<ans<<endl;
    }
    
}

int main(){
//    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
图论
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
严格次小生成树

							
							

							
银河「建图 + Tarjan缩点 + 拓扑排序 + 最长路」或者 「差分约束跑最长路 + SPFA的SLF优化」

							
							

							
「kuangbin带你飞」专题四最短路专题题解

							
							

							
走廊泼水节「并查集 + 贪心」｜｜「最小生成树」

							
							

							
AtCoder Beginner Contest 243「E – Edge Deletion」「floyed思维」