这道题做法很简单,年鉴上讲的很复杂的样子……
首先第一问,对于每个节点来说,他肯定要比自己的后继先,在此基础上越往后越好(尽量满足限制严格的其他点)
那么可以将一个节点i的k更新为min(k[i],k[j]-1)j为i的后继
注意更新的时候要按照拓扑序来,否则有可能更新不完全//他儿子还没更新完就更新他了
//我一开始没有注意拓扑序,后面懒得改了仿照Bellman-Ford在外面再套了一层控制次数,于是超慢……
最后按照这个k排序输出即可,可以证明这样一定满足条件
重点是第二问
对于每个点i,首先DFS一下,那么他肯定要放在他这棵子树的所有点的后面 //实际上不是棵树,但还是认为是一棵树吧
记当前答案为ans ,已经放了cnt个点了,那么初始cnt=ans,然后每访问一个没放到序列中的点,cnt++
然后对于其他的点,按照第一问求得的k从小到大访问
有可能存在点的k>ans,意味着这个点一定要放在ans前面,那么ans++
还有可能存在点的k<=cnt,也就是说点i无论如何一定要放在这个点后面,否则怎样都无法满足,那么ans=k+1
然后搞定……
分享到:
相关推荐
noi2010测试数据
NOI2010竞赛知识点导图
NOI题库1.6一些题目,可供初学者参考
NOI大纲NOI大纲NOI大纲.pdf
noi2010-网上同步赛2
个人写的,求Rp+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
NOI2021Day2
noi2009测试数据
noi2006测试数据
NOI2004测试数据
noi2005测试数据
noi2008测试数据
NOI 2021基础知识题库 NOI官网发布版.pdf
【ACM/NOI/CSP】NOI嘉年华 solution and code of NOI比赛经验分享&代码程序资源 ACM/NOI/CSP比赛经验分享&代码程序资源 说明:solution and code of NOI 文件列表: NOI嘉年华\NOI嘉年华.docx (61480, -04-26) NOI...
AFO后发福利,noi模拟题(有代码,有解题报告,有大样例),可对拍
noi2002测试数据
noi2001测试数据
NOI2011测试数据
noi2002题目、标准程序、
NOI笔试复习题.pdf