2021.10.5 pm模拟赛题解

发表于 2022-07-13 分类于信奥，题解阅读次数：

A 小奇采药 \(herb\)

题面描述

山洞里有一些不同的草药，小奇采每一株都需要一些时间，每一株也有它自身的价值。在一段时间里，小奇可以采到一些草药，如何让采到的草药的总价值最大。

输入格式

第1行包括1个整数 \(T\) ，表示数据组数。

对于每组数据，第1行包括2个整数 \(n,m\) ，表示草药的数目和能用于采药的时间。

接下来n行，每行两个整数 \(ti,vi\) 。保证 \(m,t_i,v_i\) 在限制范围内均匀随机生成。

输出格式

输出 \(T\) 行，每行1个数字，表示每组数据答案。

样例输入

样例输出

数据范围

对于 \(30 \%\) 的数据， \(1 \leq n \leq 20,1 \leq m,ti,vi \leq 10^4\) ;
对于 \(60 \%\) 的数据， \(1 \leq n \leq 100,1 \leq m,ti,vi \leq 10^5\) ;
对于 \(100 \%\) 的数据， \(1 \leq T \leq 10,1 \leq n \leq 150,1 \leq m,ti,vi \leq 10^9\) 。

思路分析

这道题的题面描述就是一道01背包的模板题，很容易想到套用模板并且把空间压缩到 \(\Theta (m)\) ，时间复杂度 \(\Theta (nm)\) ，但是看到后 \(40 \%\) 的数据范围， \(1 \leq m,ti,vi \leq 10^9\) ， \(m\) 太大了，空间和时间都会炸掉，所以考虑与 \(m\) 无关的算法。

由于 \(n \leq 150\) ，可以想到深搜，~~毕竟剪枝剪得好，搜索少不了~~，但是150还是有点大，需要进行可行性剪枝和最优化剪枝，其中最优化剪枝需要先行排序。由于题目说了随机生成，所以剪枝被卡的概率微乎其微。

AC代码

code

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

#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio (false); /*cin.tie();*/ } while (false)
#define endl '\n'

const ll mod = 1e9 + 7, inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, maxn = 2e2 + 5;

struct node {
    int t, v;
};

int T, n;
ll ans, m;
node a[maxn];
ll st[maxn], sv[maxn];

bool compare (node x, node y) {
    return x.t > y.t;
}

void dfs (int nod, ll t, ll v) { //t为时间和，v为价值和
    ans = max (ans, v);
    if (t + a[n].t > m) return; //可行性剪枝
    if (v + sv[nod] < ans) return; //最优化剪枝
    if (t + st[nod] <= m) {
        ans = max (ans, v + sv[nod]); //剩下的全选
        return;
    }
    if (t + a[nod].t <= m) dfs (nod + 1, t + a[nod].t, v + a[nod].v);
    dfs (nod + 1, t, v);
}

int main () {
	use_cin_cout;
	// freopen ("herb.in", "r", stdin);
	// freopen ("herb.out", "w", stdout);
	cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].t >> a[i].v;
        }
        sort (a + 1, a + n + 1, compare);
        sv[n + 1] = st[n + 1] = 0;
        for (int i = n; i >= 1; i--) {
            st[i] = st[i + 1] + a[i].t;
            sv[i] = sv[i + 1] + a[i].v;
        }
        ans = 0;
        dfs (1, 0, 0);
        cout << ans << endl;
    }
	return 0;
}

B 小奇取石子 \(stone\)

题面描述

小奇最近在研究取石子游戏。

有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗，最多取 \(m\) 堆石子（保证 \(m \leq n\) ）。

请问在要求总石子数不超过 \(k\) 颗的情况下最多能取多少石子。

输入格式

第一行输入三个数字 \(n,m,k\) ，意义见上。第二行 \(n\) 个数字，依次表示 \(a_i\) 。

输出格式

输出一个数字，表示最多能取石子的个数。

样例输入

1 2	4 3 5 1 1 2 3

样例输出

数据范围

对于其中 \(30 \%\) 的数据，\(1 \leq m \leq n \leq 10,1 \leq k \leq 1000,1 \leq ai \leq 100\) ;
对于其中 \(30 \%\) 的数据， \(1 \leq m \leq n \leq 20,1 \leq k \leq 10^8,1 \leq ai \leq 10^6\) ;
对于另 \(40 \%\) 的数据， \(1 \leq m \leq n \leq 200,1 \leq k \leq 2500,1 \leq ai \leq 50\) 。

思路分析

把拿一堆石子看做两个代价：拿了一堆和拿了 \(a_i\) 个。由于题目说了最多取 \(m\) 堆石子，总石子数不超过 \(k\) 颗，这道题就可以转化成一个多维限制的01背包，空间复杂度 \(\Theta (mk)\) ，时间复杂度 \(\Theta (nmk)\) 。但是这套卷子~~好像特别喜欢卡常~~又给了一个特别大的 \(k\) ，所以跟第一题一样，考虑深搜。

