Znzryb's Blog
0%

Posted on Edited on

题目大意

题目描述
有一个大小为 3×33 \times 3 的矩形安全箱。
共有 nn 件物品，第 ii 件物品的大小为 ai×bia_i \times b_i（可以水平放置或旋转 90∘90^{\circ}），价值为 viv_i。
你需要选择若干件物品放入安全箱内，物品必须完全在箱子内部且互相之间不能有重叠部分。
求能够放入安全箱内物品的最大总价值。

输入格式
第一行输入一个整数 TT（1≤T≤100001 \le T \le 10000），表示测试数据的组数。
对于每组数据：
第一行输入一个正整数 nn（1≤n≤1061 \le n \le 10^6），表示物品的数量。
接下来 nn 行，每行输入三个整数 ai,bi,via_i, b_i, v_i（1≤ai,bi≤3,1≤vi≤1081 \le a_i, b_i \le 3, 1 \le v_i \le 10^8），分别代表第 ii 件物品的长、宽和价值。
保证所有测试组的 nn 之和不超过 10610^6。

输出格式
对于每组数据，输出一行一个整数，表示最大的总价值。

样例输入

1
2
3
4
5
6
7
8
9
10
2
5
2 3 20
1 3 5
1 2 4
1 1 4
1 3 6
2
1 1 13141314
3 3 6947311

样例输出

1
2
28
13141314

样例解释第一组数据：最优策略是放入第 11 件物品（大小 2×32 \times 3，价值 2020）、第 33 件物品（大小 1×21 \times 2，价值 44）以及第 44 件物品（大小 1×11 \times 1，价值 44）。第 11 件物品占用 2×32 \times 3 的空间后，安全箱还会剩余 1×31 \times 3 的空白区域，恰好可以无重叠地容纳第 33 件和第 44 件物品。总价值为 20+4+4=2820 + 4 + 4 = 28。
第二组数据：虽然第 22 件物品（大小 3×33 \times 3，价值 69473116947311）能正好填满整个安全箱，但只放入第 11 件物品（大小 1×11 \times 1，价值 1314131413141314）可以获得更高的总价值。因此最优选择是仅放置第 11 件物品，最大总价值为 1314131413141314。

思路讲解

不难发现，一共只有 21 种有效状态。

开个玩笑，这个是提前用 dfs 跑出来的，直接打表，跳过这个预处理。

image

那你都预处理出来所有的这个情况了，做起来就很简单了。

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=13515

心路历程（WA，TLE，MLE……）

常见 dfs 错误及原因

Posted on Edited on

题目大意

image

题目背景与目标
有 nn 张牌从上至下组成的牌堆，每张牌上有一个点数 aia_i。共有 mm 名玩家按 1,2,…,m1, 2, \dots, m 的顺序依次循环摸牌。玩家 kk 作为游戏组织者，在所有人开始摸牌之前，可以进行至多一次切牌操作（即将牌堆从任意位置分为上下两部分，并交换这两部分的位置）。目标是求出玩家 kk 通过合理切牌，最终自己摸到的牌的点数总和的最大值。

输入格式
第一行包含一个整数 TT，表示测试用例的数量。
每组数据包含两行：
第一行输入三个正整数 n,m,kn, m, k，分别代表牌的总数、玩家的总数以及目标玩家的顺位。
第二行输入 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n，自顶向下给出牌堆中每张牌的点数。

输出格式
对于每组数据，输出一行一个整数，表示玩家 kk 可以获得的最大点数和。

样例输入

1
2
3
4
5
2
2 2 1
114514 1919810
3 1 1
1 -3 2

样例输出

1
2
1919810
0

样例解释第一组样例：牌堆共 22 张牌，有 22 名玩家，主角是第 11 名玩家。初始牌堆点数为 114514, 1919810。主角可以通过切牌操作，将上面的第一张牌移到最下方，得到新牌堆 1919810, 114514。开始发牌后，主角作为第 11 名玩家摸走第一张牌，获得最大点数 19198101919810。
第二组样例：牌堆共 33 张牌，只有 11 名玩家，主角是第 11 名玩家。无论主角在开始前如何切牌，因为只有他一个人玩，他都会摸走所有的牌。因此他获得的总点数固定为 1−3+2=01 - 3 + 2 = 0。

