Petrozavodsk Summer Training Camp 2017

Petrozavodsk Summer Training Camp 2017

Problem A. Connectivity

题目描述：有(n)个点，现不断地加边。每条边有一种颜色，如果一个点对((a, b))，满足(a=b)或对于每一种颜色的子图（图中只有该种颜色的边），(a, b)总是连通，则该点对称为好连通。求出每加一条边，好连通的点对数。

solution
每个子图用并查集维护连通块，并且用(vector)记录每个连通块的点，便于之后进行答案的统计，合并时启发式合并即可。
每种颜色生成一个(hash)值，每个点记录一个(hash)值，表示在每个子图中是属于哪个并查集，若两个点的(hash)值相同，则认为它们是好连通。

时间复杂度：(O(mlogn))（常数比较大）

Problem B. Hotter-colder

Problem C. Painting

题目描述：有连续(n)个，每个点开始时都没有颜色，现在每次选择一个连续的区间，然后将这个区间涂成一种颜色，使得最终变成目标的样子。颜色有(m)种，每种颜色至少出现一次，涂色也只能涂(m)次，每次涂色的花费为区间长度。问总花费的最大值。

solution
可以先预处理出每种颜色的最小涂色区间，由于数据的特殊性，这些区间是不相交的，只可能是相离或包含。这样就可以按嵌套关系将区间分成很多层，必须先涂外层，再涂内层。对于同一层的区间，再分成很多段，每一段是连续的相邻的区间，每一段用(dp)来确定如何涂色，答案就是全部加起来的值。

时间复杂度：(O(n^2))

Problem D. Ones

题目描述：定义一种1-expressions (E ::= 1 | E+E | E*E | (E+E) | (E*E))，给出一个数(k)，用一个不多于(100)个(1)的表达式，使得答案为(k)。

solution
偶数时除于二，奇数时减一。

时间复杂度：(O(logk))（每次询问）

Problem E. Seats

Problem F. Ants

Problem G. Permutation

题目描述：给出一个(n)排列(p_i)，将其分成两个子序列，使得一个子序列递增，另一个递减。或无解。

solution
贪心。假设枚举到第(i)个数，如果(p_i)小于递增序列最后一个数，则扔进递减序列，若大于递减序列最后一个数，则扔进递增序列，若两个条件都满足，则无解。如果是介于两者之间，则考虑(p_{i+1})，若(p_{i+1}>p_i)，则扔进递增序列，否则扔进递减序列。

时间复杂度：(O(n))（每次询问）

Problem H. Primes

题目描述：定义(pi (x, y))表示能同时整除(x, y)的质数个数。给出((a, b))，求出(sum_{a leq x < y leq b} pi(x, y))

solution
答案为(sum_{d} left lfloor frac{b}{d} ight floor - left lfloor frac{a-1}{d} ight floor)，(d)为质数。然后其实对于不同的(d)，里面的值也可能一样，可以将值一样的(d)一起算，也就是跳着跳着算。

时间复杂度：(O(log^2n)) （每次询问）

Problem I. Vertex covers

Problem J. Scheduling

题目描述：有(m)个线程，有(n)个需要执行的程序，每个程序需要在时刻(p_i)到(k_i)内执行，执行时间为(c_i)，每条程序可以随意暂停，跳转线程，但同一线程同一时刻只能执行一条程序。问是否能执行所有程序。

solution
将时刻拆分成若干个区间，每个区间连向汇点，流量为区间长度，每个程序连向源点，流量为程序的执行时间，然后每个程序连向所在的区间。跑一遍网络流就可以了。

时间复杂度：(O(n^2m))

Problem K. Shufe

题目描述：有(2^n)张牌，有一种洗牌的方法：1、如果只有两张牌，则交换它们。2、将牌分成上下两堆，交换两堆牌，然后每堆牌递归操作。问洗(t)次牌后的顺序。

solution
显然，洗一次牌后所有牌会调转，再洗一次就会变回原样。

时间复杂度：(O(2^n))