前言

首先感谢各位dalao前来参赛，感谢各位领队帮忙判题发球。

比赛之前我们做了不少准备，为的是能做好命题和评测以及招待外宾的工作，不知道各位是否还觉得满意呢。

很高兴这次比赛没有出什么大问题，尽管有熟悉的ESA，熟悉的烂鼠标，以及热身最后崩了一小下。同时赛后我们发现打印的题面并不是最新版本的，但是数据并没有问题，这可能导致一些选手白白花时间多考虑了一些细节上的问题，深表歉意。

我们强行续了一把OJ，尽管它还不是很稳定，目前只放了这次迎新杯的题目，欢迎选手补题，没来现场的也可以在OJ上小玩一下。

题面链接：戳这里看热身赛题面
题面链接：戳这里看正式赛题面
比赛链接：点击进入,需要先注册
终榜链接：戳这里膜大佬

最后，希望各大院校今后都能加强交流与友好往来，祝陕西省的ACM越来越好。

热身赛

难度分布

热身赛主要让选手熟悉环境与PC^2的使用方法，一共设置了四道题目。其中第一道为测试提交的题，另外三道大概是随便暴力题或比较近期的一些原题简化。由于是热身赛所以难度上也没有去把控，导致有萌新绝望卡题，也有dalao光速AK。

A.欢迎来到彩虹岛 签到

题意：输出“Welcome to CHD”

解析：本题为测试提交题，Hint中写了AC代码。

吐槽：judge真的收到了好多奇怪的东西……

B.粉刷篱笆 模拟 暴力

题意：n段篱笆，初始为原木色，m次操作，$[l{i},r{i}],color_{i}$，表示把区间的篱笆染成该颜色，问篱笆最后有几种颜色。

解析：模拟染色过程，用一个数组维护篱笆的颜色，每次染色操作暴力扫染色区间修改颜色，最后扫一遍统计多少种不同颜色，复杂度O(nm)。

C.拯救小伙伴 博弈

题意：给一个二进制串，每次操作选择一个“1”，将其自身及其左边所有数字进行0/1反转，无法操作者输，问谁胜。

解析：注意到每次操作最左边的数字必然会被翻转，而结束时最左边的数字必然是0，故若初始时最左边的数字是0，则到游戏结束时必然翻了偶数次，即后手胜，反之则先手胜。

吐槽：比较近的原题简化……

D.魔法少女的数学题 数学

题意：给一个正整数k，问存在多少二元组(p, q)使得$p \cdot q = k$且gcd（p， q） = 1。
解析：对于k的每个素因子$Prime{i}$，它不能同时是p,q的因子，否则不满足pq互质，故只有$Prime{i}$是p的因子或者$Prime_{i}$是q的因子这2种情况，如果k有n个不同的素因子，那么答案就是$2^n$。统计不同素因子个数暴力O($\sqrt k$)分解即可。

吐槽：依然比较近的原题简化……

正式赛

难度分布

由于去年题目难度分布不合适，给一些学校的萌新造成了心理阴影，今年花了很长时间来确定题目难度分布，同时想把题面讲的更清楚更有趣些。从结果来看除了G题描述上坑到了不少人，其他题目与我们的期望差不多。

考虑到来参加比赛的选手水平差距较大，有刚上手的萌新，也有在Regional拿了许多牌的dalao，我们今年增加题目数量至12题，让萌新能有题做，dalao也不会觉得很无趣。

其中A，B，C三题的定位是简单题，希望大部分人都能出，考虑到题数较多，萌新不太会找水题，于是特意放在了最前面，但似乎造成了题目是难度递增的假象。

我们认为在这样的个人赛中，CF风的题目是比较合适的，对于新人来说难度与码量不会太大，需要稍微想一些trick，于是便有了DE。结果确实卡了不少人，尤其是E题甚至卡到了dalao，裁判组甚至一度陷入了怀疑数据出错的状态。

为了丰富内容，我们又增加了一个中学知识足以解决的几何F，一个暴力的回文串H，以及一个容易猜结论的构造L。我们认为这几个题目都是不需要前置知识，只要肯想肯算，有一定码力都能出。最后F的出题量比我们预期少很多，而猜出L的人很多。

由于我们之前给自己学校的新人讲过一些算法，于是我们决定出少量套路题给努力做练习的同学，于是有了I题二分与J题BFS，事实证明我们的小朋友果然没有做题呢。: )

