叉姐200题

叉姐200题

转载自：，侵权删。

PublicTransitHard =problem_statement&pm=13797

BichromeSky =problem_statement&pm=13711
n个红点，m个蓝点，没有三点共线，第i个红点以p_i的概率出现，求红点的凸包包含所有蓝点的概率
n, m <= 100

InverseRMQ =problem_statement&pm=13235

TreeDistance =problem_statement&pm=13369

TreePuzzle =problem_statement&pm=13185

EagleInZoo =problem_statement&pm=13117

EllysLamps =problem_statement&pm=11906

SimilarSequencesAnother =problem_statement&pm=12742
(A, B) 是相似的，当且仅当A, B各删不超过2个字符后相等。给定长度n和字符集m，问相似(A, B)数量。
n <= 100

TaroCheckers =problem_statement&pm=12996
n * m的棋盘，第i行前l[i]个格子有一个棋子，后r[i]个格子有一个棋子，每列最多有一个棋子，问方案数。
n <= 50, m <= 200

OneDimensionalRobot =problem_statement&pm=12999

PerfectSquare =problem_statement&pm=13145

AlienAndPermutation =problem_statement&pm=12949

Perfect Matching /
n个点的二分图，假设完备匹配的数量是x，判断x = 0 (mod 2)
n <= 300

(False) Face .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
长度为n的排列，m次交换a_i, b_i，每个交换a_i, b_i有50%的概率不发生，问逆序数的期望
n, m <= 1000

Inversions problem
长度为n的排列，每次随机一个子段翻转，问m轮后逆序数的期望
n <= 300, m <= 10^9

Cliquers [PA 2008, Round 5]

求 n $n$个点有标号的无向图的数量，要求每个连通分量都是团。
n≤200000$n leq 200000$

Isomorphism [SGU 282]

n $n$个点的完全图m$m$染色，问同构意义下有多少种染色方案。
n≤53,m≤1000 $n leq 53, m leq 1000$

Writing n as the product of k distinct positive integers [PE 495]

求 n! $n!$写成 k $k$个不同的数的乘积的方案数。
n≤104,k≤30$n leq 10^4, k leq 30$

Partition [HDOJ 4651]

求 n $n$的拆分数pn$p_n$。
n≤105 $n leq 10^5$

∏n=1∞(1−xn)=∑k=0∞xk(3k±1)2 $$prod_{n = 1}^{infty} (1 - x^n) = sum_{k = 0}^{infty} x^{frac{k(3k pm 1)}{2}}$$

Integer Partition [HDOJ 4658]

求 n $n$的拆分数，要求数字出现不超过k$k$次。
k≤n≤105 $k leq n leq 10^5$

Chocolate triangles

求 n $n$边型剖分中恰好有k$k$个三角形的方案数。
n,k≤300 $n, k leq 300$

SWERC 2014 Problem J The Big Painting

给出矩阵 A,B $A, B$，问 A $A$在B$B$中出现了多少次。

SWERC 2014 Problem H Money Transfers

给出 n $n$个点m$m$条边的无向图，和一个顶点集 M $M$，现在给所有边的权值增加c$c$，使得 1 $1$到n$n$的最短路只包含 M $M$中的点，求c$c$的最小值。
n,m≤1000 $n, m leq 1000$

CERC 2014 Problem F Vocabulary

给出 3 $3$个包含?的字符串A$A$, B $B$, C$C$，问有多少种把?替换为小写字母的方案，使得 A<B<C $A < B < C$，答案模 (109+9) $(10^9+9)$
|A|,|B|,|C|≤106 $|A|, |B|, |C| leq 10^6$

CERC 2014 Problem E Can’t stop playing

你正在玩 1 $1$维版本的2048游戏。数字2a1,2a2,…,2an$2^{a_1}, 2^{a_2}, dots, 2^{a_n}$依次出现，你可以选择加到左边还是右边，问最后能不能只剩 1 $1$个，输出方案。
n≤1000,2a1+2a2+⋯+2an≤213$n leq 1000, 2^{a_1} + 2^{a_2} + dots + 2^{a_n} leq 2^13$

CERC 2014 Problem L Outer space invader

有 n $n$个怪物，第i$i$个怪物于第 ai $a_i$秒出现，第 bi $b_i$秒消失，高度是 di $d_i$。你可以使用威力是 x $x$的炸弹，消灭高度不超过x$x$的所有怪物，代价是 x $x$。
问消灭所有怪物的最小的总代价。
n≤300$n leq 300$

CERC 2014 Problem J Pork barrel

给出 n $n$个点m$m$条边的无向图，在线回答 q $q$个询问(li,ri)$(l_i, r_i)$，求只考虑长度在 [li,ri] $[l_i, r_i]$内的边时，最小生成树的大小。
n≤1000,m≤105,q≤106 $n leq 1000, m leq 10^5, q leq 10^6$

CERC 2014 Problem G Virus synthesis

给出字符串 S $S$，可以进行2$2$种操作：
- 在某端删除一个字符
- 如果 S $S$是偶数长度的回文串，删除左半边/右半边
问得到空串最少要几步。
|S|≤105$|S| leq 10^5$

