http://www.lydsy.com/JudgeOnline/problem.php?id=2002 题意+思路： 同codeforces 13 E holes. /* *********************************************** Author :111qqz Created Time :2016年02月21日 星期日 02时29分39秒 File Name :code/bzoj/2002.cpp ************************************************ */ #include <cstdio> #include <cstring> …

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来 n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i].... 思路：分块大法好。具体见代码注释。以及。。。cin加速之后还是很慢。。。能不用就不用吧。 /* *********************************************** Author :111qqz Created Time :2016年02月20日 星期六 23时48分28秒 File Name …

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大小的布尔数组即可（我竟然傻逼 …