Codeforces Round #441 (Div. 2)

A. Trip For Meal

题目描述：给出(3)个点，以及任意两个点之间的距离，求从(1)个点出发，再走(n-1)个点的最短路径。

solution
当(n=1)时，答案为(0)，当(n=2)时，答案等于与开始点相连的两条边的最小值，当(n>2)时，答案等于与开始点相连的两条边的最小值+三条边最小值*((n-2))
时间复杂度：(O(1))

B. Divisiblity of Differences

题目描述：给出(n)个数，从中选出(k)个数，使得任意两个选出的数的差是(m)的倍数。输出其中一种方案。

solution
两个数的差是(m)的倍数，说明这两个数对(m)取余相等。所以可以统计对(m)取余每种余数有多少个，如果某一种余数超过或等于(k)个，则随意选择(k)个该种余数的数即是答案。
时间复杂度：(O(n))

C. Classroom Watch

题目描述：给出一个数(n)，求有哪些正整数(x)，满足(x)的每一位的数的和加(x)等于(n)。

solution
因为(n leq 10^9)，所以(x)的每一位的数的和最大是(90)，由于加法只能产生百位加一的效果，所以(x)的最高位到百位与(n)相同，或是(x)的百位比(n)少一。按此分成两种情况，然后枚举十位和个位即可。
时间复杂度：(O(200))

D. Sorting the Coins

题目描述：一行(n)个'o'，然后依次将第(p[i])位的'o'变成'x'，每次改变后进行以下操作：从左看到右，如果遇到第(i)位为'o'，(i+1)位为'x'，则交换这两位，然后从第(i+1)位继续往右看。如果某一轮看完后没有进行交换操作，则结束，输出看了多少轮，然后进行下一次的改变。

solution
手工画了样例后发现，除了最右边的连续的'x'不用动之外，其它'x'都要通过看一轮使它成为最右边连续的'x'，所以只要维护最右边有多少个连续的'x'即可。
时间复杂度：(O(n))

E. National Property

题目描述：给出(n)个字符串，字符串的每一位都是一个数字，数字有大小写之分，任意大写数字比任意小写数字小，同种数字比较时，数字小的比较小。现在把某种数字从小写变成大写，使得这(n)个字符串从小到大排好序，输出一种可行的方案。

solution
考虑相邻两个字符串，只要所有的相邻字符串都满足前者小于后者，则这(n)个数就已经从小到大排好。相邻字符串比较：从左到右找到第一个不同的位置：
1、如果前者为数字，后者为空，则无解；
2、如果前者为空，后者为数字，则不用任何操作；
3、如果前者数字大于后者数字，则前者数字一定要变为大写；
4、如果前者数字小于后者数字，则这两种数字要同为大写或小写。
根据最后一种情况，我们可以从后者数字连一条有向边到前者数字，表示如果某个点变为大写(true)，则连出去的边指向的点都要为true，这就有点像2-SAT，但不同的是2-SAT可能有环，需要缩点，而这题一定不会有环。构图后按照2-SAT构造解的方式构造答案即可。
时间复杂度：(O(n))

F. High Cry

题目描述：给出一个数组(a[i])，求数对((x, y))的个数，((x, y))满足((a[x] | a[x+1] | ... | a[y])>max){(a[x], a[x+1], ..., a[y])}

solution
从表达式可知，最大值是一个重要的值。所以可以枚举一个位置(i)作为数对((x, y))之间的最大值，那么先可以预处理出(i)左边离(i)最近的大于(a[i])的位置(L[i])，以及(i)右边离(i)最近的大于(a[i])的位置(R[i])，因为(x)一定在((L[i], i])中选，(y)一定在([i, R[i]))中选。
那(x，y)可以选什么位置呢？因为最后或操作后的数要大于(a[i])，所以只要([x, y])中存在一个数与(a[i])或操作后大于(a[i])即可，即存在一个数,(a[i])的二进制第(w)位为(0),但它的第(w)位为(1)。所以我们可以预处理出(i)的左边离(i)最近的二进制第(j)位为(1)的位置(Lone[i][j])，以及(i)的右边离(i)最近的二进制第(j)位为(1)的位置(Rone[i][j])。
这样(x)的可选范围是((L[i], max){(Lone[i][j])}(]), (y)的可选范围是([min){(Rone[i][j])}(, R[i]))，而求答案时只要(x,y)有一个在可选范围内就是正确答案。
要注意的是(a[i])相等的情况，可以规定(a[L[i]] geq a[i], a[R[i]]>a[i])，这样就能避免重复计算。
时间复杂度：(O(nlogn))