改了网站关键词,北京到安阳火车票,麦进斗网站建设,商城微信网站怎么做离散化
定义
把无限空间中有限的个体映射到有限的空间中去#xff0c;以此提高算法的时空效率。通俗的说#xff0c;离散化是在不改变数据相对大小的条件下#xff0c;对数据进行相应的缩小。 适用范围#xff1a;数组中元素值域很大#xff0c;但个数不是很多。 比如将…离散化
定义
把无限空间中有限的个体映射到有限的空间中去以此提高算法的时空效率。通俗的说离散化是在不改变数据相对大小的条件下对数据进行相应的缩小。 适用范围数组中元素值域很大但个数不是很多。 比如将a[][1,3,100,2000,500000]映射到[0,1,2,3,4]这个过程就叫离散化。
两种离散化方式
1.利用sortunique进行数据离散化适用于区间查找及更新 常与前缀和、树状数组、线段树和动态规范结合考查。 先来看一个金典题目 题目 假定有一个无限长的数轴数轴上每个坐标上的数都是 0。 现在我们首先进行 n次操作每次操作将某一位置 x 上的数加 c。 接下来进行 m 次询问每个询问包含两个整数 l 和 r你需要求出在区间 [ l , r ] 之间的所有数的和。
输入格式 第一行包含两个整数 n 和 m。 接下来 n行每行包含两个整数 x 和 c。 再接下来 m 行每行包含两个整数 l 和 r。
输出格式 共 m 行每行输出一个询问中所求的区间内数字和。
数据范围 −109 ≤ x ≤ 109
1 ≤ n ≤ 105
1 ≤ m ≤ 105
−109 ≤ l ≤ r ≤ 109
− 10000 ≤ c ≤ 10000 输入样例 3 3 1 2 3 6 7 5 1 3 4 6 7 8 输出样例 8 0 5 思路 由于1 ≤ n ≤ 105 和1 ≤ m ≤ 105 所调用的数字范围较小而数轴范围较大故可以将通过离散化处理将−109 ≤ x ≤ 109 范围缩为 −105 ≤ x ≤ 105 左右大大提高效率。 代码
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includealgorithm
#includevector
using namespace std;
typedef pairint, int PII;
const int N 3 * 1e5 10;
int a[N], s[N];
vectorint alls;
vectorPII add, query;// 二分查找
int find(int x)
{int l 0, r alls.size() - 1;while (l r){int mid l ((r - l) 1);if (alls[mid] x) r mid;else l mid 1;}return l 1; // 由于S是从1开始的所以对应映射位置都往前提一位
}
int main()
{int n, m;cin n m;for (int i 0; i n; i){int x, c;cin x c;add.push_back({x, c});alls.push_back(x);}for (int i 0; i m; i){int l, r;cin l r;query.push_back({l, r});alls.push_back(l);alls.push_back(r);}sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());for (auto item : add){int x find(item.first);a[x] item.second;}for (int i 1; i alls.size(); i) s[i] s[i - 1] a[i];for (auto item : query){int l find(item.first), r find(item.second);cout s[r] - s[l - 1] endl;}return 0;
}
当然这里也可以用数组lower_bound来做下面会说
1.1 Mayor’s posters POJ - 2528 思路 可以将问题转化为求区间的最小值让每个区间的海报标记为第i个放的然后用线段树来做。 查询每个海报区间的最小值是否等于i如果等于i则没有被完全覆盖。本题的数据量太大区间是[1, 1e7] 所以要用离散化存取l和r的相对大小因为n 1e4所以离散过后的区间为[1, 2 * n]。 时间复杂度O(nlogn)
#includecstdio
#includemap
#includeiostream
#includealgorithm
#define ls rt 1, l, m
#define rs rt 1 | 1, m 1, r
using namespace std;
const int maxn 2e4 5;
int mi[maxn 2], a[maxn], add[maxn2];
struct node{int l, r, pos;
}arr[maxn];
int n;
void pushUp(int rt){mi[rt] min(mi[rt 1], mi[rt 1 | 1]);
}
//下推标记
void pushDown(int rt){add[rt 1] add[rt];add[rt 1 | 1] add[rt];mi[rt 1] add[rt];mi[rt 1 | 1] add[rt];add[rt] 0;
}
//建树此过程可用memset代替
void build(int rt, int l, int r){if (l r){mi[rt] 0;return;}int m (l r) 1;build(ls);build(rs);pushUp(rt);
}
//区间修改
void update(int rt, int l, int r, int L, int R, int C){if (L l r R){mi[rt] C;add[rt] C;return;}if(add[rt] ! 0) pushDown(rt);int m (l r) 1;if (L m) update(ls, L, R, C);if (m R) update(rs, L, R, C);pushUp(rt);
}
//查询区间最小值
int query(int rt, int l, int r, int L, int R){if (L l r R){return mi[rt];}if (add[rt] ! 0) pushDown(rt);int m (l r) 1;int res maxn;if (L m) res min(res, query(ls, L, R));if (m R) res min(res, query(rs, L, R));return res;
}
//离散化
void disc(int cnt){sort(a, a cnt);int lena unique(a, a cnt) - a;for (int i 0; i n; i){arr[i].l lower_bound(a, a lena, arr[i].l) - a 1;arr[i].r lower_bound(a, a lena, arr[i].r) - a 1;// printf(l %d r %d\n, arr[i].l, arr[i].r);}
}
void solve(){scanf(%d, n);build(1, 1, n 1);int cnt 0;for (int i 0; i n; i){scanf(%d%d, arr[i].l, arr[i].r);arr[i].pos i 1;a[cnt] arr[i].l;a[cnt] arr[i].r;}disc(cnt);for (int i 0; i n; i){update(1, 1, n 1, arr[i].l, arr[i].r, arr[i].pos);} int ans 0;for (int i 0; i n; i){int x query(1, 1, n 1, arr[i].l, arr[i].r);//printf(x %d\n, x);if (x arr[i].pos) ans;}printf(%d\n, ans);
}
int main(){int t;scanf(%d, t);for (int i 0; i t; i) solve();return 0;
}1.2 Mayor’s posters POJ - 2528
/*
需要计划你接下来k天的日程。在每一天里.她可以选择学习或者颓废但是为了劳逸结合日程表有两类限制:
1、在某个时间段中至少有一天要学习。
2、在某个时间段中至少有一天要颓废。
请问一共有多少种合法的日程表?答案对1000000007取模。
输入格式
第一行三个非负整数k,n,m分别表示天数至少有一天学习的时间段个数和至少有一天颓废的时间段个数。
接下来n行每行两个正整数l,r表示第l至第r天中至少有一天学习。
接下来m行.每行两个正整数l,r表示第l至第r天中至少有一天颓废。
输出格式
一行一个整数表示答案对1000000007取模后的结果。
样例输入
5 2 2
1 3
3 5
2 2
4 5
样例输出
8以下把学习称为填黑颓废称为填白。先离散化一下每段有三种情况∶全黑、全白、有黑有白。
最终方案需要满足没有一个连续黑段包含完整的第二类区间,也没有一个连续白段包含完整的第一类区间。
设fi.gi,hi表示从左到右填到第i段且结尾是黑、白、有黑有白的合法方案数那么i这个位置往前的最长黑色、白色连续
段长度很容易求出,转移用前缀和优化一下就行了。复杂度瓶颈是离散化。
也有开两个线段树记录最后一个和末尾不同的位置的做法但是比较难写常数也较大可能被卡常。接着我们使用动态规划来计算填黑和填白的方案数。我们用fs[i]表示以第i个时间段结尾的全填黑的方案数ft[i]表示以第i个时间段结尾的全填白的方案数g[i]表示以第i个时间段结尾有黑有白的方案数。对于fs[i]我们可以根据之前的结果得到如果第i个时间段全填黑那么前一个时间段只能全填白或者有黑有白所以有fs[i] (sg[i-1] - sg[mt[i]-1] MOD) % MOD (st[i-1] - st[mt[i]-1] MOD) % MOD其中sg[i]和st[i]分别表示前i个时间段填黑和填白的方案数的前缀和mt[i]表示以第i个时间段结尾的最短黑色时间段的左端点。对于ft[i]同理我们有ft[i] (sg[i-1] - sg[ms[i]-1] MOD) % MOD (ss[i-1] - ss[ms[i]-1] MOD) % MOD其中sg[i]和ss[i]分别表示前i个时间段填黑和填白的方案数的前缀和ms[i]表示以第i个时间段结尾的最短白色时间段的左端点。对于g[i]如果我们在第i个时间段结尾填黑那么前i-1个时间段可以是全填黑、全填白或者有黑有白所以有g[i] ((fs[i-1] ft[i-1]) % MOD g[i-1]) * (2^(h[i] - h[i-1]) - 2 MOD) % MOD其中2^(h[i] - h[i-1]) - 2表示前i个时间段填黑或填白的所有方案数。
这里2^(h[i] - h[i-1]) - 2表示前i个时间段有黑有白的方案数一共有h[i]-h[i-1]并且每个时间点可以填黑或填白所以就是2^(h[i] -h[i-1])。-2是要减去全黑和全白的两种情况。最后答案就是fs[hc] ft[hc] g[hc]。*/#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
const int N 400005, mod 1e9 7;
/*ls,rs表示填黑时间段的左端点和右端点lt,rt表示填白时间段的左端点和右端点hc, h: h表示存填白\黑的时间段左右端点hc表示一共有多少个时间段 * 2 注要多存整个时间段(0, k] fs, ft, g分别表示全填黑、全填白和有黑有白的方案数。 ssstsg分别是全填黑、全填白和有黑有白的前缀和。ms和mtms存的是以R离散化过后为右端点的最短黑段的L值mt同理。
*/
int k, n, m, hc;
int ls[N], rs[N], lt[N], rt[N], h[N], ms[N], mt[N];
int fs[N], ft[N], g[N], ss[N], st[N], sg[N];
int ksm(int a, int b) { // 快速幂 int x 1;for (; b 0; b 1 ? x 1ll * x * a % mod : 0, a 1ll * a * a % mod, b 1);return x;
}
inline int m1(int x) { //求余 return x mod ? x - mod : x;
}
inline int input() {int x 0, F 1;char c getchar();while (c 9 || c 0) {if (c -)F -1;c getchar();}while (c 9 c 0) {x x * 10 c - 0;c getchar();}return x * F;
}
int main() {k input();n input();m input();for (int i 1; i n; i)ls[i] input(), rs[i] input(), h[hc] ls[i] - 1, h[hc] rs[i];for (int i 1; i m; i)lt[i] input(), rt[i] input(), h[hc] lt[i] - 1, h[hc] rt[i];h[hc] 0;h[hc] k;sort(h 1, h hc 1);hc unique(h 1, h hc 1) - h - 1; // 排序去重 for (int i 1; i n; i) { // 填黑 int L lower_bound(h 1, h hc 1, ls[i] - 1) - h, R lower_bound(h 1, h hc 1, rs[i]) - h;ms[R] max(ms[R], L 1); // LR是相对大小以R为右端点存的是最短的区间}for (int i 1; i m; i) { // 填白 int L lower_bound(h 1, h hc 1, lt[i] - 1) - h, R lower_bound(h 1, h hc 1, rt[i]) - h;mt[R] max(mt[R], L 1);}g[1] sg[1] 1; // 第一天可填黑可填白ms[1] mt[1] 1; // ms和mt保存的是第一个时间段为[1, 1]的值for (int i 2; i hc; i) {ms[i] max(ms[i - 1], ms[i]); //黑 这里找一个以i点为右端点的最大左端点mt[i] max(mt[i - 1], mt[i]);fs[i] m1(m1(sg[i - 1] - sg[mt[i] - 1] mod) m1(st[i - 1] - st[mt[i] - 1] mod));// 第i段以i结尾的全填黑 ft[i] m1(m1(sg[i - 1] - sg[ms[i] - 1] mod) m1(ss[i - 1] - ss[ms[i] - 1] mod));g[i] 1ll * m1(m1(fs[i - 1] ft[i - 1]) g[i - 1]) * (ksm(2, h[i] - h[i - 1]) - 2 mod) % mod;ss[i] m1(ss[i - 1] fs[i]);st[i] m1(st[i - 1] ft[i]);sg[i] m1(sg[i - 1] g[i]);}printf(%d, m1(m1(fs[hc] ft[hc]) g[hc]));return 0;
}
2.利用map或unordered_map进行数据离散化 使用与非区间操作 常与差分、并查集、DFS等算法结合考察 2.1 邮票 FZU - 2227【DFS】
题目描述 思路 可以先做映射关系离散化然后从最小的数并且这个数出现的次数为1开始dfs走到哪直接就存到哪。 代码
#includecstdio
#includevector
#includemap
#includecstring
using namespace std;
const int maxn1e55;
mapint,intindex,data,num;
vectorintv[maxn];//邻接表存相对大小的关系
int cnt,pos;
int dis[maxn];
bool vis[maxn];
void dfs(int x)
{if(cntpos) return;//int lenv[x].size();for(int i0;i2;i) // 题目保证有解说明一个顶点最多有两个出度{int yv[x][i];if(!vis[y]){vis[y]true;dis[pos]data[y];dfs(y);}if(cntpos) return;}
}
int main()
{int n;while(scanf(%d,n)!EOF){int ui,vi;cnt0,pos0;index.clear();data.clear();num.clear();memset(vis,false,sizeof(vis));for(int i0;i2*n;i) v[i].clear();while(n--){scanf(%d%d,ui,vi);if(!num[ui]) {index[ui]cnt;data[index[ui]]ui;//建立映射关系 1100 1001 }if(!num[vi]){index[vi]cnt;data[index[vi]]vi;}v[index[ui]].push_back(index[vi]);//建立相对大小的对应关系 v[index[vi]].push_back(index[ui]);num[ui];num[vi];}int st0;for(mapint,int::iterator itnum.begin();it!num.end();it){if(it-second1) //判断是否唯一出现第一个唯一出现的肯定是字典序最小且起始的位置 {stindex[it-first];break;}}vis[st]true;dis[pos]data[st];dfs(st);for(int i0;icnt;i){printf(%d,dis[i]);if(icnt-1) printf( );else printf(\n);}}
}2.2 More is better HDU - 1856 【并查集】
题目描述 思路 在集合合并的时如果两个集合不同那么在合并成同一个集合的时候 将被合并的集合里的个数加到这个集合里面并统计最大值。 坑点就是当输入n为0时答案为1因为当没有朋友对时各自在自己的房间所以说答案为1。 代码
#includeiostream
#includecstdio
#includemap
#includeutility
#includevector
#includealgorithm
using namespace std;
const int maxn 1e5 5;
mapint, int mp;
int fa[maxn], num[maxn], ans 0;
void init(int n){for (int i 1; i n; i){fa[i] i;num[i] 1;}
}
int find(int x){return fa[x] x ? fa[x] : fa[x] find(fa[x]);
}
void _union(int x, int y){x find(x);y find(y);if(x ! y){num[y] num[fa[x]];ans max(ans, num[y]);fa[x] y;}
}
void solve(){int n, x, y;while (scanf(%d, n) ! EOF){int cnt 0;ans 0;init(maxn); mp.clear();if (n 0){puts(1);continue;}while (n--){scanf(%d%d, x, y);if(!mp[x]) mp[x] cnt;if(!mp[y]) mp[y] cnt;_union(mp[x], mp[y]);}printf(%d\n, ans);}
}
int main(){solve();return 0;
}
2.3 金发姑娘和 N 头牛 - 1952. AcWing题库
题目描述 思路 代码
#include iostream
#include cstring
#include map
#include algorithmusing namespace std;const int INF 2e9;int n, x, y, z;int main()
{mapint, int b; // 离散化及差分数组cin n x y z;for (int i 0; i n; i ){//给三个大区间 cint l, r;cin l r;//[-INF,r)b[-INF] x;b[l] - x;//[l, r]b[l] y;b[r 1] - y;//b(r, INF]b[r 1] z;b[INF] - z;}int res 0, sum 0;// 枚举差分数组求前缀和更新最大值for(auto item : b){sum item.second;// 前缀和res max(res, sum);}cout res;return 0;
}
