SRM 638 Div2_html/css_WEB-ITnose
程序员文章站
2022-06-09 15:12:01
...
2333.。。
由于TC参赛数太少,加上不断的fst 我都降到div2了。
还好做完就回div1了。。
250
水题
500
水题。。
直接bfs扩展就行了
注意判重, 我还用康托展开了真是多此一举。。
1000
这题理解错题意了。。我说看别人代码怎么看着不对劲来着
不过还是非常容易的一道题
二进制枚举烧哪些叶子结点
然后对每种烧法
求最短路
求完最短路,枚举边
假设边的两个结点是u,v权值为w
就求最大的(dis[u]+dis[v]+w )/2就是烧完的时间
为啥这样呢
假设某边是最后被烧掉的,有两种情况
一种是u,v分别都是由别的结点传来的火烧过来的
一种是u被v传来的火烧过来的
第一种,不妨设dis[u] > dis[v]
答案就是( L-(dis[u] - dis[v]) ) / 2 + dis[u] = (dis[u] + dis[v] + L) / 2
第二种
dis[v] + L = dis[u]
那么同样dis[u] = (dis[v] + L + dis[u]) / 2
二者都可以用这个表示了
然后为了方便我们就不除以2了
struct node { int v, w; node () {} node (int _v, int _w) {v = _v; w = _w;}};vectorg[22];int ind[22], lea[22], pos[22], d[22], vis[22], q[1111];set s;class CandleTimerEasy{public: int differentTime(vector A, vector B, vector len) { int n = A.size() + 1; for(int i = 0; i
推荐阅读
-
Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose
-
SRM 638 Div2_html/css_WEB-ITnose
-
SRM 638 Div2_html/css_WEB-ITnose
-
Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose
-
SRM 630 DIV2_html/css_WEB-ITnose
-
SRM 400 Div1_html/css_WEB-ITnose
-
【TopCoder SRM 157 DIV 1】 Salary 解题报告_html/css_WEB-ITnose
-
【TopCoder SRM 157 DIV 1】 Salary 解题报告_html/css_WEB-ITnose
-
SRM 400 Div1_html/css_WEB-ITnose
-
TopCoder SRM 634 Div.2[ABC]_html/css_WEB-ITnose