Znzryb's Blog
0%

Posted on Edited on

注意 dfs 要记得进行回退操作的时候，所有东西都要回退，包括这个 vis 数组。

image

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