长安大学第二届ACM程序设计竞赛校赛简要题解

写在前面

1.出现了密码条打错，网络故障，全程开外网，现场缺乏管理，配置不好用等等问题，沿袭了一直以来校赛出状况的传统，真心感谢各位能够谅解。
2.特别感谢西邮袁子涵和张浩然，帮我们解决了$PC^2$的种种问题，并帮忙渡过了正赛开场时最艰难的时候。

A.Count Circles

简单统计一下即可，一些写法需要特判$0$的情况。

B.Boys and Girls

注意到同性之间的交换位置没有意义，故初始序列和最终序列相比，同性之间的相对位置是不发生变化的。即是说如果初始序列是$B{1}…B{2}…B{3}……B{n}$，省略号处表示有若干个$G$，那么最终序列是$B{1}GB{2}GB{3}G…B{n}G$或者$GB{1}GB{2}GB{3}…GB{n}$,那么最少交换次数就是每个$B$从初始位置移动到最终位置需要的步数之和，分别计算$BGBG…$和$GBGB…$的答案取小者即可。

C.Roses

枚举一个圆，对没有被此圆覆盖的点求最小圆覆盖，复杂度为$O（n^4）$。

D.Arrays

离线询问，将点按$A$，询问按$x$排序后，问题变成了带修改的求$[L， R]$区间内$B$大于等于$y$的数目，这个问题可以用树套树解决。

E.Colorful Ribbon

考虑$dp[i]$表示前$i$个字符的合法方案数，枚举上一个断点，那么$dp[i] = \sum _{k = p} ^ {i - 1} dp[k]$, 其中$p$代表上一个断点能取的位置中最靠前的一个，容易发现$p$是单调递增的，因此只要维护$p$和$dp$的前缀和以及每个字母上一次出现的位置就能$O（n）$解决。

F.XOR-mean

考虑分块，块长为$C$，对于当前块，统计：

1.$i$，$j$，$k$均属于当前块

2.$i$，$j$属于当前块，$k$属于后一块

3.$i$属于前一块，$j$，$k$属于当前块

4.$i$属于前一块，$j$属于当前块，$k$属于后一块

这样是不重不漏的，前三种情况可以暴力，第四种情况 $ fwt $，总复杂度.

G.K-partite Graph

检查补图是否是$k$个完全图即可。

H.Boxes

比较的耿直费用流，边用$（flow， cost）$表示：

源点到每个格子$（a， 0）$，

每个格子到汇点$（h， 0）$，

每个格子到相邻格子$（INF， 1）$。

I.Annual Party

单次询问可以维护子树中关键点数目和关键点到根距离之和两次树$dp$解决，由于$\sum k \leq 100000$，建虚树处理每次询问。

J.Repeated String

容易观察到每一位的字母对答案的影响是独立的，只要统计这一位每个字母出现了几次，再枚举这一位填什么字母即可求得最小值，复杂度$O（26nm）$。

K.Brackets

按照题中所给的条件，第$x$对括号内可以包含至少$y - x$对括号，至多$n - x$对括号。假设要统计第$x$对括号内包含$k$对括号的方案数，我们可以假想把第$x$对括号与其内部包含的所有括号压缩成单对括号，那么令$f[i][j]$表示由$i$对括号组成，第$j$对括号紧贴（即第$j$对括号中间不含其他括号）的方案数，答案为$f[n-k][x] \cdot Catalan(k)$。

同样利用压缩的思想，考虑由所有合法括号序列减去不符合要求的情况，容易得到递推关系：

直接做预处理$f$的复杂度是$O(n^3)$，也可以用分治$fft$加速，单组询问$O(n)$。

难以发现但可以证明，事实上$f[i][j] = \sum _{k = 1} ^{j} Catalan(i-k) \cdot Catalan(k-1)$，可以$O(n^2)$预处理。

场上过的都是用$dp[i][j]$表示$i$个左括号和$j$个右括号的合法前缀数，把序列按$x$左侧，$x$与$y$之间，$y$右侧分成三段，每组询问$O(n^2)$枚举其中两段的右括号数目统计方案数。

L.QAQ Number

数据范围内所有的$QAQ$数总共只有$540$个，打表。