2 条题解

  • 0
    @ 2025-10-8 16:51:55

    求最小值,即求最长路。设 s[i]为区间[0,i]被选中的数的个数,区间[a b]至少选2个数可以转化为:s[ b ] -s[a-1]>=2 -> s[a-1]+2 <= s[ b ] -> G[a-1].push_back({b, 2}), s[i]-s[i-1]<=1 -> s[i] -1 <=s[i-1] -> G[i].push_back({i-1, -1}), s[i]-s[i-1]>=0 -> s[i-1] <=s[i] -> G[i-1].push_back({i, 0}),

    #include <bits/stdc++.h>
    using namespace std;
    const int N=1e4+10;
    vector<pair<int,int>> G[N];
    int st,ed,d[N],dd[N];bool v[N];
    int spfa()
    {
        memset(d,0,sizeof(d));
        memset(dd,0,sizeof(dd));
        memset(v,0,sizeof(v));
        deque<int> Q;
        for(int i=st;i<=ed;i++) Q.push_front(i),v[i]=1;
        d[st]=0;
        while(!Q.empty())
        {
            int x=Q.front();Q.pop_front();v[x]=0;
            for(auto i:G[x])
            {
                int y=i.first,w=i.second;
                if(d[y]<d[x]+w)
                {
                    d[y]=d[x]+w;if(x==y){return -1;}//判断负自环 
                    dd[y]=dd[x]+1;if(dd[y]>(ed-st+1)){return -1;}
                    if(v[y]==0) Q.push_front(y),v[y]=1;
                }
            }
        }
        return d[ed]-d[st];
    }
    int main()
    {
        int n;scanf("%d",&n);
        ed=0,st=N;
        for(int i=1,x,y;i<=n;i++)
        {
            scanf("%d%d",&x,&y);x++,y++;
            G[x-1].push_back({y,2});
            ed=max(ed,y);
            st=min(st,x-1);
        }
        for(int i=st+1;i<=ed;i++)
        {
            G[i].push_back({i-1,-1});
            G[i-1].push_back({i,0});
        }
        printf("%d\n",spfa());
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:51:44
      /*
      求最小值,即求最长路。
      设 s[i]为区间[0,i]被选中的数的个数,
      区间[a b]至少选2个数可以转化为:s[ b ] -s[a-1]>=2 -> s[a-1]+2 <= s[ b ] -> G[a-1].push_back({b, 2}),
      s[i]-s[i-1]<=1 -> s[i]   -1 <=s[i-1] ->  G[i].push_back({i-1, -1}),
      s[i]-s[i-1]>=0 -> s[i-1]    <=s[i]   ->  G[i-1].push_back({i, 0}),
      */
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1e4+10;
      vector< pair<int,int> >G[N];
      int st,ed,d[N],dd[N];bool v[N];
      int spfa()
      {
          memset(d,0,sizeof(d));
          memset(dd,0,sizeof(dd));
          memset(v,0,sizeof(v));
          deque<int>Q;
          for(int i=st;i<=ed;i++)Q.push_front(i),v[i]=1;
          d[st]=0;
          while(!Q.empty())
          {
              int x=Q.front();Q.pop_front();v[x]=0;
              for(auto i:G[x])
              {
                  int y=i.first,w=i.second;
                  if(d[y]<d[x]+w)
                  {
                      d[y]=d[x]+w;if(x==y){return -1;}//判断负自环 
                      dd[y]=dd[x]+1;if(dd[y]>(ed-st+1)){return -1;}
                      if(v[y]==0) Q.push_front(y),v[y]=1;
                  }
              }
          }
          return d[ed]-d[st];
      }
      int main()
      {
          int n;scanf("%d",&n);
          ed=0,st=N;
          for(int i=1,x,y;i<=n;i++)
          {
              scanf("%d%d",&x,&y);x++,y++;
              G[x-1].push_back({y,2});
              ed=max(ed,y);
              st=min(st,x-1);
          }
          for(int i=st+1;i<=ed;i++)
          {
              G[i].push_back({i-1,-1});
              G[i-1].push_back({i,0});
          }
          printf("%d\n",spfa());
          return 0;
      }
      • 1

      信息

      ID
      703
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      38
      已通过
      10
      上传者