2020, XIII Samara Regional Intercollegiate Programming Contest

2020, XIII Samara Regional Intercollegiate Programming Contest

题目比较简单， 找几个比较难的题讲一下。

B. Bonuses on a Line

题意：

给你一些在x轴上的坐标， 每个坐标都有一些食物， 给你一个时间t， 你每秒钟可以一个单位， 刚开始你在原点(0)问在t秒之后你最多可以获得多少食物？

题解：

A: 这题是枚举状态吧？

B：是的！难点就是你要如何找到所有状态。

A: 如何找到所有状态呢？

B: 因为刚开始在0的位置， 所以先枚举在x轴左边， 最后一次到的点 ，剩下的时间走右边，

同理 ， 在枚举x轴的右边最后一次走的点 剩下时间走左边。

A: 那暴力查找会超时呀。

B：这里可以用二分取优化， 查第一个大于就行了。

代码：

#include 
using namespace std;typedef long long ll;const int N = 200000 + 7;ll n, t, a[N];
vectorpositive, negative;int main(){    ll ans = 0;scanf("%lld %lld", &n, &t);for(int i = 1; i <= n; i++){scanf("%lld", &a[i]);if(a[i] == 0){ans++;}else if(a[i] > 0){positive.push_back(a[i]);}else{negative.push_back(-a[i]);}}sort(negative.begin(), negative.end());positive.push_back(100000000000000);negative.push_back(100000000000000);// positivell cnt = t;ll res = 0;ll maxn = 0;for(int i = 0; i < positive.size() - 1; i++){if(cnt >= positive[i]){res++;ll cn =cnt - positive[i];if(cn >= positive[i]){ll cat =cn - positive[i];int p = upper_bound(negative.begin(), negative.end(), cat) - negative.begin();maxn = max(ans + res + p, maxn);}}else{break;}}maxn = max(maxn, res + ans);// negativeres = 0;cnt = t;for(int i = 0; i < negative.size() - 1; i++){if(cnt >= negative[i]){ll cn =cnt - negative[i];res++;if(cn >= negative[i]){ll cat = cn - negative[i];int p = upper_bound(positive.begin(), positive.end(), cat) - positive.begin();maxn = max(ans + res + p, maxn);}}else{break;}}maxn = max(ans + res, maxn);printf("%lld\n", maxn);}

D. Lexicographically Minimal Shortest Path

题意：

给你一张图边权是字符， 问找一个最多路径，如果有多个输出经过的边的字符字典序最小的那个。

题解：

A：这题咋想的？

B: 先求出最短路然后， 找出所有最短路径， 枚举一个字典序最小的。

A: 就是找出所有的最短路径然后再枚举？不会超时吗？

B: 不能直接找出所有的最短路径枚举， 那样肯定会超时！， 我们可以先求出来 到 n的所有点的最短路 ，

如果 有一条边 比如(u， v) dist[u] == dist[v] - 1, 那么(u, v) 这条边就可以做最短路的一条边， 找出所有可能的边，

然后从源点 (1)开始贪心枚举， 要是当前边有一个最小的就走这个， 要是有多个最小的， 就全部都走 ， 然后第二层继续枚举， 之前的走的点， 要是有多个最小的也是全部都走， 有一个就走一个， 这样的话时间复杂度最多也就是 o(m).

A：没听懂！！!

B: 我想你看我代码模拟一边会更好。

A: 好的。

#includeusing namespace std;
const int N = 200007;vector > g[N];int n, m, dist[N];queue > q;void bfs(){q.push({n, 0});memset(dist, -1, sizeof(dist));while (q.size()){auto cd = q.front();q.pop();if (dist[cd.first] != -1) continue;dist[cd.first] = cd.second;for (auto it: g[cd.first]) {int to = it.first;q.push({to, cd.second + 1});}}
}int vis[N];
vectorQ;
vector ans;
int fa[N];void path(int x){if(x == 0) return;path(fa[x]);printf("%d ", x);
}int main(){scanf("%d %d", &n, &m);for (int i = 1; i <= m; i++) {int u, v;char w;scanf("%d %d %c", &u, &v, &w);g[u].push_back({v, w});g[v].push_back({u, w});}bfs();Q.push_back(1);for (int i = 1; i <= dist[1]; i++) {int minn = 1000;vector v;for(int cd: Q) {for (auto it: g[cd]){int to = it.first;int cost = (int)it.second;if (dist[to] + 1 == dist[cd])minn = min(minn, cost);}}for(int cd: Q){for (auto it: g[cd]){int to = it.first;int cost = (int)it.second;if (dist[to] + 1 == dist[cd]) {if (cost == minn && vis[to] == 0) {v.push_back(to);fa[to] = cd;vis[to] = 1;}}}}ans.push_back(minn);Q.clear();for(int j: v){Q.push_back(j);}}printf("%d\n", (int)ans.size());path(n);puts("");for(int i: ans){printf("%c", (char)i);}puts("");}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！