月度归档:2017年10月

hihocoder#1384 Genius ACM(倍增+二分)

描述
Advanced CPU Manufacturer (ACM) is one of the best CPU manufacturer in the world. Every day, they manufacture n CPU chips and sell them all over the world.

As you may know, each batch of CPU chips must pass a quality test by the QC department before they can be sold. The testing procedure is as follows:

1) Randomly pick m pairs of CPU chips from the batch of chips (If there are less than 2m CPU chips in the batch of chips, pick as many pairs as possible.)

2) For each pair, measure the Relative Performance Difference (RPD) between the two CPU chips. Let Di be the RPD of the i-th pair

3) Calculate the Sqared Performance Difference (SPD) of the batch according to the following formula:

SPD=∑Di2

If there are only 1 CPU in a batch, then the SPD of that batch is 0.

4) The batch of chips pass the test if and only if SPD≤k, where k is a preseted constant

Usually they send all the n CPU chips as a single batch to the QC department every day. As one of the best CPU manufacturer in the world, ACM never fail the test. However, with the continuous improvement of CPU performance, they find that they are at risk!

Of course they don’t want to take any risks. So they make a decision to divide the n chips into several batches to ensure all of them pass the test. What’s more, each batch should be a continuous subsequence of their productions, otherwise the QC department will notice that they are cheating. Quality tests need time and money, so they want to minimize the number of batches.

Given the absolute performance of the n chips P1 … Pn mesured by ACM in order of manufacture, your task is to determine the minimum number of batches to ensure that all chips pass the test. The RPD of two CPU chips equals to the difference of their absolute performance.

输入
The first line contains a single integer T, indicating the number of test cases.

In each test case, the first line contains three integers n, m, k. The second line contains n integers, P1 … Pn.

T≤12
1≤n,m≤5×105
0≤k≤1018
0≤Pi≤220

输出
For each test case, print the answer in a single line.

样例输入
2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9
样例输出
2
1

首先要段数最小那么肯定是对于每个起点来说,区间长度越长越好。对于一段定长的区间,我们肯定是最大配最小来凑出一对是最好的。我们可以通过倍增确定\([pos,pos+2^{k}]\)是否合法,如果不合法,那么我们相当于固定左端点,可以在\([pos+2^{k-1},pos+2^{k}]\)二分右端点。在二分之前可以先把所有数排序,然后根据下标是否超过二分的右端点来进行选值。
时间复杂度大概是nlogn的。

BZOJ 4864: [BeiJing 2017 Wc]神秘物质(splay)

Description

21ZZ 年,冬。
小诚退休以后, 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器,整天研究各种微观粒子。这
一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始观测。 在精密仪器的视野下,构成陨石
的每个原子都无比清晰。 小诚发现, 这些原子排成若干列, 每一列的结构具有高度相似性。于是,他决定对单
独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初, 第 i 个原子具有能量 Ei。 随着
时间推移和人为测试, 这列原子在观测上会产生两种变化:
merge x e 当前第 x 个原子和第 x+1 个原子合并,得到能量为 e 的新原子;
insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。
对于一列原子,小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值,
称为区间极差。 因此, 除了观测变化外,小诚还要经常统计这列原子的两类数据:
max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值;
min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。
其中, 子区间指的是长度至少是 2 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿,你能否帮助他实现上述的观测和测量呢?
Input

第一行, 两个整数 N, M, 分别表示最初的原子数目和事件总数。
第二行, N 个整数 E1, E2, …, EN, 由空格隔开。依次表示每个原子的能量。
接下来 M 行, 每行为一个字符串和两个整数, 描述一次事件,格式见题目描述。
N<=100,000,M<=100,000 1 ≤ e, Ei ≤ 109。 设 N’ 为当前时刻原子数目。 对于 merge 类事件, 1 ≤ x ≤ N’-1; 对于 insert 类事件, 1 ≤ x ≤ N’; 对于 max 和 min 类事件, 1 ≤ x < y ≤ N’。 任何时刻,保证 N’ ≥ 2。 Output 输出若干行, 按顺序依次表示每次 max 和 min 类事件的测量结果。 Sample Input 4 3 5 8 10 2 max 1 3 min 1 3 max 2 4 Sample Output 5 2 8 一个细节很多的题目。。。调了半天。。 因为随着一个区间的长度增大,其最大值减最小值的差值也会越来越大。所以对于一个区间来说,其极差最大的子区间就是整个区间,其极差最小的区间必然是相邻的两个数。 splay维护区间最大值和最小值,以及相邻两个数的差值即可。在插入和删除的时候修改相邻的两个数的差值(注意这里一定要把两个数都旋转到当前节点的左右两侧)。

BZOJ 1441: Min(裴蜀定理)

Description

给出n个数(A1…An)现求一组整数序列(X1…Xn)使得S=A1*X1+…An*Xn>0,且S的值最小
Input

第一行给出数字N,代表有N个数 下面一行给出N个数
Output

S的最小值
Sample Input

2

4059 -1782

Sample Output

99

如果题目要求一组非负整数解,那么就是之前一种转成最短路问题的做法了。但是这个题目说得是整数解,那么直接用裴蜀定理就好了。
裴蜀定理就是:对于整系数方程ax+by=m,设g=(a,b),方程有整数解当且仅当g|m。可以拓展到n元形式。所以这个题就是求个gcd就没了。。。