首页 > 代码库 > Codeforces Round #398 (Div. 2)
Codeforces Round #398 (Div. 2)
A - Snacktower(water)
题意:一个数字在,所有比他大的数放出来以前,不能被放出来。
思路:瞎搞就好了
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 100000 + 5; 5 typedef long long LL; 6 typedef pair<int, int>pii; 7 8 int main() 9 { 10 priority_queue<int>que; 11 int n; 12 scanf("%d", &n); 13 int nn = n; 14 for(int i = 0; i < nn; i++) 15 { 16 int x; 17 scanf("%d", &x); 18 que.push(x); 19 if(x == n) 20 { 21 while(que.top() == n) 22 { 23 printf("%d ", que.top()); 24 que.pop(); 25 n--; 26 } 27 } 28 puts(""); 29 } 30 31 return 0; 32 }
B - The Queue
C - Garland(dfs)
题意:给你一棵树,每个结点上都有值,然后问你能不能把,整棵树根据值,断开两条边,平均分成三份。
思路:
第一次dfs,切掉一段,然后去边,再dfs一次就得到答案了。这题坑点比较多。如果找不到切点或者切点是根,显然是不行的。没考虑到。
用flag记录cut点而不是直接erase掉的原因是,erase一不小心 就会把迭代器弄乱掉,特别是这种搜索的写法中,要小心。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 const int maxn = 1e6 + 5; 5 typedef long long LL; 6 typedef pair<int, int>pii; 7 8 9 set<int>G[maxn]; 10 int v[maxn]; 11 LL cnt[maxn]; 12 int flag; 13 LL sum; 14 int cut; 15 16 void dfs(int cur, int pa) 17 { 18 if(cur == flag) return; 19 if(cut != -1) return ; 20 21 cnt[cur] = v[cur]; 22 for(auto o : G[cur]) 23 { 24 dfs(o, cur); 25 cnt[cur] += cnt[o]; 26 } 27 28 if(cut == -1 && cnt[cur] * 3 == sum) 29 { 30 cut = cur; 31 flag = cur; 32 } 33 } 34 int main() 35 { 36 int n, root; 37 scanf("%d", &n); 38 sum = 0; 39 for(int i = 1; i <= n; i++) 40 { 41 int pa, val; 42 scanf("%d%d", &pa, &val); 43 if(pa == 0) root = i; 44 G[pa].insert(i); 45 v[i] = val; 46 sum += val; 47 } 48 49 flag = -1; 50 cut = -1; 51 dfs(root, -1); 52 53 54 if(cut == -1 || cut == root) 55 { 56 puts("-1"); 57 } 58 else 59 { 60 int temp = cut; 61 memset(cnt, 0, sizeof(cnt)); 62 cut = -1; 63 dfs(root, -1); 64 if(cut == -1 || cut == root) puts("-1"); 65 else printf("%d %d\n", temp, cut); 66 } 67 68 69 return 0; 70 }
D - Cartons of milk
Codeforces Round #398 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。