首页 > 其他分享 >ABC245G题解

ABC245G题解

时间:2022-11-20 22:33:07浏览次数:38  
标签:终点 颜色 题解 短路 所有 更新 ABC245G 起点

似乎是经典套路?
先不考虑颜色限制,那么就直接把 \(l\) 个关键点当作起点跑多源最短路就行了。

现在考虑颜色限制,有一种暴力的想法是枚举所有颜色,只把这种颜色的点当作起点,然后跑dijkstra,然后更新颜色不为这个的终点。
发现这样终点就被更新了很多次,考虑优化。

考虑枚举颜色的每个二进制位,把所有特殊点这一位上颜色是 \(1\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(0\) 的终点,然后倒过来,把所有特殊点这一位上颜色是 \(0\) 的加入起点,跑最短路,更新所有终点中这一位上颜色是 \(1\) 的终点。

由于两个颜色不同一定至少有一个二进制位不同,因此上述算法可以保证所有终点都被颜色不同的起点更新到。
复杂度 \(\mathcal{O}(m\log n\log k)\)。

标签:终点,颜色,题解,短路,所有,更新,ABC245G,起点
From: https://www.cnblogs.com/cooltyl/p/16909837.html

相关文章

  • Codeforces 1740 F Conditional Mix 题解
    题目链接对于任意一个multiset,我们都把它的元素从大到小排序来观察。发现一个multiset合法有个必要条件:对于每个i,multiset中最大的i个元素之和不能超过\(lim_i\),如果令\(c......
  • 2022/11/20 集训题解 Longest Loose Segment
    linkDescription定义\(a_{1,2,...,m}\)为好序列当且仅当\(\maxa_i+\mina_i>m\),给出一个长度为\(n\)的序列,问最长好序列子段长度。有\(T\)次修改。\(n\le10^6,......
  • P4047 [JSOI2010]部落划分 题解
    最小生成树做法之Kruskal算法流程(详细分析请看代码注释):1.初始化并查集并查集模板不过多解释,还不懂请参阅并查集-OIWiki。每个节点的祖先最开始都是自己。还有......
  • U255813 争宠题解
    题目传送门#include<bits/stdc++.h>usingnamespacestd;voidjia(strings1,strings2){boolaaa=0;inta[5010],b[5010],c[5010];memset(a,0,sizeof(......
  • AtCoder Beginner Contest 278题解
    A-Shift题意给一个长度为\(n\)的数组,有\(k\)次操作,每次操作会将数组最前面的元素删掉,再在数组最后面加上一个0元素,问\(k\)次操作后的数组中的数字。思路看\(n\)与\(k......
  • Codeforces 704 B Antman 题解 (dp,贪心,结论)
    题目链接这题两种不同做法,普通的\(O(n^2)\)和奇怪的\(O(nlogn)\)。如果用\(O(nlogn)\)的话可以加强到1e6。做法1时间复杂度\(O(n^2)\)先把最终的排列随便画一个出来观......
  • C. Sum of Substrings题解
    C.SumofSubstrings题目大概意思,给你一个01串,求和最小,其中和是该串所有相邻字符所组成的十进制数的和。如:0110,sum=01+11+10=22。通过观察我们可以发现,除了第......
  • cf796部分题解
    C.ManipulatingHistory题意:给出一些字符串,有原始串(只含一个字符的串)、被替换的串、替换串、最终串(最后一行),求原始串。2aabbcdacdInitiallysis"a".Inthe......
  • B - Bracket Sequence题解
    B-BracketSequence思路:用一个flag来标记括号的数目,如果括号数目是个偶数的话,就代表当前要执行'+'操作,反之就是'*'操作。对于最外层的数,是没有计算的。所以最后要单独......
  • Auxiliary Set题解
    FAuxiliarySet树上LCA+DFS注意一下输出格式!#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;intt,n,q,ans;intfa[N];//存储点i的......