2026.8.8暑假作业第二套——做题随笔/题解

---

---

做题感受

这是一套较为简单但需要一点点思考且不那么常规的题。题目叙述乍一看“欸！这题我会做！”实际上暗含了一部分“坑”。

---

T1苹果树

题意简述

给你一个长度为$n$的序列$a$(3≤$n$≤1000)。其中有$n-1$个元素都相同，让你找出剩下一个不同元素的位置和键值。

赛时感受

这么简单的签到题？切了。

---

T2机器人寻宝

题意简述

在平面坐标系内给你$n$个点的坐标$(x_i,y_i)$(0≤x_i,y_i≤1e9;x_i,y_i均为整数),你可以定义若干个移动模式：

每个移动模式包含两个参数 $a,b$，意味着机器人可以从坐标$(x,y)$移动到$(x+a,y+b)$；

每个移动模式可以被调用任意正整数次；

现在想知道：至少定义多少个移动模式，才能实现任意两点之间能通过若干次调用同一移动模式到达？

赛时感受

很快想到题目实际上可以转化成：统计平面内直线条数，最后输出答案$\times 2$即可。¹

可是要如何记录已经出现过的直线呢？要使用 $y=kx+b$ double的精度误差²能害死我。

嗯…不会，敲个暴力走了🛺🛺🛺

---

正解

思路

确实不能直接存斜率截距，但是我们可以存两点之间的有向差量 （好吧我之前没听说过这玩意儿）。也就是说：

对于任意两点$P_i,P_j$,计算有向差量：
$$(dx,dy)=(x_j-x_i,y_j-y_i)$$
一条移动模式$(a,b)$能从$P_i$一次到$P_j$，当且仅当存在正整数$k$，使得：
$$(dx,dy)=k\cdot (a,b)$$
所以只需要把每个差向量化简成最简整数方向：
$$(\frac{dx}{g},\frac{dy}{g})，g=gcd(|dx|,|dy|)$$
并且它的相反方向也要加入，因为反过来走需要另一种模式。

最后统计不同的最简有向向量个数即可。

---

实现步骤

1. 读入所有点。
2. 枚举所有点对$i<j$。
3. 计算$dx,dy$。
4. 求出$g=gcd(dx,dy)$，得到最简方向。
5. 把这个方向和它的相反方向都存入数组。
6. 排序、去重，输出数组大小。

参考代码

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int o=5e2+22;   // 最大点数 500，数组大小略大

int n;

// 存储每个宝藏的坐标
struct node
{
    int x,y;
}a[o];

// 手动实现最大公约数（欧几里得算法）
// 先取绝对值，处理负数情况，保证 gcd 非负
int gcdll(int a,int b)
{
    if(a<0) a=-a;
    if(b<0) b=-b;
    
    while(b)
    {
        int t=a%b;
        a=b;
        b=t;    
    }
    return a;
}

signed main()
{
    //freopen("name.in", "r", stdin);
    //freopen("name.out", "w", stdout);
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    
    // 存储所有不同的有向最简向量（方向模式）
    vector<pair<int,int>> ans;
    
    // 枚举所有点对 (i, j)，i < j
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            // 计算从 j 到 i 的差向量（也可以反过来，不影响，因为会同时加入相反方向）
            int dx=a[i].x-a[j].x;
            int dy=a[i].y-a[j].y;
            
            // 排除相同点（数据保证不会出现，但保留安全）
            if(dx==0&&dy==0) continue;
            
            // 化简为最简方向向量
            int f=gcdll(dx,dy);
            ans.push_back({dx/f, dy/f});     // 原方向
            ans.push_back({-dx/f, -dy/f});   // 相反方向，因为从 j 到 i 也需要模式
        }
    }
    
    // 排序去重，统计不同模式的数量
    sort(ans.begin(),ans.end());
    ans.erase(unique(ans.begin(),ans.end()),ans.end());
    
    // 输出答案
    cout<<ans.size()<<"\n";
    return 0;
}

