http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15) 思路：贪心。如果让有限的maxsum个技能满级的话，那么一定是让初始最大的maxsum技能满级更优。我们O(n)可以预处理一个c[i]数组，表示将i个技能变成最大值的最小花费。 然后再预处理一个前缀和数 …

http://www.lydsy.com/JudgeOnline/problem.php?id=3289 题意：中文题目，简单来说就是求某一区间内的逆序对数。 思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。 还有这题没给数据范围但是需要离散化。。。不然会re... /* *********************************************** Author :111qqz Created Time :2016年02月17日 星期三 20时18分51秒 File Name :code/bzoj/3289.cpp …

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和位数来实现。 然后用前缀和。 /* *********************************************** Author :111qqz Created Time :2016年02月19日 星期五 13时25分36秒 File Name :code/hdu/5327.cpp …

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意： n+2个人取吃饭，每人w元，每k个人可以少付一个人的钱，问最后两个教练每人要付多少钱。 思路：贪心。坑点在读题。。选手n个人，不要忘记两个教练，以及，钱数是两个教练平分。 /* *********************************************** Author :111qqz Created Time :2016年02月18日 星期四 15时16分59秒 File Name :code/zoj/3693.cpp …

http://codeforces.com/contest/373/problem/C 题意：n个袋鼠，每个袋鼠的size为a[i],一只袋鼠的size至少是另一只两倍时才能将它装下，被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路：贪心。最多有n/2个袋鼠被装下。先排序，然后贪心即可。 /* *********************************************** Author :111qqz Created Time :2016年02月18日 星期四 14时32分29秒 File Name :code/cf/problem/373C.cpp …

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 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。 /* *********************************************** Author :111qqz Created Time :2016年02月16日 星期二 16时58分59秒 File Name :code/cf/problem/614C.cpp …

写了几道莫队，总结下。 目前只会区间莫队。。树上莫队以后再补。 莫队算法学习 说说我自己的理解： 莫队算法是一类用来处理离线静态区间问题的算法。 必须是离线，而且对区间没有修改。 还要满足，如果我们知道区间[l,r]的答案，那么知道区间[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案都是平凡的。。也就是O(1)可以实现才可以。 本质的话。。感觉就是分块+暴力？ 通过离线操作，把查询按照某种顺序均分使得复杂度降低。 除了bzoj的权限题。。。区间莫队基本都A掉了。