杂记

· · 算法·理论

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

1：杂谈

有的时候会出现O(n)枚举，并且答案是静态的，n次询问但是总共要求在O(n\log n)的复杂度，这个时候可以考虑与处理出倍增的数组，用倍增的思想解决

2：

输入循环要因题而异

3：

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

在遇到直接 O(n) 不难但是不可通过的时候，可以考虑倍增优化，因为倍增确实在优化这个“转移”的过程

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

此外，如果询问非常少，那么 O(n \log n) 的预处理就感觉没有什么用了，第一个n代指起始点的规模，第二个n代指一共的“转移”步数的 max

4：

```cpp inv[n]=ksm(fac[n],mod-2);//费马小定理 for(int i=n;i>=1;i--) inv[i-1]=inv[i]*i%mod;//简单操作 ``` #### 5: 闲着没事Trie树不要写递归的询问 #### 6：倍增LCA第二维开大一些，否则会何意味错误 #### 7: 二叉树的前中后序遍历可以将子树视为区间（好像dfs序列也是可以的），能区间dp等操作 ## 2：算法 #### 1： $Floyd 
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找负环

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";//不存在负环

8：线段树合并

WA，20pts：在线段树合并的时候，需要有 root[u] = merge(u, v, ...)，因为可能 u 是空节点，需要将非空节点 v 传到节点 u 这里，也就是root[u] = root[v]。

WA，50pts：需要在合并的 dfs 里就把答案记录下来，如上一点所说，可能会被覆盖。比如 u 是空节点，就会令 root[u] = root[v]，然后后续的有关 u 其它儿子的合并，就会把本来 v 节点的值给覆盖掉，所以要拿个数组记录。

线段树空间至少要开到 4×mlogV，因为 m 次操作，每次操作树上差分要更新 4 次，然后值域是 V。也就是说线段树数组至少要开到 4.7e6 这样

参考代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int MAXN = 1e5 + 5;
struct Seg{
    ll ls, rs, ans, cnt;
}seg[MAXN * 80];
ll segcnt;
ll New(){
    return ++segcnt;
}
void pushup(ll x){
    if(seg[x].ls == 0){
        seg[x].ans = seg[seg[x].rs].ans;
        seg[x].cnt = seg[seg[x].rs].cnt;
        return;
    }
    if(seg[x].rs == 0){
        seg[x].ans = seg[seg[x].ls].ans;
        seg[x].cnt = seg[seg[x].ls].cnt;
        return;
    }
    if(seg[seg[x].ls].cnt >= seg[seg[x].rs].cnt){
        seg[x].ans = seg[seg[x].ls].ans;
        seg[x].cnt = seg[seg[x].ls].cnt;
    }
    else{
        seg[x].ans = seg[seg[x].rs].ans;
        seg[x].cnt = seg[seg[x].rs].cnt;
    }
    return;
}
void insert(ll& x, ll l, ll r, ll a, ll val){//a += val
    if(!x)x = New();
    if(l == r){
        // cout << x << ' ' << a << endl;
        seg[x].cnt += val;
        seg[x].ans = a;
        return;
    }
    ll mid = (l + r) >> 1;
    if(a <= mid){
        // if(seg[x].ls == 0)seg[x].ls = New();
        insert(seg[x].ls, l, mid, a, val);
    }
    else{
        // if(seg[x].rs == 0)seg[x].rs = New();
        insert(seg[x].rs, mid + 1, r, a, val);
    }
    pushup(x);
}
ll root[MAXN], ans[MAXN];
ll merge(ll u, ll v, ll l, ll r){
    if(u == 0 || v == 0)return u + v;
    if(l == r){
        seg[u].ans = l;
        seg[u].cnt += seg[v].cnt;
        return u;
    }
    ll mid = (l + r) >> 1;
    seg[u].ls = merge(seg[u].ls, seg[v].ls, l, mid);
    seg[u].rs = merge(seg[u].rs, seg[v].rs, mid + 1, r);
    pushup(u);
    return u;
}
ll n, m;
int st[MAXN][20], d[MAXN];
vector<int> e[MAXN];
void dfs(ll u, ll fa){
    d[u] = d[fa] + 1;
    st[u][0] = fa;
    for(auto v : e[u])if(v != fa)dfs(v, u);
}
int lca(ll x, ll y){
        if(d[x] != d[y]){
        if(d[x] < d[y])swap(x, y);
        // ll dif = d[x] - d[y];
        for(int i = 19; i >= 0; i--)if(d[st[x][i]] >= d[y])x = st[x][i];
    }
    if(x == y)return x;
    for(int i = 19; i >= 0; i--)if(st[x][i] != st[y][i]){x = st[x][i], y = st[y][i];}
    return st[x][0];
}
void dfs2(ll u, ll fa){
    for(auto v : e[u])if(v != fa){
        dfs2(v, u);
        root[u] = merge(root[u], root[v], 1, MAXN);
    }
    ans[u] = (seg[root[u]].cnt == 0 ? 0 : seg[root[u]].ans);
}
signed main(){
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1, u, v; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        // root[i] = New();
    }
    // root[n] = New();
    dfs(1, 0);
    for(int i = 1; i <= 19; i++)
        for(int j = 1; j <= n; j++)
            st[j][i] = st[st[j][i - 1]][i - 1];
    for(int i = 1, u, v, z, l, fl; i <= m; i++){
        cin >> u >> v >> z;
        l = lca(u, v);fl = st[l][0];
        insert(root[u], 1, MAXN, z, 1);
        insert(root[v], 1, MAXN, z, 1);
        insert(root[l], 1, MAXN, z, -1);
        insert(root[fl], 1, MAXN, z, -1);
    }
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)cout << ans[i] << '\n';
    return 0;
}

