8月20日 至 8月30日的CSP-JS 2022复赛全真模拟赛圆满结束，下面分别公布3个组别的题目解析，本帖发布CSP-S组复赛模拟解析，语言基础组和CSP-J组复赛模拟解析可查看查看本贴的头条和次条；需要回顾题目的选手可以在电脑上打开www.xiaohoucode.com，从首页头图或左侧边栏的编程活动进入赛事页面；需要看模拟赛成绩的选手可以在进入赛事页面登录参赛账号后，点击左上角的“参赛进展”即可进入下载”活动证书“；8月31日18:00后会再次放出模拟赛供大家调试订正练习所用，不过不再限时评测。
输入N，求出所有长度为N且不含前导0的非负整数中，恰好偶数个1（包括0个）的数字个数。
普及+/提高
这道题的最高有10000，如果要在规定时限内完成，我们需要考虑递推法。
当时，一共有9个数字符合要求，1个数字不符合要求；当时，有两种数字符合要求，一种是在本来有偶数个1的数字后面加上0或者2~9，另一种是在本来是奇数个1的数字后面加上1。
设为长度为的数字中有奇数个1的数字个数，为长度为的数字中有偶数个1的数字个数，很容易得到如下递推方程：
由于这道题没有取模，所有最终答案可能有10000位，必须使用高精度。但是总的时间复杂度是高精度复杂度，为了不超时，我们需要进行高精度压位计算。
在坐标原点附近建一系列大楼，每栋大楼最多建K层，多建时第i层需要Ci的成本，另外每栋大楼还有交通成本，成本为T*d，T是系数，d是该大楼到空间站的距离。大楼每层一个家庭，一共需要容纳N个家庭，求最少花费的总成本。
普及+/提高
首先很容易发现，越远的大楼交通成本越高，如果一个家庭想住第i层，那么应该尽可能住得更近。因此我们建造大楼的时候，越近的大楼建的楼层会越多。
假设使用贪心法的话，可以使用优先队列，存储当前每栋大楼新建一层的成本，然后每次选择成本最低的建造，一共执行N次，就能求出最少花费的总成本了，此时可以获得60分。
由于最大数据N为10的12次方，因此我们需要其他方法。根据贪心思路很容易发现随着N变大，第N个家庭的成本也会越大，而第N个家庭的成本越小，总成本就会越小，我们可以而二分第N个家庭的成本mid，然后计算是否能得到至少N个位置的成本<=mid，直到确定第N个家庭的最小成本。（对于成本mid，我们可以枚举大楼的距离d，然后二分求出距离为d时这栋大楼能达到的最高高度，然后拿最高高度×距离为d的大楼数）
得到成本上限后，可以枚举距离，然后计算出最终的最小成本。
在一个矩形棋盘中有多个格子放置了宝藏，从(1,1)出发，希望能够拿到所有宝藏， 然后在(Ex,Ey)结束，每次移动一格会消耗掉一定量的体力，捡到宝藏时能恢复一定体力，体力要保持不低于0。求拿到所有宝藏后离开迷宫剩下的最多体力值。
普及+/提高
考虑到数据中N≤10，宝藏的数量是非常少的。我们可以枚举宝藏的拾取顺序，然后判断按照顺序拾取后，是否能宝藏体力不低于0，然后求出对应的答案即可。
如果已经确定了拾取宝藏的顺序，那么接下来的重点就是最快时间求出在宝藏之间转移的代价。由于整个棋盘的大小有限，可以通过预处理，以每个宝藏作为起点，可以求出所有点到这个宝藏的最短距离，然后把任意两个宝藏之间的最短距离存储下来。
使用DFS枚举宝藏之间的拾取顺序，同时维护体力的变化，在所有结果之中存最小值，就能得到答案了。
给定N个字符串，需要构造出一个回文字符串，这N个字符串都是它的子串，并且求回文字符串的最小长度。
提高+/省选
由于最终我们会求出一个回文串，因此每个字符串的正序和倒序都会出现在最终的答案串中，我们可以把每个串t的倒序形式t'求出来，方便我们后续推导。
由于N≤15，是一个非常小的数字，那么我们可以考虑枚举字符串的合并顺序，比如aba、aabb、abba这三个串，如果按照顺序合并，aba和aabb会合并成bbaabaabb，然后再和abba合并成abbaabaabba。如果按照aabb、abba、aba的顺序，先合并成aabbaa，再合并成abaabbaaba。这样子可以发现，每次合并字符串t就是在当前字符串前面增加t，后面增加t'。（也可以反过来，前面增加t'，后面增加t）并且去除重复部分（比如abba和aba重复了1个字母）。
首先我们把能被其他字符串完全覆盖的串删掉，例如对于bba和aabb，合并aabb到回文串里面时一定会产生bba，所以bba不应该计算。
去掉被覆盖的串后，求出任意两个字符串直接拼接的重复部分。（注意正反拼接，比如aabbbc和cbba在正向时只重复1个字符，但是反向可以重复3个字母）
虽然合并顺序很重要，但是直接枚举合并顺序一定会超时，而答案串每次合并时增加的长度只与边界和下一个串有关系，之前的合并顺序不重要，因此我们可以维护已经合并的集合以及最后一个合并进来的串的编号，就能递推下一次合并的结果了，得到一个状态压缩DP的模型：
设f[S][j][0/1]表示当前已经合并进来的串的集合是S，集合中最后一个合并进来的串是j，0表示j是正向合并（j是S后缀），1表示j是反向合并（j是S前缀），在这个状态下合并生成的最小回文串长度。
初值：f[1<<i][i][0] 为i正向形成回文串的最短长度
f[1<<i][i][1] 为i反向形成回文串的最短长度
递推式：设i是下一个合并的串，
f[S|1<<i][i][0] = min( f[S|1<<i][i][0], f[S][j][0/1] +
正序i串合并对应顺序的j串的新增长度 )
f[S|1<<i][i][1] = min( f[S|1<<i][i][1], f[S][j][0/1] +
逆序i串合并对应顺序的j串的新增长度 )
最终答案：合并所有字符串的方案最小值。
