首页 > 其他分享 >暑假集训CSP提高模拟2

暑假集训CSP提高模拟2

时间:2024-07-19 21:40:46浏览次数:15  
标签:rt int ll tree 集训 暑假 200010 CSP rson

暑假集训CSP提高模拟2

\(T1\) T2745. 活动投票 \(30pts\)

  • 原题: luogu P2397 yyy loves Maths VI (mode)

  • 懒得再复制一遍了,直接挂当时的 题解 得了。

    点击查看代码
    int main()
    {
        ll n,a,sum=0,ans=-0x7f7f7f7f,i;
        scanf("%lld",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&a);
            if(ans==a)
            {
                sum++;
            }
            else
            {
                sum--;
                if(sum<=0)
                {
                    sum=1;
                    ans=a;
                }
            }
        }
        printf("%lld\n",ans);
        return 0;
    }
    

\(T2\) T2741. 序列 \(0pts\)

  • 原题: UVA1608 不无聊的序列 Non-boring sequences
  • 部分分
    • \(10pts\) :莫队处理出所有区间,询问即可。

      点击查看代码
      int a[200010],b[200010],cnt[200010],sum[200010],L[200010],R[200010],pos[200010],klen,ksum;
      struct ask 
      {
          int l,r,id;
      }q[10000010];
      bool q_cmp(ask a,ask b)
      {
          return (pos[a.l]==pos[b.l])?((pos[a.l]%2==1)?(a.r<b.r):(a.r>b.r)):(a.l<b.l);
      }
      void init(int n,int m)
      {
          klen=n/sqrt(m)+1;
          ksum=n/klen;
          for(int i=1;i<=ksum;i++)
          {
              L[i]=R[i-1]+1;
              R[i]=R[i-1]+klen;
          }
          if(R[ksum]<n)
          {
              ksum++;
              L[ksum]=R[ksum-1]+1;
              R[ksum]=n;
          }
          for(int i=1;i<=ksum;i++)
          {
              for(int j=L[i];j<=R[i];j++)
              {
                  pos[j]=i;
              }
          }
      }
      void add(int x)
      {
          cnt[x]++;
          if(cnt[x]==1)
          {
              sum[pos[x]]++;
          }
          if(cnt[x]==2)
          {
              sum[pos[x]]--;
          }
      }
      void del(int x)
      {
          cnt[x]--;
          if(cnt[x]==1)
          {
              sum[pos[x]]++;
          }
          if(cnt[x]==0)
          {
              sum[pos[x]]--;
          }
      }
      int query()
      {
          for(int i=1;i<=ksum;i++)
          {
              if(sum[i]>=1)
              {
                  return 1;
              }
          }
          return 0;
      }
      int main()
      {
          int t,n,m,l,r,flag,i,j;
          scanf("%d",&t);
          for(j=1;j<=t;j++)
          {
              scanf("%d",&n);
              m=flag=0;
              memset(cnt,0,sizeof(cnt));
              memset(sum,0,sizeof(sum));
              for(i=1;i<=n;i++)
              {
                  scanf("%d",&a[i]);
                  b[i]=a[i];
              }
              sort(b+1,b+1+n);
              b[0]=unique(b+1,b+1+n)-(b+1);
              for(i=1;i<=n;i++)
              {
                  a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
              }
              for(l=1;l<=n;l++)
              {
                  for(r=l;r<=n;r++)
                  {
                      m++;
                      q[m].l=l;
                      q[m].r=r;
                      q[m].id=m;
                  }
              }
              init(n,m);
              sort(q+1,q+1+m,q_cmp);
              l=1;
              r=0;
              for(i=1;i<=m;i++)
              {
                  while(l>q[i].l)
                  {
                      l--;
                      add(a[l]);
                  }
                  while(r<q[i].r)
                  {
                      r++;
                      add(a[r]);
                  }
                  while(l<q[i].l)
                  {
                      del(a[l]);
                      l++;
                  }
                  while(r>q[i].r)
                  {
                      del(a[r]);
                      r--;
                  }
                  if(query()==0)
                  {
                      flag=1;
                      break;
                  }
              }
              if(flag==0)
              {
                  printf("non-boring\n");
              }
              else
              {
                  printf("boring\n");
              }
          }
          return 0;
      }
      
  • 正解
    • 线段树优化 \(DP\) 。

      • 设 \(f_{l,r}\) 表示 \([l,r]\) 中仅出现 \(1\) 次的数的个数。

      • 从 \(r-1\) 到 \(r\) 的过程,实际上是多加了一个 \(a_{r}\) 。若 \(a_{r}\) 以前没有出现过,则 \(f_{k,r}=f_{k,r-1}+1 (k \in [1,r])\) ;否则有 \(\begin{cases} f_{k,r}=f_{k-1,r}(k \in [1,lastlast_{a_{r}}]) \\ f_{k,r}=f_{k,r-1}-1 (k \in (lastlast_{a_{r}},last_{a_{r}}]) \\ f_{k,r}=f_{k,r-1}+1 (k \in (last_{a_{r}},r]) \end{cases}\) 。序列合法当且仅当 \(\forall r \in [1,n],\min\limits_{l=1}^{r} \{ f_{l,r} \} \ge 1\) 。

      • 区间修改、区间查询的线段树维护即可。

        点击查看代码
        int a[200010],b[200010],f[200010],pos[200010];
        pair<int,int>last[200010];
        struct SMT
        {
            struct SegmentTree
            {
                int l,r,minn,lazy;
            }tree[1600010];
            int lson(int x)
            {
                return x*2;
            }
            int rson(int x)
            {
                return x*2+1;
            }
            void pushup(int rt)
            {
                tree[rt].minn=min(tree[lson(rt)].minn,tree[rson(rt)].minn);
            }
            void build(int rt,int l,int r,int a[])
            {
                tree[rt].l=l;
                tree[rt].r=r;
                tree[rt].lazy=0;
                if(l==r)
                {
                    tree[rt].minn=a[l];
                    return;
                }
                int mid=(l+r)/2;
                build(lson(rt),l,mid,a);
                build(rson(rt),mid+1,r,a);
                pushup(rt);
            }
            void pushdown(int rt)
            {
                if(tree[rt].lazy!=0)
                {
                    tree[lson(rt)].lazy+=tree[rt].lazy;
                    tree[rson(rt)].lazy+=tree[rt].lazy;
                    tree[lson(rt)].minn+=tree[rt].lazy;
                    tree[rson(rt)].minn+=tree[rt].lazy;
                    tree[rt].lazy=0;
                }
            }
            void update(int rt,int x,int y,int val)
            {
                if(x<=tree[rt].l&&tree[rt].r<=y)
                {
                    tree[rt].lazy+=val;
                    tree[rt].minn+=val;
                    return;
                }
                pushdown(rt);
                int mid=(tree[rt].l+tree[rt].r)/2;
                if(x<=mid)
                {
                    update(lson(rt),x,y,val);
                }
                if(y>mid)
                {
                    update(rson(rt),x,y,val);
                }
                pushup(rt);
            }
            int query(int rt,int x,int y)
            {
                if(x<=tree[rt].l&&tree[rt].r<=y)
                {
                    return tree[rt].minn;
                }
                pushdown(rt);
                int mid=(tree[rt].l+tree[rt].r)/2,ans=0x7f7f7f7f;
                if(x<=mid)
                {
                    ans=min(ans,query(lson(rt),x,y));
                }
                if(y>mid)
                {
                    ans=min(ans,query(rson(rt),x,y));
                }
                return ans;
            }
        }T;
        int main()
        {
            int t,n,flag=0,i,j;
            scanf("%d",&t);
            for(j=1;j<=t;j++)
            {
                scanf("%d",&n);
                flag=0;
                for(i=1;i<=n;i++)
                {
                    scanf("%d",&a[i]);
                    b[i]=a[i];
                    last[i]=make_pair(0,0);
                    pos[i]=0;
                }
                sort(b+1,b+1+n);
                b[0]=unique(b+1,b+1+n)-(b+1);
                for(i=1;i<=n;i++)
                {
                    a[i]=lower_bound(b+1,b+1+b[0],a[i])-b;
                }
                T.build(1,1,n,f);
                for(i=1;i<=n;i++)
                {
                    last[i].first=pos[a[i]];
                    last[i].second=last[last[i].first].first;
                    pos[a[i]]=i;
                    if(last[i].first==0)
                    {
                        T.update(1,1,i,1);
                    }
                    else
                    {
                        T.update(1,last[i].second+1,last[i].first,-1);
                        T.update(1,last[i].first+1,i,1);
                    }
                    if(T.query(1,1,i)<=0)
                    {
                        flag=1;
                        break;
                    }
                }
                if(flag==1)
                {
                    printf("boring\n");
                }
                else
                {
                    printf("non-boring\n");
                }
            }
            return 0;
        }
        
    • 官方题解

      也可以分治递归求解,代码看 luogu 题解吧。

