科大讯飞笔试-算法（8.30）

1. 大小为 n 的数组 a，下标是 [1, n]，这n个数初始值都为0， 有 p 次操作，每次操作会取反 a[p] ，也就是0变1，1变0。给定 x 和 y（ x 和 y 是最开始的输入，操作过程中是不变的），问每次操作后区间 [1, x] 和 [y, n] 中分别有多少个0？【10分】

模拟就行，注意y <= x的情况

2. 有1-n n个数，每次移动选择[l, r]子区间移动到数组末尾，有q次移动，问最终所有的数字 i (1 <=i <= n) 在几个不同的索引位置上出现过？【15分】

n 和 q 范围只有3e3，O(n*n)模拟就行

3. 给定一个01字符串，定义得分是所有连续1子串的长度的平方和，有k次将0修改为1的机会，问修改后最大得分？【25分】

第三题没想出来最优的情况TAT，写了两种

第一种将0子串按照长度排序之后修改k个0为1，再计算得分，过了15%。这样肯定是不对，因为没考虑合并后1子串的长度。

第二种就无脑把前k个0改为1，过了23%