2019icpc沈阳区域赛 A + H题

2019icpc沈阳区域赛 A + H题

​​题目链接​​

A题

题意：

小伙找女朋友，看n个照片，每个照片有欺骗值，现在要更新真实值。对于第i个照片，前i - 1个比它欺骗值大的照片中的最小欺骗值为它的真实值。如果没有比它大的，那它的真实值就为0。

思路：

对于前i - 1个数，我们用set储存，同时使用set的自带函数upper_bound。 这里需要用iterator迭代器将值表示出来。 upper_bound返回的是储存地址，最后要用*来获取实际值。 具体看代码。

#include #include #include #include #include using namespace std;long long v[100005];sets;int main(){ int n; scanf("%d", &n); int cnt = 0; long long sum = 0; for(int i = 0; i < n; i++) { long long x; scanf("%lld", &x); set ::iterator it; it = s.upper_bound(x); if(it != s.end()){ sum += *it; } s.insert(x); } printf("%lld\n", sum); return 0;}

H题

题意:

给你一颗树，找到有几个叶子结点。

思路:

图论基础题，vector建立邻接表即可。

​​#include #include #include using namespace std; vectorv[100005]; int main() { int n; cin >> n; for(int i = 0;i < n - 1;i++){ int x; int y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); } int cnt = 0; for(int i = 1;i <= n;i++){ if(v[i].size() == 1)cnt++; } cout << cnt << endl; return 0; } ​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。