CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. ACM-ICPC
  3. 图论
  4. 正文

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

2022年2月6日 487点热度 0人点赞 0条评论

题目链接

1738. 蹄球 - AcWing题库

题意

给出n(1\leq n\leq 100)头牛,每头牛有自己的位置x_i(1\leq x_i\leq 1000)。每头牛给两侧相邻的牛传球,规定是传给距离较小的那个,如果相同则选左边的,每个牛都需要传一次球,你可以一开始在若干个牛上放球,然后开始传,问开始需要放置多少个球使得所有牛都持球一次。

思路

有n个点,每个点传一次(这个是固定的),就是n条边。

n个点,n条边 —— 基环树

所以,这里面是若干个基环树,为什么说若干的,是因为有可能它不连通,所以我们分为两种情况:

image-20220222145755583

1)左边的情况是基环树,一棵环上接了很多树:
我们需要统计入度为0的,也就是d[i]==0的时候,这个时候我们需要放一个球,因为没有其他地方可以传入,每个入读为0的点的贡献是1

2)右边的情况就是单独的一个奇环:
我们只需要一次就可以传遍这两个,我们在for循环的时候每个点的贡献是0.5,为了整数计算,我们可以选择+1之后让i++达到continue效果,也可以+1并且让第一种情况的贡献+2,最后输出的时候除以2即可

基环树

基环树示意图

代码

1)思维计算贡献

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    a[0]=-inf;a[n+1]=inf;//这样可以让第一个点传给第二个,最后一个给前一个
    for (int i=1;i<=n;i++)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i]) e[i]=i+1,d[i+1]++;
        else e[i]=i-1,d[i-1]++;//e[i]统计传给哪个点,d[i]统计入度
    }
    for (int i=1;i<=n;i++)
        if (e[e[i]]==i&&d[i]==1&&d[e[i]]==1) ans++;//第二种情况,两个点的环,入度均为1
        else if (!d[i]) ans+=2;
    cout<<ans/2;
}

2)拓扑思想dfs

inline void dfs(int x)
{
    vis[x]=1;
    if (!vis[e[x]]) dfs(e[x]);
}//dfs用来遍历可以达到的
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    e[1]=2;e[n]=n-1;
    for (int i=2;i<n;i++)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i]) e[i]=i+1;
        else e[i]=i-1;
    }
    for (int i=1;i<=n;i++) ind[e[i]]++;
    for (int i=1;i<=n;i++)
        if (!ind[i]) ans++,dfs(i);//拓扑 第一种情况,入度为0就开始放置球遍历
    for (int i=1;i<=n;i++)
        if (!vis[i]) ans++,dfs(i);//还没有达到的 也需要放球,这个就是第二种情况
    cout<<ans;
}
标签: AcWing寒假每日一题 基环树 思维
最后更新:2022年7月12日

Carry

来自于湖南长沙

点赞
下一篇 >

文章评论

取消回复
标签
AcWing寒假每日一题 基环树 思维
文章目录
  • 题目链接
  • 题意
  • 思路
  • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

【双端队列广搜/搜索+图论】AcWing 2019.拖拉机 USACO 2012 March Contest Silver Division

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS