摘要：这个文章是自己刷题的时候的错误大赏以及有趣思路记录

1：杂谈

有的时候会出现

O(n)

枚举，并且答案是静态的，

n

次询问但是总共要求在

O(n\log n)

的复杂度，这个时候可以考虑与处理出倍增的数组，用倍增的思想解决

2：

输入循环要因题而异

3：

暴力是可以倍增优化的，例如P10976

在遇到直接

O(n)

不难但是不可通过的时候，可以考虑倍增优化，因为倍增确实在优化这个“转移”的过程

但是如果问题是动态的，会出现修改，那么则无法使用

此外，如果询问非常少，那么

O(n \log n)

的预处理就感觉没有什么用了，第一个n代指起始点的规模，第二个n代指一共的“转移”步数的

max

4: 闲着没事Trie树不要写递归的询问

5：倍增LCA第二维开大一些，否则会何意味错误

2：算法

1： $Floyd$

CPP

memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= n; i++)dis[i][i] = 0;
for(int k = 1; k <= n; k++)
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      chkmin(dis[i][j], dis[i][k] + dis[k][j]);

最外层枚举中转点，

O(n^3)

2：

数位dp一般写记忆化，方便理解，并且在受到限制的时候不做记忆化，否则会有统计错误

可以简单理解说记忆化就是不受限制，否则也无法记忆化

3: $kmp$

这个算法的kmp数组本质是最长公共前后缀，所以也可以做最短的公共非空前后缀

kmp_i = 0

所以kmp数组也是可以作各种字符串的循环周期的

4: $Tarjain$

5：单调队列

先入队，再出队，不会有错

端点定义如下：

l = 0, r = 1, [l, r]

6：单调栈

同上，也需要注意题目让你干什么

7：SPFA找负环

CPP

memset(d, 0x3f, sizeof(d));
memset(cnt, 0, sizeof(cnt));
memset(vis, false, sizeof(vis));
queue<int> q;
q.push(1);d[1] = 0;vis[1] = true;//1开始，但如果不联通记得循环一下
while(!q.empty()){
  int u = q.front(); q.pop();
  vis[u] = false;
  for(auto ed : e[u]){
    int v = ed.v, w = ed.w;
    if(w + d[u] < d[v]){
      d[v] = w + d[u];
      if(!vis[v]){
        if(++cnt[v] >= n){
          cout << "YES\n";//找到了
          return;
        }
        q.push(v);
        vis[v] = true;
      }
    }
  }
}
cout << "NO\n";//不存在负环

3：比赛策略

NOIP和CSP-S特殊性质会有正解提示性。

可以打多个暴力，进行判断

NOIP现阶段策略：因为菜，选择NOIP4.5h凑200+pts（大概T1AC,T2AC，T3&T4拿暴力）

看题解不同解法也是重要的

利用assert调试

多函数调试，手算确定正确值传入，进行调试

计数题对拍（从大样例弄出来一些，因为可能有corner case）

提交之前一定在Lemon测试，保证行为一致

Windows下Linux虚拟机速度受限

NOIP若通过大样例，约等于通过，挂分应该不会太多的吧……

4: 优秀trick

P4643 图论边权拆分trick

边权可以拆为

\frac12 w

到点上

考虑差,可知都选上时贡献存在,各选一个贡献抵消

按新点权贪心即可

P3953 图论反图dfs等价拓扑排序转移trick

这题有一个重要的点在于求解是否有一种方案会经过0环，并且还需要维护方案数的dp

如果采用拓扑排序，容易发现并不好写

介绍trick：建反图跑记忆化搜索，如果有遇到已经访问过的点，并且是路径长度也相等的情况下，这表明我们经过了一个0环，可以break了

并且在反图上dfs等价拓扑序，是可做的。

介绍性质：最短路由最短路拼接，否则不为最短路

正确性显然

P12448 数据结构拆分 $\max$ trick

原题：

给定序列

a_1 ... a_n

单点加1修改

\sum_{1 \le i \le n - k + 1}\max_{i \le j \le i + k - 1}a_j

上式查询

trick：拆分max

先把和式改为

\sum_{t \ge 1}\sum_{i=1}^{n-k+1}[(\max_{i \le p \le i + k - 1}a_p)\ge t] \\

再设a上界为 $V$ ，查询修改为

(n - k + 1)V - \sum_{t = 1}^V\sum_{i = 1}^{n - k + 1}[(\min_{i\le p\le i + k - 1}a_p < t)]

再进一步预处理出

b_i = [a_i \ge t]

的极长1连续段的长度，对于固定的t，和式可化为

\sum^z_{i=1}\max\{0, len_i-k+1\}

此时题意转化为：

求大于一定值的len的数量与和，单点修改&区间查询，树状数组可做

求一个极大区间max恰好为a[k]的左端点和右端点，线段树二分可做

初始化的时候用单调栈预处理len即可, V上限是

\max\{a_i\} + Q

P5664 合理的dp状态优化以及容斥原理

不多于

\frac k2

下取整是很烦人的条件

考虑反过来,要求i出现超过k/2次

可是设计出一种

O(n^3m)

的算法

但是并不能完美通过此题

其实本质上我们只是关心i和非i之间的大小关系, 具体是多少无人在意

所以把两维压缩为一维,

O(n^2m)

做完了

5: STL

1: set

set，不做重载有

set.lower_bound(x) 返回第一个 不小于 x的iterator

set.upper_bound(x) 返回第一个小于 x的iterator

重载之后是反过来的

set.erase(x)传入值而非迭代器

杂记

文章操作

摘要：这个文章是自己刷题的时候的错误大赏以及有趣思路记录

1：杂谈

2：

3：

4: 闲着没事Trie树不要写递归的询问

5：倍增LCA第二维开大一些，否则会何意味错误

2：算法

1： $Floyd$

2：

3: $kmp$

4: $Tarjain$

5：单调队列

6：单调栈

7：SPFA找负环

3：比赛策略

4: 优秀trick

P4643 图论边权拆分trick

P3953 图论反图dfs等价拓扑排序转移trick

P12448 数据结构拆分 $\max$ trick

P5664 合理的dp状态优化以及容斥原理

5: STL

1: set

相关推荐

评论

杂记

文章操作

摘要：这个文章是自己刷题的时候的错误大赏以及有趣思路记录

1：杂谈

2：

3：

4: 闲着没事Trie树不要写递归的询问

5：倍增LCA第二维开大一些，否则会何意味错误

2：算法

1： FloydFloydFloyd

2：

3: kmpkmpkmp

4: TarjainTarjainTarjain

5：单调队列

6：单调栈

7：SPFA找负环

3：比赛策略

4: 优秀trick

P4643 图论边权拆分trick

P3953 图论反图dfs等价拓扑排序转移trick

P12448 数据结构拆分 max⁡\maxmax trick

P5664 合理的dp状态优化以及容斥原理

5: STL

1: set

相关推荐

评论

1： $Floyd$

3: $kmp$

4: $Tarjain$

P12448 数据结构拆分 $\max$ trick