Created
June 10, 2015 02:26
-
-
Save ftiasch/007a7732456cc8f88ba6 to your computer and use it in GitHub Desktop.
misc
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
PublicTransitHard http://community.topcoder.com/stat?c=problem_statement&pm=13797 | |
SimilarNames http://community.topcoder.com/stat?c=problem_statement&pm=12868 | |
n个字符串s_1, s_2, …, s_n,m个条件(a_i, b_i),统计满足s_{p(a_i)}是s_{p(b_i)}前缀的排列p_1, p_2, …, p_n数量 | |
n <= 50, |s_i| <= 50, m <= 8 | |
BichromeSky http://community.topcoder.com/stat?c=problem_statement&pm=13711 | |
n个红点,m个蓝点,没有三点共线,第i个红点以p_i的概率出现,求红点的凸包包含所有蓝点的概率 | |
n, m <= 100 | |
InverseRMQ http://community.topcoder.com/stat?c=problem_statement&pm=13235 | |
TreeDistance http://community.topcoder.com/stat?c=problem_statement&pm=13369 | |
TreePuzzle http://community.topcoder.com/stat?c=problem_statement&pm=13185 | |
EagleInZoo http://community.topcoder.com/stat?c=problem_statement&pm=13117 | |
EllysLamps http://community.topcoder.com/stat?c=problem_statement&pm=11906 | |
SimilarSequencesAnother http://community.topcoder.com/stat?c=problem_statement&pm=12742 | |
(A, B) 是相似的,当且仅当A, B各删不超过2个字符后相等。给定长度n和字符集m,问相似(A, B)数量。 | |
n <= 100 | |
TaroCheckers http://community.topcoder.com/stat?c=problem_statement&pm=12996 | |
n * m的棋盘,第i行前l[i]个格子有一个棋子,后r[i]个格子有一个棋子,每列最多有一个棋子,问方案数。 | |
n <= 50, m <= 200 | |
OneDimensionalRobot http://community.topcoder.com/stat?c=problem_statement&pm=12999 | |
PerfectSquare http://community.topcoder.com/stat?c=problem_statement&pm=13145 | |
AlienAndPermutation http://community.topcoder.com/stat?c=problem_statement&pm=12949 | |
Perfect Matching http://www.spoj.com/problems/MATCH/ | |
n个点的二分图,假设完备匹配的数量是x,判断x = 0 (mod 2) | |
n <= 300 | |
(False) Face https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=360&page=show_problem&problem=2625 | |
n个点的二分图,假设完备匹配的数量是x,判断x = 0 (mod 4) | |
n <= 300 | |
Little Elephant and Broken Sorting http://codeforces.com/contest/258/problem/D | |
长度为n的排列,m次交换a_i, b_i,每个交换a_i, b_i有50%的概率不发生,问逆序数的期望 | |
n, m <= 1000 | |
Inversions problem http://codeforces.com/problemset/problem/513/G3 | |
长度为n的排列,每次随机一个子段翻转,问m轮后逆序数的期望 | |
n <= 300, m <= 10^9 | |
# Cliquers [PA 2008, Round 5] | |
求$n$个点有标号的无向图的数量,要求每个连通分量都是团。 | |
$n \leq 200000$ | |
# Isomorphism [SGU 282] | |
$n$个点的完全图$m$染色,问同构意义下有多少种染色方案。 | |
$n \leq 53, m \leq 1000$ | |
# Writing n as the product of k distinct positive integers [PE 495] | |
求$n!$写成$k$个不同的数的乘积的方案数。 | |
$n \leq 10^4, k \leq 30$ | |
# Partition [HDOJ 4651] | |
求$n$的拆分数$p_n$。 | |
$n \leq 10^5$ | |
$$\prod_{n = 1}^{\infty} (1 - x^n) = \sum_{k = 0}^{\infty} x^{\frac{k(3k \pm 1)}{2}}$$ | |
# Integer Partition [HDOJ 4658] | |
求$n$的拆分数,要求数字出现不超过$k$次。 | |
$k \leq n \leq 10^5$ | |
# Little Elephant and Broken Sorting [CF 258D] | |
$1, 2, \dots, n$的排列$p$。 | |
``` | |
for i := 1 .. m do | |
if random() mod 2 == 0 | |
swap(p[a[i]], p[b[i]]) | |
end | |
end | |
``` | |
求逆序对数量的期望。 | |
$n, m \leq 1000$ | |
# Inversions problem [CF 513G] | |
$1, 2, \dots, n$的排列。 | |
等概率地选择一个连续子串,将其翻转。 | |
求$m$次操作后逆序对数量的期望。 | |
$n \leq 300, m \leq 10^9$ | |
# BichromeSky [SRM 655 Hard] | |
$n$个红点,$m$个蓝点,没有三点共线。 | |
第i个红点以p_i的概率出现,求红点的凸包包含所有蓝点的概率。 | |
$n, m \leq 100$ | |
# Chocolate triangles | |
求$n$边型剖分中恰好有$k$个三角形的方案数。 | |
$n, k \leq 300$ | |
# Perfect Matching [SPOJ MATCH] | |
$n$个点的二分图,假设完备匹配的数量是$x$,判断$x \equiv 0 \pmod 2$。 | |
$n \leq 300$ | |
# (False) Face [CERC 2009F] | |
$n$个点的二分图,假设完备匹配的数量是$x$,判断$x \equiv 0 \pmod 4$。 | |
$n \leq 300$ | |
# SWERC 2014 Problem J The Big Painting | |
给出矩阵$A, B$,问$A$在$B$中出现了多少次。 | |
# SWERC 2014 Problem H Money Transfers | |
给出$n$个点$m$条边的无向图,和一个顶点集$M$,现在给所有边的权值增加$c$,使得$1$到$n$的最短路只包含$M$中的点,求$c$的最小值。 | |
$n, m \leq 1000$ | |
# CERC 2014 Problem F Vocabulary | |
给出$3$个包含`?`的字符串$A$, $B$, $C$,问有多少种把`?`替换为小写字母的方案,使得$A < B < C$,答案模$(10^9+9)$ | |
$|A|, |B|, |C| \leq 10^6$ | |
# CERC 2014 Problem E Can't stop playing | |
你正在玩$1$维版本的2048游戏。数字$2^{a_1}, 2^{a_2}, \dots, 2^{a_n}$依次出现,你可以选择加到左边还是右边,问最后能不能只剩$1$个,输出方案。 | |
$n \leq 1000, 2^{a_1} + 2^{a_2} + \dots + 2^{a_n} \leq 2^13$ | |
# CERC 2014 Problem L Outer space invader | |
有$n$个怪物,第$i$个怪物于第$a_i$秒出现,第$b_i$秒消失,高度是$d_i$。你可以使用威力是$x$的炸弹,消灭高度不超过$x$的所有怪物,代价是$x$。 | |
问消灭所有怪物的最小的总代价。 | |
$n \leq 300$ | |
# CERC 2014 Problem J Pork barrel | |
给出$n$个点$m$条边的无向图,**在线**回答$q$个询问$(l_i, r_i)$,求只考虑长度在$[l_i, r_i]$内的边时,最小生成树的大小。 | |
$n \leq 1000, m \leq 10^5, q \leq 10^6$ | |
# CERC 2014 Problem G Virus synthesis | |
给出字符串$S$,可以进行$2$种操作: | |
- 在某端删除一个字符 | |
- 如果$S$是偶数长度的回文串,删除左半边/右半边 | |
问得到空串最少要几步。 | |
$|S| \leq 10^5$ | |
# CERC 2014 Problem B Mountainous landscape | |
$n$条线段组成的山,对于每条线段,输出站在它上面时,所能看到的第一个顶点 | |
$n \leq 10^5$ | |
Subarray Cuts http://codeforces.com/problemset/problem/513/E2 | |
数组a_1, a_2, …, a_n,选择k个不相交的连续段,设(从左到右)的和分别是s_1, s_2, …, s_k,最大化|s_1 - s_2| + |s_2 - s_3| + … + |s_{k - 1} - s_k| | |
n <= 30000, k <= 200 | |
Permanent http://acdream.info/problem?pid=1027 | |
A是n * n的矩阵,计算perm(A) | |
n <= 20 | |
Permutation http://acm.hdu.edu.cn/showproblem.php?pid=4917 | |
n个点m条边的有向图,统计拓扑排序的数量 | |
n <= 40, m <= 20 | |
SimilarNames http://community.topcoder.com/stat?c=problem_statement&pm=12868 | |
n个字符串s_1, s_2, …, s_n,m个条件(a_i, b_i),统计满足s_{p(a_i)}是s_{p(b_i)}前缀的排列p_1, p_2, …, p_n数量 | |
n <= 50, |s_i| <= 50, m <= 8 | |
Perfect Matching http://www.spoj.com/problems/MATCH/ | |
n个点的二分图,假设完备匹配的数量是x,判断x = 0 (mod 2) | |
n <= 300 | |
(False) Face https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=360&page=show_problem&problem=2625 | |
n个点的二分图,假设完备匹配的数量是x,判断x = 0 (mod 4) | |
n <= 300 | |
Permanent http://codeforces.com/problemset/problem/468/E | |
A是n * n的矩阵,除了给定的k个位置以外都是1,计算perm(A) | |
n <= 10^5, k <= 50 | |
Little Elephant and Broken Sorting http://codeforces.com/contest/258/problem/D | |
长度为n的排列,m次交换a_i, b_i,每个交换a_i, b_i有50%的概率不发生,问逆序数的期望 | |
n, m <= 1000 | |
Inversions problem http://codeforces.com/problemset/problem/513/G3 | |
长度为n的排列,每次随机一个子段翻转,问m轮后逆序数的期望 | |
n <= 300, m <= 10^9 | |
WinterAndSnowmen Kai! | |
X, Y \subset {1, 2, …, n},f({x_1, x_2, …, x_n}= x_1 xor x_2 xor … xor x_n,求f(X) <= f(Y)的方案数 | |
n <= 5000 | |
WinterAndSnowmen http://community.topcoder.com/stat?c=problem_statement&pm=12891 | |
X \subset {1, 2, …, n}, Y \subset {1, 2, …, m},f({x_1, x_2, …, x_n}= x_1 xor x_2 xor … xor x_n,求f(X) <= f(Y)的方案数 | |
n, m <= 2000 | |
Everlasting L http://acm.hdu.edu.cn/showproblem.php?pid=5116 | |
n * m的有障碍的棋盘,求放2个L的不同方案数,要求L的两边长度互质 | |
n, m <= 200 | |
ThreeLLogo http://community.topcoder.com/stat?c=problem_statement&pm=13059 | |
n * m的有障碍的棋盘,求放3个L的不同方案数 | |
n, m <= 30 | |
BichromeSky http://community.topcoder.com/stat?c=problem_statement&pm=13711 | |
n个红点,m个蓝点,没有三点共线,第i个红点以p_i的概率出现,求红点的凸包包含所有蓝点的概率 | |
n, m <= 100 | |
Chocolate triangles | |
求n边型剖分(不一定是三角剖分)中恰好有k个三角形的方案数 | |
n, k <= 300 | |
FencingPenguins http://community.topcoder.com/stat?c=problem_statement&pm=12339 | |
正N边型内有M个企鹅,选择一些顶点建立围栏,要求: | |
1. 围栏不能相交 | |
2. 每个围栏至少包含1个企鹅 | |
3. 企鹅都被包围 | |
4. 同色企鹅在同一围栏 | |
求方案数。 | |
N <= 222, M <= 50 | |
An easy problem about trees http://codeforces.com/problemset/problem/457/F | |
Mr. Kitayuta's Gift http://codeforces.com/problemset/problem/506/E | |
Deja Vu http://codeforces.com/problemset/problem/331/E2 | |
Tree and Table http://codeforces.com/problemset/problem/251/E | |
Buy One, Get One Free http://codeforces.com/problemset/problem/335/F | |
Triangles 3000 http://codeforces.com/problemset/problem/528/E | |
3k条直线,等概率挑选3条,求围成三角形面积的期望 | |
Fox and Meteor Shower http://codeforces.com/problemset/problem/388/E | |
1k条3维直线,求最大的两两相交的子集 | |
Gena and Second Distance http://codeforces.com/problemset/problem/442/E | |
1k个点,求次近的点最远的点 | |
Drawing Circles is Fun http://codeforces.com/problemset/problem/372/E | |
OI论文 | |
(有用)的论文有两类,第一类是讲授知识方法的,第二类是习题的堆砌。 | |
知识方法型: | |
漆子超《分治算法在树的路径问题中的应用》 | |
罗穗骞《后缀数组——处理字符串的有力工具》 | |
姜碧野《SPFA算法的优化及应用》 | |
金斌《欧几里得算法的应用》 | |
贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》<— 有些民科,但是内容还是不错的 | |
徐持衡《浅谈几类背包题》 | |
陈丹琦《基于连通性状态压缩的动态规划问题》 | |
汪一宁《1D/1D动态规划优化初步》 | |
杨哲《凸完全单调性的一个加强与应用》<— 有些不明觉厉 | |
杨弋《Hash在信息学竞赛中的一类应用》 | |
周冬《生成树的计数及其应用》<— Matrix Tree | |
胡伯涛《最小割模型在信息学竞赛中的应用》<— 最小割的一个里程碑 | |
罗剑桥 《浅谈分块思想在一类数据处理问题中的应用》 | |
王子昱 《分块方法的应用》 | |
陈立杰 《重量平衡树和后缀平衡树在信息学奥赛中的应用》<— ICPC短期内还不会出现 | |
陈立杰《可持久化数据结构研究》 | |
王钦石《浅析一类二分方法》 | |
习题型: | |
乔明达 《搜索问题中的meet in the middle技巧》 | |
曹钦翔《数据结构的提炼与压缩》 | |
俞华程《矩阵乘法在信息学中的应用》 | |
刘聪《浅谈数位类统计问题》<— 他的数位DP方法不够优秀,不应该学 | |
汤可因《浅析竞赛中一类数学期望问题的解决方法》 | |
徐源盛《对一类动态规划问题的研究》 | |
张昆玮《数学归纳法与解题之道》 | |
向量 | |
cross product, dot product | |
对象 | |
点,直线(线段、射线),圆,多边形(简单多边形、凸多边形) | |
点 在 直线(线段、射线)上 | |
点 在 圆 内 | |
点 在 简单多边形 内 | |
点 在 凸多边形内 O(log N) | |
直线 和 直线 的夹角 | |
直线 和 直线 的交点 | |
直线 和 圆 的交点 | |
直线 和 凸多边形的交点 O(log N) | |
圆 和 圆 的交点 | |
凸多边形 和 凸多边形 的交 O(N log N) / O(N) | |
点 和 圆 的切线 | |
圆 和 圆 的切线 | |
圆 和 简单多边形 的交 | |
点 到 直线 的投影 | |
点 关于 直线的对称 | |
平移 | |
关于原点的旋转 | |
对偶 | |
反演 | |
点 到 点 的距离 | |
点 到 线段 的距离 | |
角 的 平分线 | |
三角形 的 外心,内心 | |
凸多边形的最大内切圆 O(N log N) | |
平面图的对偶图 | |
圆凸包 | |
kd-tree | |
最小圆覆盖 | |
欧几里得距离最小生成树 | |
最近点对 | |
最小周长三角形 | |
最远点对 | |
最大面积三角形 | |
Timus 1469 No Smoking! | |
Timus 1464 Light | |
四边形面积统计 | |
TCO 2012 Round 3B PQHull | |
三维几何 | |
维护数组A,支持Q次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求#{i : a <= i <= b and A[i] > 0} | |
Codeforces 15E Holes | |
维护有根树,支持Q次操作: | |
- parent[v] := p,保证p > v | |
- 询问点v的深度 | |
$n, q <= 10^5$ | |
Codeforces 348C | |
$n$个元素,$m$个集合$S_1, S_2, …, S_m$,$q$次操作: | |
- 把集合$S_i$的元素权值+= v | |
- 询问集合$S_i$元素的权值和 | |
$n, |S_1| + |S_2| + … + |S_m|, q <= 10^5$ | |
Chengdu 2012 Problem D / HDOJ 4467 | |
$n$个点$m$条边的无向图,点有2种颜色,边有权值,$q$次操作: | |
- 改变点$v$的颜色 | |
- 查询端点颜色是$(a, b)$的边权值之和 | |
$n, m, q <= 10^5$ | |
Chengdu 2013 Problem G / HDOJ 4787 | |
** 在线 ** 维护字符串集合$S$,$q$次操作: | |
- 在$S$中插入$s$ | |
- 查询$t$在$S$中的子串数 | |
$s$总长$10^5$,$t$总长$5 * 10^6$ | |
(2~3 solutions will be presented) | |
SPOJ UNTITLE1 | |
维护数组$A$,支持$q$次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求max{S[i] : a <= i <= b},其中S[i] = A[1] + A[2] + … + A[i] | |
$|A|, q <= 50000$ | |
BZOJ 2724 | |
**在线**查询区间众数。 | |
(an elegant algorithm to count occurrence) | |
BZOJ 2741 | |
**在线**查询区间最大连续异或和。 | |
BZOJ 巧克力王国 | |
查询半平面内点权的和。 | |
Codechef March14 GERALD07 | |
无向图,询问编号在$[L_i, R_i]$的边组成子图的连通块数量。 | |
Codeforces 19E | |
无向图,询问有多少条边,删掉之后的图是二分图。 | |
SPOJ COT2 | |
查询树上路径不同颜色数量。 | |
(2 solutions will be presented) | |
SPOJ COT3 Combat on a tree | |
SPOJ RECTANGL Rectangles | |
POJ 3145 Harmony Forever | |
POJ 1741 Tree | |
统计树上距离不超过$k$的点对数量。 | |
SPOJ FTOU2 | |
点有黑白两色,边有长度,求黑点数量<= K的最长路径。 | |
HDU 4812 / Nanjing 2013 K | |
点有权,求权值之积 mod (10^6 + 3) = K的路径数量。 | |
TYVJ 1953 | |
等概率地选择点作为剖分中心,求复杂度的期望。 | |
WC 2010 重建计划 | |
求长度在[L, R]之间的,平均数最大的路径。 | |
Codeforces 150E | |
求长度在[L, R]之间的,中位数最大的路径。 | |
Codeforces 193E | |
统计距离不超过L,权值之和不超过W的点对数量。 | |
SPOJ QTREE4 | |
点有黑白两色,支持(a)修改点的颜色;(b)询问白点对的最大距离。 | |
Codeforces 342E | |
点有黑白两色,支持(a)把点变成黑色;(b)询问距离v点最近的黑点距离。 | |
SPOJ QTREE5 | |
点有黑白两色,支持(a)修改点的颜色;(b)询问距离v点最远的白点距离。 | |
— | |
SPOJ QTREE | |
边有权值,支持(a)修改边的权值;(b)询问路径上权值的最大值。 | |
Codeforces 117E | |
章鱼图,支持(a)修改ab最短路上边的状态(存在、不存在互换)(b)询问连通块数量。 | |
BZOJ 3083 | |
点有权值,支持(a)修改路径上的权值;(b)修改根节点;(c)询问子树的最大值。 | |
— | |
BZOJ 2049 / SDOI 2008 | |
支持(a)插入、删除边;(b)询问ab是否连通。保证中间结果是森林。 | |
(LCT or ETT) | |
SPOJ OTOCI | |
支持(a)插入边;(b)询问路径上的权值之和。强制在线。 | |
Topcoder Open 2013 Round 2A ThePowers | |
给出A, B,问集合{a^b : 1 <= a <= A, 1 <= b <= B}的大小。 | |
A, B <= 10^9 | |
SGU 550 Tree Queries Online | |
在线维护一棵树,支持删除边,并把它的边权乘在较小的连通块,加在较大的连通块。 | |
HDU 4621 Life Game | |
N * M的点阵,对于点(i, j),将其指定为A类型有A(i, j)的收益,指定为B类型有B(i, j)的收益。R个要求,如果矩形(L_i, D_i) — (R_i, U_i)全是A(或全是B),则获得W_i的收益,问最大收益。 | |
N, M <= 50, R <= 50000 | |
HDU 4673 Pirate's Chest | |
N个箱子,对于i号箱子,要么使用A_i号钥匙打开,要么使用B_i号撬棍打开,要么付出D_i点血打开。 | |
M层的塔,每一层塔有入口,怪物,至多两个工具,且一定同类型,可以在任意地点上下楼。 | |
你讨厌上楼梯,现在有H点血,问最少上到几层可以打开所有箱子,同时要求掉血最少。 | |
N <= 30000, M <= 1000 | |
HDU 4679 Terrorist’s destroy | |
N个点的树,删除一条边,使得边权和剩下的树的直径乘积最小。 | |
N <= 10^5 | |
HDU 4689 Derangement | |
给出数列A_1, A_2, …, A_N,A_i in {+1, -1},求满足(P_i - i) * A_i > 0的排列P数量。 | |
N <= 1000 | |
Single Round Match 566 FencingPenguins | |
正N边型内有M个企鹅,选择一些顶点建立围栏,要求: | |
1. 围栏不能相交 | |
2. 每个围栏至少包含1个企鹅 | |
3. 企鹅都被包围 | |
4. 同色企鹅在同一围栏 | |
求方案数。 | |
N <= 222, M <= 50 | |
Single Round Match 565 UnknownTree | |
N + 3个点的树,给出disA[i], disB[i], disC[i]表示1 <= i <= N号点到A, B, C的距离,求可能的树的方案数。 | |
N <= 50 | |
Single Round Match 561 Orienteering | |
N个点的树,随机选择K个点,问遍历K个点最短路径的期望。 | |
K <= N <= 300 | |
SCOI 2013 数数 | |
求[L, R]的数字B进制表示的所有子串的和。 | |
1 <= L <= R < B^100000, B <= 10^5 | |
SCOI 2012 Blinker的仰慕者 http://www.lydsy.com/JudgeOnline/problem.php?id=2757 | |
Codeforces 273D Dima and Figure | |
N * M的点阵,问凸的点集的数量,mod (10^9 + 7)。 | |
(N, M <= 150) | |
Codeforces 375E Red and Black Tree | |
N个点的树。点有黑、白2种颜色。任意交换点的颜色,使得对于任一个点,距离它D以内都至少有一个黑点,求最少的交换次数。 | |
N <= 500 | |
Codeforces 392E Deleting Substrings | |
序列{A_1, A_2, …, A_N}。每次删除连续的子序列{x_1, x_2, …, x_k},要求 | |
- |x_{i + 1} - x_i| = 1, | |
- 2 x_i >= x_{i - 1} + x_{i + 1}, | |
收益W_k,求删除整个序列的最大收益。 | |
N <= 400 | |
NEERC Eastern Subregional Contest 2013 Problem C CVS | |
支持Q次操作: | |
1. learn(i, j) | |
2. rollback(i) | |
3. relearn(i) | |
4. clone(i) | |
5. check(i) | |
Q <= 10^5 | |
NEERC Northern Subregional Contest 2013 Problem L Lonely Mountain | |
JAG Summer 2012 Problem G Presentation | |
N <= 10^5 | |
Single Round Match 570 CurvyonRails | |
unhappy = 1, 0 | |
M * M棋盘上有N个有缺陷的皇后(只能攻击主对角线),求被至少1个皇后攻击的格子数量。 | |
N, M <= 10^5 | |
给出串P, T,求T的连续子串S,使得hamming(S, P)最小。 | |
|P|, |T| <= 10^5,|Sigma| <= 10 | |
给出串P, T(可能带有通配符?),求P在T中所有匹配位置。 | |
|P|, |T| <= 10^5 | |
胡渊鸣 城市规划 | |
计算N个点带标号的连通图数量,答案模1004535809(= 479 * 2^21 + 1)。 | |
N <= 130000 | |
O(N log^2 N) | |
给出A_1, A_2, …, A_N,求min_{i, j} popcount(A_i xor A_j)。 | |
A_i <= 10^6 | |
(FWT) | |
Topcoder Open 2012 Round 2A EvenPaths | |
N个点的有向无环图,K个点可能有障碍。 | |
合法当且仅当点0到点1恰有偶数条路径。 | |
求2^K种可能中合法的图的数量。 | |
N <= 50, K <= 32 | |
HDOJ 4656 Evaluation | |
给出A_0, A_1, …, A_{N - 1}, 求f(B * C^{2k} + D),答案模(10^6 + 3),其中f(x) = sum_i A_i x^i。 | |
N <= 10^5, A_i, B, C, D <= 10^6 | |
Number theory | |
求x^2 = 1 (mod M)的所有解。 | |
求x^K = x (mod M)的解的数量。 | |
求P / Q在B进制下的循环节。 | |
SPOJ MOD Power Modulo Inverted | |
给出A, B, M,求最小的x >= 0,使得A^x = B (mod M)。 | |
A, B, M <= 10^9 | |
Petrozavodsk Summer 2011 Kyiv + Kharkiv NU Contest Problem A A Lot | |
给出P,Q组询问(A, B),求最小x >= 0满足A^x = B (mod P)。 | |
P <= 10^8, Q <= 10^4 | |
求A x^2 + B x + C = 0 (mod P)的解。 | |
Project Euler 457 A polynomial modulo the square of a prime | |
设f(p)表示最小的n满足n^2 - 3n - 1 = 0(mod p^2),求sum_{p is prime, p <= N} f(p)。 | |
N <= 10^7 | |
Codeforces 193E Fibonacci Number | |
给出F,求最小的n,使得fib(n) = F (mod 10^13)。 | |
F < 10^13 | |
Petrozavodsk Winter 2008 Warsaw Contest Problem J Sum of a subsequence | |
给出A_1, A_2, …, A_{2N},求它的N元子集,满足元素和是N的倍数。 | |
N = 10^k,k <= 5 | |
Codeforces 62E World Evil | |
n * m的点阵,如下图,求左边到右边的最大流。 | |
n <= 5, m <= 10^5 | |
Single Round Match 608 BigO | |
N个点的有向图,假设在上面走x步的方案数是O(x^K)的,求K的最小值。 | |
N <= 50 | |
Single Round Match 607 CombinationLockDiv1 | |
给出两个10进制串A, B,每次可以选择一段数字rotate,求把A变成B的最小操作次数。 | |
|A|, |B| <= 50 | |
Single Round Match 592 LittleElephantAndPermutationDiv1 | |
设a_1, a_2, …, a_N和b_1, b_2, …, b_N是两个1, 2, …, N的排列, | |
问max{a_1, b_1} + max{a_2, b_2} + … + max{a_N, b_N} >= K的排列数量。 | |
N <= 50, K <= 2500 | |
Single Round Match 588 KeyDungeonDiv1 | |
N个房间,每个房间需要doorRed[i]把红钥匙,doorGreen[i]把绿钥匙,房间里面有roomRed[i], roomGreen[i], roomWhite[i]把红、绿、白钥匙。白钥匙可以作为红、蓝钥匙使用。初始有keys[]把三种钥匙,打开一些房间,问手上最多的钥匙数。 | |
N <= 12, 钥匙数 <= 10 | |
Single Round Match 582 ColorfulBuilding | |
N个矩形,第i个矩形的高度是i,颜色是color[i],问所有排列中从左到右能看到K次颜色变化的数量。 | |
K <= N <= 36 * 36 | |
Codeforces 258D Little Elephant and Broken Sorting | |
N个数,M次交换操作,每次交换操作有1/2概率进行,问最终序列逆序对的期望。 | |
N, M <= 1000 | |
Single Round Match 577 EllysChessboard | |
8 * 8的棋盘上,在指定位置放棋子,放棋子的代价是到曼哈顿距离最远的棋子距离,问最小的总代价。 | |
Topcoder Open 2012 Round 3B ElevenMultiples | |
N个10进制数字片段P_1, P_2, …, P_n,问有多少种方法使得连接之后是11的倍数。 | |
N <= 50 | |
Single Round Match 601 WinterAndShopping | |
N个商店卖球。第i个商店在第first[i]天开业,有red[i]个红球,green[i]个绿球,blue[i]个蓝球。商店每天卖1个球,所有商店卖的球颜色相同。同时营业的商店不超过2个。求方案数。 | |
N <= 50,red[i], green[i], blue[i] <= 100,first[i] + red[i] + green[i] + blue[i] <= 500 | |
Single Round Match 594 FoxAndAvatar | |
1, 2, …, N以行为主序排列在宽度是W的矩阵上。每次可以删除一个子矩形中的所有数字,并重新排列剩余数字。问最后留下数字X的最小操作次数。 | |
W <= N <= 3000 | |
Single Round Match 593 WolfDelaymasterHard | |
定义形如0^n1^n的串是好的,好串的连接是好的。长度为N的字符串,包含0、1、?三种字符,替换?为0、1,使得形成的串是好的。求方案数。 | |
N <= 2 * 10^6 | |
Single Round Match 591 StringPath | |
给出字符串A, B,问有多少N * M的字符矩形,使得存在两条(1, 1)到(N, M)的路径上面的字符串恰好是A, B。 | |
N, M <= 8 | |
Single Round Match 589 FlippingBitsDiv1 | |
给出长度为n的01串和常数M,通过下面两种操作使得长度为N - M的前后缀相等: | |
1. 翻转某位 | |
2. 翻转长度k * M的前缀(k >= 1) | |
求最少的操作次数。 | |
N <= 300 | |
Single Round Match 583 RandomPaintingOnABoard | |
N * M的矩阵P,每次以P[i][j] / sum{P[i][j]}的概率选择格子(i, j),问每行每列都被选择至少一次所需要的步数期望。 | |
N, M <= 21, N * M <= 50, P[i][j] < 10 | |
Topcoder Open 2013 Round 3A TrickyInequality | |
M个整数变量x_1, x_2, …, x_M满足: | |
1. x_1, x_2, …, x_M >= 1 | |
2. x_1 + x_2 + … + x_M <= S | |
3. x_1, x_2, …, x_N <= T | |
求方案数模(10^9 + 7)。 | |
M <= 10^9, M - N <= 100, T <= 10^5, N * T <= S | |
Single Round Match 578 DeerInZooDivOne | |
n个点的树,求两颗不相交的子树,它们同构同时大小最大。 | |
n <= 50 | |
Single Round Match 573 WolfPack | |
求从(X_1, Y_1)移动M步到(X_2, Y_2)的方案数,每次移动可以往上下左右移动一格。 | |
M <= 100000 | |
Single Round Match 569 MegaFactorial | |
定义f(n, k)满足: | |
1. f(n, k) = f(n - 1, k) * f(n, k - 1) | |
2. f(0, k) = 1 | |
3. f(n, 0) = n | |
求f(N, K)在B进制下末尾0的数量。结果模(10^9 + 7)。 | |
N <= 10^9, K <= 16, B <= 10 | |
Single Round Match 566 FencingPenguins | |
正N边型内有M个企鹅,选择一些顶点建立围栏,要求: | |
1. 围栏不能相交 | |
2. 每个围栏至少包含1个企鹅 | |
3. 企鹅都被包围 | |
4. 同色企鹅在同一围栏 | |
求方案数。 | |
N <= 222, M <= 50 | |
Single Round Match 562 InducedSubgraphs | |
N个点的树,问有多少种标号方式,使得对所有1 <= i <= N - K + 1,点集{i, i + 1, …, i + K- 1}是连通的。 | |
N <= 40 | |
Single Round Match 560 BoundedOptimization | |
N个变量x_i,满足L_i <= x_i <= R_i,且X_1 + X_2 + … + X_n <= S,求一个特殊二次式的最大值(无平方项,无一次项,系数都是1)。 | |
N <= 13 | |
Single Round Match 550 ConversionMachine | |
给出只包含abc 3种字符的串A和串B,把a -> b的花费是cost[0],b -> c是cost[1],c -> a是cost[2],问在总费用不超过M的情况下,有多少方式能让A变换到B。 | |
|A|, |B| <= 11 | |
POJ 2793 / NEERC 2005 | |
求仙人掌的生成仙人掌数量。 | |
IOI 2008 Islands | |
求章鱼图的直径。 | |
POJ 3567 / NEERC 2007 | |
求仙人掌图的直径。 | |
POJ 3961 / NEERC 2010 | |
把仙人掌图分成N / K个连通块,每个连通块大小恰好是K。 | |
Codeforces 379G | |
仙人掌,可以把涂成黑白两色(可以不涂),相邻的点不能有相同的颜色。对于所有的1 <= a <= n,求最多能放的白点数量。 | |
Fast Fourier Transformation and related topics | |
Division of polynomials | |
胡渊鸣 城市规划 | |
计算N个点带标号的连通图数量,答案模1004535809(= 479 * 2^21 + 1)。 | |
N <= 130000 | |
Project Euler 416 A frog's trip | |
N个格子,一只青蛙1 -> N -> 1,重复M次。 | |
青蛙每次只能跳跃1、2、3个格子,问至多只有1个格子没被访问过的路径数量。 | |
N <= 10^12, M <= 10 | |
Number theoretical transformation | |
伍一鸣 Binomial | |
给出N, P,计算C(r) = # of k where 0 <= k < N and binom(N, k) = r (mod P),答案模29。 | |
P = 51061, N < P^10 | |
SRM 518 Nim | |
统计满足以下条件的(x_1, x_2, …, x_K)的数量: | |
1. x_i是质数 | |
2. x_i <= L | |
3. x_1 xor x_2 xor … xor x_K = 0 | |
K <= 10^9, L <= 5 * 10^4 | |
Single Round Match 601 WinterAndShopping | |
N个商店卖球。第i个商店在第first[i]天开业,有red[i]个红球,green[i]个绿球,blue[i]个蓝球。商店每天卖1个球,所有商店卖的球颜色相同。同时营业的商店不超过2个。求方案数。 | |
N <= 50,red[i], green[i], blue[i] <= 100,first[i] + red[i] + green[i] + blue[i] <= 500 | |
Single Round Match 594 FoxAndAvatar | |
1, 2, …, N以行为主序排列在宽度是W的矩阵上。每次可以删除一个子矩形中的所有数字,并重新排列剩余数字。问最后留下数字X的最小操作次数。 | |
W <= N <= 3000 | |
Topcoder Open 2012 Round 2B SequenceTransmission | |
将A + B, A * 2 + B, …, A * N + B的二进制表示连接,问相邻两位不同的数量。 | |
A <= 40000,B <= 10^18, N <= 10^12 | |
Project Euler 439 Sum of sum of divisors | |
设d(n)表示n的约数和,给出N,求sum_{1 <= i <= N} sum_{1 <= j <= N} d(i * j)。 | |
N <= 10^11 | |
Mobius inversion | |
SPOJ LCMSUM | |
给出N,求lcm(N, 1) + lcm(N, 2) + … + lcm(N, 3)。 | |
N <= 1000000, 300000组数据 | |
贾志鹏 Crash的数字表格 | |
给出N, M, 求sun_{1 <= i <= N} sum_{1 <= j <= M} lcm(i, j),答案模20101009。 | |
N, M <= 10^7 | |
顾昱洲 JZPKIL | |
给出N, A, B,求sum_{1 <= i <= N} gcd(N, i)^A lcm(N, i)^B$,答案模(10^9 + 7)。 | |
N <= 10^9, A, B <= 3000 | |
**Power sums | |
POI X Trinomial | |
求(1 + x + x^2)^N展开式中x^K的系数,答案模3。 | |
SRM 536 BinaryPolynomialDivOne | |
求多项式P(x)^M中x^K的系数,答案模2。 | |
deg P < 50, M <= 10^18 | |
TCO 2013 3A TrickyInequality | |
M个整数变量x_1, x_2, …, x_M满足: | |
1. x_1, x_2, …, x_M >= 1 | |
2. x_1 + x_2 + … + x_M <= S | |
3. x_1, x_2, …, x_N <= T | |
求方案数模(10^9 + 7)。 | |
M <= 10^9, M - N <= 100, T <= 10^5, N * T <= S | |
HDOJ 4658 Partition | |
求N的拆分数,要求相同的数出现次数小于K。 | |
N, K <= 10^5,10^5组数据 | |
Topcoder Open 2012 Round 3A CowsMooing | |
N头牛,第i头牛按照pattern_i moo,求count[i]表示50!内恰好有i头牛moo的时间,答案模$10^9+7$。 | |
N <= 30, |pattern_i| <= 50 | |
BOI 2010 Candy | |
定义distinct({a_1, a_2, …, a_n}) = # of {sum_i a_i x_i : x_i in {0, 1}}. | |
给出a_1, a_2, …, a_n,求distinct({a_1, a_2, …, a_n} \ {a_i} + {x})的最大值,和(i, x)字典序最小的解。 | |
n <= 100 | |
1 <= a_i <= 7000 | |
SRM 478 RandomApple | |
n个盒子,m种苹果,第i个盒子里第j种苹果的数量是A(i, j)。 | |
等概率地选择盒子的子集,等概率地选择前一步选中的苹果,求prob(1), prob(2), …, prob(m)。其中prob(i)表示选中第i种苹果的概率。 | |
n, m <= 50, 0 <= A(i, j) < 200 | |
SPOJ LIS2 | |
给出(x_1, y_1), (x_2, y_2), …, (x_n, y_n),求i_1 < i_2 < … < i_k,满足 | |
x_{i_1} < x_{i_2} < … < x_{i_k} | |
y_{i_1} < y_{i_2} < … < y_{i_k},求k的最大值。 | |
n <= 10^5 | |
SRM 610 MiningGoldHard | |
给出(x_1, y_1), (x_2, y_2), …, (x_n, y_n), {a_1, a_2, …, a_{n - 1}), (b_1, b_2, …, b_{n - 1}), | |
求(x’_1, y’_1), (x_2’, y_2’), …, (x’_n, y’_n)满足: | |
¥ 0 <= x’_i < A, 0 <= y’_i < B | |
¥ |x’_{i + 1} - x’_i| <= a_i, |y’_{i + 1} - y’_i| <= b_i | |
求sum_i |x_i - x’_i| + |y_i - y’_i|的最小值。 | |
n <= 1000 | |
A, B <= 10^6 | |
IOI 2004 Hermes | |
按顺序访问(x_1, y_1), (x_2, y_2), …, (x_n, y_n),只要横或者纵坐标相当即算访问,问曼哈顿距离的最小值。 | |
n <= 2000, |x_i|, |y_i| <= 1000 | |
IOI 2002 Batch Scheduling | |
n个任务顺序执行,第i个任务所需时间time[i],权重是weight[i]。 | |
任务分批进行,每批任务所需时间是sum time[i] + T。 | |
在t时刻完成任务i的代价是t * weight[i],求总代价的最小值。 | |
n <= 10000 | |
POI XIII Frogs (Simplified) | |
n * m的棋盘,k个障碍,对于每个点,求其欧几里得距离最近的障碍。 | |
n, m <= 1000 | |
World Finals 2011 Machine Works | |
m天,初始有c元。n个机器可以购买,对于第i个机器,只有在第day[i]天可以购买,买入的价格是buy[i],卖出的价格是sell[i],每天的利润是profit[i]。 | |
开始、结束都没有机器,同时最多拥有1个机器,求最大的利润。 | |
n <= 100000 | |
PA 2011 Drilling | |
给出c_1, c_2, …, c_n,求f(1, n)。 | |
其中f(i, j) = min_{i < k < j} {max{f(i, k), f(k, j)} + c[k]}。 | |
n <= 2000 | |
Codeforces 321E | |
n个人顺序分成k组,使同组人之间的关系之和最大。 | |
n <= 4000, k <= 800 | |
SRM 478 KiwiJuice | |
n个杯子,容量是c,初始的水量是c_1, c_2, …, c_n。可以互相倒水,每次只能在空或满时停止。卖掉一个水量是x的杯子获得value[x]元,问最多获得的钱数。 | |
n <= 15 | |
SPOJ TLE | |
给出c_1, c_2, …, c_n,求x_1, x_2, …, x_n的方案数,满足: | |
¥ 0 <= x_i < 2^m | |
¥ x_i mod c_i != 0 | |
¥ a_{i + 1} & a_i = 0 | |
n <= 50, m <= 15 | |
SGU 327 Yet Another Palindrome | |
n个字符串s_1, s_2, …, s_n,找包含它们作为子串的最短回文串。 | |
n <= 14, |s_i| <= 30 | |
Codeforces 86C Genetic engineering | |
m个模板串s_1, s_2, …, s_m,求长度为n的序列,使得能被完全覆盖。 | |
m <= 10, |s_i| <= 10, n <= 1000, s_i in {A, C, T, G}^+ | |
Codeforces 55D Beautiful numbers | |
求[L, R]中能被非零数位整除的数。 | |
L, R <= 9 * 10^18 | |
SGU 258 Almost Lucky Numbers | |
数x是幸运的,当且仅当它的前、后半的数位和相等。数x几乎是幸运的,当且仅当至多修改1位之后是幸运的。 | |
求[L, R]中几乎幸运的数。 | |
L, R <= 10^9 | |
SGU 390 Tickets | |
依次考虑[L, R]的数,每次把x的数位和加进计数器counter,如果counter >= K则counter清零,问counter清零的次数。 | |
L, R <= 10^18, K <= 1000 | |
SPOJ ININT | |
对于数字x,每次可以将它加上它的一位。求1变到n的最小次数,并求方案数。 | |
n <= 10^9 | |
POI XVII Crystals | |
给出a_1, a_2, …, a_n,求x_1, x_2, …, x_n的数量满足: | |
¥ 0 <= x_i < a_i | |
¥ a_1 xor a_2 xor … xor a_n = 0 | |
¥ n <= 50, 0 < a_i < 2^32 | |
SGU 542 Gena vs Petya | |
给出a_1, a_2, …, a_n,求x的数量满足(a_1 - x) xor (a_2 - x) xor … xor (a_n - x) = 0。 | |
n <= 2 * 10^5, a_i <= 10^18 | |
http://main.edu.pl/en/archive/oi/13/tan | |
Project Euler 355 Maximal coprime subset | |
给出N,在{1, 2, …, N}中挑选一个两两互素的子集,使得元素的总和最大。 | |
N <= 200000 | |
计算sum_{0 <= i < n} [(a i + b) / c]。 | |
Project Euler 452 Long Products | |
统计x_1 * x_2 * … * x_N <= M,答案模1234567891。 | |
N, M <= 10^9 | |
Winter Camp 2012 糖果公园 | |
SGU 529 It's Time to Repair the Roads | |
无向图,修改边权,询问最小生成树。 | |
BOI 2010 Candy | |
定义distinct({a_1, a_2, …, a_n}) = # of {sum_i a_i x_i : x_i in {0, 1}}. | |
给出a_1, a_2, …, a_n,求distinct({a_1, a_2, …, a_n} \ {a_i} + {x})的最大值,和(i, x)字典序最小的解。 | |
n <= 100 | |
1 <= a_i <= 7000 | |
Tsinsen 1321 Attack (Chao Li) | |
2维平面上$n$个点,支持$q$次操作: | |
- 修改点权 | |
- 询问平行于坐标轴的矩形区域内点权第$k$小的值 | |
$n <= 60000, q <= 10000$ | |
$k$-th number with insertion | |
PA 2011 Kangaroos | |
给出${(A_1, B_1), (A_2, B_2), …, (A_n, B_n)}$,$q$次询问$[l, r]$,询问满足$l <= A_i <= B_i <= r$的最长连续i数量。 | |
$n <= 50000, m <= 200000$ | |
CTSC 2010 jewelry | |
树,点上有字符,定义$ps(x, y)$表示点$x$到点$y$唯一路径上字母的连接,$count(p, t)$表示串$p$在$t$中的出现次数。给定$T$,求$sum_{x, y} count(ps(x, y), T)$ | |
Knapsack [Unpublished problem] | |
$n$个数$A_1, A_2, …, A_n$,对于所有$s$,求和恰好是$s$的子集个数。 | |
($n, A_1 + A_2 + … + A_n <= 10^5$) | |
Codeforces 235E Number Challenge | |
设sigma(n)表示n的约数个数,给出A, B, C,求sum_{1 <= i <= A, 1 <= j <= B, 1 <= k <= C} d(i * j * k)。 | |
A, B, C <= 2000 | |
SGU 542 Gena vs Petya | |
给出A_1, A_2, …, A_N,求满足0 <= x <= min{A_1, A_2, …, A_N}且(A_1 - x) xor (A_2 - x) xor … xor (A_N - x) = 0的x数量。 | |
N <= 10^5, A_i <= 10^18 | |
HDU 4626 Jinkeloid | |
字符串|S|,Q个询问T = {T(i, 1), T(i, 2), …, T(i, C_i)},有多少子串T中字符出现了偶数次。 | |
|S| <= 10^5, Q <= 10^5,|Sigma| <= 20, C_i <= 5 | |
Single Round Match 593 WolfDelaymasterHard | |
定义形如0^n1^n的串是好的,好串的连接是好的。长度为N的字符串,包含0、1、?三种字符,替换?为0、1,使得形成的串是好的。求方案数。 | |
N <= 2 * 10^6 | |
Single Round Match 573 WolfPack | |
求从(X_1, Y_1)移动M步到(X_2, Y_2)的方案数,每次移动可以往上下左右移动一格。 | |
M <= 100000 | |
Single Round Match 569 MegaFactorial | |
定义f(n, k)满足: | |
1. f(n, k) = f(n - 1, k) * f(n, k - 1) | |
2. f(0, k) = 1 | |
3. f(n, 0) = n | |
求f(N, K)在B进制下末尾0的数量。结果模(10^9 + 7)。 | |
N <= 10^9, K <= 16, B <= 10 | |
Single Round Match 562 InducedSubgraphs | |
N个点的树,问有多少种标号方式,使得对所有1 <= i <= N - K + 1,点集{i, i + 1, …, i + K- 1}是连通的。 | |
N <= 40 | |
Single Round Match 550 ConversionMachine | |
给出只包含abc 3种字符的串A和串B,把a -> b的花费是cost[0],b -> c是cost[1],c -> a是cost[2],问在总费用不超过M的情况下,有多少方式能让A变换到B。 | |
|A|, |B| <= 11 | |
Single Round Match 596 BitwiseAnd | |
集合S是好的,当且仅当: | |
- 任意x, y in S, x & y > 0 | |
- 任意x, y, z in S, x & y & z = 0 | |
给出T,求T \subset S \subset [2^60 - 1],使得S是好的,而且字典序最小。 | |
Single Round Match 596 SparseFactorial | |
定义sparse factorial f(n) = n * (n - 1^2) * (n - 2^2) * … * (n - k^2) where k^2 < n <= (k + 1)^2。 | |
求满足L <= n <=R且f(n) % D = 0的n的数量。 | |
L, R <= 10^12,D <= 10^6 | |
PQHull | |
Chengdu 2012 Problem I / HDOJ 4472 | |
统计满足$1 <= x * y * z <= n$的$(x, y, z)$ | |
$n <= 10^11$ | |
Project Euler 381 | |
统计满足$1 <= lcm(x, y) <= n$的$(x, y)$ | |
$n = 10^12$ | |
POI XIV Queries | |
$n$个询问形如$(a, b, d)$,统计满足$1 <= x <= a, 1 <= y <= b$且$gcd(x, y) = d$的$(x, y)$ | |
$n, a, b, d <= 50000$ | |
SPOJ PGCD | |
$t$个询问形如$(n, m)$,统计满足$1 <= x <= n, 1 <= y <= m$且$gcd(x, y)$是质数的$(x, y)$ | |
$t <= 10, n, m <= 10^7$ | |
Hangzhou 2013 Online / HDOJ 4746 | |
定义$p(n)$表示$n$的**不同**质因子个数。 | |
$q$个询问形如$(n, m, k)$,统计满足$1 <= x <= n, 1 <= y <= m$且$p(gcd(x, y)) <= k$的$(x, y)$ | |
$q <= 5000, n, m, k <= 5 * 10^5$ | |
Project Euler 388 | |
统计满足$1 <= x, y, z <= n$且$gcd(x, y, z) = 1$的$(x, y, z)$ | |
$n = 10^10$ | |
Project Euler 402 Integer-valued polynomial | |
定义$M(a, b, c) = \gcd\{n^4 + a n^3 + b n^2 + c n : n in \mathbb{N}\}$,例如$M(4, 2, 5) = 6$。 | |
$S(n) = \sum_{0 < a, b, c \leq n} M(a, b, c)$。 | |
求$sum_{2 <= k <= K} S(fib_k) \bmod 10^9$。 | |
TCO 2013 2B LitPanels | |
$n * m$的矩形,把若干格子点亮,要求点亮的格子能被$2$个$a * b$的覆盖,求方案数。 | |
Project Euler 453 | |
$n \times m$的点阵,统计非退化的四边形数量,答案mod 135707531。 | |
SRM 600 LotsOfLines | |
给出$A, B$,考虑所有直线$y = ax + b$满足$0 <= a < A, 0 <= b < B$,问平面被分成了几块。 | |
$A, B <= 1200$ | |
HDOJ 4609 | |
给出$A_1, A_2, ..., A_n$,统计有多少对$(i, j, k)$满足$A_i, A_j, A_k$是三角形的三边。 | |
$n, A_i <= 10^5$ | |
SRM 603 SumOfArrays | |
给出长度为$n$的数组$A, B$,安排一个顺序,使得$A[i] + B[i]$的众数最大。 | |
$1 <= n <= 10^5, 0 <= A[i], B[i] <= 10^5$ 数据随机 | |
HDOJ 4624 | |
给出一棵树,求$E(u) = sum_v (dist(u, v))^k$,答案模$10007$。 | |
$n <= 50000, k <= 500$ | |
SRM 583 RandomPaintingOnABoard | |
$n \times m$的矩阵$P$,每次以$P[i][j] / sum P$的概率选择格子$(i, j)$,问每行每列都被选择至少一次所需要的步数期望。 | |
$n, m <= 21, n * m <= 50, P[i][j] < 10$ | |
HDOJ 4624 | |
$n$个白球,每次随机段区间染黑,问染成全黑的期望次数。 | |
$n <= 50$ | |
SRM 560 BoundedOptimization | |
$n$个变量$x_i$,满足$l_i <= x_i <= r_i$,且$x_1 + x_2 + … + x_n <= S$,求一个特殊二次式的最大值(无平方项,无一次项,系数都是1)。 | |
$n <= 13$ | |
维护数组$A$,支持$q$次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求#{i : a <= i <= b and A[i] > 0} | |
Codeforces 15E Holes | |
维护有根树,支持$q$次操作: | |
- parent[v] := p,保证p > v | |
- 询问点v的深度 | |
$n, q <= 10^5$ | |
Codeforces 348C | |
$n$个元素,$m$个集合$S_1, S_2, …, S_m$,$q$次操作: | |
- 把集合$S_i$的元素权值+= v | |
- 询问集合$S_i$元素的权值和 | |
$n, |S_1| + |S_2| + … + |S_m|, q <= 10^5$ | |
Chengdu 2012 Problem D / HDOJ 4467 | |
$n$个点$m$条边的无向图,点有2种颜色,边有权值,$q$次操作: | |
- 改变点$v$的颜色 | |
- 查询端点颜色是$(a, b)$的边权值之和 | |
$n, m, q <= 10^5$ | |
Chengdu 2013 Problem G / HDOJ 4787 | |
** 在线 ** 维护字符串集合$S$,$q$次操作: | |
- 在$S$中插入$s$ | |
- 查询$t$在$S$中的子串数 | |
$s$总长$10^5$,$t$总长$5 * 10^6$ | |
(2~3 solutions will be presented) | |
SPOJ UNTITLE1 | |
维护数组$A$,支持$q$次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求max{S[i] : a <= i <= b},其中S[i] = A[1] + A[2] + … + A[i] | |
$|A|, q <= 50000$ | |
BZOJ 2724 | |
**在线**查询区间众数。 | |
(an elegant algorithm to count occurrence) | |
BZOJ 2741 | |
**在线**查询区间最大连续异或和。 | |
BZOJ 巧克力王国 | |
查询半平面内点权的和。 | |
Codechef March14 GERALD07 | |
无向图,询问编号在$[L_i, R_i]$的边组成子图的连通块数量。 | |
Codeforces 19E | |
无向图,询问有多少条边,删掉之后的图是二分图。 | |
SPOJ COT2 | |
查询树上路径不同颜色数量。 | |
(2 solutions will be presented, the online version will also be discussed) | |
Tsinsen 1321 Attack (Chao Li) | |
2维平面上$n$个点,支持$q$次操作: | |
- 修改点权 | |
- 询问平行于坐标轴的矩形区域内点权第$k$小的值 | |
$n <= 60000, q <= 10000$ | |
$k$-th number with insertion | |
PA 2011 Kangaroos | |
给出${(A_1, B_1), (A_2, B_2), …, (A_n, B_n)}$,$q$次询问$[l, r]$,询问满足$l <= A_i <= B_i <= r$的最长连续i数量。 | |
$n <= 50000, m <= 200000$ | |
CTSC 2010 jewelry | |
树,点上有字符,定义$ps(x, y)$表示点$x$到点$y$唯一路径上字母的连接,$count(p, t)$表示串$p$在$t$中的出现次数。给定$T$,求$sum_{x, y} count(ps(x, y), T)$ | |
Knapsack [Unpublished problem] | |
$n$个数$A_1, A_2, …, A_n$,对于所有$s$,求和恰好是$s$的子集个数。 | |
($n, A_1 + A_2 + … + A_n <= 10^5$) | |
# Number theory | |
统计满足$1 <= x * y <= n$的$(x, y)$ | |
$n <= 10^14$ | |
Chengdu 2012 Problem I / HDOJ 4472 | |
统计满足$1 <= x * y * z <= n$的$(x, y, z)$ | |
$n <= 10^11$ | |
Project Euler 381 | |
统计满足$1 <= lcm(x, y) <= n$的$(x, y)$ | |
$n = 10^12$ | |
POI XIV Queries | |
$n$个询问形如$(a, b, d)$,统计满足$1 <= x <= a, 1 <= y <= b$且$gcd(x, y) = d$的$(x, y)$ | |
$n, a, b, d <= 50000$ | |
SPOJ PGCD | |
$t$个询问形如$(n, m)$,统计满足$1 <= x <= n, 1 <= y <= m$且$gcd(x, y)$是质数的$(x, y)$ | |
$t <= 10, n, m <= 10^7$ | |
Hangzhou 2013 Online / HDOJ 4746 | |
定义$p(n)$表示$n$的**不同**质因子个数。 | |
$q$个询问形如$(n, m, k)$,统计满足$1 <= x <= n, 1 <= y <= m$且$p(gcd(x, y)) <= k$的$(x, y)$ | |
$q <= 5000, n, m, k <= 5 * 10^5$ | |
Project Euler 388 | |
统计满足$1 <= x, y, z <= n$且$gcd(x, y, z) = 1$的$(x, y, z)$ | |
$n = 10^10$ | |
Chengdu 2012 Problem I / HDOJ 4472 | |
统计满足$1 <= x * y * z <= n$的$(x, y, z)$ | |
$n <= 10^11$ | |
Project Euler 381 | |
统计满足$1 <= lcm(x, y) <= n$的$(x, y)$ | |
$n = 10^12$ | |
POI XIV Queries | |
$n$个询问形如$(a, b, d)$,统计满足$1 <= x <= a, 1 <= y <= b$且$gcd(x, y) = d$的$(x, y)$ | |
$n, a, b, d <= 50000$ | |
SPOJ PGCD | |
$t$个询问形如$(n, m)$,统计满足$1 <= x <= n, 1 <= y <= m$且$gcd(x, y)$是质数的$(x, y)$ | |
$t <= 10, n, m <= 10^7$ | |
Hangzhou 2013 Online / HDOJ 4746 | |
定义$p(n)$表示$n$的**不同**质因子个数。 | |
$q$个询问形如$(n, m, k)$,统计满足$1 <= x <= n, 1 <= y <= m$且$p(gcd(x, y)) <= k$的$(x, y)$ | |
$q <= 5000, n, m, k <= 5 * 10^5$ | |
Project Euler 388 | |
统计满足$1 <= x, y, z <= n$且$gcd(x, y, z) = 1$的$(x, y, z)$ | |
$n = 10^10$ | |
Project Euler 402 Integer-valued polynomial | |
定义$M(a, b, c) = \gcd\{n^4 + a n^3 + b n^2 + c n : n in \mathbb{N}\}$,例如$M(4, 2, 5) = 6$。 | |
$S(n) = \sum_{0 < a, b, c \leq n} M(a, b, c)$。 | |
求$sum_{2 <= k <= K} S(fib_k) \bmod 10^9$。 | |
TCO 2013 2B LitPanels | |
$n * m$的矩形,把若干格子点亮,要求点亮的格子能被$2$个$a * b$的覆盖,求方案数。 | |
Project Euler 453 | |
$n \times m$的点阵,统计非退化的四边形数量,答案mod 135707531。 | |
SRM 600 LotsOfLines | |
给出$A, B$,考虑所有直线$y = ax + b$满足$0 <= a < A, 0 <= b < B$,问平面被分成了几块。 | |
$A, B <= 1200$ | |
HDOJ 4609 | |
给出$A_1, A_2, ..., A_n$,统计有多少对$(i, j, k)$满足$A_i, A_j, A_k$是三角形的三边。 | |
$n, A_i <= 10^5$ | |
SRM 603 SumOfArrays | |
给出长度为$n$的数组$A, B$,安排一个顺序,使得$A[i] + B[i]$的众数最大。 | |
$1 <= n <= 10^5, 0 <= A[i], B[i] <= 10^5$ 数据随机 | |
HDOJ 4624 | |
给出一棵树,求$E(u) = sum_v (dist(u, v))^k$,答案模$10007$。 | |
$n <= 50000, k <= 500$ | |
SRM 583 RandomPaintingOnABoard | |
$n \times m$的矩阵$P$,每次以$P[i][j] / sum P$的概率选择格子$(i, j)$,问每行每列都被选择至少一次所需要的步数期望。 | |
$n, m <= 21, n * m <= 50, P[i][j] < 10$ | |
HDOJ 4624 | |
$n$个白球,每次随机段区间染黑,问染成全黑的期望次数。 | |
$n <= 50$ | |
SRM 560 BoundedOptimization | |
$n$个变量$x_i$,满足$l_i <= x_i <= r_i$,且$x_1 + x_2 + … + x_n <= S$,求一个特殊二次式的最大值(无平方项,无一次项,系数都是1)。 | |
$n <= 13$ | |
维护数组$A$,支持$q$次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求#{i : a <= i <= b and A[i] > 0} | |
Codeforces 15E Holes | |
维护有根树,支持$q$次操作: | |
- parent[v] := p,保证p > v | |
- 询问点v的深度 | |
$n, q <= 10^5$ | |
Codeforces 348C | |
$n$个元素,$m$个集合$S_1, S_2, …, S_m$,$q$次操作: | |
- 把集合$S_i$的元素权值+= v | |
- 询问集合$S_i$元素的权值和 | |
$n, |S_1| + |S_2| + … + |S_m|, q <= 10^5$ | |
Chengdu 2012 Problem D / HDOJ 4467 | |
$n$个点$m$条边的无向图,点有2种颜色,边有权值,$q$次操作: | |
- 改变点$v$的颜色 | |
- 查询端点颜色是$(a, b)$的边权值之和 | |
$n, m, q <= 10^5$ | |
Chengdu 2013 Problem G / HDOJ 4787 | |
** 在线 ** 维护字符串集合$S$,$q$次操作: | |
- 在$S$中插入$s$ | |
- 查询$t$在$S$中的子串数 | |
$s$总长$10^5$,$t$总长$5 * 10^6$ | |
(2~3 solutions will be presented) | |
SPOJ UNTITLE1 | |
维护数组$A$,支持$q$次操作: | |
- add(a, b, v) for all a <= i <= b, A[i] += v | |
- query(a, b) 求max{S[i] : a <= i <= b},其中S[i] = A[1] + A[2] + … + A[i] | |
$|A|, q <= 50000$ | |
BZOJ 2724 | |
**在线**查询区间众数。 | |
(an elegant algorithm to count occurrence) | |
BZOJ 2741 | |
**在线**查询区间最大连续异或和。 | |
BZOJ 巧克力王国 | |
查询半平面内点权的和。 | |
Codechef March14 GERALD07 | |
无向图,询问编号在$[L_i, R_i]$的边组成子图的连通块数量。 | |
Codeforces 19E | |
无向图,询问有多少条边,删掉之后的图是二分图。 | |
SPOJ COT2 | |
查询树上路径不同颜色数量。 | |
(2 solutions will be presented, the online version will also be discussed) | |
Tsinsen 1321 Attack (Chao Li) | |
2维平面上$n$个点,支持$q$次操作: | |
- 修改点权 | |
- 询问平行于坐标轴的矩形区域内点权第$k$小的值 | |
$n <= 60000, q <= 10000$ | |
$k$-th number with insertion | |
PA 2011 Kangaroos | |
给出${(A_1, B_1), (A_2, B_2), …, (A_n, B_n)}$,$q$次询问$[l, r]$,询问满足$l <= A_i <= B_i <= r$的最长连续i数量。 | |
$n <= 50000, m <= 200000$ | |
CTSC 2010 jewelry | |
树,点上有字符,定义$ps(x, y)$表示点$x$到点$y$唯一路径上字母的连接,$count(p, t)$表示串$p$在$t$中的出现次数。给定$T$,求$sum_{x, y} count(ps(x, y), T)$ | |
Knapsack [Unpublished problem] | |
$n$个数$A_1, A_2, …, A_n$,对于所有$s$,求和恰好是$s$的子集个数。 | |
($n, A_1 + A_2 + … + A_n <= 10^5$) | |
# Number theory | |
统计满足$1 <= x * y <= n$的$(x, y)$ | |
$n <= 10^14$ | |
Chengdu 2012 Problem I / HDOJ 4472 | |
统计满足$1 <= x * y * z <= n$的$(x, y, z)$ | |
$n <= 10^11$ | |
Project Euler 381 | |
统计满足$1 <= lcm(x, y) <= n$的$(x, y)$ | |
$n = 10^12$ | |
POI XIV Queries | |
$n$个询问形如$(a, b, d)$,统计满足$1 <= x <= a, 1 <= y <= b$且$gcd(x, y) = d$的$(x, y)$ | |
$n, a, b, d <= 50000$ | |
SPOJ PGCD | |
$t$个询问形如$(n, m)$,统计满足$1 <= x <= n, 1 <= y <= m$且$gcd(x, y)$是质数的$(x, y)$ | |
$t <= 10, n, m <= 10^7$ | |
Hangzhou 2013 Online / HDOJ 4746 | |
定义$p(n)$表示$n$的**不同**质因子个数。 | |
$q$个询问形如$(n, m, k)$,统计满足$1 <= x <= n, 1 <= y <= m$且$p(gcd(x, y)) <= k$的$(x, y)$ | |
$q <= 5000, n, m, k <= 5 * 10^5$ | |
Project Euler 388 | |
统计满足$1 <= x, y, z <= n$且$gcd(x, y, z) = 1$的$(x, y, z)$ | |
$n = 10^10$ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment