ABC261 总结

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16513099.html

比赛地址

比赛情况

排名：885
AC：5 / 8

题目分析

A

签到题

B

W记为1，L记为3，D记为2，判断 $(i,j)$ 与 $(j,i)$ 的和是否为4

C

map+string即可

D

设 $dp_{i,j}$ 代表前 $i$ 次末尾有连续 $j$ 次1的最大价值，记 $z_i$ 代表连续 $i$ 次的奖励（没有则为0）

$$\Large dp_{i,0}=\max_{1\leq j\leq i-1} dp_{i-1, j}\\ \Large dp_{i,j}=dp_{i-1,j-1}+x_i+y_j\;(1\leq j\leq i)$$

E

由于只有位运算操作，所以每一位都可以单独考虑

然后维护每一位即可，维护每一位一开始是0和1的最终值

时间复杂度 $O(n\log n)$

赛后总结

很可惜F没做出来

2min过A，B有个错误wa了一次，7min过

C就是水，9min过，D看完就想到dp，16min时过

E一开始没思路，后来上了个厕所想到就只影响一位，然后打了打31min就过了

F想了好久，觉得如果打个线段树+set二分应该能过，但set二分我不熟，不会打，于是弃了