7.20集训模拟赛题目及题解

T1 染色(paint)(T788047)

题目背景

小 E 同学和他的朋友小 S 在数轴上作画。

题目描述

小 E 同学选择了红色颜料，小 S 选择了蓝色颜料。

小 E 同学先在数轴上画了一笔，然后小 S 也画了一笔。小 E 知晓，当数轴上的某一位置同时被涂上红色和蓝色，最终会呈现出紫色。

现在，他想知道数轴上呈现紫色的长度，你能告诉他吗？

输入格式

输入的第一行包含四个整数 ，分别表示小 E 和小 S 在数轴上涂色的区间。

输出格式

输出共一行，包含一个整数，表示数轴上呈现紫色的长度。

输入输出样例 #1

输入 #1

0 3 1 5

输出 #1

2

输入输出样例 #2

输入 #2

0 1 4 5

输出 #2

0

输入输出样例 #3

输入 #3

0 3 3 7

输出 #3

0

说明/提示

样例 1 解释

小 E 的涂色区间为 ，小 S 的涂色区间为 ，那么二者都涂色的区间为 ，所以紫色的长度为 。

数据规模与约定

• 对于 的数据，保证 。
• 对于另 的数据，保证数轴上最终不存在紫色。
• 对于另 的数据，保证 。
• 对于 的数据，保证 。

小 E 的涂色区间为 ，小 S 的涂色区间为 ，那么二者都涂色的区间为 ，所以紫色的长度为 。

数据规模与约定

• 对于 的数据，保证 。
• 对于另 的数据，保证数轴上最终不存在紫色。
• 对于另 的数据，保证 。
• 对于 的数据，保证 。

思路分析

两个区间 和 的重叠部分，可以用以下方法计算：

1. 重叠区间的左端点：取两个左端点的最大值，即
2. 重叠区间的右端点：取两个右端点的最小值，即

如果 ，说明两个区间没有重叠，紫色长度为 0。

否则，紫色长度为

如果 max(L1​,L2​)≥min(R1​,R2​)，说明两个区间没有重叠，紫色长度为 0。

否则，紫色长度为 min(R1​,R2​)−max(L1​,L2​)。

代码实现

cpp

复制

下载

#include
#include
using namespace std;
int main() {
int L1, R1, L2, R2;
cin >> L1 >> R1 >> L2 >> R2;

int left = max(L1, L2);   // 重叠区间的左端点
int right = min(R1, R2);  // 重叠区间的右端点

if (left < right) {
    cout << right - left << endl;
} else {
    cout << 0 << endl;
}

return 0;

}

复杂度分析

• 时间复杂度：O(1)，只进行常数次运算。

• 空间复杂度：O(1)，只使用了几个变量。

这种方法直接明了，能够处理所有可能的情况。计算：

1. 重叠区间的左端点：取两个左端点的最大值，即

2. 重叠区间的右端点：取两个右端点的最小值，即 min⁡(R1,R2)\min(R_1, R_2)min(R1​,R2​)

如果 max⁡(L1,L2)≥min⁡(R1,R2)\max(L_1, L_2) \geq \min(R_1, R_2)max(L1​,L2​)≥min(R1​,R2​)，说明两个区间没有重叠，紫色长度为 0。

否则，紫色长度为 min⁡(R1,R2)−max⁡(L1,L2)\min(R_1, R_2) - \max(L_1, L_2)min(R1​,R2​)−max(L1​,L2​)。

代码实现

#include
#include
using namespace std;
int main() {
int L1, R1, L2, R2;
cin >> L1 >> R1 >> L2 >> R2;

int left \= max(L1, L2);   // 重叠区间的左端点
int right \= min(R1, R2);  // 重叠区间的右端点

if (left < right) {
    cout << right \- left << endl;
} else {
    cout << 0 << endl;
}

return 0;

}

复杂度分析

• 时间复杂度：O(1)O(1)O(1)，只进行常数次运算。

• 空间复杂度：O(1)O(1)O(1)，只使用了几个变量。

这种方法直接明了，能够处理所有可能的情况。

T1 题解

AC Code

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int L1, R1, L2, R2;
    cin >> L1 >> R1 >> L2 >> R2;
    
    int left = max(L1, L2);   // 重叠区间的左端点
    int right = min(R1, R2);  // 重叠区间的右端点
    
    if (left < right)
        cout << right - left << endl;
    else
        cout << 0 << endl;
    
    return 0;
}

思路分析

这道题要求计算两个区间重叠的长度，也就是紫色的长度。

