科大讯飞笔试-算法(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%