3: 神秘数学：

Prufer序列

建立无根树到n-2序列的双射关系

也就是说，有两两对应关系

生成Prufer序列源码：

for(int i = 1; i < n; i++){
  cin >> f[i];
  d[f[i]]++;
}
for(int i = 1, j = 1; i <= n - 2; i++, j++){
  while(d[j])++j;
  p[i] = f[j];
  while(i < n && !--d[p[i]] && p[i] < j)p[i + 1] = f[p[i]], ++i;
}

解码Prufer序列源码：

for(int i = 1; i <= n - 2; i++){
    cin >> p[i];
    d[p[i]]++;
}
p[n - 1] = n;
for(int i = 1, j = 1; i < n; i++, j++){ 
    while(d[j])++j;
    f[j] = p[i];
    while(i < n && !--d[p[i]] && p[i] < j)f[p[i]] = p[i + 1], ++i;

}

作用：各种计数

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)

做完了

P14638 NOIPT4 区间在二维空间上的映射，分治的提示

可以把一个区间转化为一个二维平面上的点 (r, l)

画出图之后不难发现只有 直线 y = x 及下的点是有意义的

题意转化为若干个在（i, i）右下的可选用点求和

可以去掉 L 变成在三角形上做，每一个(i, i)由若干连续新询问的 max 构成，单调队列

对于每一个点，考虑特殊性质D和E，分别为 L > \frac n2 和 L > \frac n4

考虑分治

分治的话可以先将整个坐标系增加到 2^k 用于方便分治

对于 R 较大，分治处理，

#### P5785 DP贡献提前计算&斜率优化 首先不难想到这样的DP $$$ dp_{i, j} = \min _{0 <= j < i} \{f[j] + 时间贡献 + 开机时间贡献\} $$$ 观察到一个有趣的事情：**开机时间贡献如果从未来的角度观看，就仅仅是一个简单的表达式，或者说一次开机只是增加了未来的贡献** 考虑**贡献提前计算**，能将dp简化为1维DP 然后就斜率优化 ## 5: STL #### 1: set set<int>，不做重载有 set.lower_bound(x) 返回第一个 **不小于** x的iterator set.upper_bound(x) 返回第一个 **小于** x的iterator 重载之后是反过来的 set.erase(x)传入值而非迭代器 ## 6: 比赛 #### NOIP 好吧这个东西以后就是NOIpromax了，没救了 #### THUPC 2026记得参赛 #### USACO 好题记得回头看（因为和期末冲突）