我是靠谱客的博主 风中花生，最近开发中收集的这篇文章主要介绍2019杭电多校第9场1002 Rikka with Cake HDU66812019杭电多校第9场1002 Rikka with Cake HDU6681解法1：红黑树+思维+贪心解法2：树状数组+思维+贪心，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
2019杭电多校第9场1002 Rikka with Cake HDU6681
题意：给你若干个点按上下左右切割平面，最后问平面内有几块被切割开来。
解法1：红黑树+思维+贪心
A：根据欧拉定理可以得出（具体参照题解），平面内有多少个交点，那么就有这么多个+1的平面被分割出来，所以这题目就是找点。
B：将U,D,L,R分开来存在四个结构体中，然后分类讨论U和L相交的点数，U和R相交的点数，D和L相交的点数，D和R相交的点数，最后相加再+1就是答案。
C：在讨论的时候。举例(U和L相交）。按着l[i]的x从小到大排序，u[i]的x从小到大排序，然后遍历l，找l[i]能和几条向上的线相交。我们可以知道相交必然意味着，u[j]的x比l[i]的小，同时我们要找在这几个中有几个u[j]的y坐标小于l[i].y，最后全部相加。这样就讨论完了一处情况。
D：关于上面C黄字的处理，利用红黑树，正好插入一个值与查询有几个小于的复杂都是log(n)，然后不停插入，然后比较相加就完事了。
解法2：树状数组+思维+贪心
A：早上看了一下题解发现树状数组也能做，贴一个树状数组的解法吧，其实和上面的解法很像，就是把(D过程）红黑树改成树状数组就OK了。
B：两者代码的不同也很明显，我直接在我的红黑树上改了一下，具体可以看代码2。
闲话123：关于红黑树，我这里偷懒使用超级STL库来实现了。比赛的时候，想了很久主席树该怎么实现，写到吐血。。最后发现了有pb_ds这个神奇的东西，最后花了30分钟写题目，WA了三发。。。最后赛后刚把题目放出来就A了，真赛后三分钟A题，谢队友不杀。
PS：超级STL库只能在clion里面运行，辣鸡VS2019
解法1代码1：
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
typedef long long ll;
ll n,m,k;
const int mx = 3e5+7;
struct node
{
ll x, y;
}u[mx],d[mx],l[mx],r[mx];
bool cmp(node a,node b) {
return a.x < b.x;
}
int main (){
ios_base::sync_with_stdio(false);
rbtree stlnb;
int t;
cin >> t;
while (t--) {
cin >> n >> m >> k;
ll cnt[6] = { 0 };
for (int i = 1; i <= k; i++) {
ll x, y; char s;
cin>>x>>y>>s;
if (s == 'U')
u[++cnt[1]].x = x, u[cnt[1]].y = y;
else if (s == 'D')
d[++cnt[2]].x = x, d[cnt[2]].y = y;
else if (s == 'L')
l[++cnt[3]].x = x, l[cnt[3]].y = y;
else if (s == 'R')
r[++cnt[4]].x = x, r[cnt[4]].y = y;
}
sort(u + 1, u + 1 + cnt[1], cmp);
sort(d + 1, d + 1 + cnt[2], cmp);
sort(l + 1, l + 1 + cnt[3], cmp);
sort(r + 1, r + 1 + cnt[4], cmp);
ll sumn = 0;
ll f = 1;
for (int i = 1; i <= cnt[3]; i++) {
for (int j = f; j <= cnt[1]; j++) {
f = j+1;
if (l[i].x >= u[j].x)
stlnb.insert(u[j].y);
else {
f = j;
break;
}
}
sumn += stlnb.order_of_key(l[i].y);
}
stlnb.clear();
f = cnt[1];
for (int i = cnt[4]; i >= 1; i--) {
for (int j = f; j >= 1; j--) {
f = j-1;
if (r[i].x <= u[j].x)
stlnb.insert(u[j].y);
else {
f = j;
break;
}
}
sumn += stlnb.order_of_key(r[i].y);
}
stlnb.clear();
f = 1;
for (int i = 1; i <= cnt[3]; i++) {
for (int j = f; j <= cnt[2]; j++) {
f = j+1;
if (l[i].x >= d[j].x)
stlnb.insert(d[j].y);
else {
f = j;
break;
}
}
sumn += stlnb.size() - stlnb.order_of_key(l[i].y);
}
stlnb.clear();
f = cnt[2];
for (int i = cnt[4]; i >= 1; i--) {
for (int j = f; j >= 1; j--) {
f = j-1;
if (r[i].x <= d[j].x)
stlnb.insert(d[j].y);
else {
f = j;
break;
}
}
sumn += stlnb.size() -stlnb.order_of_key(r[i].y);
}
stlnb.clear();
cout<<sumn+1<<endl;
}
return 0;
}
解法2代码：
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,m,k;
const int mx = 3e5+7;
const ll wa = 1e9+7;
struct node
{
ll x, y;
ll qx,qy;
}u[mx],d[mx],l[mx],r[mx];
ll ssx[mx],ssy[mx];
bool cmp(node a,node b) {
return a.x < b.x;
}
int bit[mx];
int lowbit(int x)
{
return x&(-x);
}
void add(int i,int x)
{
while(i<=k)
{
bit[i]+=x;
i+=lowbit(i);
}
}
void sub(int i,int x)
{
while(i<=k)
{
bit[i]-=x;
i+=lowbit(i);
}
}
int sum(int i)
{
int s=0;
while(i>0)
{
s+=bit[i];
i-=lowbit(i);
}
return s;
}
int main (){
ios_base::sync_with_stdio(false);
#ifdef ACM_LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
cin >> n >> m >> k;
ll cnt[6] = { 0 };
for (int i = 1; i <= k; i++) {
ll x, y; char s;
cin>>x>>y>>s;
if (s == 'U')
u[++cnt[1]].x = x, u[cnt[1]].y = y;
else if (s == 'D')
d[++cnt[2]].x = x, d[cnt[2]].y = y;
else if (s == 'L')
l[++cnt[3]].x = x, l[cnt[3]].y = y;
else if (s == 'R')
r[++cnt[4]].x = x, r[cnt[4]].y = y;
ssx[i] = x;
ssy[i] = y;
}
sort(ssx+1,ssx+1+k);
sort(ssy+1,ssy+1+k);
sort(u + 1, u + 1 + cnt[1], cmp);
sort(d + 1, d + 1 + cnt[2], cmp);
sort(l + 1, l + 1 + cnt[3], cmp);
sort(r + 1, r + 1 + cnt[4], cmp);
ll sumn = 0;
ll f = 1;
for (int i = 1; i <= cnt[3]; i++) {
for (int j = f; j <= cnt[1]; j++) {
f = j+1;
if (l[i].x >= u[j].x) {
int sr = lower_bound(ssy+1,ssy+1+k,u[j].y)-ssy;
add(sr,1);
//stlnb.insert(u[j].y);
}
else {
f = j;
break;
}
}
//sumn += stlnb.order_of_key(l[i].y);
sumn+=sum(lower_bound(ssy+1,ssy+1+k,l[i].y)-ssy);
}
//stlnb.clear();
memset(bit,0,sizeof(bit));
f = cnt[1];
for (int i = cnt[4]; i >= 1; i--) {
for (int j = f; j >= 1; j--) {
f = j-1;
if (r[i].x <= u[j].x)
add(lower_bound(ssy+1,ssy+1+k,u[j].y)-ssy,1);//stlnb.insert(u[j].y);
else {
f = j;
break;
}
}
// sumn += stlnb.order_of_key(r[i].y);
sumn += sum(lower_bound(ssy+1,ssy+1+k,r[i].y)-ssy);
}
//stlnb.clear();
memset(bit,0,sizeof(bit));
f = 1;
ll ssr = 0;
for (int i = 1; i <= cnt[3]; i++) {
for (int j = f; j <= cnt[2]; j++) {
f = j+1;
if (l[i].x >= d[j].x)
add(lower_bound(ssy+1,ssy+1+k,d[j].y)-ssy,1),ssr++;//stlnb.insert(d[j].y);
else {
f = j;
break;
}
}
//sumn += stlnb.size() - stlnb.order_of_key(l[i].y);
sumn += ssr - sum(lower_bound(ssy+1,ssy+1+k,l[i].y)-ssy);
}
//stlnb.clear();
memset(bit,0,sizeof(bit));
ssr = 0;
f = cnt[2];
for (int i = cnt[4]; i >= 1; i--) {
for (int j = f; j >= 1; j--) {
f = j-1;
if (r[i].x <= d[j].x)
add(lower_bound(ssy+1,ssy+1+k,d[j].y)-ssy,1),ssr++;//stlnb.insert(d[j].y);
else {
f = j;
break;
}
}
//sumn += stlnb.size() -stlnb.order_of_key(r[i].y);
sumn += ssr - sum(lower_bound(ssy+1,ssy+1+k,r[i].y)-ssy);;
}
//stlnb.clear();
memset(bit,0,sizeof(bit));
cout<<sumn+1<<endl;
}
return 0;
}
最后
以上就是风中花生为你收集整理的2019杭电多校第9场1002 Rikka with Cake HDU66812019杭电多校第9场1002 Rikka with Cake HDU6681解法1：红黑树+思维+贪心解法2：树状数组+思维+贪心的全部内容，希望文章能够帮你解决2019杭电多校第9场1002 Rikka with Cake HDU66812019杭电多校第9场1002 Rikka with Cake HDU6681解法1：红黑树+思维+贪心解法2：树状数组+思维+贪心所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复