csp-j总结

· · 生活·游记

T1 T2

纯水

T3

经过我1h的思考，写出了可持久化01字典树优化dp(由于不熟，写了1h共花2h)

思路是这样的设 dp_i 表示以 i 为结尾( i 必选)的最大区间个数， maxx_i 为 dp_i 的前缀和，然后二分最后一个点使得 a_l ^ a_{l+1}.....^a_i==k,然后dp_i=maxx_{l-1};

我觉得很明显我二分的那个东西用数组记下来，很容易就做完了，我应该多想想，不应该被学过的东西固化思维

另外这道题拍了，写法太复杂怕有问题

T4

看了半天没思路，设了个 dp_{i,j,k,（0/1/2/3）} 表示枚举到第i个数和为j（将最大为10001，因为他只要>2*a_{max}就行了，k为当前最大值，最后一维表示选的个数（同理，>3就行）

然后模拟样例，发现a_i从小到大排序，考虑将a_i排序，设dp_{i,j,w(0/1/2/3)}表示枚举到i（i必选），和为j,个数为w的方案数

前缀和优化+滚动就过了

这道题用时挺短的，没什么失误

估分

100+100+100+100=400