但是~~很容易就发现~~由于存在多维限制，剪枝难以进行（反正本蒟蒻想不出来），再次观察题面，发现 \(k\) 非常大的时候 \(n\) 非常小，所以可以把 \(k > 2500\) 的情况进行深搜，把 \(k \leq 2500\) 的情况进行dp，时间复杂度 \(\Theta (nmk)\) 或 \(\Theta (2^n)\) 。

AC代码

code

#include <bits/stdc++.h>
using namespace std;
 
#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio (false); /*cin.tie();*/ } while (false)
#define endl '\n'
 
const ll mod = 1e9 + 7, inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, maxn = 2e2 + 5, maxm = maxn, maxk = 2.5e3 + 5;
 
int n, m, k;
int a[maxn];
ll dp[maxm][maxk];
 
ll dfs (int x, int y, int z) {
    if (z > k) return 0;
    if (y > m) return 0;
    if (x > n) return z;
    return max (dfs (x + 1, y, z), dfs (x + 1, y + 1, z + a[x]));
}
 
int main () {
    use_cin_cout;
    // freopen ("herb.in", "r", stdin);
    // freopen ("herb.out", "w", stdout);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (k <= 2500) {
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 1; j--) {
                for (int _k = k; _k >= a[i]; _k--) {
                    dp[j][_k] = max (dp[j][_k], dp[j - 1][_k - a[i]] + a[i]);
                }
            }
        }
        cout << dp[m][k] << endl;
    }
    else {
        cout << dfs (0, 0, 0) << endl;
    }
    return 0;
}

C 小奇的旅行计划 \(plan\)

题面描述

小奇所在的国家一共由 \(n\) 个城市和 \(m\) 条连接这些城市的双向道路组成。

小奇非常喜欢骑自行车，它常常骑着自行车从一个城市，沿着某些双向道路到达另一个城市。 ~~（真闲得慌）~~

现在，这个国家要关闭其所有的道路以便翻修 ~~（国王出来挨打）~~ ，但为了保证必要的交通运输，第 \(i\) 条道路会在第 \(i\) 天暂时开放。小奇为了了解本次翻修对它旅行的影响，因此想知道，如果它第 \(L\) 天在一个城市 \(S\) ，在第 \(R\) 天或之前是否能到达城市T。（小奇不需要第 \(L\) 天就立即离开，也不需要恰好在第 \(R\) 天到达城市。）

为了更全面地评估这个影响，小奇会有多次询问，但它一下子算不过来，就只好找你帮忙了。

输入格式

第一行三个正整数 \(n,m,q\) ，分别表示城市数、道路数、询问数。

接下来有 \(m\) 行，其中第 \(i\) 行有两个正整数 \(u_i,v_i(u_i \ne v_i)\) ，表示有一条连接 \(u_i,v_i\) 两座城市的双向道路，并且这条道路在第 \(i\) 天暂时开放，不保证整张图连通，不保证有且仅有一条道路连接 \(u_i,v_i\) 两座城市。

接下来 \(q\) 行，每行四个正整数 \(L_i,R_i,S_i,T_i\) ，表示一次询问。

输出格式

输出 \(q\) 行，第 \(i\) 行表示第 \(i\) 次询问的答案，可行输出Yes，不可行输出No。

样例输入

样例输出

No
No
No
Yes
No
Yes
Yes
Yes
Yes
No

数据范围

对于 \(30 \%\) 的数据， \(2 \leq m,q \leq 2000\) 。
对于 \(100 \%\) 的数据， \(2 \leq n \leq 1000,1 \leq m,q \leq 2 \times 10^5,1 \leq Li \leq Ri \leq m,1 \leq Si,Ti \leq n,Si \ne Ti\) 。

思路分析

很明显，这个题如果在线处理，每次查询只能限制在 \(O (n)\) 以内，但是无论怎么设计算法都得与 \(m\) 相关，所以考虑 \(O (nm)\) 的离线算法。

我们先把所有数据都读进来，对于所有询问，根据 \(l\) 从大到小排序，然后从 \(m\) 到 1 枚举每一条边，看看这一条边能够使得哪些点相连，则这两个点之间通行的开始时间就是枚举到的边的序号，然后用一个 \(date\) 数组储存两个点之间通行的结束时间。再枚举所有开始时间为边序号的查询，如果这两点通行的结束时间比要求的结束时间短，那么输出Yes，否则输出No。

AC代码

code

#include <bits/stdc++.h>
using namespace std;
 
#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio (false); /*cin.tie();*/ } while (false)
#define endl '\n'
 
const ll mod = 1e9 + 7, inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, maxn = 1e3 + 5, maxm = 2e5 + 5, maxq = maxm;
 
struct edge {
    int u, v;
};
 
struct question {
    int l, r, s, t, i;
};
 
