Znzryb's Blog
0%

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……）

Posted on Edited on

杭电 OJ 暂不支持调整栈空间大小。如果使用 G++ 提交代码，并且代码中含有递归，递归层数较深，会返回 Runtime Error (STACK_OVERFLOW)。添加如下代码可以开大栈空间：

1
2
3
4
5
6
7
int main() {
    int size(256<<20);  // 256M
    __asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
    // 关同步流代码
    // 主程序代码
    exit(0); // 一定要添加这一条，不然会返回 Runtime Error (ACCESS_VIOLATION)
}

Posted on Edited on

题目大意

题目描述

给定二维平面第一象限上的 nn 个弹幕发射器。第 ii 个发射器位于坐标 (xi,yi)(x_i, y_i)，并向四个方向之一发射一条射线（激光）：

  • di=0d_i = 0：向上发射

  • di=1d_i = 1：向右发射

  • di=2d_i = 2：向下发射

  • di=3d_i = 3：向左发射

射线的照明路径包含发射器本身所在的位置。题目保证任意两个发射器不会同时在对方的照明路径上。

现在可以在平面上放置障碍物（允许放置在发射器所在的坐标上），只要障碍物位于某条射线上，就能阻挡该射线的照射。求最少需要放置多少个障碍物，才能使得所有 nn 个发射器的照射路径上都至少包含一个障碍物。

输入格式

第一行包含一个整数 tt（1≤t≤1001 \le t \le 100），表示测试用例的数量。

每个测试用例第一行包含一个整数 nn（1≤n≤3001 \le n \le 300），表示发射器的数量。
接下来 nn 行，每行包含三个整数 xi,yi,dix_i, y_i, d_i（1≤xi,yi≤1091 \le x_i, y_i \le 10^9，di∈{0,1,2,3}d_i \in \{0, 1, 2, 3\}），表示发射器的坐标与发射方向。

保证所有测试用例中 nn 的总和不超过 30003000。

输出格式

对于每个测试用例，输出一行一个整数，表示最少需要放置的障碍物数量。

样例输入

1
2
3
4
5
6
7
8
9
10
2
6
5 5 0
3 7 1
9 9 2
9 1 3
5 2 0
1 20 3
1
1 1 0

样例输出

1
2
3
1

样例解释

在第一个测试用例中，有 66 个发射器。一种最优方案是放置 33 个障碍物，具体位置如下：

  1. 在坐标 (5,7)(5, 7) 处放置一个障碍物：该点覆盖了第 11 束（从 (5,5)(5,5) 向上）、第 22 束（从 (3,7)(3,7) 向右）以及第 55 束（从 (5,2)(5,2) 向上）激光。

  2. 在坐标 (9,1)(9, 1) 处放置一个障碍物：该点覆盖了第 33 束（从 (9,9)(9,9) 向下）以及第 44 束（从 (9,1)(9,1) 向左）激光。

  3. 在坐标 (−2025,20)(-2025, 20) 处放置一个障碍物：该点覆盖了第 66 束（从 (1,20)(1,20) 向左）激光。

该方案共使用了 33 个障碍物，且可以证明不存在比 33 更少的放置方案。

思路讲解

一种错误的图论建模方式是把激光当作左边的点，把这个障碍物当成右边的点，但是这样子建图是做不出来这道题目的，因为我们不是要让激光和障碍物一一匹配，这个非常容易就能做到。

P3386 【模板】二分图最大匹配

那么要做这道题目，最重要的就是我们要把障碍物看成连边，左边的点指的是这个方向为上下的点，右边的点指的是这个方向为左右的点。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Solve() {
    ll N;
    cin >> N;
    vector<X_y_d> xyd_ls(N);
    for (int i = 0; i < N; ++i) {
        cin >> xyd_ls[i].x >> xyd_ls[i].y >> xyd_ls[i].d;
    }
    xyd_ls = unique_xyd_ls(xyd_ls);
    auto g = build_graph(xyd_ls);
    Bi_graph_matcher matcher(g,SZ(xyd_ls));
    ll mx_match = matcher.mx_match();
    ll ans = (SZ(xyd_ls) - 2 * mx_match) + mx_match;
    cout << ans << "\n";
}

AC代码

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

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

最好显式忽略这个其他情况：

image

使用 offset 进行 swap，最后也要 swap 回来。

image

将哨兵值设置为 -1，可以避免 0-based 造成问题。

image