BZOJ 3262: 陌上花开 (cdq分治模板题,三维偏序)

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性[……]

Read more

codeforces #413 C. Fountains (BIT维护前缀max)

题目链接

题意:有2种货币,分别为C和D.给出n种资源的代价和美丽度,每种资源只能用其中一种资源购买。现在拥有货币C的数量是c,拥有货币D的数量是d.然后恰好买2个资源,问最大美丽度,不能的话输出0.

思路:首先显然三种情况。。。CC,CD,DD.

CD直接扫一遍。。重点是CC和D[……]

Read more

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数%1E9+7的答案是多少。

思路:这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数,意义为小于等于n并且与n互质的数的个数。

To calculate the answer on eve[……]

Read more

codeforces #351 D. Jeff and Removing Periods (线段树/树状数组判断位置成等差数列)

题目链接
题意:有n个数,每次可以删除掉数值相同并且所在位置成等差数列(只删2个数或者只删1个数应该也是可以的),删掉这些数以后可以将剩下的数重新以任意顺序排列,称为一次操作。现在给出m个询问,每个询问一个区间[l,r],问删光区间[l,r]中的数最少需要的操作次数。

思路/题解:由于第一次[……]

Read more

BZOJ 3289 Mato的文件管理 (莫队算法套树状数组)

http://www.lydsy.com/JudgeOnline/problem.php?id=3289

题意:中文题目,简单来说就是求某一区间内的逆序对数。

思路:逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。[……]

Read more

hdu 1394 Minimum Inversion Number (树状数组 逆序对)

题目链接

题意:
这题是问一个长度为n的循环数组中,逆序对最少的个数。。。
我们可以先用树状数组求出初始的数列的逆序对。。。
然后其他的可以通过递推得到。。。。
当a[i]从处于位置1而被放到最后的时候。。。
cnt = cnt -a[i]+n-a[i]+1;
然后取所有cnt[……]

Read more

hdu 5480|| bestcoder   #57 div 2 Conturbatio(前缀和||树状数组)

比较水.
唯一一点需要注意的是…
可能有重复元素…
因为我的思路是用两棵一维树状数组搞..
每个点标记为1
然后看矩形的两个方向中是否至少有一个方向上和等于长度…
所以这样如果有重复元素的话,不处理会出错.. 
 
但实际上又没修改..直接前缀和就好了...

[……]

Read more

bestcoder #56 div 2 C Clarke and puzzle (nim游戏 树状数组)

比赛的时候没过.还以为是树状数组写残了.
但实际上是有自己不知道的东西.
这种博弈叫 nim游戏
所以这是一个二维的nim游戏.
nim游戏的性质是xor 和为0必败,否则必胜.
xor和也有前缀和性质,所以可以用树状数组维护.

[crayon-5a8f19daa556773755[……]

Read more

hdu 3333 Turing Tree (求区间中不相同数的和,离线+线段树/树状数组)

题目链接

喵呜,离散树状数组。

这道题由于相同的值加和的时候只算一次,所以比较伤脑筋==

怎么办呢?

我们发现对于一个值,由于相同的只算一次,所以在任意时间内,这个值只需要出现一次。

如果我们从作往右将原数组更新到树状数组,如果某个值之前出现过,那么我在更新当前的时[……]

Read more

hdu 3584 Cube (三维树状数组,更新区间,查询单点)

三维树状数组
容斥那里注意一下。
多组数据因为忘记清空c数组而wa了1次,细心!

poj 2155- Matrix (树状数组,二维,更新区间,查询单点)

1

和上一道类似,也是更新区间,查询单点。
用到了容斥原理。