\(T3\) T6201. Legacy \(100pts\)

  • 原题: CF786B Legacy

  • 部分分

  • 正解

    • 直接挂学习笔记的 题解 了。

      点击查看区间连区间代码
      struct SegmentTree
      {
          ll l,r;
      }tree[2000010];
      vector<pair<ll,ll> >e[2000010];
      ll dis[2000010],id[2000010],vis[2000010],cnt=0;
      ll lson(ll x)
      {
          return x*2;
      }
      ll rson(ll x)
      {
          return x*2+1;
      }
      void build(ll rt,ll l,ll r,ll n)
      {
          tree[rt].l=l;
          tree[rt].r=r;
          e[rt+n*4].push_back(make_pair(rt,0));
          if(l==r)
          {
              id[l]=rt;
              return;
          }
          e[lson(rt)].push_back(make_pair(rt,0));
          e[rson(rt)].push_back(make_pair(rt,0));
          e[rt+n*4].push_back(make_pair(lson(rt)+n*4,0));
          e[rt+n*4].push_back(make_pair(rson(rt)+n*4,0));
          ll mid=(l+r)/2;
          build(lson(rt),l,mid,n);
          build(rson(rt),mid+1,r,n);
      }
      void update(ll rt,ll x,ll y,ll pd,ll n,ll t,ll w)
      {
          if(x<=tree[rt].l&&tree[rt].r<=y)
          {
              if(pd==0)
              {
                  e[rt].push_back(make_pair(n*8+t,0));
              }
              else
              {
                  e[n*8+t].push_back(make_pair(rt+n*4,w));
              }
              return;
          }
          ll mid=(tree[rt].l+tree[rt].r)/2;
          if(x<=mid)
          {
              update(lson(rt),x,y,pd,n,t,w);
          }
          if(y>mid)
          {
              update(rson(rt),x,y,pd,n,t,w);
          }
      }
      void dij(ll p)
      {
          ll x,i;
          priority_queue<pair<ll,ll> >q;
          memset(dis,0x3f,sizeof(dis));
          memset(vis,0,sizeof(vis));
          dis[p]=0;
          q.push(make_pair(-dis[p],-p));
          while(q.empty()==0)
          {
              x=-q.top().second;
              q.pop();
              if(vis[x]==0)
              {
                  vis[x]=1;
                  for(i=0;i<e[x].size();i++)
                  {
                      if(dis[e[x][i].first]>dis[x]+e[x][i].second) 
                      {
                          dis[e[x][i].first]=dis[x]+e[x][i].second;
                          q.push(make_pair(-dis[e[x][i].first],-e[x][i].first));
                      }
                  }
              }
          }
      }
      void add(ll a,ll b,ll c,ll d,ll w,ll n)
      {
          cnt++;
          update(1,a,b,0,n,cnt,w);
          update(1,c,d,1,n,cnt,w);
      }
      int main()
      {
          ll n,m,p,pd,w,a,b,c,d,i;
          scanf("%lld%lld%lld",&n,&m,&p);
          build(1,1,n,n);
          for(i=1;i<=m;i++)
          {
              scanf("%lld",&pd);
              if(pd==1)
              {
                  scanf("%lld%lld%lld",&a,&c,&w);
                  b=a;
                  d=c;
              }
              if(pd==2)
              {
                  scanf("%lld%lld%lld%lld",&a,&c,&d,&w);
                  b=a;
              }
              if(pd==3)
              {
                  scanf("%lld%lld%lld%lld",&c,&a,&b,&w);
                  d=c;
              }
              add(a,b,c,d,w,n);
          }
          dij(id[p]);
          for(i=1;i<=n;i++)
          {
              if(i==p)
              {
                  printf("0 ");
              }
              else
              {
                  printf("%lld ",(dis[id[i]+n*4]==0x3f3f3f3f3f3f3f3f)?-1:dis[id[i]+n*4]);
              }
          }
          return 0;
      }
      