/*
样例测试：
3
1 2
3 6
7 4
输出 6

3
1 1
2 2
3 3
输出 2


3
1 1
2 1
0 1
输出 2
*/

---

小结

这道题算是一道还可以的“数论 + 暴力枚举 + 去重”类题目，主要就是有向差量+GCD要拐一下，其他还好。

调试心得（血泪汇总）

• 千万不要用$double$存斜率截距来做，虽然我没试过能不能卡过，但这样的习惯是不好滴
• 一条直线，两种移动模式，不要漏存
• 而且，也不能只存单向去重后最后输出结果$\times 2$，这样做会导致答案偏大，因为单向集合里可能已经同时包含了某个方向和它的相反方向，直接乘以 2 会把它们重复计算。具体见参考代码后的第三个样例
• 只要不犯贱，其他都还好…

---

T3大富翁

题意简述

现在需要将$1$通过一系列操作提升到$E$（$1\le E\le 1e18$）,给予你两种操作：

1. 将当前的数加上1~$k$（$1\le k\le 1000$）中任意一个数；
2. 将当前的数乘$p$（$1\le p\le 1000$）;

问最少操作次数。

赛时感受

难得不考数据结构，而且这题目叙述比我脸都干净。从1到$E$，到约数然后加倍？不行，$p$改不了。在所有约数中枚举选一个来将就$p$？可$E$有$1e18$啊，这个范围肯定不是拿来给我枚举的。啊哈，正难则反！从$E$降到$1$完全等价嘛！接下来——能除就除，不行就减到下一个能除的数。嗯哏，AC。

---

贪心正确性

1. 问题重新建模（反向视角）

正向：从 1 出发，操作是 +1~+k 或 *p（其中 k < p，这是题目给定的关键条件）。

反向：从 E 出发，操作是 -1~-k 或 ÷p（必须能整除时才能用）。

我们定义函数 f(x) 表示从当前数 x 变到 1 的最少步数。

显然，当 x < p 时，无法使用除法，只能用减法：
f(x) = ceil((x - 1) / k)

当 x ≥ p 时，为了使用除法，我们必须先通过减法将 x 变成 p 的倍数。

设 x = q × p + r，其中 0 ≤ r < p。

贪心策略：只减到最近的倍数 q × p，即只减 r（如果 r=0 就直接除）。

那么贪心代价为：

cost_greedy = ceil(r / k) + 1 + f(q)

---

2. 为什么不考虑“减到更远的倍数”（例如 (q - t) × p）？

假设我们不只减 r，而是多减 t × p（t ≥ 1），也就是减到 (q - t) × p。
那么代价为：

cost_t = ceil((r + t × p) / k) + 1 + f(q - t)

我们要证明：cost_greedy 永远小于或等于 cost_t。

关键不等式（核心）：

因为题目给定 p > k（这是保证贪心成立的唯一数学条件），所以：

ceil((r + t × p) / k) ≥ ceil(r / k) + t

说明：多减 t × p 这一步，至少要额外付出 t 次减法操作（实际上因为 p > k，额外付出的次数还大于 t）。

另一方面，减到更小的商 q - t 后，最多能省下多少步呢？
最理想的情况是：q - t 比 q 小很多，从而省下一些除法/减法次数。但即便在最乐观的情况下，从 q 变到 q - t 也只需要最多 t 次操作（比如全用减法），所以：

f(q - t) ≥ f(q) - t

也就是说，把数变小 t 个单位，最多只能节省 t 步³。

合并：

把两个不等式相加：

cost_t ≥ [ceil(r/k) + t] + 1 + [f(q) - t] 
       = ceil(r/k) + 1 + f(q) 
       = cost_greedy

结论：多减 t × p 带来的额外减法开销（至少 t 步），完全抵消甚至超过它能节省的步骤（最多 t 步）。因此，减到比“最近倍数”更小的倍数，绝不会更优。

