A

题意:有$n\le 10^5$个物品,每个位置在$a_i$,选了就不能选$[a_i,a_i+x_i]$里面的东西,价值为$p_i$,问最大价值。

解:dp,从后往前,设$f[i]$表示选择$i$处的物品且已经处理过$[i+1,n]$中的物品时的最大价值,同时设$g[i]$表示$max{a_{k}}(i+1\le k\le n)$。则显然可以利用二分查找方便找到选择$i$物品时可选的最近物品$y$,则显然$f[i]=p[i]+g[y]$。答案为$g(1)$。时间复杂度$O(n\lg n)$。许多同学是正着做的,其实本质差不多,只是更新的顺序不一样。

C

题意:给定数据是01矩阵画着扑克四种花色,判断是哪种。果然不同地方说这四种花色的说法也不一样,wzh应该是江苏人,刚才更多是习惯说红桃黑桃方片草花;杭州习惯说红桃黑桃方块草花。但是网上可以发现草花基本上不会被当作正式用语,都用的是梅花,而红桃经常被称作红心。

解:wzh讲题时候给出的判断条件比如最宽的地方在哪里这种其实有点不精确。因为缩放时候差两三个像素其实也是不违反题意的。我的做法当中首先是判断横行和纵列是否出现了跳跃(即1方格当中夹着0方格)。容易发现,红桃会横着跳不会竖着跳,方块不会跳,剩下两种会竖着跳也会横着跳。接下来只需要区分黑桃和草花。这里观察发现,草花的竖跳列数远大于黑桃(刚开始我观察样例觉得至少是2倍,但有几组样例很不幸地故意把草花上面的弧线弄平了,但也至少是1.7倍),最后调参发现如果总列数/跳跃列数>7就判断为黑桃比较合适。

D

裸的数位DP,算是唤醒了一下自己的脑子。好像三年没写数位dp了。但我写的其实不规范。

题意:$L\cdots R$有多少个数的二进制不包含连续的$1$

解:(规范的LYF写法)设$f[i][j][k]$表示第$i$位,$j$代表当前是否选择,$k$代表前面一个是否是$1$。然后转移还是比较显然的。我的是定义$f[i]$表示所有有$i$位的数加起来有几个符合,求前缀和$sum[i]$就代表从$0$到$i$有多少个符合。然后在计算具体数字$x$的答案$calc(x)$时候可以发现,$0\cdots x$之间的可行数量实际上等于$sum[log2(x)]+calc(x第2位是1?log2(x-1):x-highbit(x))$写起来比规范dp短但是容易写错。而且有点依赖于找规律。

E

签到题,但看着反正不看罚时于是多wa了几发。

B

https://loj.ac/p/6503