A. 数字游戏

Solution

显然每次要么翻转最高位的1，要么把最后位置取反改变1的奇偶性，枚举一下即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260210

B. 跳跳跳

Solution

区间dp, 令 $dp[i][j]dp[i][j]$ 表示 $[i,j][i,\; j]$ 经过一系列跳跃后的最优值，因为区间长度为 $kk$ 的话代表我们跳第 $kk$ 次，显然有

• $dp[i][j]=max(dp[i+1][j]+a[i]\ast (i-j+1),dp[i][j-1]+a[j]\ast (i-j+1))dp[i][j]\; =\; max(dp[i\; +\; 1][j]\; +\; a[i]\; *\; (i\; -\; j\; +\; 1),\; dp[i][j\; -\; 1]\; +\; a[j]\; *\; (i\; -\; j\; +\; 1))$

由于是环形，需要扩展成 $2n2n$ 的序列。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49331799

C. 数字匹配

Solution

考虑数据范围，显然可以先预处理出一个表记录串 $xx$ 中长度为 $kk$ 的所有子串（可以直接用数字存储），那么直接暴力枚举串 $yy$ 的长度为 $kk$ 子串是否在这个表中即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49277751

D. 优美字符串

Solution

不难看出要让任意相邻字符都不相等，只需要统计每个连续相同的子段，他们的长度为 $l_{i}l\_i$，贡献就为 $l_i-1l\_i\; -\; 1$，最后记得加上原来的长度。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260214

E. 分组

Solution

人数最多的小组的人尽可能少， 经典二分题目, 考虑二分答案，让每个组尽可能均匀分配即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260213

F. 过桥

Solution

考虑 $dpdp$，因为 $a_{i}a\_i$ 为负相当于折返跑没有意义，只考虑 $a_i>0a\_i\; >\; 0$ 的情况，暴力做转移即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260215

G. 空调遥控

Solution

直接树状数组统计所有符合情况的即可

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260211

H. 来点gcd

Solution

考虑到每个数字只需要判断1次，并且所有$gcdgcd$ 为 $kk$ 的候选只会在$kk$ 的倍数里出现，所以可以在调和级数的复杂度 $O(nlnn)O(nlnn)$下遍历所有倍数，对所有倍数取 $gcdgcd$ 判断能否达到目标值即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49277226

I. 体操队形

Solution

数据量很小，可以直接找全排列，验证即可。因为 $10!=362880010!\; =\; 3628800$，因此，$O(n!)O(n!)$ 完全可以接受。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49260216