It's my fault QAQ

· · 个人记录

P2704炮兵阵地
主要是优化：

  1. 提前处理 1 2 行的状态，提前跑一遍存好答案；
  2. 提前处理好每一行的合法状态,lgS[i][S]存的就是第i行的S状态是不是合法;
  3. 用Set提前存好所有本行内左右两格不存在相邻1的合法状态，然后dp的二维和三维就可以改成存下标了，遍历也可以只从Set里面选了,时空双优化;

Code

P2915 奶牛混合
论读题 眼睛不需要可以给有需要的人 的重要性，题目里说了相邻奶牛的编号之差均超过K,超过K,超过K,超过K，然后就写了>=;

  1. 一看奶牛数那么少，果断压！
  2. 状态依赖什么呢？很明显，你都压奶牛了肯定要放个奶牛进去，然后呢，因为要求相邻奶牛的数量要超过k,所以我们上次放的奶牛也很关键，那么我们就定义f[i][S]表示，目前我们刚刚放的是奶牛i，我们现在已经放好的奶牛集合是S
  3. 那么我们就可以用填表了！为什么？因为填表很好写鸭。我们枚举S,i然后要先判断S里面必须包括i并且之前没刷过f[i][S]，所以要预处理好每个奶牛单独在队里的情况，然后就可以内层枚举奶牛i前面的奶牛j，j的情况就应该是S里面没有i的情况，然后拿f[j][S-{i}]更新就行了，最后统计一遍以每个奶牛为结尾的全集的f,就切了

    Code

    RMQ online
    不带脑子敲循环导致数组越界的惨案 按照题目要求，我们需要动态的求区间的最小值，但ST表效率很优秀，我们就可以每次插入都重新更新最小值，是不会超时的qwq除非有毒瘤数据;

    • 插入操作
      用数组st[i][j]表示从下标j开始跳2^i步会到的数，那么我们规定st[0][j]就是代表num[j]，那么插入就很简单了,st[0][++n] = x就可以了，然后再来个倍增，不断地把起始端点从右向左移动，更新最小值，跳到最左端就阔以break辽
    • 询问操作
      也是倍增，老套路统计，len = Log[r-l+1]，然后在st[len][l], st[len][r-(1<<len)+1]取最小就行了
    • 删除操作
      直接pop掉n位的那个数就阔以了，n++ ;
      注意Log你开了N的大小但是她的下标只能到N-1……循环i <= N就会把她填的太满了

      Code

      index 这个有毒，会CE

      手写函数要注意返回值和传参的类型，不然会有十分惨痛的教训

惨痛教训，矩阵乘法莫得交换律，所以必须要让横着乘的前面，竖着乘的在后面

扩欧要注意解的范围，尽量转化到同余类里面去

加了快速乘或者快速幂爆掉的原因可能是传值传了负数，死循环或者一直不出数就要检验快速乘和快速幂

CRT扩欧和后来求解取模要记得取大模

  1. 边集数组无向边要开两倍，线段树维护数组要开四倍！
    小根堆结构体生成例
struct POI {
    int Id, Val;
    POI(int Id = 0, int Val = 0) : Id(Id), Val(Val) {}
    bool operator < (const POI &a) const {
        return Val > a.Val;
    }
};

并查姬

  1. 记得初始化！初始化！初始化！
  2. 带权并查集的路径压缩不要乱搞！递归一下fa[x] = find(fa[x]),然后再统计关系……不然就会把路径搞乱，假如先搞关系就跟没搞一样，应该要先把x给路径压缩过去再重新统计关系……

注意取模数变0的情况啊！！！

不要乱给题目数据排序，有时候是不对的！有可能排序之后就不符合题目要求了