Codeforces Round #710 (Div. 3) F. Triangular Paths

題意

有一個無限高度的三角形，頂端編号為\((1,1)\)，第\(r\)層有\(r\)個點，從左至右按順序\(c\)編号為\((r,c)\)，如圖所示

對于每個節點\((r,c)\)，都有兩條連接配接下一層相鄰節點\((r+1,c),(r+1,c+1)\)的單向邊，但這兩條邊在同一時間隻有一條是有效邊，且隻有有效邊能夠通過

初始時，如果\(r+c\)是偶數，那麼\((r,c)\rightarrow (r+1,c)\)是有效邊；如果是奇數，那麼\((r,c)\rightarrow (r+1,c+1)\)是有效邊

你可以改變從某個點出發的有效邊（若原來指向左邊則現在指向右邊，反之指向左邊），這需要産生花費\(1\)

現給定\(n\)個點，保證在不考慮有效邊的前提下，一定存在一條單向路徑能夠同時通過這\(n\)個點

問如果按任意順序經過全部\(n\)個點，最小花費是多少

限制

\(1\le T\le 10^4\)

\(1\le n\le 2\cdot 10^5\)

\(1\le r_i\le 10^9\)

\(1\le c_i\le r_i\)

\(\sum n\le 2\cdot 10^5\)

思路

淦讀錯題了，是道水題，又是差點ak的一次。。。

由于這是一個單向圖，且根據題意，每走過一條邊行數一定會增加\(1\)

又因為保證在不考慮有效邊的前提下，一定存在一條單向路徑能夠同時通過這\(n\)個點，是以每個點的經過順序一定是确定的

是以按照層數對\(n\)個點進行排序，然後按順序處理即可

根據題意的初始有效邊分布，可繪出下圖

因為一定存在一條路徑

往左下走會使得\(r-c\)值\(+1\)，\(c\)值不變

往右下走則會使得\(c\)值\(+1\)，\(r-c\)值不變

是以可以得到：每個經過的點的\(c\)與\(r-c\)值一定是非遞減的

于是可以分類讨論“上一點”與“下一點”之間的關系來計算答案

假如“上一點\((r_a,c_a)\)”與“下一點\((r_b,c_b)\)”的\(r-c\)值相同

說明路徑隻有可能是全部按照\((r,c)\rightarrow (r+1,c+1)\)進行移動

那麼讨論\(r-c\)的奇偶性：

如果\(r-c\)為奇數，那麼在初始圖中兩點間剛好全是有效邊，不需要産生任何花費

如果\(r-c\)為偶數，那麼沒有路徑上沒有任何一條邊是有效邊，将會産生\(c_b-c_a\)的花費

假如“上一點\((r_a,c_a)\)”與“下一點\((r_b,c_b)\)”的\(r-c\)值不同

這裡可以将\(\lfloor\frac{r-c}2\rfloor\)值相同的所有點看作一組，那麼産生的花費就是這兩個點跨越的組的數量

如果上一點的\(r_a-c_a\)值為偶數，則花費增加\(\lfloor\frac{\Delta (r-c)}2\rfloor\)

如果上一點的\(r_a-c_a\)值為奇數，則花費增加\(\lfloor\frac{\Delta (r-c)+1}2\rfloor\)

代碼

(109ms/2000ms)

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int r,c,d;
    bool operator < (const node& a)
    {
        return r<a.r;
    }
}ar[200050];

void solve()
{
    int n;
    cin>>n;
    
    ar[0]={1,1,0};
    for(int i=1;i<=n;i++)
        cin>>ar[i].r;
    for(int i=1;i<=n;i++)
    {
        cin>>ar[i].c;
        ar[i].d=ar[i].r-ar[i].c;
    }
    
    sort(ar+1,ar+1+n);
    
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(ar[i].d==ar[i-1].d)
        {
            if(ar[i].d%2==0)
                ans+=ar[i].c-ar[i-1].c;
        }
        else
        {
            if(ar[i-1].d%2==0)
                ans+=(ar[i].d-ar[i-1].d)/2;
            else
                ans+=(ar[i].d-ar[i-1].d+1)/2;
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;while(T--)
        solve();
    return 0;
}

https://blog.csdn.net/qq_36394234/article/details/115223089

Codeforces 1506F - Triangular Paths

題意

限制

思路

代碼