Codeforces Round #441 (Div. 2)

嗯……好久不练习了。这一场的时间很好，所以试试参加。结果上看还好。

综述#

总共 6 道题，整体还是比较简单的。A、B、C、D、F 一次 Accepted，E 题只读题，没时间做了，赛后补掉了。C 题想的有点慢，F 写的有点慢。

题意和题解#

A. Trip For Meal#

加权无向无自环的三元图，问固定起点最短的有 $n$ 个点的路径为多长。

显然在最短的边上抖动就好，如果那条边不和起点关联就走个最短的先过去。

B. Divisiblity of Differences#

给 $n$ 个数，选 $k$ 个模 $m$ 同余的。

开 $m$ 个桶，扔到对应余数的就行。随便找一个符题的桶输出就好。

C. Classroom Watch#

给一个数 $x$，找有哪些 $n$，满足 $n$ 的十进制的各位和 $s$ 与 $n$ 的和等于 $x$。

$s$ 范围很小，枚举 $s$，有 $n_0 \gets x - s$，看看得到的 $n_0$ 的各位和是不是 $s$ 就行。

D. Sorting the Coins#

给一个长度为 $n$，初始全为0的数组，会有 $n$ 次操作把数组的某一个位置改为1，问当前情况下，如果用冒泡排序，排完前最多会扫几次。

考虑最右边的0，找到它左面第一个1，这个1肯定会被换过来，并且刚好换到排好序的位置上；其它的1会与其右边连续的若干个0交换位置，但依然没有被交换到排好序的位置上，继续从头进行同样的操作，直到发现数组已经排好。这样就发现，排序的扫描次数就是从右边第一个0开始，左边的1的个数加一。所以，记一下总共有多少个1，末尾有多少个连续的1，两者的差加一即为答案。

E. National Property (2-sat)#

有 $n$ 个数组，长度分别为 $l_i$，数组的元素为正整数都小于或等于 $m$，初始时数组的每个元素为“小写”，现在你可以让某些数字全部变成“大写”，让这些数组变成字典序升序（即大写小于小写，其余按正整数的比较方式比较）。

两两间比较时，遇到的第一个不同的位置会对这两个数字的大小写进行限制。比如两者关系在小写的时候是符合字典序的，那这两个数字应同时大写或同时小写；如果不符合字典序就直接限制在前面的数字取大写，后面的取小写；如果前缀都一样，但是前面的比后面的长，那答案就只能是否定了。这显然是一个 2-sat 模型，跑一个解就行。（对这个模型太不熟悉了，当时没想到）

F. High Cry (two pointers)#

给个长度为 $n$ 的数组 $a_i$，求有多少个区间 $[l, r)$ 满足区间内所有值的二进制或严格大于区间最大值。

卡住右端点 $r$，考虑每一个左端点内区间的性质。会发现“区间或”的取值的个数是 $\mathcal{O}(\log{a})$，并且随左端点远离右端点，“区间或”单调不减，这样就可以维护“区间或”相同的左端点的范围了；进一步会发现“区间或”实际是大于或等于区间最大值的，为了方便，可以计算区间最大值刚好等于区间或的左端点范围（倒立做题）；由于区间最大值也有单调不减的性质，因此可以对于每个“区间或”的值和区间，找在区间内和这个值相等的、最靠右的元素位置（开个 map 就行），从这个元素开始到“区间或”所在的区间的左端点就都是不符题的左端点范围了。