\(T4\) T2731. DP搬运工1 \(22pts\)

  • 部分分
    • \(22pts\) :生成所有全排列,依次判断。

      点击查看代码
      const ll p=998244353;
      ll a[100];
      int main()
      {
          ll n,k,sum,ans=0,i;
          cin>>n>>k;
          for(i=1;i<=n;i++)
          {
              a[i]=i;
          }
          do
          {
              sum=0;
              for(i=2;i<=n;i++)
              {
                  sum+=max(a[i],a[i-1]);
              }
              ans=(ans+(sum<=k))%p;
          }while(next_permutation(a+1,a+1+n));
          cout<<ans<<endl;
          return 0;
      }
      
  • 正解

总结

  • \(T1\) 看到是原题后,马上就写了,结果把将 sum=1 写成 sum++; 了,迷之自信让我没再去测别的样例,挂了 \(70pts\) 。
  • \(T2\) 两次大样例有点弱,都把乱搞做法放过去了。
  • \(T3\) 赛时在想 \(Dijkstra\) 怎么写,真就应了前几天听牛客的课时授课老师说的“要把广搜,\(Dijkstra,SPFA\),堆优化 \(Prim\) 这几个容易搞混的代码之间的不同点搞清楚,别整的最后场上一直在纠结某个地方应该怎么写”。

