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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include <bits/stdc++.h> using namespace std;#define uns unsigned #define ll long long #define use_cin_cout do {ios::sync_with_stdio (false); } 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) { 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; 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\) 。
输出格式 输出一个数字,表示最多能取石子的个数。
样例输入 样例输出 数据范围 对于其中 \(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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <bits/stdc++.h> using namespace std; #define uns unsigned #define ll long long #define use_cin_cout do {ios::sync_with_stdio (false); } 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; 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
。
样例输入 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 6 10 10 1 2 1 3 2 4 3 5 3 6 4 5 3 6 2 6 5 6 1 4 1 2 3 4 1 2 3 5 1 3 4 6 1 1 1 2 1 4 5 6 1 4 1 2 1 6 1 6 1 8 1 5 3 7 4 5 5 8 2 4
样例输出 1 2 3 4 5 6 7 8 9 10 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <bits/stdc++.h> using namespace std; #define uns unsigned #define ll long long #define use_cin_cout do {ios::sync_with_stdio (false); } 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; 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\) 个宝箱的价值。
样例输入 样例输出 数据范围 对于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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std; #define uns unsigned #define ll long long #define use_cin_cout do {ios::sync_with_stdio (false); } 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 () { 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 ; }