CSP-S T1~T3 题解
CSP-S T1~T3 题解
T1
“他配得上自己的评级”
一道不太难想的
排序题？
思路：
我们先要考虑要减少数目要让每一只怪都攻击哪一只怪。由题易推得，我们只有每次攻击数值比当前的这只小的才最优。所以每次让每只怪攻击当前还存活的最小数值的怪一定是最优的。
实现：
sort排序后每次攻击队首（最小）的怪。
TIPS：
千万不要写72行得40分。
T2
文化课还是很重要的！！！
思路：
现在再看这题跟纯的中等大小模拟也没啥大区别了。
二分+贪心=黄+黄=绿
但由于这个题太难调了所以建议升蓝
我们先看看问题是啥：
1：当所有测速仪开启时，将会有多少辆车被判为超速？
2：关闭尽可能多的测速仪，使得原本被判为超速的车仍然被判为超速。所以关多少个？
我们可以分一下几个点理顺一下思路：
1：由于是匀加速直线运动，所以超速的区间一定是连续的，而且是可以被计算出来的。（但是要注意开闭！）
2：第一问：计算每辆车的超速区间并转换成测速仪的分布区间
3：第二问：一个比较经典的贪心（不大板子的板子，P1520），给定 n 个区间，m 个给定的点，求使用最少点使得所有区间中都包含点。这是一类经典的序列上贪心问题。首先把区间按右端点排序，然后对每个区间讨论：如果已经包含了之前选过的点（直接用上一个选的点判断）就跳过，否则选一个最靠近右端点的点。
实现：
1：分类讨论加速度情况（正负零）后二分处理
2：按照右端点排序（从小到大），然后在尽可能少的右端点处开测速仪。
TIPS：
1：需要加快读。
2：注意区间开闭！
3：精度！精度！精度题目都有暗示了，别开double！！！
4：别复制粘贴！改死你！
T3
缩点DP？
思路&实现：
设 dp[i][0/1] 表示当前填到第 i 个的情况。
1：放弃最后一个点，判断倒数第二个点是否已经确定与最后一个点不同
状态转移方程
dp[i][0]=max(dp[i][0],dp[i-1][0]);
dp[i][1]=max(dp[i][1],dp[i-1][0]);2：然后特判处理特殊情况，i 在 i-1 没被确定前可以与 i-1 相同，被确定时可以与 i-2 相同且转移到 i-1 。
状态转移方程
if(a[i]==a[i-1]) dp[i][0]=max(dp[i][0],dp[i-1][0]+a[i]);
if(a[i]==a[i-2]) dp[i][1]=max(dp[i][1],dp[i-1][1]+a[i]);3：最后可以枚举上一个颜色相同的数，记录出所有满足<= i 且 a[j]=a[j+1] 的j的a[j]之和
状态转移方程
dp[i][1]=max(dp[i][1],maxi[a[i]]+c[i-2]+a[i]);
if(i>2) maxi[a[i-2]]=max(maxi[a[i-2]],dp[i-1][1]-c[i-2]);
dp[i][0]=max(dp[i][0],maxi[a[i]]+c[i-2]+a[i]);TIPS：
实际上挺难想的，我们需要熟练地掌握暴力的20分。
T4
return 0;