所以，每一步“只减余数 r”就是全局最优的贪心策略。

---

参考代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int o = 1e5 + 22;

// 全局变量
int k, p, e; 
// k : 指定骰子一次最多可走的步数
// p : 倍数骰子的乘数
// e : 终点

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 读入三个整数
    cin >> k >> p >> e;

    int ans = 0;          // 记录“混合使用两种骰子”的最少步数
    int x = e - 1;        // 只用指定骰子时，从 1 到 e 需要前进的总步数

    // 反向递推：从终点 e 倒推回起点 1
    // 循环条件：当前值 e 不小于倍数乘数 p，这样才可能使用倍数骰子
    while (e >= p)
    {
        // 特殊处理 p == 1 的情况，因为除以 1 和取模 1 会导致死循环
        if (p == 1)
        {
            ans = LLONG_MAX;   // 置为无穷大，表示该方案无效
            break;
        }

        // 计算当前值 e 除以 p 的余数 r
        int ned = e % p;
        // 需要先使用指定骰子将 e 减到最近的 p 的倍数（即 e - ned）
        // 每次指定骰子最多走 k 步，因此所需次数为 ceil(ned / k)
        ans += ned / k;
        if (ned % k) ans++;   // 处理向上取整

        // 执行减法：将 e 变为 p 的倍数
        e -= ned;

        // 使用一次倍数骰子：从 e 跳到 e / p
        ans++;
        e /= p;
    }

    // 循环结束后，e 已经小于 p，无法再使用倍数骰子
    // 现在只能用指定骰子从当前位置 e 走到 1（起点）
    // 需要前进 (e - 1) 步，所需次数为 ceil((e - 1) / k)
    if (e != 1 && p != 1)   // 当 p==1 时已经置为无穷大，不再计算
    {
        ans += (e - 1) / k;
        if ((e - 1) % k) ans++;
    }

    // 计算“只用指定骰子”的方案所需次数
    // 从 1 到 e 需要前进 (e - 1) 步，每次最多走 k 步
    int num = x / k;
    if (x % k) num++;   // 向上取整

    // 答案取两种方案的最小值
    cout << min(ans, num) << "\n";

    return 0;
}

---

T4背包问题

题意简述

有一个背包的最大载重为$H$,容积为$V$（$1\le H,V\le 300$）。这个背包可以按$1:1$的汇率将载重换成容积（只能单向转换）。现有$n$（$1\le n\le 1000$）个物品，每物品$i$有三个属性：$h_i$重量、$V_i$体积、$W_i$价值。

求能取得的最大价值。

赛时感受

