A. Nico~ Nico~ Ni~
题目描述
给定一个字符串，问字符串中 NicoNicoNi 这个子串有多少个。
数据范围：。
题解
按题意模拟即可，按顺序每次取出长度为 的子串，判断它是否为 NicoNicoNi 即可。
有没有写 KMP，AC 自动机，后缀数组，后缀自动机的童鞋啊。
时间复杂度：，空间复杂度：。
参考程序：C++，Java。
我曾经出过类似的题……
Problem Setter: Sugarii
B. Help Fat_Dog Kill Bugs
题目描述
有 个数 。对于每个数，你可以给 加 ，或者给 减 。求最终 的最大值。
数据范围：。
题解
结论是，把这 个数全部加给 ，最后 是最大的。
考虑我们给 加了 ，给 减了 。那么 且 。最后答案变为 ，化简整理为 。
考虑到 为一个定值，不妨设 。那么 。由于要使得 这个值最大， 为定值，因此目标要使得 最大。代入 ，得到 ，我们即要使这个式子的值最大。首先观察得这个是关于 的一次函数，由于 ，那么斜率一定是正数，那么最大值点就出现在定义域的最右端。即 时这个式子的值最大。至此我们证明了前面贪心的策略是正确的。
需要注意数据范围和数据类型的使用。
时间复杂度：，空间复杂度：。
参考程序：C++，Java。
Problem Setter: Kaiser
C. Expected Score
题目描述
有 个数 。每次可以均匀随机选一个除了最后一个位置之外的位置，把这个位置的值改为这个位置的值与后一个位置的值之差，然后把后一个位置的数删去。这个过程一直进行，直到整个数列就剩一个数。求剩下的这个数的期望大小。
数据范围：。
题解
结论是，。
考虑这个过程进行到倒数第二步，即序列只剩下两个数的时候。可以发现，除了前两个数，后面的数对于每种情况正负出现次数相等。也就是说，对于 ，对最后期望的贡献 ，所以在计算期望的时候，后面的数没有贡献。第一个数的贡献恒正，第二个数由于在最后一步被减掉，所以贡献恒负。因此有之前的结论。
下面是出题人给出的关于 的元素贡献为 的证明：
由于取数对是随机的，那么第一轮取数取到 与取到 的概率是相等的。
那么经过操作后，组成的序列为 与 的概率是相等的。我们记前者为 (1) 式，后者为 (2) 式。
在第二次操作中，在 (1) 式中选择 与 在 (2) 式中选择 的概率是相等的，我们记为 。这两种选择对于答案的贡献为 ，这也是区间 的贡献。
类似区间 DP 的思想，我们可以合并这些小区间得到整个区间的情况。
这里不需要把 个数全部输入进来。只需要读入前两个数即可。
时间复杂度：，空间复杂度：。
参考程序：C++，Java。
Problem Setter: fatdog_jo
D. Linear Algebra
题目描述
给了 个矩阵，他们重新排列之后一定能乘起来。问重新排列后乘起来，这个矩阵的最大可能大小。
数据范围：。
题解
如果我们把重新排列之后的矩阵大小写成一排，大概类似于下面的形式：
可以看出，这是一个从 出发到 的一条欧拉通路。欧拉通路是指从起点出发，经过边均不同到达终点的一条简单路径，也就是「一笔画问题」。
对于求解这样的问题，如果学过图论的话就可以很轻松地用一些判定定理进行判断。性质是：统计每个 的出现次数，则按题目保证，一定没有或只有两个次数为奇数。如果没有次数为奇数，则输出出现次数不为 对应的大小的平方，否则输出两个出现次数为奇数的大小的乘积。
证明比较简单，观察前面的序列，除了 和 ，其余数都出现了偶数次，如果 ，那么就对应上述情况的第一种，否则对应第二种。
时间复杂度：，空间复杂度：。
参考程序：C++，Java。
Problem Setter: Macaron_lin
E. Sugarii and String
题目描述
给了一个长度为 的 字符串，按照接下来的规则生成一个无限长度的字符串：
- 将自己复制一遍接到原字符串后面；
- 将复制过去的部分 翻转，即 变成 ， 变成 。
询问这个无限字符串的第 位是什么。
数据范围：。
题解
首先我们考虑 位置对应的原来的字符串的字符位置。虽然字符串以倍增方式增加，但是我们还是可以把无限字符串按长度为 分块，每块要么与原字符串相同，要么 是反转的。因此，可以计算出第 个字符对应原字符串的第 个字符。
我们考虑这一块是和原字符串相同的还是翻转的。第 个字符所在块为 。记 为第 个字符所在块，并且在第 次新生成的块中，那么 ，我们将其减去 ，就知道了它是由之前的哪个块经 翻转得到的。每次我们找到小于等于 的最后一个二的幂次，然后每次让 减去这个值，并记录一共翻转了多少次。直到 时停止。
观察这个过程，其实我们减去的这个二的幂次是 的二进制中所有等于 的位。实际上，如果所在块编号从 开始，块编号的二进制表示中 为偶数个的话，这个块就与原字符串相同，否则 互换。
因此，记块编号的二进制表示中 为奇数个时 ，否则 ，答案就是字符串中第 个字符与 的异或。
时间复杂度： 或 ，空间复杂度：。
参考程序：C++，Java。
Problem Setter: cjj490168650
至此，电子科技大学第十一届 ACM 趣味程序设计竞赛就结束了。完结撒花~