题目链接:zoj 3511 Cake Robbery
题目大意:就是有一个N边形的蛋糕,切M刀,从中挑选一块边数最多的,保证没有两条边重叠。
解题思路:有多少个顶点即为有多少条边,所以直接按照切刀切掉点的个数排序,然后用线段树维护剩下的还有哪些点。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 10005;
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)|1)
int lc[maxn << 2], rc[maxn << 2], s[maxn << 2];
inline void pushdown(int u) {
if (s[u] == 0)
s[lson(u)] = s[rson(u)] = 0;
}
inline void pushup(int u) {
s[u] = s[lson(u)] + s[rson(u)];
}
void build (int u, int l, int r) {
lc[u] = l;
rc[u] = r;
if (l == r) {
s[u] = 1;
return;
}
int mid = (l + r) / 2;
build(lson(u), l, mid);
build(rson(u), mid + 1, r);
pushup(u);
}
void modify (int u, int l, int r) {
if (l > r)
return;
if (l <= lc[u] && rc[u] <= r) {
s[u] = 0;
return;
}
pushdown(u);
int mid = (lc[u] + rc[u]) / 2;
if (l <= mid)
modify(lson(u), l, r);
if (r > mid)
modify(rson(u), l, r);
pushup(u);
}
int N, M;
struct Seg {
int l, r, c;
Seg (int l = 0, int r = 0) {
this->l = l;
this->r = r;
this->c = r - l + 1;
}
friend bool operator < (const Seg& a, const Seg& b) {
return a.c < b.c;
}
};
vector<Seg> vec;
int main () {
while (scanf("%d%d", &N, &M) == 2) {
int l, r, ans = 0;
build(1, 1, N);
vec.clear();
while (M--) {
scanf("%d%d", &l, &r);
if (l > r) swap(l, r);
vec.push_back(Seg(l, r));
}
sort(vec.begin(), vec.end());
for (int i = 0; i < vec.size(); i++) {
int tmp = s[1];
modify(1, vec[i].l + 1, vec[i].r - 1);
ans = max(ans, tmp - s[1] + 2);
}
printf("%d\n", max(ans, s[1]));
}
return 0;
}
分享到:
相关推荐
本资源是对线段树操作比较完整的操作,包括线段树的动态插入,动态删除和维护,可以查询区段的最大值,最小值,完成线段树的基本操作。
hdu 1166线段树
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
2416和2451测试程序原代码,编译成功,好使
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
浙江大学2451题 用线段树思想解的,c++语言版本
acm中zoj1002的可运行C++程序
包含了zoj700多道题目的源代码,在做题时可以参考
Problem Arrangement zoj 3777
ZOJ题目答案源码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
一个非常非常非常非常实用的zoj结题代码
zoj 1003 c语言的,要写这么多描述吗。。
ZOJ1805代码
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
zoj1027解题指南和代码,还不错,是学校培训给的。
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm