2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest

Problem A. Advertising Strategy

题目描述：给出两个数(n, k)，初始时(a_1=0)，每一天开始时令(b_i=a_i+x_i)，每天结束时(a_{i+1}=b_i+min(b_i, left lfloor frac{n-b_i}{2} ight floor))，其中(sum x_i leq k)，问最少多少天使得(a_i geq n)

solution
将(k)分为两部分，一部分为(x_1)，另一部分为最后一天的(x)，这样最优，然后枚举(x_1)即可。

时间复杂度：(O(klogn))

Problem B. Byteland Trip

题目描述：给出一个字符串(st)，由<, >组成，当(st_i='<')时，(i)可以去到(i)左边的任意一个点，当(st_i='>')时，(i)可以去到(i)右边的任意一个点。问从任意一个点出发，遍历所有的点，最终去到(i)的方案数，对于每个(i)输出答案。

solution
还没想到。。。

Problem C. Carpet

题目描述：给出一棵树，将这棵树的节点放在一个(1 000 000 imes 20)的网格中，每个格只能有一个节点，使得树边不相交（树边为线段），输出一种方案。

solution
因为高度只有(20)所以只能尽量横向发展。
设(size[i])为子树(i)的大小，(longest[i])为(i)子树中(i)到叶子的最长距离，(longid[i])为最长链中(i)的儿子。
因为尽量要横向发展，所以将最长链横放，假设(i)的位置是((x, y))，则(longid[i])的位置为((x+size[i]-size[longid[i]], y))，即将(longid[i])与(i)放在同一行，并且给(i)的其它儿子留足空间，其它儿子依次放在(y+1)行，第一个儿子放在((x, y+1))，第二个放在((x+size[son_1], y+1))，以此类推，目的是给每棵子树都留足空间。

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

Problem D. Decoding of Varints

题目描述：对整数进行编号：(0)编号为(0)，(-1)为(1)，(1)为(2)，即当(x geq 0)时，编号为(2x)，当(x<0)时，编号为(-2x-1)。有一个数列(x_i)(未知)，将(x_i)的编号化为(128)进制，然后除了最高位外，其余的数加(128)，按顺序给出操作后的序列，求原序列。

solution
模拟。

时间复杂度：(O(9n))

Problem E. Empire History

题目描述：给出一个无向图，将该图的节点分成两部分，使得这两部分分别连通，并且存在两个非空集合(u, v)，分别为两个部分的点的子集，使得(u, v)之间两两有边。输出一种方案。

solution
还不会。。。

Problem F. Fake or Leak?

题目描述：根据ACM的赛制，给出封榜时每个队伍的做题情况，再给出最终结果排名的连续(k)个人的做题情况，问是否可能出现。

solution
先按照规则判断终榜的顺序是否正确，如果正确，再判断其它人是否都能排在他们的前面或者后面。排在前面的话肯定是假设全部题都答对，看看能不能排在终榜第一个人的前面；至于排在后面，则是根据封榜作为终榜，看看能不能排在终榜最后一个人的后面。

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

Problem G. God of Winds

题目描述：给出一个(n imes m)的网格图，网格图的每条边都有一个值。现在在每个格子中填一个整数，若是正数(x)，则在格子的左、下边加(x)，右、上边减(x)；若是负数(-x)，则在格子的右、上边加(x)，左、下边减(x)。初始时网格的所有边都是(0)，问是否存在一种填数的方案使得最后所有边的值等于给出的边值。

solution
容易找到规律：若存在方案，则存在无数种方案，即第一个方格填什么数都可以。所以设第一个方格为(0)，然后推出所有格子的数，然后再验证所有边是否正确。

时间复杂度：(O(nm))

Problem H. Hilarious Cooking

题目描述：存在一个序列(a_i)，满足(a_i geq 0, | a_i-a_{i+1} | leq 1)，给出某些位置的数和一个数(T)，问是否存在一个序列(a_i)，使得(sum a_i=T)。

solution
由于(sum a_i)是连续的，所以可以求出(sum a_i)的范围，然后判断(T)是否在这个范围内。

时间复杂度：(O(m))

Problem I. Infinite Gift

题目描述：在(k)维空间中选(n)个向量，然后将(k)维空间的所有向量(a)向(a+v_i)连边。问构成的图是否是二分图。

solution
是否是二分图相当于判断是否有奇环。
然后队友找到一个规律：设(k)个未知数，列(n)条方程，将向量的每一维都模(2)，然后方程是(x_1v_{i1} XOR x_2v_{i2} XOR ... XOR x_kv_{ik}=1)
然后方程有解则表示有奇环，所以可以压位求解异或方程。

时间复杂度：(O(frac{nk^2}{64}))

Problem J. Judging the Trick

题目描述：在一个(w imes h)矩形中有若干个三角形，求矩形中的一个没有被三角形覆盖的点。

solution
还不会。。。