首页 > 其他分享 >NOIP2024加赛4

NOIP2024加赛4

时间:2024-11-11 16:29:36浏览次数:1  
标签:优惠券 int ll freopen ans 加赛 500010 NOIP2024

NOIP2024加赛4

\(T1\) luogu P11267 【MX-S5-T1】王国边缘 \(85pts\)

  • 预处理前缀中最后一个 \(1\) 出现的位置然后就可以倍增跳了。

    点击查看代码
    const ll p=1000000007;
    int nxt[200010][62],f[200010][62],last[200010];
    char t[200010];
    ll divide(ll s,ll k)
    {
        ll ans=0;
        for(ll i=60;i>=0;i--)
        {
            if((k>>i)&1)
            {
                ans=(ans+f[s][i])%p;
                s=nxt[s][i];
            }
        }
        return ans;
    }
    int main()
    {
    #define Isaac
    #ifdef Isaac
        freopen("kingdom.in","r",stdin);
        freopen("kingdom.out","w",stdout);
    #endif
        ll n,m,q,s,k,r,i,j;
        cin>>n>>m>>q>>(t+1);
        last[0]=-1;
        for(i=1;i<=n;i++)
        {
            last[i]=(t[i]=='1')?i:last[i-1];
        }
        for(i=1;i<=n;i++)
        {
            if(i+m<=n)
            {
                if(last[i+m]<=i)
                {
                    nxt[i][0]=i+1;
                    f[i][0]=1;
                }
                else
                {
                    nxt[i][0]=last[i+m];
                    f[i][0]=last[i+m]-i;
                }
            }
            else
            {
                r=(m+i)%n;
                k=(m+i)/n-1;
                if(last[r]==-1)
                {
                    if((k==0&&last[n]<=i)||(last[n]==-1))
                    {
                        nxt[i][0]=i%n+1;
                        f[i][0]=1;
                    }
                    else
                    {
                        nxt[i][0]=last[n];
                        f[i][0]=(n-i+(k-1)*n%p+last[n])%p;
                    }
                }
                else
                {
                    nxt[i][0]=last[r];
                    f[i][0]=(n-i+k*n%p+last[r])%p;
                }
            }
        }
        for(j=1;j<=60;j++)
        {
            for(i=1;i<=n;i++)
            {
                nxt[i][j]=nxt[nxt[i][j-1]][j-1];
                f[i][j]=(f[i][j-1]+f[nxt[i][j-1]][j-1])%p;
            }
        }
        for(i=1;i<=q;i++)
        {
            cin>>s>>k;
            cout<<(s+divide((s-1)%n+1,k))%p<<endl;
        }
        return 0;
    }
    

