刷题总结

_QWQ__QWQ_ · 2024-11-27 21:41:18 · 个人记录

同步于Luogu bolg然后发现洛谷渲染的还没cnbolgs好

题单

T1 AT_arc174_a A Multiply

题意简化

有一个长度为n的序列a，你可以选择一个区间，让区间离的数全部\times c，求a序列的最大值。

• 1\ \le\ N\ \le\ 3\ \times\ 10^5
• -10^6 \ \le\ C\ \le\ 10^6
• -10^6 \ \le\ A_i\ \le\ 10^6

  分析

  观察数据范围，可发现c有正负之分，则想要让序列总长度最大，分类讨论：

• c<0$，则需要使用最小的区间$\times c
• c>0$，则用最大的区间$\times c
• c=0$，则使用最小的区间$\times c

所以要求两个东西：区间最大最小值 发现1\le n\le 10^5，考虑DP

1. 定义状态：dp_i \ or \ pd_i：以i结尾的区间最大/最小值
2. 答案：\max{dp_i}\ or \ \min{pd_i}
3. 状态转移方程：由于区间是连续的，所以dp_i的状态只能由dp_{i-1}得到 对于每个dp_i： 一.由dp_{i-1}+a_i，得到新的子段和 二.自己单独成一个子段 得出dp_i=\max(dp_{i-1}+a_i,a_i)
4. 边界条件：dp设极小值，pd设极大值

DP值求完了，接下来计算总序列和：

• (c>0)

  一.序列不变，因为可能序列全是负数，乘后还变小了 二.减去区间最大值，再加上区间最大值\times c

• (c\le 0)

  一.序列不变，因为可能序列全是正数，乘后还变小了 二.减去区间最小值，再加上区间最小值\times c

Code

link

T2 AT_dwango2017qual_b ニコニコレベル

题意简化

给你一个字符串，里面可能有数字或"?"，你可以将问号替换成数字，求替换后这个字符串里面由"25"重复得到的字符串的最长长度 字符串长度小于等于1e5

分析

发现数据需使用\Theta(n) or \Theta(n\log_n)做法通过，考虑DP

1. 状态: dp1_i：第i个位置是2时的答案，dp2_i：第i个位置是5时的答案
2. 答案：因为答案必须以5结尾，所以得出答案为\max{dp2_i}
3. 方程：对于每个"2"或"?"： 可以由上一个字符为5时的答案更新，并且不用考虑前一个数，可以直接单独成段 对于每个"5"或"?"： 可以由上一个字符为2时的答案更新，但是要考虑前一个数，如果前一个数不是2，即dp_{i-1}=0，则不能更新答案
4. 边界：dp_i=0

   Code

   link

T3 AT_soundhound2018_summer_final_b Neutralize

题意简化

有一个序列a，你可以进行任意次将k个连续的数变为0，求最后数组的总和最大值

分析

由于有k的限制条件，显然不能