牛半仙的妹子序列 题解 《关于我因过于这道题卡常而将其称为"贞卡常"的这件事》 场上被卡常了,下来加了几个优化就卡过去了。 这道题应该很容易看出是一个dp,40pts的 O ( n 2 ) O(n^2) O(n2)的dp式子应该是很好想的。 我们定义 d p i dp_{i} dpi为在只关注第 i i i个数到第 n n n个数之间的序列构成合法序列的方案数。 容易得到方程式 d
题目 分析(线段树) 首先,要维护区间颜值和以及区间妹子个数,其实最难的应该是删除,在找的时候运用区间妹子个数,但是好像非正解,因为应该容易被HACK掉 代码(线段树) #include <cstdio>#include <cctype>#define rr registerusing namespace std;typedef long long ll;const in