后记

标签:rt,int,ll,tree,集训,暑假,200010,CSP,rson
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18312248

相关文章

  • 多校联合暑假训练赛第一场
    B.对数组的最小操作次数Code:#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;intdp[N][8],n,k,a[N];intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(inti=1;i......
  • 暑假集训CSP提高模拟2
    A.活动投票主元素问题,用摩尔投票#include<bits/stdc++.h>usingnamespacestd;intn,a=-1,acnt,x;intmain(){ scanf("%d",&n); for(inti=1;i<=n;++i){ scanf("%d",&x); if(acnt==0){ a=x; acnt++; } elseif(a==x){ acnt++......
  • YOLOV8自定义数据集训练过程中遇到的问题
    书接上回,在弄好了Labelimg了以后,便开始了图像的标注。按照官网推荐的格式,建好文件夹。文件夹格式:dataset下为train和val两个文件夹,两个文件夹中的内容均为images和labels。images里放的就是图像了,labels为标注的数据。接下里就是创建自己的yaml文件,文件的内容指定数据集的根......
  • 暑假集训CSP提高模拟1考试题解
    A.Start洛谷原题链接一道大模拟,赛时20pts。教授の高光时刻-输出没加句号、空格。-C++向0取整。-DOUBLE没传递。--9操作成-1(复制粘贴导致的)。-负数位运算卡常。其实这题还是比较简单的,细节在题目中讲的很详细,跟着它说的去做就好了。我的方法是把每个玩家用一个结构......
  • 暑假集训 · 第二间
    放假7.14因为是坐火车回去所以早走了2小时发现提前一小时让huge给手机充电然后只充到50%似乐,原要更新,打崩铁,坐到一半就没电了......
  • 手机玩电脑游戏攻略教程 出门在外如何用手机畅玩3A大作?暑假游戏推荐
    小编这几天盘点了一下在暑假上线的电脑游戏,发现真是不少。什么《魔兽世界》《艾登法环黄树幽影》《绝区零》PC端、《第一后裔》《七日世界》等等,还有即将到来的《黑神话》和《魔兽世界》的正式服。各位玩家是不是已经按捺不住,想要把它们都体验一遍了?可是暑假又想出去玩,又不想......
  • 暑假两个月学习AI产品经理详细路线,看这一篇就够了
    以下是一个暑假期间学习AI产品经理的详细路线,分为八个周来进行:第1周:了解AI产品管理基础阅读材料:《人工智能:一种现代的方法》了解AI基础。《人人都是产品经理》了解产品管理基础。在线课程:Coursera上的“人工智能基础”课程。edX上的“产品管理基础”课程。实践:调研......
  • 暑假集训CSP模拟一
    赛时rank14T10,T20,T3100,T40T1大模拟出题人_______T1Start大模拟,注意细节。点此查看代码#include<bits/stdc++.h>usingnamespacestd;#ifdefLOCALFILE*InFile=freopen("in.in","r",stdin),*OutFile=freopen("out.out","w&quo......
  • 2022CSP答案+解析(附题目)
    一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)1.以下哪种功能没有涉及C++语言的面向对象特性支持:()。A.C++中调用printf函数B.C++中调用用户定义的类成员函数C.C++中构造一个class或structD.C++中构造来源于同一基类的多个派生类答......
  • 『模拟赛』暑假集训CSP提高模拟1
    Rank感冒了,同时心情极差,状态不好wwA.Start打磨你。T1放大模拟还是过于抽象了,开局劝退,遂倒序开题。赛时想复杂了一点,开了两个二维数组存牌,同时存double状态时也出了问题,还没有考虑负数的向下取整。我太蒻了改后虽然还是300多行,但是思路起码清晰了很多,改了几个小错就......