两个区间  和  的重叠部分，可以用以下方法计算：

1. 重叠区间的左端点：取两个左端点的最大值，即 

2. 重叠区间的右端点：取两个右端点的最小值，即 

如果  ，说明两个区间没有重叠，紫色长度为 0。

否则，紫色长度为 。

T2 石头称重(stone)(T788054)

T788054 T2 石头称重（stone）

题目背景

小 E 有 块石头，编号从 到 。第 号石头的重量是正整数 。

题目描述

对于每一个 ，我们保证编号为 的石头比所有编号小于 的石头的重量总和还要重。

小 E 有时会在使用天平秤称量物体时运用他收集的石头：他将物体放在一个盘子上，将一些石头放在另一个盘子上，如果两个盘子处于平衡状态，他就知道物体的重量与石头组合的重量相同。

当然，并不是所有的物体都可以用上述方法来称重：有时不存在与该物体重量相同的石头组合。

如果可以用一些石头的组合（可能是空集）来平衡重量为 的物体，则称重量 是可接受的。

例如，如果小 E 拥有的石头重量为 和 ，则可接受的重量有 。

对于给定的 块石头，考虑所有不同的可接受重量的严格递增序列，请求出此序列中第 个元素的重量是多少。如果不存在第 个元素，则输出 。

输入格式

输入的第一行，包含一个正整数 ，表示石头的数量。

输入的第二行，包含 个正整数，表示每个石头的重量。

输入的第三行，包含一个正整数，表示题目中所给出的 。

输出格式

输出共一行，包含一个整数，即可接受重量的第 个元素，若不存在则输出 。

输入输出样例 #1

输入 #1

2
4 7
1

输出 #1

0

输入输出样例 #2

输入 #2

5
1 3 7 13 30
10

输出 #2

14

说明/提示

数据规模与约定

• 对于 的数据，保证 。

• 对于另 的数据，保证 。

• 对于 的数据，保证 。

T2 题解

AC Code

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    
    vector<ll> w(n + 1);  // 1-indexed
    vector<ll> sum(n + 1, 0);
    vector<ll> dp(n + 1, 0);
    
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum[i] = sum[i-1] + w[i];
    }
    
    dp[0] = 1;  // 空集
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i-1] * 2;
        // 防止溢出，如果超过1e18就设为1e18+1
        if (dp[i] > 1000000000000000000LL) {
            dp[i] = 1000000000000000001LL;
        }
    }
    
    ll k;
    cin >> k;
    
    if (k > dp[n]) {
        cout << -1 << endl;
        return 0;
    }
    
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        if (k > dp[i-1]) {
            // 需要选第i块石头
            ans += w[i];
            k -= dp[i-1];
        }
        // 否则不选，继续
    }
    
    cout << ans << endl;
    
    return 0;
}

题目分析

题目给定 块石头，重量分别为 ，且满足一个关键性质：每块石头比前面所有石头重量之和还要重。这意味着石头重量序列满足”超级递增”性质，类似于二进制表示中的 。
这种性质保证了：任意一个可接受的重量（即某些石头的重量之和）的表示方式是唯一的。也就是说，每个石头要么选要么不选，不同的选择对应不同的总重量。

核心思路

由于每个可接受重量对应一个子集，而石头数量 ，总子集数最多为 ，远大于 ，因此不可能枚举所有子集。
但我们可以利用”超级递增”的性质：对于前 块石头，它们能组成的所有重量中，最小的非零重量是 ，最大的是前 块石头重量之和。而且，这些重量恰好是 个不同的值。
我们可以将问题转化为：在所有 种选择中，按总重量从小到大排序，找出第 个总重量（空集重量为 ，是第 个）。

递推关系

设 表示前 块石头能组成的可接受重量的个数。由于每增加一块石头，相当于在原来所有组合基础上加上或不加这块石头，所以：

初始值 （只有空集重量 ）。
同时，设 表示前 块石头的重量总和。
关键性质：由于 ，这意味着如果将第 块石头加入，新得到的重量必然大于之前所有重量。因此，所有 个重量可以分成两个连续块：前半部分不含第 块石头（重量范围 到 ），后半部分含第 块石头（重量范围 到 ）。

算法设计

从第 块石头开始，逆序考虑每一块石头是否被选中：

• 如果 ，说明目标重量在前 块石头的组合中（即不选第 块石头），继续向前搜索。
• 否则，说明目标重量必须包含第 块石头。此时从 中减去 ，并将答案加上 ，然后继续在前 块石头中搜索。
  这类似于在二进制表示中确定每一位是 还是 。