codeforces 555C Case of Chocolate set操作

65 阅读 0 评论 43 点赞

我是靠谱客的博主曾经橘子，最近开发中收集的这篇文章主要介绍codeforces 555C Case of Chocolate set操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

有一块n*n大小的巧克力，n<=1e9。现在进行操作，每次都从反对角线上选择一点，然后往上或往左一直吃（说明下三角部分是废了），每当到达巧克力边缘或者下一块已经被吃了，则停止。问你每次操作能吃到几块巧克力。

思路：

网上各种搜，代码抄大神们的= =，题解都写得好简洁啊。

首先先介绍区间这一个概念。

例如第一个样例，在执行完第二个操作后，区间就分为了【2,3】和【5,6】，其实就是按行来分，被选过的行就不要了。

在第五个操作4 3 U 中，我们想知道最大能往上多少，实际上这个信息就保存在临近x = 1(第一次操作的位置）

如果换成是L操作，那么最大能往左多少，就保存临近的x = 4（第二次操作的位置）

因此我们就想到用set根据输入的x寻找所存在的区间。

在每次输出结果之后，我们都会将旧区间的信息赋值给新生成的区间（不得不佩服这代码写得真够简练）。

一开始，只有一个区间，并且最大能往上和最大能往左都是坐标都是最大的。

code：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
typedef pair<int, int> pii;
#define mp make_pair
set <pii> st;
set <pii>::iterator it;
int n, q;
char ch[5];
int x[N], y[N];
int main() {
scanf("%d%d", &n, &q);
st.insert(mp(0, 0));
st.insert(mp(n+1, q+1));
for(int i = 1;i <= q; i++) {
scanf("%d%d%s", &y[i], &x[i], ch);
if(ch[0] == 'U') {
it = st.lower_bound(mp(x[i], -1));
if(it->first > x[i]) it--;
}
else {
it = st.upper_bound(mp(x[i], -1));
}
if(it->first == x[i]) {
puts("0");
continue;
}
st.insert(mp(x[i], i));
if(ch[0] == 'U') {
printf("%dn", x[i]-x[it->second]);
x[i] = x[it->second];
}
else {
printf("%dn", y[i]-y[it->second]);
y[i] = y[it->second];
}
}
return 0;
}