int n, m, q;
edge e[maxm];
question ques[maxq];
int date[maxn][maxn];
bool ans[maxq];
 
bool compare (question a, question b) {
    return a.l > b.l;
}
 
int main () {
    use_cin_cout;
    // freopen ("plan.in", "r", stdin);
    // freopen ("plan.out", "w", stdout);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v;
    }
    for (int i = 1; i <= q; i++) {
        cin >> ques[i].l >> ques[i].r >> ques[i].s >> ques[i].t;
        ques[i].i = i;
    }
    sort (ques + 1, ques + q + 1, compare);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            date[i][j] = inf;
        }
    }
    int p = 1;
    for (int i = m; i >= 1; i--) {
        date[e[i].u][e[i].v] = date[e[i].v][e[i].u] = i;
        for (int j = 1; j <= n; j++) {
            date[e[i].u][j] = date[e[i].v][j] = min(date[e[i].u][j], date[e[i].v][j]);
        }
        while (p <= q && ques[p].l == i) {
            ans[ques[p].i] = (date[ques[p].s][ques[p].t] <= ques[p].r);
            p++;
        }
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

D 小奇探险 \(explore\)

题面描述

小奇去遗迹探险，遗迹里有 \(n\) 个宝箱，有的装满了珠宝，有的装着废品。

小奇有地图，所以它知道每一个宝箱的价值，但是它不喜欢走回头路，所以要按顺序拿这 \(n\) 个宝箱中的若干个。拿宝箱很累的。一开始小奇的体力是 \(1\) ，每得到一个宝箱之后，小奇得到的价值是体力 \(\times\) 宝箱的价值，之后它的体力就会变为原来的 \(k\) 倍 \((0<k<1)\) 。

小奇不喜欢连续放过很多宝箱，所以任意一段长度为 \(m\) 的序列中，小奇一定要取走其中的一个宝箱。现在小奇想知道它能得到的最大价值和。

输入格式

第一行，两个整数 \(n,m\) ，表示的含义如题目中所述。

第二行，一个小数 \(k\) ，表示的含义如题目中所述，最多4位小数。

第三行， \(n\) 个整数，第 \(i\) 个整数 \(v_i\) 表示第 \(i\) 个宝箱的价值。

输出格式

第一行，两个整数 \(n,m\) ，表示的含义如题目中所述。

第二行，一个小数 \(k\) ，表示的含义如题目中所述，最多4位小数。

第三行， \(n\) 个整数，第 \(i\) 个整数 \(v_i\) 表示第 \(i\) 个宝箱的价值。

样例输入

1
2
3

3 2
0.1
1 2 3

样例输出

2.30

数据范围

对于30%的数据， \(1 \leq n \leq 10\) ；
对于60%的数据， \(1 \leq n \leq 1000\) ；
对于100%的数据， \(1 \leq n \leq 100000,1 \leq m \leq n,0<k<1,-10^9 \leq vi \leq 10^9\) 。

思路分析

~~很容易想到~~定义状态 \(f(i)\) 表示前 \(i\) 个宝箱的最大价值，但是取走前面的会对后面的宝箱产生影响，不满足无后效性的要求，所以考虑用 \(f(i)\) 表示后 \(i\) 个宝箱的最大价值。由于每 \(m\) 个宝箱至少取走一个，那么 \(f(i) = max (f(i + 1),...,f(i + m)) * k + v(i)\) ，这样就有了状态转移方程，然后考虑优化，因为 \(\Theta (nm)\) 是绝对过不了的。在求最大值的过程中，我们可以用单调队列进行维护，相当于在一个长度为 \(m\) 的滑动窗口中求出最大值，这样时间复杂度就是 \(\Theta (n)\) 。

AC代码

code

#include <bits/stdc++.h>
using namespace std;
 
#define uns unsigned
#define ll long long
#define use_cin_cout do {ios::sync_with_stdio (false); /*cin.tie();*/ } while (false)
#define endl '\n'
 
const ll mod = 1e9 + 7, inf_ll = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f, maxn = 1e5 + 5;
 
deque<int> q;
int n, m;
int v[maxn];
double ans = -inf, k, dp[maxn];
 
int main () {
    // freopen ("explore.in", "r", stdin);
    // freopen ("explore.out", "w", stdout);
    scanf ("%d%d", &n, &m);
    scanf ("%lf", &k);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &v[i]);
    }
    q.push_back (n + 1);
    for (int i = n; i >= 1; i--) {
        while (!q.empty () && q.front () > i + m) q.pop_front ();
        dp[i] = dp[q.front ()] * k + (double)v[i];
        while (!q.empty () && dp[q.back ()] <= dp[i]) q.pop_back ();
        q.push_back (i);
    }
    for (int i = 1; i <= m; i++) ans = max (ans, dp[i]);
    printf ("%.2lf\n", ans);
    return 0;
}