思路讲解

其实这道题目的思路说起来也很简单，就是在一个环上跑这个滑动窗口。

这个切牌其实可以看作循环位移操作。

image

然后，需要注意到的就是，无论你怎么切牌，第 k 个玩家所能吃到的牌的数量是不变的（也就是代码中的 cnt_k ）

因此，我们是用 2N 技巧，在这个 2N 上模拟环，进行一个滑动窗口，就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
for (ll i = K - 1; i < N; i += M) {
    cnt_k++;
    ans += A[i];
}
for (int i = 0; i < M; ++i) {
    ll lans = 0;
    ll cnt_i = 0;
    queue<ll> q;
    for (ll j = i; j < 2 * N; j += M) {
        lans += A[j];
        q.push(A[j]);
        if (SZ(q) == cnt_k) {
            ans = max(ans, lans);
        }
        if (SZ(q) > cnt_k) {
            lans -= q.front();
            q.pop();
            ans = max(ans, lans);
        }
    }
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=8833

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述总结

给定一个长度为 nn 的数列 a1,a2,…,ana_1, a_2, \dots, a_n 和一个定值 xx。两名玩家（铃仙和因幡帝）交替从数列中取数，取出的数会立刻从原数列中删除。规则如下：

  1. 铃仙先手，每次可以从当前数列中任选一个数。

  2. 因幡帝后手，每次必须选择当前数列头部的前 xx 个数（即剩下数列的第 11 到第 xx 个数）。若当前数列剩余元素不足 xx 个，则因幡帝会将剩余的所有数全部取走。

  3. 两人交替选数，直到数列为空。

铃仙的目标是最大化自己所取出的所有数字之和。
假设铃仙始终采取最优策略，请对于所有的 x=1,2,3,…,n−1x = 1, 2, 3, \dots, n-1，分别独立求出铃仙所能获得的数字和的最大值。

输入格式
第一行包含一个整数 tt（1≤t≤10001 \le t \le 1000），表示测试用例数量。
每个测试用例包含两行：
第一行是一个整数 nn（2≤n≤2×1052 \le n \le 2 \times 10^5），表示数列长度。
第二行是 nn 个正整数 aia_i（1≤ai≤1091 \le a_i \le 10^9），表示给定的数列。
保证所有测试用例中 nn 的总和不超过 5×1055 \times 10^5。

输出格式
对于每个测试用例输出一行，包含 n−1n-1 个正整数。第 ii 个整数表示当 x=ix=i 时，铃仙能获得的最大数字和。

样例数据

输入样例：

1
2
3
4
5
6
7
3
2
1 2
6
1 1 4 5 1 4
11
12 11 10 9 1 2 3 4 5 12 11

输出样例：

1
2
3
2
13 9 9 9 5
54 44 35 35 24 24 24 24 23 12

样例解释
在样例 22 中，初始数列为 1,1,4,5,1,41, 1, 4, 5, 1, 4。

当 x=1x=1 时，一种使得铃仙获得最大和的方案为：

  • 铃仙先选取 a4=5a_4=5，删除该数，此时数列变为 1,1,4,1,41, 1, 4, 1, 4；

  • 因幡帝必须选取头部的 11 个元素 a1=1a_1=1，此时数列变为 1,4,1,41, 4, 1, 4；

  • 铃仙再选取 a2=4a_2=4，此时数列变为 1,1,41, 1, 4；

  • 因幡帝必须选取头部的 11 个元素 a1=1a_1=1，此时数列变为 1,41, 4；

  • 铃仙再选取 a2=4a_2=4，此时数列变为 11；

  • 因幡帝必须选取头部的 11 个元素 a1=1a_1=1，此时数列为空，停止。
    铃仙所选之数的和为 5+4+4=135+4+4=13。可以证明，该方案铃仙所选之数的和最大。

当 x=3x=3 时，一种使得铃仙获得最大和的方案为：

  • 铃仙先选取 a4=5a_4=5，删除该数，此时数列变为 1,1,4,1,41, 1, 4, 1, 4；

  • 因幡帝必须选取头部的 33 个元素 a1=1,a2=1,a3=4a_1=1, a_2=1, a_3=4，此时数列变为 1,41, 4；

  • 铃仙再选取 a2=4a_2=4，此时数列变为 11；

  • 因幡帝必须选取头部的 33 个元素，但当前数列大小小于 33，全部取完，此时数列为空，停止。
    铃仙所选之数的和为 5+4=95+4=9。可以证明，该方案铃仙所选之数的和最大。

思路讲解

说实话，看完这道题目，我的感觉是不是特别困难。

那么，这道题目的第一个难点就是时间复杂度分析：

呃，其实我们会发现，使用数据结构优化的这个贪心，因为有调和级数的保障，时间复杂度是对的。

或者，换句话说，如果我们的这个**每次铃仙选数的次数（在所有 x 下）**加起来是 n/2+n/3+n/4+n/5+⋯+1n/2+n/3+n/4+n/5+\cdots+1，是不是就是这个调和级数？

然后这道题目的第二个难点就是这个贪心策略地选择：

⚠️注意：容易想到的贪心策略有~~不断地取前 x+1 个中最大的数字，不断地取全局最大数字~~，但是这些都是错的！

The 2026 ICPC Latin America Championship（2026 拉丁美洲决赛）-Gym-106416——D. Dropshipping（正过来看，ddl 是 ddl，也就是截止时间，但是反过来看，ddl 是激活时间）

我们可以采用这道题目的一个思路，就是，截止时间，ddl 非常难以处理，但是反过来看，就是这个激活时间，激活时间以后，这个点就想选就选，不想选就不选了。

然后，我们再来看这个东西，就是我们已经想到了这个 ddl 就是这个激活时间，然后我们现在的问题就是每个点的这个 ddl 是什么，能不能批量处理呢？

我们来看最差情况下和最好情况下的这个差别：最坏情况下（也就是假设所有的我们自己选的都在前面），第 kk 次操作的剩余数字的下标要求是 i>k(x+1)i>k(x+1) 。在最好情况下，第 kk 次操作的剩余数字的下标要求是 i>kxi>kx。那么 (kx,k(x+1))(kx,k(x+1)) 中的这个数字的 ddl 是 k+1k+1，即在 k+1k+1 次操作之前，这个数都是一定可以选的。((k+1)x,(k+1)(x+1))((k+1)x,(k+1)(x+1))。

通过上面👆的这个分析，我们会发现 ddl 如果采用真实游戏结束回合的定义，也就是什么时候会被取走，那么这个点的 ddl 就不是固定的，这非常不适合我们进行优化以及操作。

所以 ddl 应该采用这个所谓的前缀容量限制的定义方法。严格来说，对于 ddliddl_i，其指的是以 A[1;i]A[1;i] 为前缀的这个序列，在游戏中，可以最多保住多少个数字？

第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）——造桥与砍树

这个其实用了这个类似于懒操作的这个设计思想，不过其实也不是很一样。以上面👆的这个例子为例，虽然 i=4i=4 可能存活到第 2 回合，但是其存不存活到第二回合都不重要，因为即便其存活到第二回合，还是改变不了 A[1;4]A[1;4] 这个前缀最多只能保住一个数字的这个事实。所以说，可以等效认为其只能存活到这个第一回合。

那么 A[1;i]A[1;i] 这个前缀可以保住多少个这个数字呢？其实就是 ⌈i/(x+1)⌉\lceil i/(x+1) \rceil。那反过来讲，其实就是 [1,x+1][1,x+1] 的 dll 都为为 1，因为最多只能保下来 1 个这个数。[x+2,2(x+1)][x+2,2(x+1)] 的 ddl 就是 2，以此类推x

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19436

心路历程（WA，TLE，MLE……）

注意，我们查的都是后缀。

image

不要因为历史原因，有的改了，有的没改，导致不一致。

image

不要忘记这里的初始化。

image

Posted on Edited on

题目大意

题目描述

给定平面上 nn 个圆形区域，第 ii 个圆的圆心坐标为 (pi,qi)(p_i, q_i)，半径为 rir_i（保证 ri≤30r_i \le 30）。

给定 mm 次询问，每次询问给出一个四边平行于坐标轴的矩形区域，指定了其左下角顶点坐标 (xi,1,yi,1)(x_{i,1}, y_{i,1}) 和右上角顶点坐标 (xi,2,yi,2)(x_{i,2}, y_{i,2})。对于每次询问，需要计算出在给定的 nn 个圆中，有多少个圆与该矩形区域存在至少一个公共点。

数据范围

测试用例数量 tt 满足 1≤t≤10001 \le t \le 1000。
每次测试中的圆的个数 nn 满足 1≤n≤1.5×1061 \le n \le 1.5 \times 10^6，询问的个数 mm 满足 1≤m≤1041 \le m \le 10^4。
对于全部测试用例，保证 ∑n≤3×106\sum n \le 3 \times 10^6，∑m≤2×104\sum m \le 2 \times 10^4。
坐标与半径范围：1≤pi,qi≤1091 \le p_i, q_i \le 10^9，1≤ri≤301 \le r_i \le 30，1≤xi,1≤xi,2≤1091 \le x_{i,1} \le x_{i,2} \le 10^9，1≤yi,1≤yi,2≤1091 \le y_{i,1} \le y_{i,2} \le 10^9。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
4 1
1 1 1
7 1 2
5 3 2
1 2 1
2 2 6 4
8 3
5 6 4
7 7 4
3 3 2
1 8 5
10 1 2
1 8 1
7 2 2
5 4 5
9 1 10 5
3 1 6 3
5 1 9 5

样例输出

1
2
3
4
3
4
4
7

样例解释

在第一组测试数据中，共有 44 个圆和 11 次询问。询问给定的矩形左下角坐标为 (2,2)(2, 2)，右上角坐标为 (6,4)(6, 4)。经过判断，该矩形与输入的第 22 个圆、第 33 个圆以及第 44 个圆（总计三个圆形）存在公共点，因此该次询问的答案为 33。第二组测试数据同理，分别输出对应矩形内包含公共点的圆的数量。

image

思路讲解

这道题目应该是一道扫描线+树状数组，应该是不需要用到这个 K-D 树这种比较高级的东西的。

呃，那我们怎么做这道题目呢？首先就是用这个数据结构，快速求解出大矩形中的这个点，所谓的大矩形，就是矩形和圆的 minkowski 和（这个 minkowski 和是一个圆角矩形），当然，圆角矩形让我们用数据结构处理实在是，我们忽略其圆角，得到的就是所谓的“大矩形”（即图中黑色框框住的部分）。

小羊-2025-12-04-M. Ahmad’s Dish（圆和正多边形的这个 minkowski 和）（minkowski 和的交换不变性）

image

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）（把二维的问题变为一维的问题来做）

okay，我们上面的这个对扫描线总结的比较好。扫描线的重点就是维护一个当前生效的这个集合。按照一顺序排序后，那么我们其实就是要维护一个目前生效的圆的集合。

首先呢，就是这道题目，因为半径比较少，我们不妨把这个不同半径的圆分开处理。

然后因为我们目前把不同的半径分开处理，我们目前可以假设，所有的圆的这个半径都是相同的。我们就是像上面一样，把这个矩形扩大这个半径（👆想上面那个黑色的矩形一样）。

然后我们把矩形先按照 x 的右端点排序，再按照 x 的左端点排序。不过，我们发现，无论你怎么排序这个矩形和这个点（也就是这个圆心嘛），都很难维护一个严格生效的这个点的集合，主要也是矩形的是一个这个区间范围，无论怎么排都比较麻烦。

不过我们采用差分思想？其实就是如下方法：

左查询：在 X=Xmin−1X = X_{min} - 1 的时刻，查询树状数组中 [Ymin,Ymax][Y_{min}, Y_{max}] 区间的点数，记为 AA，从答案中减去 AA。（记录权重为 −1-1）

右查询：在 X=XmaxX = X_{max} 的时刻，查询树状数组中 [Ymin,Ymax][Y_{min}, Y_{max}] 区间的点数，记为 BB，加到答案中。（记录权重为 +1+1）

采用如上👆方法，我们只需要维护一个 [−INF,idx][-INF,idx] 的生效点集合就可以了，可以说是非常轻松惬意了，我们也不需要删除。

然后我们要进行这个几何点的这个扣除：

image

只要像上面👆一样，不断的枚举这个 dx，就可以排除掉所有的这个不合法的点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

struct Solve {
    ll N, M;
    Compress_<ll> li_y;
    vector<vector<X_y> > r_xy_ls;
    vector<Event> events_backup;
    vector<int> Ans;

    vector<Event> gen_event(ll r) {
        // vector<Event> tmp_events;
        vector<Event> events;
        // tmp_events.reserve(SZ(r_xy_ls[r]));
        for (auto [x,y]: r_xy_ls[r]) {
            events.push_back({x, y, Insert});
        }
        for (auto e: events_backup) {
            e.y1 -= r;
            e.y2 += r;
            if (e.type == Left) {
                e.x -= r;
            } else if (e.type == Right) {
                e.x += r;
            }
            events.push_back(e);
        }
        sort(all(events));
        return events;
    }

    void solve_single_r(ll r) {
        BIT tr(li_y.size());
        sort(all(r_xy_ls[r]));
        auto events = gen_event(r);
        for (auto &e: events) {
            if (e.type == Insert) {
                tr.add(li_y.get_i(e.y1), 1);
            } else if (e.type == Left) {
                Ans[e.id] -= tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y1+r,-1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x+r,e.y2-r,-1,1);
            } else {
                Ans[e.id] += tr.query(li_y.get_i(e.y1), li_y.get_i(e.y2));
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y1+r,1,-1);
                Ans[e.id] -= redundant_circle_cnt(r,e.x-r,e.y2-r,1,1);
            }
        }
    }
		
		// 查找以这个 x 为首的，在范围 [ly,ry] 之间的这个点的数量
    ll query_r_x_l_r_cnt(ll r, ll x, ll ly, ll ry) {
        if (ly > ry) {
            return 0;
        }
        auto &xy_ls = r_xy_ls[r];
        auto itl = lower_bound(all(xy_ls), X_y{x, ly});

        if (itl == xy_ls.end()) {
            return 0;
        }
        if (itl->x != x) {
            return 0;
        }
        if (itl->y > ry) {
            return 0;
        }
        auto itr = upper_bound(all(xy_ls), X_y{x, ry});
        ll num = itr - itl;
        return num;
    }
		
		// 计算边缘的，可能被多算的这个点。
    ll redundant_circle_cnt(ll r, ll x, ll y, ll dirx, ll diry) {
        ll res = 0;
        for (int dx = 1; dx <= r; ++dx) {
            ll tox = x + dirx * dx;
            ll disy = sqrtl(r * r - dx * dx);
            ll toy = y + diry * disy;
            ll ly = min(toy + diry, y + diry * r);
            ll ry=max(toy + diry, y + diry * r);
            res += query_r_x_l_r_cnt(r, tox, ly, ry);
        }
        return res;
    }

    Solve() : r_xy_ls(32) {
        cin >> N >> M;
        li_y.reserve(N + M);
        // for (int i = 1; i <= 30; ++i) r_xy_ls[i].reserve(N);
        for (int i = 1; i <= N; ++i) {
            ll x, y, d;
            cin >> x >> y >> d;
            r_xy_ls[d].push_back({x, y});
            li_y.add(y);
        }
        events_backup.reserve(N + 30 * M);
        Ans.resize(M);
        for (int i = 0; i < M; ++i) {
            ll x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            for (int r = 0; r <= 30; ++r) {
                li_y.add(y1 - r, y2 + r);
            }
            events_backup.push_back({x1, y1, Left, i, y2});
            events_backup.push_back({x2, y1, Right, i, y2});
        }
        sort(all(events_backup));
        li_y.init();
        for (int i = 1; i <= 30; ++i) {
            solve_single_r(i);
        }
        for (int i = 0; i < M; ++i) {
            cout << Ans[i] << "\n";
        }
    }
};

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1198&rid=19570

