欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

SRM 638 Div2_html/css_WEB-ITnose

程序员文章站 2022-06-03 12:18:09
...
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 
相关标签: SRM 638 Div2