嗯……好久不练习了。这一场的时间很好，所以试试参加。结果上看还好。
综述#
总共 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 就行），从这个元素开始到“区间或”所在的区间的左端点就都是不符题的左端点范围了。
评论