每日一题冲刺大厂第二十天提高组 最大食物链计数

简介: 大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题提高组是为了有余力的同学准备的,让大家练到各种各样的题目,一年以后,蜕变成为一个不一样的自己!

今日题目:食物链


给你一个食物网,你要求出这个食物网中最大食物链的数量。


(这里的“最大食物链”,指的是生物学意义上的食物链,即最左端是不会捕食其他生物的生产者,最右端是不会被其他生物捕食的消费者。)


Delia 非常急,所以你只有 11 秒的时间。


由于这个结果可能过大,你只需要输出总数模上 80112002 的结果。


输入格式


第一行,两个正整数 n、m,表示生物种类 n 和吃与被吃的关系数 m。


接下来 m 行,每行两个正整数,表示被吃的生物A和吃A的生物B。


输出格式


一行一个整数,为最大食物链数量模上 80112002 的结果。


题目分析


题目难度:⭐️⭐️⭐️


题目涉及算法:拓扑排序,记忆化搜索。


ps:有能力的小伙伴可以尝试优化自己的代码或者一题多解,这样能综合提升自己的算法能力


题解报告:


1.思路


拓扑排序的板子,数据范围不大所以开了个二维数组哈哈哈,第二个是记忆化搜索


2.代码


#include<bits/stdc++.h>
using namespace std;
const int N = 5005; 
int n,m,ru[N],chu[N],a,b,f[N],ans;
int mp[N][N];
queue<int>q;
int main()
{
  cin>>n>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>a>>b;
    mp[a][b]=1;
    chu[a]++;
    ru[b]++;
  }
  for(int i=1;i<=n;i++)
  {
    if(ru[i]==0)
    {
      f[i]=1;
      q.push(i);
    }
  }
  while(!q.empty())
  {
    int a=q.front();
    q.pop();
    for(int k=1;k<=n;k++)
    {
      if(mp[a][k]==0)
      {
        continue;
      }
      f[k]+=f[a];
      f[k]%=80112002;
      ru[k]--;
      if(ru[k]==0)
      {
        if(chu[k]==0)
        {
          ans+=f[k];
          ans%=80112002;
                    continue;
        }
        q.push(k);
      }
    }
  }
  cout<<ans; 
}


记忆化搜索:


一共五条食物链 ,通过对图观察能够发现一条完整的食物链最高级消费者是没有被吃过的,而生产者和低级别的消费者是会被吃过,所以可以设置两个标记数组来表示被吃过与吃过的。


创建了这两个数组之后我们就要着手将他们的关系存下来了,因此我们可以创建一个结构体数组用来表示吃与被吃的关系,然后选择找到相对的关系而不是循环遍历,就能避免tle


#include<bits/stdc++.h>
using namespace std;
const int N = 5005; 
int n,m,c[N];
int w[N],u[N],ans,c2[N];
int j=1;
struct node{
  int x,y,next;
}mp[500005];
int dfs(int t)
{ 
  int num=0;
  if(!u[t])
  {     
    return 1;
  }
  if(c[t])
  {
    return c[t];
  }
  for(int i=c2[t];i;i=mp[i].next)
  {
    (num+=dfs(mp[i].x))%=80112002;
  }
  return c[t]=num;
}
int main()
{
  cin>>n>>m;
  while(m--)
  {
    int a,b;
    cin>>a>>b;
    w[a]=1;
    u[b]=1;
    mp[j].x=a;
    mp[j].y=b;  
    mp[j].next=c2[b];
    c2[b]=j;
    j++;
  }
  for(int i=1;i<=n;i++)
  {
    if(!w[i])
    {
      (ans+=dfs(i))%=80112002;
    }
  }
  cout<<ans;
}


目录
相关文章
|
8月前
|
算法
【错题集-编程题】城市群数量
【错题集-编程题】城市群数量
|
8月前
【错题集-编程题】活动安排(贪心 - 区间)
【错题集-编程题】活动安排(贪心 - 区间)
天梯赛真题——7-6 老板的作息表(25 分)
新浪微博上有人发了某老板的作息时间表,表示其每天 4:30 就起床了。但立刻有眼尖的网友问:这时间表不完整啊,早上九点到下午一点干啥了? 本题就请你编写程序,检查任意一张时间表,找出其中没写出来的时间段。
710 0
天梯赛真题——7-6 老板的作息表(25 分)
|
JavaScript 小程序 Shell
🤒如果老板搞代码量统计,打工人如何自救?
“一个下午做出一个微信小程序”,“一个下午搞定业务方案”,每天写1000行代码的成绩,大家你们真的做得到吗?
344 0
🤒如果老板搞代码量统计,打工人如何自救?
|
安全 搜索推荐 Java
2020蓝桥杯省赛C/C++第二场B组反思
2020蓝桥杯省赛C/C++第二场B组反思
|
Python
LeetCode每日一题——857. 雇佣 K 名工人的最低成本
有 n 名工人。 给定两个数组 quality 和 wage ,其中,quality[i] 表示第 i 名工人的工作质量,其最低期望工资为 wage[i] 。
141 0
LeetCode每日一题——857. 雇佣 K 名工人的最低成本
|
算法
每日一题冲刺大厂提高组第八天 栗酱的数列
大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题提高组是为了有余力的同学准备的,让大家练到各种各样的题目,一年以后,蜕变成为一个不一样的自己!
115 1
少林、武当、峨眉三大门派会师,会师成功可得20元猫超卡。活动时间7.25-8.5日。
少林、武当、峨眉三大门派会师,会师成功可得20元猫超卡。活动时间7.25-8.5日。
142 0
少林、武当、峨眉三大门派会师,会师成功可得20元猫超卡。活动时间7.25-8.5日。
【蓝桥杯省赛】冲刺练习题【超大数】倒计时【14】天
【蓝桥杯省赛】冲刺练习题【超大数】倒计时【14】天
193 0
|
算法
每日一题冲刺大厂提高组 第二十四天 胖胖的奶牛
大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题为了让大家练到各种各样的题目,熟悉各种题型,一年以后,蜕变成为一个不一样的自己!
96 0

热门文章

最新文章

下一篇
开通oss服务