admin管理员组文章数量:1026989
D. Boris and His Amazing Haircut（线段树）
传送门
题意：
给定长度为 n 的数组 A ，代表 Boris 现在的头发长度，和一个长度为 n 的数组 B ，代表他希望的发型的头发长度。理发师手里有 m 把剪刀，每个都只能用一次，剪刀的所剪的高度用 xi 给出。
对于每一把未使用过的推子：
理发师可以选择一个 [l,r] 区间；
将该区间的所有头发 ai 修建为 min(ai,x) 。
请问理发师用手中的这些推子，能不能剪完 Boris 的发型。思路：
首先分析一定剪不出发型的可能：
１）现在的头发长度小于要剪的头发长度
２）要剪的发型的长度没有对应的剪刀
然后对于剩下的情况，我们剪头发肯定是要从高的剪刀开始剪，因为处理完高的情况可以处理低的头发，但是对于低的情况一定处理不了高的头发了。然后考虑某个区间［ｌ，ｒ］，如果，并且在［ｌ＋１，ｒ－１］上，那么这一把剪刀可以把ｌ和ｒ两个点的发型都完成。
就相当于如果对于两个相邻的相同的，如果最大值不大于，那么就不需要花费额外的剪刀；否则就需要多花费一把剪刀。那么就可以简化为对于某一种长度的头发x，遍历他的下标，如果有区间的最大值大于x就需要的剪刀数++（最少剪刀要一把），然后遍历完之后如果存在的剪刀数小于需要的剪刀数就可以直接标记，最后直接输出答案即可。
这里找区间最大值我用的是线段树，用树状数组也是可以的（自己找罪受）。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long
using namespace std;const int N = 1000000 + 100;
int n, m, h;
int a[N], b[N], be[N];
struct lk
{int x;int l;int r;int max;
} tr[N * 4];
void update(int u);
void update(lk &u, lk &l, lk &r);void update(int u) { update(tr[u], tr[u << 1], tr[u << 1 | 1]); }void update(lk &u, lk &l, lk &r) { u.max = max(l.max, r.max); }void build(int u, int l, int r)
{int mid = l + r >> 1;if (l == r){tr[u] = {a[l], l, l, a[l]};}else{tr[u].l = l, tr[u].r = r;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);update(u);}
}int get(int u, int l, int r)
{int res = 0;if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;else{int mid = tr[u].l + tr[u].r >> 1;if (mid >= l)res = max(res, get(u << 1, l, r)); // 访问左区间if (mid < r)res = max(res, get(u << 1 | 1, l, r)); // 访问右区间update(u);}return res;
}void solve()
{sc_int(n);bool flag = 0;vector<int> cnt;//有多少种发型map<int, vector<int>> q;//每种发型的下标map<int, int> p;//每种剪刀的数量for (int i = 1; i <= n; i++)sc_int(be[i]);for (int i = 1; i <= n; i++){sc_int(a[i]);if (be[i] < a[i]) flag = 1;if(be[i]!=a[i])q[a[i]].push_back(i);}build(1, 1, n);sc_int(m);for (int i = 1; i <= m; i++){sc_int(b[i]);if (!p[b[i]])cnt.push_back(b[i]);p[b[i]]++;}for (int i = 1; i <= n; i++)if (!p[a[i]] && a[i] != be[i])flag = 1;if (flag){printf("NO\n");return;}for (int i = 0; i < cnt.size(); i++){int time = p[cnt[i]];int num = 1;if (q[cnt[i]].size() == 0)continue;for (int k = 0; k < q[cnt[i]].size() - 1; k++){int l = q[cnt[i]][k], r = q[cnt[i]][k + 1]; // 左右区间if (get(1, l, r) > cnt[i])num++;}if (num > time)flag = 1;}if (flag)printf("NO\n");elseprintf("YES\n");return;
}int main()
{int t;sc_int(t);while (t--)solve();return 0;
}
D. Boris and His Amazing Haircut（线段树）
传送门
题意：
给定长度为 n 的数组 A ，代表 Boris 现在的头发长度，和一个长度为 n 的数组 B ，代表他希望的发型的头发长度。理发师手里有 m 把剪刀，每个都只能用一次，剪刀的所剪的高度用 xi 给出。
对于每一把未使用过的推子：
理发师可以选择一个 [l,r] 区间；
将该区间的所有头发 ai 修建为 min(ai,x) 。
请问理发师用手中的这些推子，能不能剪完 Boris 的发型。思路：
首先分析一定剪不出发型的可能：
１）现在的头发长度小于要剪的头发长度
２）要剪的发型的长度没有对应的剪刀
然后对于剩下的情况，我们剪头发肯定是要从高的剪刀开始剪，因为处理完高的情况可以处理低的头发，但是对于低的情况一定处理不了高的头发了。然后考虑某个区间［ｌ，ｒ］，如果，并且在［ｌ＋１，ｒ－１］上，那么这一把剪刀可以把ｌ和ｒ两个点的发型都完成。
就相当于如果对于两个相邻的相同的，如果最大值不大于，那么就不需要花费额外的剪刀；否则就需要多花费一把剪刀。那么就可以简化为对于某一种长度的头发x，遍历他的下标，如果有区间的最大值大于x就需要的剪刀数++（最少剪刀要一把），然后遍历完之后如果存在的剪刀数小于需要的剪刀数就可以直接标记，最后直接输出答案即可。
这里找区间最大值我用的是线段树，用树状数组也是可以的（自己找罪受）。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long
using namespace std;const int N = 1000000 + 100;
int n, m, h;
int a[N], b[N], be[N];
struct lk
{int x;int l;int r;int max;
} tr[N * 4];
void update(int u);
void update(lk &u, lk &l, lk &r);void update(int u) { update(tr[u], tr[u << 1], tr[u << 1 | 1]); }void update(lk &u, lk &l, lk &r) { u.max = max(l.max, r.max); }void build(int u, int l, int r)
{int mid = l + r >> 1;if (l == r){tr[u] = {a[l], l, l, a[l]};}else{tr[u].l = l, tr[u].r = r;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);update(u);}
}int get(int u, int l, int r)
{int res = 0;if (tr[u].l >= l && tr[u].r <= r) return tr[u].max;else{int mid = tr[u].l + tr[u].r >> 1;if (mid >= l)res = max(res, get(u << 1, l, r)); // 访问左区间if (mid < r)res = max(res, get(u << 1 | 1, l, r)); // 访问右区间update(u);}return res;
}void solve()
{sc_int(n);bool flag = 0;vector<int> cnt;//有多少种发型map<int, vector<int>> q;//每种发型的下标map<int, int> p;//每种剪刀的数量for (int i = 1; i <= n; i++)sc_int(be[i]);for (int i = 1; i <= n; i++){sc_int(a[i]);if (be[i] < a[i]) flag = 1;if(be[i]!=a[i])q[a[i]].push_back(i);}build(1, 1, n);sc_int(m);for (int i = 1; i <= m; i++){sc_int(b[i]);if (!p[b[i]])cnt.push_back(b[i]);p[b[i]]++;}for (int i = 1; i <= n; i++)if (!p[a[i]] && a[i] != be[i])flag = 1;if (flag){printf("NO\n");return;}for (int i = 0; i < cnt.size(); i++){int time = p[cnt[i]];int num = 1;if (q[cnt[i]].size() == 0)continue;for (int k = 0; k < q[cnt[i]].size() - 1; k++){int l = q[cnt[i]][k], r = q[cnt[i]][k + 1]; // 左右区间if (get(1, l, r) > cnt[i])num++;}if (num > time)flag = 1;}if (flag)printf("NO\n");elseprintf("YES\n");return;
}int main()
{int t;sc_int(t);while (t--)solve();return 0;
}本文标签： D Boris and His Amazing Haircut（线段树）
版权声明：本文标题：D. Boris and His Amazing Haircut（线段树） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/IT/1694634348a254319.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论