题目链接 题意: 求矩形周长并。 思路： 线段树+扫描线。 和前面的求面积并比较类似，我们先考虑平行x轴的线段，考虑线段树，维护的一段区间中被矩形覆盖的次数cnt和至少覆盖一次的长度的len. 只不过我们这次求的是每条扫描线的长度对周长的贡献，因此不需要乘高度。 需要注意的是，每条扫描线对周长的贡献，是目前扫描线的长度，与上一次扫描线长度的差的绝对值。（不是与上一次答案的差的绝对值！） 演示x轴求长度和的部分 图片来自 lwt聚聚的博客 以及一个小细节是，求面积的时候，最后一条扫描线对答案是没有贡献的（因为每次是求当前扫描线与下一条扫描线之间的面积） 但是求周长的时候，最后一条扫描线是一定会对答案有贡献的。 /* …

题目链接 题意： 求n（1000）个矩形的面积交，也就是至少有2个矩形覆盖的区域的面积。 思路： 和矩形面积并_hdu1542解题报告  类似 面积并问题中，线段树len维护的是至少覆盖一次的区域的长度 在面积交的问题中，我们需要多维护一个"至少覆盖两次的区域的长度"的域（设为double two;） 同时也要维护至少覆盖一次的区域的长度（设为double one;），是因为至少覆盖两次的区域的长度可以由至少覆盖一次的区域长度得到（好像是废话） PushUp的时候要格外注意当前节点被完整覆盖一次的情况。 此时tree[rt].two 可以由两个子区间的one的情况想加得到 （因为rt节点被完整覆盖了至少一次，那么 …

hdu1542题目链接 题意： 求n(100)个矩形的面积并。 思路： 扫描线+线段树 题目是2000年中欧区域赛的题目，虽然年代久远，但是有好几个点还是很值得学习的。 首先是离散化的适用范围: 之前比较常用的是将比较大的整数值离散化，常常是因为数值太大无法作为下标。 那么其实，浮点数有的时候也需要进行离散化，比如作为数组的下标，比如用来枚举。 做法上是和将较大的整数值离散化没有区别，因为遇到的题目不多，所以特意记录一下。 第二点是扫描线的思想： 其实扫描线的思想很早就接触过，noip2011的时候，tyvj上有一道类似的题目，不过是一唯的，当时印象深刻的是@Ocean 兄的那个比喻： 一段公路上右很多区间要收不同的费用，区间的开始 …

zoj3606题目链接 题意：有个小女孩卖火柴,有n个人会来买，分别在时间t[i]，以价格p[i]，买的火柴个数为1+(k-1)%3,其中k为这是小女孩第几次卖火柴。 如果有大于w的时间没人来买火柴，小女孩就会睡着。小女孩睡着后如果有人来买火柴，那小女孩就会醒过来，但是不会卖给这个人火柴。现在问使营业额最大的基础上最小的时间间隔w。 思路： 显然，w应该是某2个顾客的来访时间只差（而不是什么任意值）. 因此我们可以通过枚举相邻访问时间的顾客的访问之间之差。 我们可以从小到大枚举w，这样就可以保证得到的最大营业额的对应w最小。 构造一颗线段树，维护4个域，cnt表示区间中，确实购买了火柴的顾客的人数，sum[i] (i属于0..2) …

题目链接 题意：n（1E5）个操作，分为三种，add x表示将x加到集合中（保证集合中之前没有x)，del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后，所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9 思路：很容易想到的是，由于插入和删除元素造成的位置改变是剧烈的，因此要分别维护i%5==k,k属于0..4的元素的和。 这道题的核心点在于，由于只有1E5个操作，我们可以将元素离散化，这样做的目的是，将每个数和位置一一对应，每个位置用1或者0，表示该位置对应的元素是否在集合中。 考虑线段树，维护6个域，1个是区间中，在集合中的元素个数，剩下5个域，分别表示以该区间的端 …

题目链接 题意：给出n,p,q,r,以及n（1E5）个数，所有数的范围都是[-1E9,1E9],现在问p_a[i]+q_a[j]+r*a[k]的最大值，满足1<=i<=j<=k<=n 思路：傻逼dp... 我。。好菜啊。。。万年dp苦手。 直接转载官方题解了。。。思路的重点是维护了一个最大前缀值。 _dp_[_i_][0] stores maximum of value _p_·_a__x_ for _x_ between 1 and _i_. Similarly _dp_[_i_][1] stores the maximum value of _p_·_a__x_ + _q_·_a__y_ such …

题目链接 题意：有若干线段，给出起点和终点，问是否有一个线段是冗余的。冗余的意思是说，对于该线段所覆盖的所有整数点，没有该线段，也能被其他一个或者多个线段覆盖到。如果有，输出任意一个冗余线段即可。 思路：画画图？ 显然可以按照第一关键字左端点升序，第二关键字右端点降序（降序是为了处理 n=2,[1,2],[1,3] 这样的case容易一些），先考虑2种最简单的情况。 第一种是a[i+1]完全被a[i]包裹在里面，准确得说不一定是a[i]，而是之前所有线段的最大右端点的那条线段，此时a[i+1]就是冗余的线段。 第二种是a[i+1]的左端点在之前所有线段的最大右端点右边，此时没有冗余，继续进行。 接下来考虑比较复杂的相交情况，我们画图 …

比赛链接 10个月没写题了，菜啊。进行一点恢复性训练好了。 A: 给一个数，可以在填写若干（或者0）个前缀0，问能否变成回文数。 思路是直接删掉后面可能的出现的0再判断回文数就好。 /* *********************************************** Author :111qqz Created Time :2017年09月24日 星期日 13时51分06秒 File Name :A.cpp ************************************************ */ #include <cstdio> #include <cstring> …

题目链接 题意： 一棵树，给出点权，问一条树链上第k大的点权，点权可以动态修改。 思路： 暴力即可orz(数据是真的水啊。 求路径上的点的时候需要用到LCA /* *********************************************** Author :111qqz Created Time :2017年07月31日 星期一 01时12分54秒 File Name :3078.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

题目链接 题意： 给出一棵树，以及三个点（可能重合），问两两组成的3条路径中，哪2条路径重合部分最长。 思路： LCA还是一下就能想到的，rmq+dfs在线求。 然后我开始分情况讨论，讨论了一年也没讨论完，哭哭 结论是：求出三个lca，并取深度最大的那个，就是我们要的三岔路口K，然后分别求出K到a，b，c三点的路径长度，取最大值+1就是答案。 所以我的问题在于，没有试图往一般性的方向考虑，以为讨论一下就可以了... 这大概就是所谓的猜结论？ 感性的理解的话，LCA越深，意味着另一个点到LCA的距离越远，也就是相交的路径越长 但是我的话，估计还是很难在短短不到一个小时内得出这样一般性的结论orz... 这大概就是数学方面的天赋差距 …