A 小奇采药 题面描述 山洞里有一些不同的草药，小奇采每一株都需要一些时间，每一株也有它自身的价值。在一段时间里，小奇可以采到一些草药，如何让采到的草药的总价值最大。
输入格式 第1行包括1个整数
对于每组数据，第1行包括2个整数
接下来n行，每行两个整数
输出格式 输出
样例输入 样例输出 数据范围 对于 对于 对于 思路分析 这道题的题面描述就是一道01背包的模板题，很容易想到套用模板并且把空间压缩到
由于 毕竟剪枝剪得好，搜索少不了，但是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 小奇取石子 题面描述 小奇最近在研究取石子游戏。
有
请问在要求总石子数不超过
输入格式 第一行输入三个数字
输出格式 输出一个数字，表示最多能取石子的个数。
样例输入 样例输出 数据范围 对于其中 对于其中 对于另 思路分析 把拿一堆石子看做两个代价：拿了一堆和拿了 好像特别喜欢卡常又给了一个特别大的
但是很容易就发现由于存在多维限制，剪枝难以进行（反正本蒟蒻想不出来），再次观察题面，发现
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 小奇的旅行计划 题面描述 小奇所在的国家一共由
小奇非常喜欢骑自行车，它常常骑着自行车从一个城市，沿着某些双向道路到达另一个城市。 （真闲得慌）
现在，这个国家要关闭其所有的道路以便翻修 （国王出来挨打） ，但为了保证必要的交通运输，第
为了更全面地评估这个影响，小奇会有多次询问，但它一下子算不过来，就只好找你帮忙了。
输入格式 第一行三个正整数
接下来有
接下来
输出格式 输出 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
数据范围 思路分析 很明显，这个题如果在线处理，每次查询只能限制在
我们先把所有数据都读进来，对于所有询问，根据 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 小奇探险 题面描述 小奇去遗迹探险，遗迹里有
小奇有地图，所以它知道每一个宝箱的价值，但是它不喜欢走回头路，所以要按顺序拿这
小奇不喜欢连续放过很多宝箱，所以任意一段长度为
输入格式 第一行，两个整数
第二行，一个小数
第三行，
输出格式 第一行，两个整数
第二行，一个小数
第三行，
样例输入 样例输出 数据范围 对于30%的数据， 对于60%的数据， 对于100%的数据， 思路分析 很容易想到定义状态
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 ; }