网站首页
编程语言
数据库
系统相关
其他分享
编程问答
D1T3
2024-09-10
「NOI2021 D1T3 庆典」题解
uoj675加强:\(\sumk\le6\times10^5\)暴力\(u\)在\(s\Rightarrowt\)路径上\(\iff\)正图上\(s\Rightarrowu\)且反图上\(u\Rightarrowt\)时间复杂度\(O((n+m)q)\)正解只关心可达性,不妨SCC缩点成DAG。注意到一个奇怪的条件:对于三座城市\(x,y,z\),若\(x\Right
2024-08-27
NOI2024 D1T3 口胡题解
NOI2024D1T3口胡题解题目条件其实就是说对于点对\((a,b)\),从\(a\)到\(b\)的路径上至少要有一条从\(b\)指向\(a\)的边。将初始状态记作\((T,S)\),其中\(T\)是树,\(S\)是二元组\((a,b)\)的集合。注意到特殊性质A蕴含了:如果对于所有二元组\((a,b)\),\(a