挑战赛 #32 | 非官方题解

杰杰

2026-06-07 22:01:59

发布于：香港

13阅读

0回复

0点赞

挑战赛 #32 题解 | 非官方

本次题目猜测的总体难度如下，仅供参考：

题目编号	题目标题	难度
T1	项目计划	$\color{red}{入门}$
T2	千载难逢的良缘	$\color{red}{入门}$
T3	保险金	$\color{orange}{普及-}$
T4	晋级赛	$\color{orange}{普及-}$
T5	科技展示	$\color{orange}{普及-}$
T6	活动筹备计划	$\color{yellow}{普及/提高-}$

T1. 项目计划

题目大意

一共有 $n$ 个任务，完成每个任务需要一定的时间，问总共需要多久完成。

解题思路

直接输入，将总时间换为秒，再转换成要求输出即可。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
 
signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, m; scanf("%lld %lld",&n,&m);
    int hh, mm, ss;
    scanf("%lld:%lld:%lld",&hh,&mm,&ss);
    int a = (n + m - 1) / m;
    int t = hh * 3600 + mm * 60 + ss;
    t *= a;
    int a1 = t / 3600;
    int a2 = (t % 3600) / 60;
    int a3 = t % 60;
    cout << a1 << ":" << a2 << ":" << a3;
    return 0;
}

时间复杂度： $O(1)$

T2. 千载难逢的良缘

题目大意

给你 $n$ 个正整数，求出绝对值最小的两个数的差。

解题思路

先排序，然后遍历一遍，用一个 $\text{min}$ 记录最小值。并用 $\text{abs}$ 计算绝对值。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
 
int a[N];
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
     	cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int minn = INT_MAX, mina, minb;
    for(int i = 1; i < n; i++) {
     	if(abs(a[i + 1] - a[i])	< minn) {
         	minb = a[i + 1];
            mina = a[i];
            minn = abs(a[i + 1] - a[i]);
        }
    }
    cout << minn << endl;
    cout << mina << " " << minb;
    return 0;
}

时间复杂度： $O(n\log n)$

T3. 保险金

题目大意

按顺序逐个处理客户，同一客户的事故金额从小到大排序后依次发放。在当天总额不超过 $T$ 的前提下，能发几笔发几笔，一旦超额立刻停止。

解题思路

利用贪心算法，将保险金排序，依照顺序遍历即可。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
 

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    int n; cin >> n;
    bool q = false;
    int cur = 0, cnt = 0;
    for(int i = 1; i <= n; i++) {
     	int id, m; cin >> id >> m;
        int a[m + 1];
        for(int j = 1; j <= m; j++) {
         	cin >> a[j];   
        }
        if(q) continue;
        sort(a + 1, a + m + 1);
        bool ok = true;
        vector<int> p;
        for(int j = 1; j <= m; j++) {
         	if(cur + a[j] <= T) {
             	cur += a[j];
                cnt++;
                p.push_back(a[j]);
            } else {
             	ok = false;
                break;
            }
        }
        if(!p.empty()) {
         	cout << setfill('0') << setw(7) << id; 
            for(int j = 0; j < p.size(); j++) cout << " " << p[j];
            cout << endl;
        }
        if(!ok) q = true;
    }
    cout << cnt << " " << cur;
    return 0;
}

时间复杂度： $O(n \times m \log m)$

T4. 晋级赛

题目大意

给你 $n$ 个数， $T$ 组测试样例中求出小于 $x$ 的个数。

解题思路

可以使用 lower_bound() 函数，找出第一个不小于 $x$ 的值的下标即可。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000010;
 
int a[N];
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    while(q--) {
    	int x; cin >> x;
        cout << lower_bound(a + 1, a + n + 1, x) - a - 1 << endl;
    }
    return 0;
}

时间复杂度： $O(n \log n + q \log n)$

T5. 科技展示

题目大意

从编号为 $1 \sim n$ 的展品中非重复地选出 $m$ 件，要求以每行升序的形式列出所有可能的选取方案。

解题思路

经典全排列，直接使用 $dfs$ 遍历所有可能性。

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;
 
int n, m;
bool vis[100];
int a[100];

void dfs(int p, int d) {
    if (p == m + 1){
        for(int i = 1; i <= m; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
        return ;
    }
    for(int i = d + 1; i <= n; i++) {
        if(!vis[i]) {
            a[p] = i;
            vis[i] = true;
            dfs(p + 1, i);
            vis[i] = false;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}

时间复杂度： $O(m \times \large{\frac{n}{m}})$ 。

T6. 活动筹备计划

题目大意

有 $n$ 天，每天有三种任务可以选择，而每天都有这个任务可以获得的值。不能连续两天选择同意项，而两天之间选择都会有加成。

解题思路

定义 $dp[i][j]$ 为，在第 $i$ 天选择任务 $j$ 能获得的最大值。转移的时候第 $i$ 天得值会由 $i-1$ 天转移过来。以下为选择任务 $1$ 的转移方程为：

$\large{dp[i][1]} = a[i] + \max_{u \neq v}(dp[i - 1][2] + w[2][1], dp[i - 1][3] + w[3][1])$

参考代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200010;

int dp[N][3];
int w[5][5];
int a[N], b[N], c[N];
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= 3; i++) {
     	for(int j = 1; j <= 3; j++) {
         	cin >> w[i][j];   
        }
    }
    for(int i = 1; i <= n; i++) {
     	cin >> a[i] >> b[i] >> c[i];   
    }
    dp[1][1] = a[1];
    dp[1][2] = b[1];
    dp[1][3] = c[1];
    for(int i = 2; i <= n; i++) {
    	dp[i][1] = a[i] + max(dp[i - 1][2] + w[2][1], dp[i - 1][3] + w[3][1]);	  
        dp[i][2] = b[i] + max(dp[i - 1][1] + w[1][2], dp[i - 1][3] + w[3][2]);	
        dp[i][3] = c[i] + max(dp[i - 1][1] + w[1][3], dp[i - 1][2] + w[2][3]);	 
    }
    cout << max({dp[n][1], dp[n][2], dp[n][3]});
    return 0;
}