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://codeforces.com/contest/617/problem/E 题意：给出n个数，m个查询，每个查询给定l,r，问在区间【l,r】内，有多少对i,j,满足i^(i+1)^(i+2)^...^j的值为给定的常数k. 思路：学了莫队算法以后。。。这题果然是莫队的一眼题。 入手点是，知道异或也像加一样有前缀和性质。如果我们处理一个按照异或规则的前缀和数组sum[i]=sum[i-1]^a[i]，那么i到j的异或和就是sum[i-1]^sum[j] （x^x==0,因此a[1]到a[i-1]的异或和被去掉了） 因此我们要找的就是区间内有多对i,j满足sum[i-1]^sum[j]==k,也就 …

http://codeforces.com/contest/611/problem/C 题意：给出一个n*m的地图，.表示可以空，#表示墙。一个东西需要占两个相邻的格子，问给定一个矩形，放一个东西的方案数。 思路：q很大。。应该是先预处理出来直接调用答案。。。计数问题累加性。。应该是前缀和之类。。需要做的就是怎么标记。。我的做法是竖着放和横着放的个数分开来存。从左往右从上往下，每次标记到后一个点。然后二维的前缀和。然后每次询问的时候，去掉最上边和最左边两条边界上对应的多加的点。 #include <cstdio> #include <cstring> #include <iostream> …

http://codeforces.com/contest/18/problem/C 题意：将一个序列分成两个非空的部分，保证和相等，问有多少种方法。 思路：做过一个三部分的。。。两部分直接一个前缀和就好了把。。。有一个需要注意的是。。判断负数是否是奇数的时候需要加个绝对值。。。 /* *********************************************** Author :111qqz Created Time :2015年12月29日 星期二 16时09分06秒 File Name :code/cf/problem/18C.cpp …

http://codeforces.com/contest/608/problem/B 题意：给定两个字符串a,b，问b中的每个连续的长度为a的子串与a的哈密顿距离的和是多少。哈密顿距离是对应位置的字符的差的绝对值的和。由于是01串，也就是字符不同的位置数。 思路：类似前缀和。0和1分别搞。注意开long long /* *********************************************** Author :111qqz Created Time :2015年12月24日 星期四 00时32分33秒 File Name :code/cf/#336/B.cpp …

比较水． 唯一一点需要注意的是... 可能有重复元素... 因为我的思路是用两棵一维树状数组搞.. 每个点标记为1 然后看矩形的两个方向中是否至少有一个方向上和等于长度... 所以这样如果有重复元素的话，不处理会出错..　但实际上又没修改..直接前缀和就好了．．． 树状数组个毛线．．． 不过看到还有人线段树搞得233333 /************************************************************************* > File Name: code/bc/#57/1002.cpp > Author: 111qqz > Email: …