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;
}