\(T2\) luogu P11268 【MX-S5-T2】买东西题 \(40pts\)

  • 考虑先将物品和优惠券分别以 \(\{ a \}\) 和 \(\{ w \}\) 升序排序,此时优惠券能被选择的一定是一段后缀。

  • 而最终对答案有关系的只有被选择的优惠券,而与其被哪个物品选择无关。即对于两个物品若可以交换其选择的优惠券则交换后并不影响最终答案。

  • 部分分

    • 测试点 \(1\) :爆搜或状压 \(DP\) 。
    • 测试点 \(4 \sim 6\) :每张优惠券可以被选择的是整个序列,将 \(a_{i}-b_{i}\) 也当做“优惠券”的一部分,排序取前 \(n\) 大即可。
    点击查看代码
    ll f[2][(1<<21)+1000000];
    pair<int,int>a[1000010],w[1000010];
    vector<int>c;
    ll lowbit(ll x)
    {
        return x&(-x);
    }
    int main()
    {
    #define Issac
    #ifdef Issac
        freopen("buy.in","r",stdin);
        freopen("buy.out","w",stdout);
    #endif
        int n,m,i,j,k;
        ll sum=0,ans=0x7f7f7f7f7f7f7f7f;
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].first,&a[i].second);
            sum+=a[i].second;
            c.push_back(a[i].first-a[i].second);
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&w[i].first,&w[i].second);
            c.push_back(w[i].second);
        }
        sort(a+1,a+1+n);
        sort(w+1,w+1+m);
        if(w[m].first<=a[1].first)
        {
            ans=0;
            sort(c.begin(),c.end(),greater<int>());
            for(i=1;i<=n;i++)
            {
                ans+=a[i].first;
                ans-=c[i-1];
            }
        }
        else
        {
            memset(f,0x3f,sizeof(f));
            f[0][0]=sum;
            for(i=1;i<=n;i++)
            {
                f[i&1][0]=f[(i-1)&1][0];
                for(j=1;j<=(1ll<<m)-1;j++)
                {
                    f[i&1][j]=f[(i-1)&1][j];
                    if(__builtin_popcount(j)<=i)
                    {
                        k=log2(lowbit(j));
                        if(w[k+1].first>a[i].first)
                        {
                            continue;
                        }
                        for(k=0;k<=m-1;k++)
                        {
                            if(((j>>k)&1))
                            {
                                if(w[k+1].first<=a[i].first)
                                {
                                    f[i&1][j]=min(f[i&1][j],f[(i-1)&1][j^(1<<k)]-a[i].second+a[i].first-w[k+1].second);
                                }
                                else
                                {
                                    break;
                                }
                            }
                        }
                    }
                }
            }
            for(i=0;i<=(1<<m)-1;i++)
            {
                ans=min(ans,f[n&1][i]);
            }
        }
        printf("%lld\n",ans);
        return 0;
    }
    
  • 正解

    • 不妨钦定在处理完物品 \(i\) 后续更新过程不会再次给它优惠券,但是可以把它的优惠券拿走给后面的物品用。
    • 考虑反悔贪心,每次将当前最优决策取出,并加入由此产生的新决策。
    • 设决策集合为 \(Q\) ,若 \(a_{i}-\min\{ Q \} \le b_{i}\) 则将 \(a_{i}-\min\{ Q \}\) 加入答案,并将 \(a_{i}-b_{i}\) 加入决策集合 \(Q\) ;否则将 \(b_{i}\) 加入答案。
      • 若 \(\min\{ Q \}\) 来自于 \(a_{j}-b_{j}(j \in [1,i-1])\) ,则等价于拿走物品 \(j\) 的优惠券并将其对答案的贡献更改为 \(b_{j}\) ;否则来自于优惠券,即选择最优的优惠券加入答案。
      • 后者的正确性显然。
    点击查看代码
    pair<ll,ll>a[1000010],w[1000010];
    priority_queue<ll>q;
    int main()
    {
    #define Issac
    #ifdef Issac
        freopen("buy.in","r",stdin);
        freopen("buy.out","w",stdout);
    #endif
        ll n,m,ans=0,i,j;
        scanf("%lld%lld",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i].first,&a[i].second);
        }
        for(i=1;i<=m;i++)
        {
            scanf("%lld%lld",&w[i].first,&w[i].second);
        }
        sort(a+1,a+1+n);
        sort(w+1,w+1+m);
        for(i=1,j=0;i<=n;i++)
        {
            while(j+1<=m&&w[j+1].first<=a[i].first)
            {
                j++;
                q.push(w[j].second);
            }
            if(q.empty()==0&&a[i].first-q.top()<=a[i].second)
            {
                ans+=a[i].first-q.top();
                q.pop();
                q.push(a[i].first-a[i].second);
            }
            else
            {
                ans+=a[i].second;
            }
        }
        printf("%lld\n",ans);
        return 0;
    }
    

\(T3\) luogu P11269 【MX-S5-T3】IMAWANOKIWA (Construction ver.) \(12pts\)

  • 部分分
    • 测试点 \(1 \sim 3\) :爆搜。

      点击查看代码
      const ull base=13331;
      int a[100010],minn;
      char aa[100010];
      vector<int>ans,tmp,s;
      bool cmp()
      {	
          for(int i=0;i<ans.size();i++)
          {
              if(ans[i]>tmp[i])
              {
                  return true;
              }
              if(ans[i]<tmp[i])
              {
                  return false;
              }
          }
          return true;
      }
      void dfs(int pos,int n)
      {
          if(pos==n)
          {
              for(int i=1;i<=n;i++)
              {
                  s.push_back(a[i]);
              }
              for(int i=0;i<tmp.size();i++)
              {
                  s[tmp[i]-1]=__builtin_popcount(s[tmp[i]-1]+s[tmp[i]]);
                  s.erase(s.begin()+tmp[i]);
              }
              if(s[0]<minn)
              {
                  minn=s[0];
                  ans=tmp;
              }
              else
              {
                  if(s[0]==minn&&cmp()==true)
                  {
                      ans=tmp;
                  }
              }
              s.pop_back();
          }
          else
          {
              for(int i=1;i<=n-pos;i++)
              {
                  tmp.push_back(i);
                  dfs(pos+1,n);
                  tmp.pop_back();
              }
          }
      }
      ull sx_hash()
      {
          ull hsh=0,jc=1;
          for(int i=ans.size()-1;i>=0;i--)
          {
              hsh+=jc*ans[i];
              jc*=base;
          }
          return hsh;
      }
      int main()
      {
      #define Issac
      #ifdef Issac
          freopen("popc.in","r",stdin);
          freopen("popc.out","w",stdout);
      #endif
          int t,n,i,j;
          scanf("%d",&t);
          for(j=1;j<=t;j++)
          {
              minn=0x7f7f7f7f;
              ans.clear();
              scanf(" %s",aa+1);
              n=strlen(aa+1);
              for(i=1;i<=n;i++)
              {
                  a[i]=aa[i]-'0';
              }
              dfs(1,n);
              printf("%d %llu\n",minn,sx_hash());
          }
          return 0;
      }
      
    • 测试点 \(13 \sim 15\) :观察到 \(\operatorname{popcount}(x+y)=((x-1) \bigoplus (y-1))+1(x,y \in \{ 1,2 \})\) ,进一步手摸后发现操作顺序并不影响最终答案,故贪心地对开头进行操作即可。

