ABC463

赛时ABCD，补题E，D题是典型的最大化最小值的二分答案问题，但是由于看错题耽误了很久，E题是一个建立超节点的单源最短路问题

ABC

A题判断x:y是否等于16:9，一个需要注意的地方就是尽量把除法判断转化为乘法以避免精度问题（前提是不越界）
B题也是简单的判断题，循环模拟一下就行了。
C题由于时间顺序已经排好了，只需要预处理一个后缀最大值再二分查找时间即可。

D

D题出现了经典的最大化最小值描述，首先考虑二分答案，而答案显然具有单调性，越小越有可能，越大越不可能。
至于check函数的写法，先对所有布的右端点进行升序排序，然后贪心地排着取布，满足不重叠，且间距大于需要判断的值就取，如果能取够K个则为True。

Code

void sol()
{
    struct clo
    {
        int l,r,i;
    };
    
    int n,k;
    cin>>n>>k;
    vector<clo>a(n);
    for(int j=0;auto &[l,r,i]:a)
    {
        cin>>l>>r;
        i=j;
        j++;
    }
    
    sort(begin(a),end(a),[](clo x,clo y)
    {
        if(x.r==y.r)return x.l>y.l;
        return x.r<y.r;
    });

    auto check=[&](int x)
    {
        int tk=k;
        int curR=a[0].r;
        tk--;
        for(int i=1;i<n;i++)
        {
            if(a[i].l-curR>=x)
            {
                curR=a[i].r;
                tk--;
            }
            if(tk<=0)return 1;
        }
        return 0;
    };


    int l=0,r=1e9;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid))
        {
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    if(l==0)l=-1;
    cout<<l;
}

补题

E

Problem Statement

The country of AtCoder has $N$ cities and $M$ roads. The $i$-th road $(1\le i\le M)$ connects cities $u _ i$ and $v _ i$ bidirectionally, and allows travel from one to the other in $T _ i$ minutes.

Additionally, each city has a warp gate installed, and you can travel from city $i\ (1\le i\le N)$ to city $j\ (1\le j\le N)$ using the warp gate in $X _ i+X _ j+Y$ minutes.

There are no other ways to travel between cities in the country.

For each $k=2,3,\ldots,N$, solve the following problem:

• Find the minimum time required to travel from city $1$ to city $k$.

The time required to transfer from a road or warp gate to another road or warp gate at the same city is negligible.

分析：

显然这是个单最短路问题，主要考虑如何处理传送门的情况。
如果暴力将所有传送方式作为路径，形成一个稠密图，采用朴素Dijkstra复杂度则为$O(N^2)$，显然是不能接受的。
注意到传送的代价与传送起点、传送终点相关，考虑建立超节点S，从u到S代价为$X_u$，由于传送还有个常数Y，建立超节点T，从S到T代价为Y，从T到v代价为$X_v$，这样从u到v的传送就变成了$u\rightarrow S\rightarrow T\rightarrow v$。
再去跑单源最短路，由于是稀疏图，采用堆优化Dijkstra，复杂度为$O((M+2N+1)\log N)$

Code

void sol()
{
    int N,M,Y;
    cin>>N>>M>>Y;
    vector<vector<pair<int,int>>>mp(N+1);
    vector<int>X(N+1);
    vector<int>res(N+1,MAX);
    for(int i=1;i<=M;i++)
    {
        int u,v,t;
        cin>>u>>v>>t;
        mp[u].emplace_back(v,t);
        mp[v].emplace_back(u,t);
    }
    for(int i=1;i<=N;i++)
    {
        cin>>X[i];
    }
    mp[N+1].emplace_back(N+2,Y);
    for(int i=1;i<=N;i++)
    {
        mp[i].emplace_back(N+1,X[i]);
        mp[N+2].emplace_back(i,X[i]);
    }
    priority_queue<pair<int,int>>que;
    que.emplace(0,1);
    res[1]=0;
    while(que.size())
    {
        auto [t,u]=que.top();
        que.pop();
        t=-t;
        if(t>=res[u])continue;
        for(auto [v,T]:mp[u])
        {
            if(res[v]>res[u]+T)
            {
                res[v]=res[u]+T;
                que.emplace(-res[v],v);
            }
        }
    }
    for(int i=2;i<=N;i++)cout<<res[i]<<' ';
}