心路历程（WA，TLE，MLE……）

也是成功一次 AC 了，当然，在写一些模块的时候，ai 也帮助我进行了一些东西。

Posted on Edited on

题目大意

题目描述
给定一个长度为 nn、仅由小写字母组成的字符串 SS 以及一个非负整数 kk。
需要计算 SS 的本质不同的非空 kk-松散子序列的数量，并将结果对 998244353998244353 取模。

相关定义

  • kk-松散子序列：如果子序列 TT 在原字符串 SS 中对应的下标序列为 pos1,pos2,…,posmpos_1, pos_2, \dots, pos_m，且满足对于所有的 i∈[1,m−1]i \in [1, m-1]，都有 posi+1−posi>kpos_{i+1} - pos_i > k，那么 TT 就是一个 kk-松散子序列。即子序列中原串相邻提取字符的原始位置距离必须严格大于 kk。

  • 本质不同：两个子序列被认为是不同的，当且仅当它们的长度不同，或者它们在某个对应位置上的字符不相同（即只对比提取出的字符构成的字符串本身是否一致）。

输入格式
第一行包含一个整数 TT（1≤T≤1061 \le T \le 10^6），表示测试用例数。
对于每组测试用例：
第一行包含两个整数 n,kn, k（1≤n≤106,0≤k≤n1 \le n \le 10^6, 0 \le k \le n）。
第二行包含一个长度为 nn 的字符串 SS，保证仅包含小写字母。
保证所有测试用例的 ∑n≤106\sum n \le 10^6。