\(T4\) luogu P11270 【MX-S5-T4】魔法少女们 \(8pts\)

  • 部分分

    • 测试点 \(1 \sim 2\) :爆搜,哈希加速字符串匹配。
    点击查看代码
    const ll p=1000000007,mod=1000003579,base=13331;
    ll hss[500010],lens[500010],hst[500010],lent[500010],hs[500010],jc[500010],ans=0;
    char s[500010];
    ll init_hash(char s[],ll len)
    {
        ll ans=0;
        for(ll i=0;i<=len;i++)
        {
            ans=(i==0)?0:(ans*base%mod+s[i])%mod;
        }
        return ans;
    }
    void sx_hash(char s[],ll len,ll a[])
    {
        for(ll i=0;i<=len;i++)
        {
            a[i]=(i==0)?0:(a[i-1]*base%mod+s[i])%mod;
        }
    }
    ll ask_hsh(ll l,ll r)
    {
        return (hs[r]-hs[l-1]*jc[r-l+1]%mod+mod)%mod;
    }
    void dfs(ll pos,ll n,ll m,ll k,ll sum1,ll sum2)
    {
        if(sum2>sum1)
        {
            return;
        }
        if(pos==k+1)
        {
            if(sum1==sum2)
            {	
                sx_hash(s,k,hs);
                ll cnt1=0,cnt2=0;
                for(ll i=1;i<=n;i++)
                {
                    cnt1+=(ask_hsh(1,lens[i])==hss[i]);
                }	
                for(ll i=1;i<=m;i++)
                {
                    cnt2+=(ask_hsh(k-lent[i]+1,k)==hst[i]);
                }	
                ans=(ans+cnt1*cnt2%p)%p;
            }
        }
        else
        {
            s[pos]='(';
            dfs(pos+1,n,m,k,sum1+1,sum2);
            s[pos]=')';
            dfs(pos+1,n,m,k,sum1,sum2+1);
        }
    }
    int main()
    {
    #define Issac
    #ifdef Issac
        freopen("magic.in","r",stdin);
        freopen("magic.out","w",stdout);
    #endif
        ll c,n,m,k,i;
        scanf("%lld%lld%lld%lld",&c,&n,&m,&k);
        for(i=1;i<=n;i++)
        {
            scanf(" %s",s+1);
            lens[i]=strlen(s+1);
            hss[i]=init_hash(s,lens[i]);
        }
        for(i=1;i<=m;i++)
        {
            scanf(" %s",s+1);
            lent[i]=strlen(s+1);
            hst[i]=init_hash(s,lent[i]);
        }
        for(i=0;i<=k;i++)
        {
            jc[i]=(i==0)?1:jc[i-1]*base%mod;
        }
        dfs(1,n,m,k,0,0);
        printf("%lld\n",ans);
        return 0;
    }
    