最后G题是一个数学递推，K题是一个无趣的LCA，纯粹是怕dalao太快AK闲着无聊，后来发现前面的trick耽误了选手太多时间，而且4小时12题确实是太多了……

以上是我们出题时的想法，而最后的Board也不算难看，对于一些不合理的地方，我们今后会吸取经验并改正。

A. 捍卫彩虹岛 签到

题意：给8个整数$Lv{i}$，输出$\left \lfloor \frac{\sum{i = 1}^{8}Lv_{i}}{8} \right \rfloor$。

解析：int直接就向下取整了。

B.恐高的单身老柴犬 暴力

题意：给n级台阶的绝对高度$h_{i}$（递增），以及一个容许高度x，一个人可以走到小于等于x的最高位置，然后用道具飞到楼梯顶端，问飞行最小高度。

解析：扫到小于等于x的最大高度，与最后一级台阶高度做差即可。

吐槽：数据中没有x大于最后一级台阶的情况……有人以为楼梯是相对高差……

C.彩虹岛电车 暴力

题意：给长度为n的数列a[]，问(a[l] + a[r])%5=0的二元组(l, r)对数，其中l$\leq$r。

解析：O（$n^2$）扫一遍即可。

D.卡片游戏 贪心

题意：n张大写字母卡片选k张，使得$\sum{i = 1}^{k} f{i}$最大，其中$f_{i}$为k张卡中与第i张卡片字母相同的卡片数目。

解析：统计每个字母的卡片数目，贪心从卡片数目最多的字母开始取k张即可。

吐槽：萌新多是卡排序，不会sort、qsort，然而字母数少可以暴力排。

E.无尽拼图 坑人

题意：给一个部分缺失的整数矩阵，问是否存在一种填数方案使得该矩阵是矩阵$a_{ij} = i + j - 1（i， j \geq 1）$的子矩阵。

解析：若全部为0则必然可以；否则找到第一个非零位置，即可填完所有数，并检查是否是$a_{ij} = i + j - 1（i， j \geq 1）$的子矩阵。坑点在于填完数的矩阵中是不能有0与负数的。

吐槽：毒瘤出题人：“我觉得这道题是出的最好的。”

F.通往彩虹岛的石头门 几何

题意：两个宽W高H的矩形重叠放置，其中一个绕形心顺时针旋转$\alpha$角，问旋转后两个矩形的重叠面积。

解析：为了避免过多的分类，我们可以先去除一些情况。

  • 对于H>W的情况，我们可以将两个矩形旋转90度，即交换W和H，不影响旋转后的相交面积，因此之后仅讨论H$\leq$W的情况。
  • 对于$\alpha > 90^{\circ}$的情况，考虑轴对称，可以将$\alpha$转变为$180^{\circ} - \alpha$，故之后只需要考虑$\alpha \leq 90^{\circ}$的情况。

为了方便叙述，我们令$\beta = arctan(\frac{H}{W})$，即$\beta$为矩形对角线与长边的夹角。

在考虑完上述两点之后，仍然有两种情况需要讨论：

  • $\alpha > 2 \beta$，这种情况较为容易，此时相交部分为一平行四边形，面积即为底乘高，结果即为$\frac{H^{2}}{\sin\alpha}$。
  • $\alpha \leq 2\beta$，即题目附图的情况，按下图设变量解二元一次方程组：

解完方程用矩形减去三角形面积即可。

Door

G.兔兔的纠纷 数学 题意杀

题意：记斐波那契数列为f[],其中f[0]=f1=1,对于i>1有f[i]=f[i-1]+f[i-2]。已知在第k年，年龄为i的兔子数目为2f[k-i]，若两只兔子年龄和为k，会发生一次纠纷。T次询问，第k年兔子间共发生多少次纠纷（$T, k \leq 200000$）。

解析：记$g[k] = \sum_{i = 0}^{k} f[i] \cdot f[k-i]$，则答案即为：

问题转化为求$g[]$数组，

即$g[k] = g[k-1] + g[k-2] + f[k]$，先预处理递推$f[]$再递推$g[]$即可，时间复杂度$O(T+k)$。

吐槽：全没看到只生两年……斐波那契数列不叫兔子数列吗？

H.七彩原石 回文串 暴力

题意：求压缩串的最长回文子串。

