【题解】哈尔滨工业大学（威海）第九届ACM程序设计竞赛
Solution
Preface
大家感觉题目怎么样啊？
我题面的乡村英语希望没有给大家造成困扰_(:зゝ∠)_。
标程有很多模板，大家可以直接拖到下面的 solve() 函数附近看就行。
Easy
A. All Palindrome
全回文串：这个字符串的所有子串都是回文串。
观察任何一个字符串，可以发现当且仅当所有字符都相同的时候这个字符串才是全回文的。
遍历一遍统计所有字母的出现次数，保留其中最多的一个其他都得删，所以是 。
B. Clarifications
好多人问我样例的问题，是不是没读 Input 啊。
用两个容器存一下，一个是愚蠢的问题，一个是其他问题。
挨个处理询问就行。
Mid-Easy
C.
首先知道每个区间的长度，比如一位数构成的区间长度只有 ，两位数构成的区间长度只有
，那么递推一下就能得出所有数区间的长度，找一下就知道这个数字在哪个区间内。
然后在这个区间内每个数的长度都是一致的，那就找到这是哪个数直接每一位去找就行了。
D. Ramen Network Protocol
由于起点和终点集合不会相交，所以直接缩点或者建立超源超汇，跑一次单源最短路就可以了。 的 Dijkstra 可以过，SPFA 也没卡。
G. Virtual Youtuber
如果枚举区间或区间长度的复杂度都是 。
不妨考虑任意一个区间 ，如果
，那么这个区间满足答案，此时我右推一下右区间变成
，那么如果此时的和大于
了，那么这个区间就不行了，我们可以右推左边界，此时答案减小。
我们现在来考虑满足条件的 ，假如这个区间满足条件，我们可以知道所有以
为起点的，最远到
的区间都是满足条件的，也就是此时对答案的贡献程度是
。
那么此时我们就好办了，我们贪心右推右边界，当且仅当某个区间 不满足条件时，我们知道
一定是满足条件的，此时计数答案同时贪心右推左边界知道区间和再次小于
即可。由于
，区间和一定是单调的，这个解法成立。
用双端队列或者双指针搞一下就可以了，由于区间长度只有 ，答案在 `long long` 范围内，直接存就行，中间结果的范围也是 `long long` 范围内。复杂度
。
H. Machine Learning
从二维前缀和考虑，考虑 是矩形
的和，那么答案询问的矩形
等于
。然后考虑怎么处理
，观察到给定的矩阵是沿对角线对称的，不失一般性，假设
，则这个矩形可以划分成两块：
- 正方形部分：这一部分可以观察到每种数的长度是
，然后我们求到第
项，等差数列求一下和，特殊处理一下延展出来的部分就行。
- 小矩形部分：这一部分每一行都是一个确定的数，而且长度都是
各自有几行即可。
Mid-Hard
E. MIRЯOЯ
对字符串正反做一次 Hash，然后单点更新区间求和就行，树状数组就够。时间上来说没有卡线段树。
做一下 URAL 1989 就懂了。
J. Bubble Sort
答案：。简单证明一下。
首先明确一个点：对于一个全排列 ，使用冒泡排序这个序列的交换次数是这个序列的逆序数。
那么假如要求平均次数，我们需要的就是所有全排列的逆序数和除以全排列总数。所有全排列总数是 。
接下来的问题是关键。我们如何求所有序列的逆序对数呢？让我们来考虑以下某个排列和它的翻转：
考虑任意一对数，容易观察得出，要么这对数在第一个序列是逆序，要么这对数在第二个序列是逆序。所以我们把每一个排列和他的翻转绑定起来求和，对逆序数的贡献值就是。
由于一个排列和它的翻转是一一对应的，那么在所有的全排列中，总共有 个排列对答案有贡献。
所以答案就是简单的：
Q.E.D.
（OEIS 搜 Bubble sort 认真读一下第一条就能 A 了）
Hard
F. Hypercube Random Number Generator
观察题意，这个超立方体总计有 个点，那么等概率任取一点的概率就是
，其实就等价于我们在每一维上等概率任取一个点，然后再组合起来而已（
）。所以题目模型就变成了我们在每一维上等概率任取一个点，然后把取到的点乘起来模
后再加一的期望。我们现在来逐轮考虑。
回忆期望的计算方法：所有可能的结果乘以概率的和。由于我们是等概率的取，那么我们可以求出在 次后所有的结果的数量，求和之后除以
就可以了。
那么接下来的问题就是怎么求所有结果的数量。假设我们知道 轮每一种数字的个数，然后我们去考虑每种数再取一轮能得到多少个每种数字。比如说，一个
可以在新的一轮产生三个
，那么我们第
轮如果有
个
，下一轮就能产生出
个
。这个计算过程应该很眼熟——矩阵乘法而已。
所以我们先枚举出每种数产生其他种数字的结果得到一个矩阵，准备一个全为 的向量不断的右乘这个矩阵，
次之后我们就得到了每一个数的数量。然后，这题就做完了。
枚举可能的结果得到矩阵，然后
的时间做矩阵快速幂，最后
统计一下答案就行。总复杂度
。
推前 50 项然后直接 BM 一下就过去了啊。
I. Matchsticks
大模拟。
题目本身一点都不复杂，做法就是
- 读出表达式
- 枚举每个符号的所有变化
- 求值
这个题注意的就是细节问题：
第一个细节问题是不要枚举漏了每一个符号加减一根火柴棍能变成的符号集合。
第二个细节问题就是枚举，除了等号不能变其他都能变。
第三个细节是求值，因为 的优先级比较高，这里要认真处理，比如写一个 RPN 求值。
第四个细节问题就是右侧的数字，也许会有前导负号变成正号的过程。
投递泰豪科技等公司10个岗位 >