总结

  • \(T1\) 预处理时少处理了能跳出至少一个 \(S\) 时的 Corner Case ,但因为大样例直接过了遂没写对拍,挂了 \(15pts\) 。
  • \(T2\) 想到了把 \(a_{i}-b_{i}\) 也当做“优惠券”的一部分,但以为只能给自己用,没想到能扩展到维护后续因拿走优惠券而产生的贡献。
  • \(T3\) 没有想到 \(\operatorname{popcount}(x+y)=\begin{cases} 1 & x=y \land x,y \in \{ 1,2 \} \\ 2 & x \ne y \land x,y \in \{ 1,2 \} \end{cases}\) 能归约到 \(\operatorname{popcount}(x+y)=((x-1) \bigoplus (y-1))+1(x,y \in \{ 1,2 \})\) ,导致 \(15pts\) 的部分分没写。

标签:优惠券,int,ll,freopen,ans,加赛,500010,NOIP2024
From: https://www.cnblogs.com/The-Shadow-Dragon/p/18540030

相关文章

  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20昨天晚上打ABC了,所以今天才发。T1星际联邦直接上菠萝(Borůvka)算法就行了,当然还可以用线段树优化prim算法,但是没打过只是口胡:就是维护当前的连通块,但一个点$i$加入连通块时,后面那些点就可以有$a_j-a_i$的贡献,前面的点可以有$a_i-......
  • NOIP2024(欢乐)加赛3
    NOIP2024(欢乐)加赛3\(T1\)CF2033BSakurakoandWater\(100pts\)枚举主对角线取\(\max\)即可。点击查看代码lla[510][510];intmain(){ llt,n,ans=0,maxx,i,j,k,h; cin>>t; for(h=1;h<=t;h++) { cin>>n; ans=0; for(i=1;i<=n;i++) { for(......
  • [赛记] 多校A层冲刺NOIP2024模拟赛20
    星际联邦80pts前连20条,后连20条80pts。。。考虑正解,发现向前连最大,向后连最小会出现重边,所以避免出现这种情况,我们只需要在做完向前连最大以后,在向后连最小的时候连不是同一个连通块的即可;时间复杂度:$\Theta(n\logn)$,瓶颈在排序;其实这个思想就是最小生成树的那个BUA算法......
  • 『模拟赛』NOIP2024(欢乐)加赛3
    Rank真欢乐吗,不过missionaccomplished.A.SakurakoandWaterCF2033B*900byd还懂难易搭配,不过这个b翻译甚至不着重以下主对角线差评,被硬控半个小时,直到手模样例才发觉不对。读懂题就很简单了,最优一定是找最长的对角线每次加,一共只有\(2n-1\)条线,枚举一下求出每条......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛20
    RankmissionfailedA.星际联邦由于急着想切题,上来没细看就打了个树状数组上去,果然寄了,然后又各种方式优化,最终还是寄了,只有50pts。正解是学最小生成树时直接跳过的prim和菠萝,但是偏不这么做,而是找性质得出严格\(\mathcal{O(n)}\)的做法。首先比较平凡发现一个点的最......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20\(T1\)A.星际联邦\(25pts\)部分分\(25pts\):暴力建边后跑\(Kruskal\)或\(Prim\)。点击查看代码structnode{ intfrom,to,w;};inta[300010];vector<node>e;structDSU{ intfa[300010]; voidinit(intn) { for(inti......
  • 多校A层冲刺NOIP2024模拟赛20
    简评:新拉的......
  • 【题解】「NOIP2024模拟赛24 T3」钙绿
    【题解】「NOIP2024模拟赛24T3」钙绿https://www.becoder.com.cn/contest/5715/problem/3\(\mathcal{Description}\)给定\(n,p,m\)。对于每个\(k=0,1,\dots,m\),统计满足下面条件的\(n\)位\(10\)进制数:(允许前导零各位数之和不超过\(k\)。\(p\)能整除这个数。数据......
  • 【题解】「NOIP2024模拟赛24 T2」子序列们
    【题解】「NOIP2024模拟赛24T2」子序列们https://www.becoder.com.cn/contest/5715/problem/2\(\mathcal{Description}\)给定一个0/1串\(a\),你需要生成一个长度为\(n\)的序列\(b\),其中\(b_i\)为\(a\)的一个子序列,且满足:\(|b_i|=n-i+1\);\(\foralli\in(1,n]\),\(b......
  • NOIP2024模拟赛 #17 总结
    省流:T1对\(998244353\)取模,T2对\(mod\)取模,T3求排名,T4对\(10^9+7\)取模。比赛出锅不少。开T1,发现并没有前几天那么简单,对着题目盯了\(1\)h毫无思路,发现没看见所有高塔的高度两两不同这个条件,看到后略有思路,但是还不太行。后来说大样例出锅了,幸好没写。T2很......