https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5,而数字1E9,所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA,要用%I64d /* *********************************************** Author :111qqz Created Time :2016年02月17日 星期三 16时11分00秒 File Name :code/nbut/1457.cpp ************************************************ */ …

http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意：有n个女孩，编号1..n,第i个女孩在第a[i]个教室,m次访问，每次访问编号[L,R]的女孩，处于同一个教室的女孩一次只能访问一个，问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。 思路：正好刚刚听完学堂在线上的组合数学的那一节，讲到有重复元素的不重复排列的个数的计算方法：可以先将所有元素看成不重复，再除以每个元素的重复度的阶乘（重复度定义为每个元素个数）。 增加一个元素的影响是，乘一个增加的长度，并且除以该元素的重复度（因为每增加一个元素就要除以以此重复度，那么当同一元素c增加到第i次时，除以的就是i的阶乘），减少一 …

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://acm.hdu.edu.cn/showproblem.php?pid=5213 题意：n个数，m个查询，每个查询由4个数l1,r1,l2,r2构成，询问分别从[l1,r1]和[l2,r2]中各取一个数，和为给定的常数k的方案数。 思路：首先分别由两个区间取数不好搞，我们可以用容斥原理对区间变换。这是这道题最关键的一步。 官方题解：这道题需要一些莫队算法的知识 定义记号f(A,B)f(A,B)表示询问区间A，B时的答案 用记号＋表示集合的并 利用莫队算法我们可以计算出任意f(A,A)f(A,A)的值 不妨假 …

http://codeforces.com/contest/220/problem/B 题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。 思路：首先，a[i]很大。。。但是n最大才1e5...每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。 /* *********************************************** Author :111qqz Created Time :2016年02月14日 星期日 00时47分18秒 File Name :code/cf/problem/220B.cpp …

http://codeforces.com/problemset/problem/86/D 题意：Ks为区间内s的数目，求区间[L,R]之间所有KsKss的和 思路：莫队算法，和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。 再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多== /* *********************************************** Author :111qqz Created Time :2016年02月13日 星期六 23时17分58秒 File Name :code/cf/problem/86D.cpp …

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多 …

http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s,满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。 如果不是回文数。。那么考虑进位的情况。 要么从后一位进1，要么从前一位退10回来。 需要特殊考虑1开头的。 /* *********************************************** Author :111qqz Created Time :2016年02月07日 星期日 18时28分39秒 File Name :code/cf/#342/D.cpp …

http://codeforces.com/problemset/problem/621/E 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。 但是由于b很大（1E9）,所以需要用矩阵加速。 /* *********************************************** …

http://codeforces.com/contest/621/problem/D 题意：给出12个式子，问哪个最大。 思路：主要记住两个。一个是比较指数形式的数一个常用办法是取对数，同时要考虑是否能取对数，分情况讨论对于不能取对数的情况经过变换去取对数。第二个是取了两次对数后比较时候的最大值可能是小于0的。所以初始时置于0不够小。官方题解说得很清楚。 The tricky Rat Kwesh has finally made an appearance; it is time to prepare for some tricks. But truly, we didn't expect it to be so hard for …