害，把体积和重量一加不完事儿了吗？Σ(⊙▽⊙"a 不对！单向转化，Oh no!不会，敲个暴力走了🛺🛺🛺

正解

解题思路

1. 转化约束条件

若选择某个 $k$，则所选物品集合 $S$ 必须满足：
$$\sum _{i\in S}{w}_i\le W-k,\sum _{i\in S}{v}_i\le V+k$$
将两式相加，可得：
$$\sum _{i\in S}(w_i+v_i)\le W+V$$
同时，重量约束依然存在：
$$\sum w_i\le W-k\le W$$
（因为 $k\ge 0$，所以 $\sum w_i\le W$ 是必要条件，且若该条件满足，总能通过选择适当的 $k$ 使第一个不等式成立，因为 $k$ 可以取足够大？实际上，更严谨的转化是：存在 $k\ge 0$ 使得：
$$\sum w_i\le W-k⟹k\le W-\sum w_i$$
且：
$$\sum v_i\le V+k⟹k\ge \sum v_i-V$$
因此存在这样的 $k$ 当且仅当：
$$\sum v_i-V\le W-\sum w_i⟺\sum (w_i+v_i)\le W+V$$
同时还需 $\sum w_i\le W$（因为 $k\ge 0$，从 $k\le W-\sum w_i$ 可知需 $\sum w_i\le W$）。

所以，可行性等价于：
$$\sum w_i\le W,\sum (w_i+v_i)\le W+V$$

---

2. 动态规划

我们有两个限制维度：总重量（限制 $W$）和总消耗 $s=w+v$（限制 $W+V$）。
定义 $dp[j][s]$ 表示考虑若干物品后，总重量恰好为 $j$，总消耗恰好为 $s$ 时能获得的最大价值。
转移为 0/1 背包：
$$dp[j][s]=\max (dp[j][s],dp[j-w_i][s-(w_i+v_i)]+va{l}_i)$$
其中 $j$ 从 $W$ 降到 $w_i$，$s$ 从 $W+V$ 降到 $w_i+v_i$。

初始化所有 $dp$ 为负无穷或 0（因为价值非负，用 0 可保证不选任何物品时价值为 0）。

最终答案为：
$$\underset{0\le j\le W,0\le s\le W+V}{\max }dp[j][s]$$

---

3. 复杂度

• 时间复杂度：$O(n\cdot W\cdot (W+V))$，在数据范围内可承受。
• 空间复杂度：$O(W\cdot (W+V))$，可用二维数组或 vector 动态分配。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int o=1e3+22;

int n,w,v; 

struct node
{
	int w,v,val;
}a[o]; 

int dp[322][622]={0}; // dp[重量][总消耗]：当前总重量为i，总消耗(重量+体积)为j时的最大价值

signed main()
{
	//freopen("name.in", "r", stdin);
	//freopen("name.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// 输入物品数量n、背包原始重量上限w、体积上限v
	cin>>n>>w>>v;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].w>>a[i].v>>a[i].val;
	}
	
	// 0/1背包DP，枚举每个物品
	for(int k=1;k<=n;k++)
	{
		int k_w=a[k].w;          // 当前物品重量
		int k_val=a[k].val;      // 当前物品价值
		int k_wv=a[k].w+a[k].v;  // 当前物品的“总消耗” = 重量+体积
		// 倒序枚举重量（第一维）和总消耗（第二维），保证每个物品只选一次
		for(int i=w;i>=k_w;i--)
		{
			for(int j=w+v;j>=k_wv;j--)
			{
				// 状态转移：选或不选当前物品
				dp[i][j]=max(dp[i][j],dp[i-k_w][j-k_wv]+k_val);
			}
		}
	}
	
	// 统计所有满足总重量<=w且总消耗<=w+v的状态的最大价值
	int ans=0;
	for(int i=0;i<=w;i++)
	{
		for(int j=0;j<=w+v;j++)
		{
			ans=max(ans,dp[i][j]);
		}
	}
	cout<<ans<<"\n";
	return 0;
}


/*
5 10 10
0 1 8
2 3 9
4 5 7
10 10 10
5 5 8

25
*/

---

总结

这套卷子我第一遍做一个小时出头是$154pts$,比预期低一些。主要是因为我在思考简单分任务时“太想当然”。比如不能像数学一样用斜率截距区分不同直线、反向由$E$归$1$而不是$0$、直接减$k$可能更优、如果$p$是1要特判、手写GCD要考虑负数、背包不能反向转化以及只存总消耗…

不过通过这套卷子我还是提升了很多：手写GCD（好吧之前不会）、转化思维进一步提升、推导能力提升、做题直觉更清晰…

希望我能继续保持！加油。

---

1. 解释：如果有几个点在同一条直线上，那么只需要定义两个移动模式就能实现直线上所有点之间的移动。但由于题目要求“任意两点”，所以要统计所有直线。 ↩︎

2. 比如1/3和2/6，浮点数结果未必完全相等。 ↩︎

3. 哪怕采用最优策略，从 q 降到 q-t 也至少需要 1 步（除非 t=0），所以省下的步数不可能超过 t。因此 f(q-t) ≥ f(q)-t。 ↩︎