CodeForces722C

梦里梦外; 2023-06-02 11:56 34阅读 0赞

[CodeForces722C][]

其实这个题我是不大会的....我一直在想怎么正面突破,然后我就冇了.  
康了康\\(dalao\\)们的做法,发现这个题反着做是个很简单的题.  
你考虑把删除操作换成倒着加入,然后就变成了一个序列合并问题.  
每次加入一个数,只需要向左向右分别判断是否已经加入过数字,  
如果加入过,就合并两个并查集,否则什么都不做.  
同时维护一下并查集的权值——区间和.(体现在并查集上是子树和.)  
最后倒序输出答案即可,不要忘记最后全部删除完成之后是\\(0\\).

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <map> #define int long long using std::max ; const int N = 1e5 + 100 ; int n , v[N] , p[N] , ans[N] , f[N] , s[N] , maxx , cnt ; inline int getf (int x) { return f[x] == x ? x : f[x] = getf ( f[x] ) ; } signed main () { scanf ("%lld" , & n ) ; for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & v[i] ) ; for (int i = 1 ; i <= n ; ++ i) scanf ("%lld" , & p[i] ) ; for (int i = n ; i >= 1 ; -- i) { int cur = p[i] ; if ( ! f[cur] ) { f[cur] = cur ; s[cur] = v[cur] ; } int y = getf ( cur ) ; if ( cur - 1 >= 1 && f[cur-1] ) { int x = getf ( cur - 1 ) ; if ( x != y ) f[x] = y , s[y] += s[x] , s[x] = 0 ; } if ( cur + 1 <= n && f[cur+1] ) { int x = getf ( cur + 1 ) ; if ( x != y ) f[x] = y , s[y] += s[x] , s[x] = 0 ; } maxx = max ( maxx , s[cur] ) ; ans[++cnt] = maxx ; } for (int i = n - 1 ; i >= 1 ; -- i) printf ("%lld\n" , ans[i] ) ; puts ("0") ; system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11394892.html

[CodeForces722C]: http://codeforces.com/problemset/problem/722/C

发表评论取消回复

表情：

评论列表（有 0 条评论，34人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces 722E 组合数学 DP

题意：有一个n \ m的棋盘，你初始在点(1, 1)，你需要去点(n, m)。你初始有s分，在这个棋盘上有k个点，经过一次这个点分数就会变为s / 2(向上取整），问从起点到终

冷不防/ 2023年08月17日 17:22/ 0 赞/ 158 阅读

相关 Codeforces 1204C

题意略。思路：我的想法是逐步地找出这个序列中的重要点，我要判断当前这个点能不能删去，就要看上一个重要点和当前这个点 i 在序列中的下一个点 i + 1之间的距离是否是最

忘是亡心i/ 2023年08月17日 16:37/ 0 赞/ 156 阅读

相关 CodeForces1214C

[CodeForces1214C][] 是个不是很难的题目. 首先考虑如果左右括号数量不匹配那么肯定无论如何都不能通过移动一个括号完成匹配. 否则,我们考虑,将所有

淩亂°似流年/ 2023年06月02日 11:58/ 0 赞/ 188 阅读

相关 CodeForces722C

[CodeForces722C][] 其实这个题我是不大会的....我一直在想怎么正面突破,然后我就冇了. 康了康\\(dalao\\)们的做法,发现这个题反着做是个很简

梦里梦外;/ 2023年06月02日 11:56/ 0 赞/ 34 阅读

相关 722-深入掌握C++智能指针

智能指针介绍学习C++的人，一直在接触裸指针，一边感受着它的强大，一边感受着它的坑爹。当然，坑不坑爹在于我们开发者，指针本身近乎完美，但奈何用的人不理解，给自己埋下无数

拼搏现实的明天。/ 2022年09月17日 04:27/ 0 赞/ 151 阅读

相关 722 删除注释（模拟）

1. 问题描述：给一个 C++ 程序，删除程序中的注释。这个程序source是一个数组，其中source\[i\]表示第i行源码。这表示每行源码由\\n分隔。在 C++

￡神魔★判官ぃ/ 2022年09月09日 13:53/ 0 赞/ 180 阅读

相关 codeforces 567C

mp2存放每个数当中间的数的次数，对每个数，如果有a\[i\]%k==0，那么ans就加上mp2\[a\[i\]/k\]，mp表示这个数当第一个数的次数，对每个数，如果有a\[

深碍√TFBOYSˉ_/ 2022年08月04日 05:10/ 0 赞/ 179 阅读

相关 CodeForces 144C

问题描述: A string t is called an anagram of the string s, if it is possible to rearrange l

亦凉/ 2022年06月04日 06:51/ 0 赞/ 208 阅读

相关 nyoj--722-数独

数独时间限制： 1000 ms | 内存限制： 65535 KB 难度： 4 描述数独是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×

心已赠人/ 2022年05月29日 05:57/ 0 赞/ 213 阅读

相关 CodeForces 455C

题意：给定N，M和Q，N表示有N个城市，M条已经修好的路，修好的路是不能改变的，然后是Q次操作，操作分为两种，一种是查询城市x所在的联通集合中，最长的路为多长。二是连接两个联

谁借莪１个温暖的怀抱￠/ 2021年10月18日 08:38/ 0 赞/ 272 阅读