输出格式
对于每组测试用例，输出一行一个整数，表示本质不同的非空 kk-松散子序列的数量对 998244353998244353 取模的结果。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
3
4 1
aabb
5 2
abcab
7 3
abcdece

输出:
3
6
10

样例解释

  • 对于第一个测试用例（S=aabbS = \text{aabb}，k=1k = 1），下标位置差必须严格大于 11。满足条件的本质不同的子序列有 a、b、ab。

  • 对于第二个测试用例（S=abcabS = \text{abcab}，k=2k = 2），下标位置差必须严格大于 22。满足条件的本质不同的子序列有 a、b、c、aa、ab、bb。

思路讲解

呃，这个我们需要想办法做到求本质不同的这个所有子序列。

我们转移的时候，就是应该以 s[i] 开头的串，在我们所有的这个的计数之中，应该以 s[i] 开头的串只应该真的以 i 开头的时候被计算，因此后面的应该被减去。（当然，我们是从后往前遍历）

具体而言，这个转移式子是：

next[i]存在: dp[i]←2×dp[i+1]−(dp[next[i]+1]+1)+1dp[i]←2×dp[i+1]−dp[next[i]+1]next[i]不存在: dp[i]←2×dp[i+1]+1next[i] 存在:\ dp[i]\gets 2\times dp[i+1]-(dp[next[i]+1]+1)+1 \\ dp[i]\gets 2\times dp[i+1]-dp[next[i]+1] \\ next[i] 不存在:\ dp[i]\gets 2\times dp[i+1]+1

注意，为什么是减去 dp[next[i]+1]+1dp[next[i]+1]+1 呢？因为其实这个才是含有 next[i]next[i] 的子序列的所有数量。

当然，这个是求本质不同的这个子序列的时候，我们要计算 k-松散子序列。

计算 k-松散子序列：

next[i]不存在: dp[i]←2×dp[i+k+1]+1next[i]存在: dp[i]←2×dp[i+k+1]+1−(dp[next[i]+k+1]+1)dp[i]←2×dp[i+k+1]−dp[next[i]+k+1]next[i] 不存在:\ dp[i]\gets 2\times dp[i+k+1]+1 \\ next[i] 存在:\ dp[i]\gets 2\times dp[i+k+1]+1-(dp[next[i]+k+1]+1) \\ dp[i]\gets 2\times dp[i+k+1]-dp[next[i]+k+1]

AC代码

心路历程（WA，TLE，MLE……）