111qqz的小窝

老年咸鱼冲锋!

BSGS(Baby steps giant steps)算法学习笔记

离散对数(Discrete Logarithm)问题是这样一个问题,它是对于模方程 a^x=b(mod prime),求满足条件的X,或者得出不存在这样的X 最暴力

spoj DQUERY - D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接 题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。 思路:离线处理+线段树的做法不多说了: /* *********************************************** Author

bzoj2002: [Hnoi2010]Bounce 弹飞绵羊 (分块)

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> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set>

codeforces 13 E. Holes (分块)

http://codeforces.com/problemset/problem/13/E 题意:给你n个洞,进入某个洞后会跑到另一个洞,到了另一个洞之后又可能会继续到下一个洞,问你从一个洞进去,钻了几个洞才会出来,在哪个洞出来 n

hdu 4638 Group

http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意:给定一个序列,序列由1-N个元素全排列而成,求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路:增加

hdu 5213 lucky (莫队算法)

http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意:n个数,m个查询,每个查询由4个数l1,r1,l2,r2构成,询问分别从[l1,r1]和[l2,r2]中各取一个数,和为给定的常数k

codeforces 220 B. Little Elephant and Array

http://codeforces.com/contest/220/problem/B 题意:n个数,m个查询区间,对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。 思路:首先,a[i]很大。。。但是n最大才1e

codeforces 86 D. Powerful array (莫队算法)

http://codeforces.com/problemset/problem/86/D 题意:Ks为区间内s的数目,求区间[L,R]之间所有KsKss的和 思路:莫队算法,和小z的袜子差不多。不明白第一次tle#54是什么情况。

(莫队算法的学习)bzoj 2038 [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子

hdoj4391 Paint The Wall

http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意:有 n 个点,每个点有一种颜色(可能相同),两种操作:1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路:因为颜色种类很

hdoj 1754 I hate it

http://acm.hdu.edu.cn/showproblem.php?pid=1754 题意:给定一个区间,有m组操作,操作可以是改变单点,或者查询区间最大值。对于每组查询,输出。 思路:分块。这篇博客说得很不错。http://

codeforces #319 div 2 E C. Points on Plane (分块)

初识分快. 引一段题解: Let's split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let's number them from left to right. We're going to pass through points rectangle by rectangle. Inside the rectangle we're going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it's odd. Let's