月度归档:2017年12月

BZOJ 1150: [CTSC2007]数据备份Backup(堆维护带有反悔性质的贪心)

Description
  你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。然而数据备份的工作是枯燥乏味
的,因此你想设计一个系统让不同的办公楼彼此之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。已知办公
楼都位于同一条街上。你决定给这些办公楼配对(两个一组)。每一对办公楼可以通过在这两个建筑物之间铺设网
络电缆使得它们可以互相备份。然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,这意味
着你仅能为 K 对办公楼(或总计2K个办公楼)安排备份。任一个办公楼都属于唯一的配对组(换句话说,这 2K
个办公楼一定是相异的)。此外,电信公司需按网络电缆的长度(公里数)收费。因而,你需要选择这 K 对办公
楼使得电缆的总长度尽可能短。换句话说,你需要选择这 K 对办公楼,使得每一对办公楼之间的距离之和(总距
离)尽可能小。下面给出一个示例,假定你有 5 个客户,其办公楼都在一条街上,如下图所示。这 5 个办公楼分
别位于距离大街起点 1km, 3km, 4km, 6km 和 12km 处。电信公司仅为你提供 K=2 条电缆。

  上例中最好的配对方案是将第 1 个和第 2 个办公楼相连,第 3 个和第 4 个办公楼相连。这样可按要求使用
K=2 条电缆。第 1 条电缆的长度是 3km-1km=2km ,第 2 条电缆的长度是 6km-4km=2km。这种配对方案需要总长
4km 的网络电缆,满足距离之和最小的要求。
Input
  输入的第一行包含整数n和k,其中n(2 ≤ n ≤100 000)表示办公楼的数目,k(1≤ k≤ n/2)表示可利用
的网络电缆的数目。接下来的n行每行仅包含一个整数(0≤ s ≤1000 000 000), 表示每个办公楼到大街起点处
的距离。这些整数将按照从小到大的顺序依次出现。
Output
  输出应由一个正整数组成,给出将2K个相异的办公楼连成k对所需的网络电缆的最小总长度。

Sample Input
5 2

1

3

4

6

12
Sample Output
4

直接找最小的贪心不对,因为是有一定限制的。。相邻的两个值不能选。。。。这样直接最小的选择的话可能会导致不能让和最小。
但是我们可以在选择一个区间并且删除他相邻区间的时候引入反悔的概念。就是相邻的两个区间的值减去选择区间的值,作为一个新值插入,这样在后面假如选到这种情况就可以实现反悔了。新生成的区间不会超过O(n)个。
用双向链表维护左右相邻的区间。
感觉是个很神的贪心,谷歌貌似也喜欢出神贪心惨啊。。。不会做啊。。。

BZOJ 1800: [Ahoi2009]fly 飞行棋(双指针找直径)

Description
给出圆周上的若干个点,已知点与点之间的弧长,其值均为正整数,并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的,并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N,表示点的个数,接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8

1

2

2

3

1

1

3

3

Sample Output
3

HINT
N<= 20 题图没粘下来还是去bzoj看吧。。。 暴力的方法不说了,但是我们发现一个问题:如果在圆上找对边相等的四个点就可以判断出来是否是矩形。因为这些都是中心对称的图形啊QAQ。。。 所以这样我们可以证明只要有两条对角线,他们就可以组成一个矩形,所以数直径就好啦QAQ。。。

hdu 6252 Subway Chasing(差分约束系统)

Problem Description
Mr. Panda and God Sheep are roommates and working in the same company. They always take subway to work together. There are N subway stations on their route, numbered from 1 to N. Station 1 is their home and station N is the company.
One day, Mr. Panda was getting up later. When he came to the station, God Sheep has departed X minutes ago. Mr. Panda was very hurried, so he started to chat with God Sheep to communicate their positions. The content is when Mr. Panda is between station A and B, God Sheep is just between station C and D.
B is equal to A+1 which means Mr. Panda is between station A and A+1 exclusive, or B is equal to A which means Mr. Panda is exactly on station A. Vice versa for C and D. What’s more, the communication can only be made no earlier than Mr. Panda departed and no later than God Sheep arrived.
After arriving at the company, Mr. Panda want to know how many minutes between each adjacent subway stations. Please note that the stop time at each station was ignored.

Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test case starts with a line consists of 3 integers N, M and X, indicating the number of stations, the number of chat contents and the minute interval between Mr. Panda and God Sheep. Then M lines follow, each consists of 4 integers A, B, C, D, indicating each chat content.
1≤T≤30
1≤N,M≤2000
1≤X≤109
1≤A,B,C,D≤N
A≤B≤A+1
C≤D≤C+1

Output
For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the minutes between stations in format t1,t2,…,tN−1. ti represents the minutes between station i and i+1. If there are multiple solutions, output a solution that meets 0=tc
ta+x<=td 否则 tb+x>tc
ta+x