Codeforces Round #218 (Div. 2) (线段树区间处理)
2024-10-19 00:25:14
A，B大水题，不过B题逗比了题意没理解清楚，讲的太不清楚了感觉= =还是英语弱，白白错了两发。
C：
二分答案判断是否可行，也逗比了下。。。二分的上界开太大导致爆long long了。。。
D：
看完题想都不想就用线段树搞起了，虽然我知道并查集很简单。。不过没用并查集写过区间处理的问题就不用多想了。。
刚开始时，所有的船都是空的，也就是说可放的水量是船的容量，然后对于第一个操作，意思就是从第x个数开始减小直到减小了p或者后面都变成0了。这里我就二分查找下最右边的会减小的数R，然后把x~R-1的数都清零，对于第R个数计算出剩余量后单点更新，mark[rt] = true表示这段区间被清零了，第二个操作直接单点询问。
E：
给你n个地铁站的位置，都是在x轴上的点，选出k个点使得k个点两两之间的距离和最小。
思路：
首先肯定是对n个点排序，这样子之后k个点肯定是排完序之后某段连续的k个。
所以可以枚举起始位置计算该位置开始的k个距离和，现在的问题就是如何O(1)的计算出该位置的结果。
假设我知道了 区间(L, R)的两两距离和，考虑区间 (L , R) 如何O(1)推出区间(L+1, R+1)，转移其实就是去掉L点，加上R+1点，很容易知道原来的距离和减小了L到其他点的距离s1，增加了R+1到其他点的距离s2，画个图很容易得到s1+s2 = （L到R+1的距离）*(k-1)，也就是说我只需要知道了L到其他点的距离和，就可以推出转移之后的两两距离和的值，所以说只需要维护上一次的两两距离和and 前一个区间的L到其他点的距离和即可。具体见代码~
这个E题实在是伤，比赛最后十分钟敲完交上了WA，最后竟然是给定的每个位置不是递增的，输出的时候要输出id，前面居然没把这个写上来= =伤，还是太弱
最新文章
- 今天被PHP短标签给坑了
- js中Array的一些扩展
- IRC常用命令
- leetcode 82. Remove Duplicates from Sorted List II
- MyEclipse中拷贝J2EE项目，发布到tomcat中名字一样的解决办法
- dede 替换后台两个文件去广告
- [转载]SQL Server内核架构剖析
- win7 Oracle 11g安装及安装中遇到的问题
- 俄罗斯方块：win32api开发
- python遗传算法实现数据拟合（转）
- CTex+WinEdt10.2安装详细教程与破解
- data-original
- jquery.datatables设置列隐藏的方法
- USACO 2008 Running(贝茜的晨练)
- 使用html2canvas将html标签转化为图片
- 不可将布尔变量直接与 TRUE、FALSE 或者 1、0 进行比较
- 【hdu6051】If the starlight never fade
- APP线上问题收集信息整理
- 简述MVC模式
- bzoj1036: [ZJOI2008]树的统计Count link-cut-tree版