CERC 2014 Problem B Mountainous landscape

n $n$条线段组成的山，对于每条线段，输出站在它上面时，所能看到的第一个顶点
n≤105$n leq 10^5$

Subarray Cuts
数组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 =1027
A是n * n的矩阵，计算perm(A)
n <= 20

Permutation .php?pid=4917
n个点m条边的有向图，统计拓扑排序的数量
n <= 40, m <= 20

SimilarNames =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

Permanent
A是n * n的矩阵，除了给定的k个位置以外都是1，计算perm(A)
n <= 10^5, k <= 50

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 =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 .php?pid=5116
n * m的有障碍的棋盘，求放2个L的不同方案数，要求L的两边长度互质
n, m <= 200

ThreeLLogo =problem_statement&pm=13059
n * m的有障碍的棋盘，求放3个L的不同方案数
n, m <= 30

FencingPenguins =problem_statement&pm=12339
正N边型内有M个企鹅，选择一些顶点建立围栏，要求：
1. 围栏不能相交
2. 每个围栏至少包含1个企鹅
3. 企鹅都被包围
4. 同色企鹅在同一围栏
求方案数。
N <= 222, M <= 50

An easy problem about trees

Mr. Kitayuta’s Gift

Deja Vu

Tree and Table

Buy One, Get One Free

Triangles 3000
3k条直线，等概率挑选3条，求围成三角形面积的期望

Fox and Meteor Shower
1k条3维直线，求最大的两两相交的子集

Gena and Second Distance
1k个点，求次近的点最远的点

Drawing Circles is Fun

维护数组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<=105 $n, q <= 10^5$

Codeforces 348C
n $n$个元素，m$m$个集合 S1,S2,…,Sm $S_1, S_2, …, S_m$， q $q$次操作：
- 把集合Si$S_i$的元素权值+= v
- 询问集合 Si $S_i$元素的权值和
n,|S1|+|S2|+…+|Sm|,q<=105 $n, |S_1| + |S_2| + … + |S_m|, q <= 10^5$

Chengdu 2012 Problem D / HDOJ 4467
n $n$个点m$m$条边的无向图，点有2种颜色，边有权值， q $q$次操作：
- 改变点v$v$的颜色
- 查询端点颜色是 (a,b) $(a, b)$的边权值之和
n,m,q<=105 $n, m, q <= 10^5$

Chengdu 2013 Problem G / HDOJ 4787
* 在线 * 维护字符串集合 S $S$，q$q$次操作：
- 在 S $S$中插入s$s$
- 查询 t $t$在S$S$中的子串数
s $s$总长105$10^5$， t $t$总长5∗106$5 * 10^6$
(2~3 solutions will be presented)

SPOJ UNTITLE1
维护数组 A $A$，支持q$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 $|A|, q <= 50000$

BZOJ 2724
在线查询区间众数。
(an elegant algorithm to count occurrence)

BZOJ 2741
在线查询区间最大连续异或和。

BZOJ 巧克力王国
查询半平面内点权的和。

Codechef March14 GERALD07
无向图，询问编号在 [Li,Ri] $[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 $k$的点对数量。

SPOJ FTOUR2
点有黑白两色，边有长度，求黑点数量<= 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 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的仰慕者 .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

Single Round Match 570 CurvyonRails

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

求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

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 <= 150, 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 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，求最多能放的白点数量。

Project Euler 416 A frog’s trip
N个格子，一只青蛙1 -> N -> 1，重复M次。
青蛙每次只能跳跃1、2、3个格子，问至多只有1个格子没被访问过的路径数量。
N <= 10^12, M <= 10

伍一鸣 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

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

SPOJ LCMSUM
给出N，求lcm(N, 1) + lcm(N, 2) + … + lcm(N, n)。
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

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

Topcoder Open 2012 Round 3A CowsMooing
N头牛，第i头牛按照pattern_i moo，求count[i]表示50!内恰好有i头牛moo的时间，答案模109+7$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)满足：
?
?
求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 2009 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的方案数，满足：
?
?
?
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的数量满足：
?
?
?

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

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
无向图，修改边权，询问最小生成树。

Tsinsen 1321 Attack (Chao Li)
2维平面上 n $n$个点，支持q$q$次操作：
- 修改点权
- 询问平行于坐标轴的矩形区域内点权第 k $k$小的值
n<=60000,q<=10000$n <= 60000, q <= 10000$

k $k$-th number with insertion

PA 2011 Kangaroos
给出(A1,B1),(A2,B2),…,(An,Bn)${(A_1, B_1), (A_2, B_2), …, (A_n, B_n)}$， q $q$次询问[l,r]$[l, r]$，询问满足 [Li,Ri] $[Li, Ri]$交 [l,r] $[l,r]$非空的最长连续i数量。
n<=50000,m<=200000 $n <= 50000, m <= 200000$

