Posts match “ 树状数组 ” tag:

http://codeforces.com/gym/100463

切了场GYM。

A题
简单树状数组。

C题
首先对每个点连出的边进行极角排序(范围内),由于题意是逆时针旋转,我们可以G[i][angle[j].y] = angle[j + 1].y;这样用邻接矩阵建图。
建好图后 DFS 下就可以求出所有圈的长度了。

(顺便吐槽下此题时限为 40 s)

D题
直接枚举红点一半的组合就行,不需要判断是否有其他红点在所选的红点围成的矩形内,因为在这种情况下,一定有比该矩形更小的矩形。

E题
并查集。合并的时候要讨论清楚:

  1. 当 x==y 时集合唯一确定,用一个布尔数组 uni 表示(uni 表示 unique);
  2. merge 时要合并人数,集合大小,uni 这三个。

I题
这题需要有特殊的 YY 技巧。
由于要使A集合与B集合扩张成一个对减法封闭的,所以必须要有单位元 1 和 -1,进一步分析发现我们要判断出是否可以从A集合中可重复地取出 x 个数,从B集合中可重复地取出 x-1 或 x 个数,使得对于某些取法 sumA-sumB=1,某些取法 sumA-sumB=-1。

显然答案与有关,设其值为g,则 g=1 时可以扩张成;由于还可以先往右边多走一步,则 g=2 且集合A中存在奇数时也可以扩张成(g=2 说明可以扩展成偶整数集合,此时只要集合A中有个奇数就可以扩张成);但是对于 g>2 的情况却不行,这是因为此时扩张成 {...,-2g,-g,0,g,2g,...} 的集合,但又由于,所以,令,则只能扩张成形如 mg+k 的集合。
优化:

  1. 可以简化为
  2. 根据此简化式,判断集合A中是否有奇数可以简化为判断是否为奇数;
  3. 判断

附代码:

继续阅读

http://codeforces.com/contest/387

E题

贪心+树状数组。
很明显,从最小的开始删除得到的香肠最多。做个位置标记,然后往set里面加要留下的数(从小到大)的位置值,并对每一个要删除的数(这个不加到set中)求出其往左往右能到达的位置值,然后用树状数组统计这一区间有多少个没有删除的数,即为得到的香肠数。

继续阅读

http://codeforces.com/contest/301

A题

注意到在若干次操作后,我们可以使序列中的 0,2,4,... 个元素改变符号,并且,当n为奇数的时候,我们可以改变奇数个元素的符号。从而在n为奇数时我们可以改变任意多个元素的符号,而在n为偶数时只能改变偶数个与元素的符号。
继续讨论n为偶数的情况,若负数有偶数个,则都变为正即可;若负数有奇数个,则需要看绝对值最小的那个在原序列中是负数还是正数,若是负数则不改,若是整数则把那个负数改为正。

附 Python 代码:

n = input()
a = map(int, raw_input().split())
aa = map(abs, a)
print sum(aa) - (1 - n % 2) * len([i for i in a if i < 0]) % 2 * 2 * min(aa)

B题

很明显,每条边i-j的权值为(abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i]

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = int(1e2) + 5;

int d[mx][mx], a[mx], x[mx], y[mx];
int floyd(int n) {int i, j, k; For(k, n) For(i, n) For(j, n) Qmin(d[i][j], d[i][k] + d[k][j]); return d[0][n - 1];}

int main()
{
    int n, c, i, j;
    SII(n, c);
    SA(a + 1, i, n - 2);
    For(i, n) SII(x[i], y[i]);
    For(i, n) For(j, n) if (j != i) d[i][j] = (abs(x[i] - x[j]) + abs(y[i] - y[j])) * c - a[i];
    PI(floyd(n));
    return 0;
}

D题

只有查询,必然离线。
由于序列是1~n的某个全排列,我们可以从1~n逐步更新,同时进行计算。
我们可以用1~R的对数减去1~L-1的对数,但是这样算的结果包含了一个属于1~L-1另一个属于L~R的对数,减之。(在写的过程中还有很多细节,详见代码)

代码:

继续阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4630

比较能体现离线威力的一道题。
为了方便使用树状数组维护区间最值,我们从右往左遍历 a 数组,这样查询也要根据 l 从大往小排序。
对于 a[i] 这个数,对它的每个因子 m,我们找一个在 a[i] 右边的,离 a[i] 最近的,且同样有因子 m 的数,其下标为 j,则更新树状数组 j 位置的最值为 m。
为什么找最近的?因为离线查询按照 l 排序后有个天然的包含关系
然后用树状数组查询区间最值就行。

继续阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4638

首先离线,按 r 从小往大排序。

由不等式 可知,集合的个数越少越好。那么这道题的关键就在于如何「合并」集合。

为了说明的方便,举个例子:

设 ID 数组为 1,3,2,5,4,我们从左往右遍历,每读到一个数,树状数组当前位置就 +1,表示新增一个集合。

然后试着合并,看当前位置 i 前面有没有 a[i]-1 和 a[i]+1,有的话树状数组 pos[a[i]-1] 和 pos[a[i]+1] 就 -1,表示合并集合。

注意,遍历到最后一个数 4 的时候,我们把 3 和 5 所在位置各 -1(合并集合),但是先前遍历 2 的时候已经把 3 所在位置 -1 了,这对结果是没有影响的,因为查询的时候,3 会与 2 相互抵消。

继续阅读