解析：类似于求普通串最长回文子串的枚举回文中心并向左右扩展的方法，在扩展的时候分三种情况：

  • 颜色相同，且长度相同，继续向两边扩展。
  • 颜色相同，但长度不同，两端取min切断，并停止扩展。
  • 颜色不相同，直接停止扩展。

单组时间复杂度$O(n^2)$。

吐槽：命题的时候想了要不要卡$O(n^3)$的做法，但是发现比$O(n^2)$还难写，大家也可以想想马拉车什么的怎么写。

I.机器人小队 二分

题意：将一个长度为n的序列划分成连续且非空的m段，设第$i$段的和为$S_i$，求使得max{$S_i$}最小的划分方案，多种情况时要求越靠前的段数字尽量少。

解析：先求解最小的max{$S_i$}，可以假设max{$S_i$}$\leq x$，来判断这种情况是否成立：对于一个x，我们可以求出在每段和不超过x的情况下所需要的最少划分数k，如果k＞m，肯定不成立，反之成立。显然x与k满足单调性，故可以用二分求解最小的x。

之后考虑方案输出，只需从后往前依次给每一段放总和小于等于max{$S_i$}的数即可，但需要注意的是每一段非空这一条件。

吐槽：输出略鬼畜，场上似乎出现了PE判WA的情况，致歉。

J.藏宝图 BFS RoyYuan

题意：给一个有障碍的$m \times n$迷宫，起点S，终点T，地图上障碍每间隔k秒会打开一次，问S能否到达T以及所需最短时间。

解析：普通的迷宫题直接用二维状态(x, y)表示位置来BFS即可。本题不同的是，障碍每隔k秒会开一次，故需多标记一维时间状态。对于同一个点(x,y)来说，t秒和t+k秒表示的状态是相同的，所以新加的维度只需要k的大小就足够，转移的时候按时间的不同讨论能否经过障碍即可。当然也可以从分层图角度来理解。

吐槽：不能因为RoyYuan超可爱就欺负他呀。

K.书人 LCA

题意：一个栈支持三种操作：

  • 1 push（x）
  • 2 pop（）
  • 3 退回第t次操作结束后的版本

对于每个操作3回答本次操作最少可以看成是由多少次操作1/2组成的。

解析：栈要可持久，建树即可：维护一个当前位置指针pos，push把pos移向儿子（没有这个儿子则需加叶子），pop把pos移向父亲。先做完所有操作把树建完，每个操作3询问的即为树上距离，故离线LCA即可。

吐槽：因为是先想好做法再套题，所以可能会被什么简单做法艹掉，欢迎dalao讨论。

L.大魔王的魔咒 构造 猜结论

题意：给L个左括号与R个右括号，构造一个串使得合法括号子串最多，输出个数。

解析：显然括号要成对，故取x = min（L,R）对括号即可，多余的没有用处。最优的构造方案为（）（）（）……即x对括号并排放，答案即为$\frac{x \cdot (x + 1)}{2}$。

证明：
1.合法括号子串的上界是$\frac{x \cdot (x + 1)}{2}$
合法括号子串的长度必然是偶数，对于长度为2x的串，将其长度为偶数的子串一共有$x^2$个，可以将其分为三类：

  • 左端点l为奇数，且右端点为2x，有$x$个。
  • 左端点l为奇数，且右端点不为2x，有$\frac{x \cdot (x-1)}{2}$个。
  • 左端点l为偶数，有$\frac{x \cdot (x-1)}{2}$个。
    注意到对于一个子串[l, r]如果它是合法括号序列，则其最左端必然是“（”，最右端必然是“）”，故[l+1, r+1]必然不是合法括号序列。在上述的3类子串中，第2类与第3类可以建立一个[l, r] $\leftrightarrow $[l+1, r+1]的双射关系。也即是说，只要第2类中有一个子串是合法括号序列，对应的第3类中有一个子串必然不是合法括号序列，故这两类中的合法括号序列之和不会超过$\frac{x \cdot (x-1)}{2}$，因此所有合法括号序列总和不会超过$\frac{x \cdot (x+1)}{2}$
    2.存在一种构造使得合法括号子串数目为$\frac{x \cdot (x+1)}{2}$。

显然并排放（）（）（）（）……即是。

证毕。

吐槽：欢迎其他证明，可以思考对应的子序列的问题。