CTSC 2010 jewelry
树，点上有字符，定义 ps(x,y) $ps(x, y)$表示点 x $x$到点y$y$唯一路径上字母的连接， count(p,t) $count(p, t)$表示串 p $p$在t$t$中的出现次数。给定 T $T$，求sumx,ycount(ps(x,y),T)$sum_{x, y} count(ps(x, y), T)$

Knapsack [Unpublished problem]
n $n$个数A1,A2,…,An$A_1, A_2, …, A_n$，对于所有 s $s$，求和恰好是s$s$的子集个数。
( n,A1+A2+…+An<=105 $n, A_1 + A_2 + … + A_n <= 10^5$)

Codeforces 235E Number Challenge
设d(n)表示n的约数个数，给出A, B, C，求sum_{1 <= i <= A, 1 <= j <= B, 1 <= k <= C} d(i * j * k)。
A, B, C <= 2000

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 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 J / HDOJ 4473
统计满足 1<=x∗y∗z<=n $1 <= x * y * z <= n$的 (x,y,z) $(x, y, z)$
n<=1011 $n <= 10^11$

Project Euler 379
统计满足 1<=lcm(x,y)<=n $1 <= lcm(x, y) <= n$的 (x,y) $(x, y)$
n=1012 $n = 10^12$

POI XIV Queries
n $n$个询问形如(a,b,d)$(a, b, d)$，统计满足 1<=x<=a,1<=y<=b $1 <= x <= a, 1 <= y <= b$且 gcd(x,y)=d $gcd(x, y) = d$的 (x,y) $(x, y)$
n,a,b,d<=50000 $n, a, b, d <= 50000$

SPOJ PGCD
t $t$个询问形如(n,m)$(n, m)$，统计满足 1<=x<=n,1<=y<=m $1 <= x <= n, 1 <= y <= m$且 gcd(x,y) $gcd(x, y)$是质数的 (x,y) $(x, y)$
t<=10,n,m<=107 $t <= 10, n, m <= 10^7$

Hangzhou 2013 Online / HDOJ 4746
定义 p(n) $p(n)$表示 n $n$的质因子个数。
q$q$个询问形如 (n,m,k) $(n, m, k)$，统计满足 1<=x<=n,1<=y<=m $1 <= x <= n, 1 <= y <= m$且 p(gcd(x,y))<=k $p(gcd(x, y)) <= k$的 (x,y) $(x, y)$
q<=5000,n,m,k<=5∗105 $q <= 5000, n, m, k <= 5 * 10^5$

Project Euler 388
统计满足 1<=x,y,z<=n $1 <= x, y, z <= n$且 gcd(x,y,z)=1 $gcd(x, y, z) = 1$的 (x,y,z) $(x, y, z)$
n=1010 $n = 10^10$

Project Euler 402 Integer-valued polynomial
定义 M(a,b,c)=gcd{n4+an3+bn2+cn:ninN} $M(a, b, c) = gcd{n^4 + a n^3 + b n^2 + c n : n in mathbb{N}}$，例如 M(4,2,5)=6 $M(4, 2, 5) = 6$。
S(n)=∑0<a,b,c≤nM(a,b,c) $S(n) = sum_{0 < a, b, c leq n} M(a, b, c)$。
求 sum2<=k<=KS(fibk)mod109 $sum_{2 <= k <= K} S(fib_k) bmod 10^9$。

TCO 2013 2B LitPanels
n∗m $n * m$的矩形，把若干格子点亮，要求点亮的格子能被 2 $2$个a∗b$a * b$的覆盖，求方案数。

Project Euler 453
n×m $n times m$的点阵，统计非退化的四边形数量，答案mod 135707531。

SRM 600 LotsOfLines
给出 A,B $A, B$，考虑所有直线 y=ax+b $y = ax + b$满足 0<=a<A,0<=b<B $0 <= a < A, 0 <= b < B$，问平面被分成了几块。
A,B<=1200 $A, B <= 1200$

HDOJ 4609
给出 A1,A2,...,An $A_1, A_2, ..., A_n$，统计有多少对 (i,j,k) $(i, j, k)$满足 Ai,Aj,Ak $A_i, A_j, A_k$是三角形的三边。
n,Ai<=105 $n, A_i <= 10^5$

SRM 603 SumOfArrays
给出长度为 n $n$的数组A,B$A, B$，安排一个顺序，使得 A[i]+B[i] $A[i] + B[i]$的众数最大。
1<=n<=105,0<=A[i],B[i]<=105 $1 <= n <= 10^5, 0 <= A[i], B[i] <= 10^5$ 数据随机

HDOJ 4624
给出一棵树，求 E(u)=sumv(dist(u,v))k $E(u) = sum_v (dist(u, v))^k$，答案模 10007 $10007$。
n<=50000,k<=500 $n <= 50000, k <= 500$

HDOJ 4624
n $n$个白球，每次随机段区间染黑，问染成全黑的期望次数。
n<=50$n <= 50$

统计满足 1<=x∗y<=n $1 <= x * y <= n$的 (x,y) $(x, y)$
n<=1014 $n <= 10^14$