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

题意

限制

思路

代码