http://www.lydsy.com/JudgeOnline/problem.php?id=3289
题意:中文题目,简单来说就是求某一区间内的逆序对数。
思路:逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。
阅读更多There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array …
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=5416
题意:给出一棵树(n<=1E5),定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询(q<=10),每组一个s,问有多少对无序点对(u,v)满足f(u,v)=s. 思路:类似codeforces #340 div 2 E XOR and Favorite Number 先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍,统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意:问给出的区间[a,b]中有多少个美丽数,美丽数的定义是所有数字都不相同,如123是,100不是,333也不是。 思路:预处理1..100000的美丽数,可以把每个数字拆开放在set里,比较set的size和位数来实现。 然后用前缀和。
阅读更多http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意: n+2个人取吃饭,每人w元,每k个人可以少付一个人的钱,问最后两个教练每人要付多少钱。
思路:贪心。坑点在读题。。选手n个人,不要忘记两个教练,以及,钱数是两个教练平分。
阅读更多http://codeforces.com/contest/373/problem/C 题意:n个袋鼠,每个袋鼠的size为a[i],一只袋鼠的size至少是另一只两倍时才能将它装下,被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路:贪心。最多有n/2个袋鼠被装下。先排序,然后贪心即可。
阅读更多http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路:增加一个元素,如果它两边的元素都出现了,那么段数-1(相当于把两段连接起来合并成了一段),如果两边元素都没有出现,那么段数+1.反过来,减少一个元素时,如果两边元素都出现了,俺么段数+1(相当于把完整的一段断开成两段),如果两边元素都没有出现,那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000,所以判断某个元素是否出现开一个100000大小的布尔数组即可(我竟然傻逼 …
阅读更多http://codeforces.com/contest/614/problem/C
题意:给一个多边形和多边形外一定点,多边形绕定点旋转,问多边形扫过的面积。 思路:简单计算几何,找到多边形距离定点的最大和最小距离R和r,答案就是(R^2-R^2)*PI 需要注意的是:最大距离一定是从某点上取得,但是最小距离可能不在顶点上,而在某条边上。
阅读更多nbut 1457 Sona
2016-02-17 · 2 min readhttps://ac.2333.moe/Problem/view.xhtml?id=1457 题意:求一段区间内数字个数的立方和。 思路:由于一共才1E5,而数字1E9,所以先离散化,再莫队,类似小z的袜子。 注意 :%lld会WA,要用%I64d
阅读更多