题解：B4519 [科大国创杯小学组 2026] 贪吃巧克力

· · 题解

解题思路

场外初一老年人用模拟再优化过的。

由题意可知，初始巧克力区间 [L, R]，长度 k = R-L+1。将区间内巧克力重新编号为 0,1,\dots,k-1，对应原始美味度 a_{L+i}。

于是，第 i 格的契合度为：b_i = a_{L+i} \times a_{L + ((i+p) \bmod k)}.

然后分情况讨论：

从左边开始吃，也就是从左向右扫描 i = 0,1,\dots,k-1，找到第一个满足 b_i = x 的 i，则需吃掉 i+1 格，公式为：\text{cost}_L = \min{i+1 \mid b_i = x,\ 0\le i<k}，若 {i\mid b_i=x,\ 0\le i<k}=\varnothing，则 \text{cost}_L = \infty.

从右边开始吃，也就是从右向左扫描 i = k-1,\dots,0，找到第一个满足 b_i = x 的 i，则需吃掉 k-i 格，公式为：\text{cost}_R = \min{k-i \mid b_i = x,\ 0\le i<k}，若 {i\mid b_i=x,\ 0\le i<k}=\varnothing，则 \text{cost}_R = \infty.

然后考虑，吃掉相应格数后如何更新？

方法如下：

若选左边：L \leftarrow L + \text{cost}_L；

若选右边：R \leftarrow R - \text{cost}_R；

若吃完：L \leftarrow R+1。

重复就可以了。容易得出第一版代码：

:::info[有问题的代码，超时，60分]

#include <iostream>
//wo chang chang zhui yi guo qu
using namespace std;
const int N=1e6+5;
int a[N];
int main(){
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    int C,n,m;cin>>C>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    int l=1,r=n;
    while(m--){
        if(l>r){cout<<"F"<<endl;continue;}
        long long p,x;cin>>p>>x;
        int len=r-l+1,pl=p%len;
        int Lc=-1,Rc=-1;
        for(int i=0;i<len;++i){
            int pos=l+i,oth=l+((i+pl)%len);
            if((long long)a[pos]*a[oth]==x){Lc=i+1;break;}
        }
        for(int i=len-1;i>=0;--i){
            int pos=l+i,oth=l+((i+pl)%len);
            if((long long)a[pos]*a[oth]==x){Rc=len-i;break;}
        }
        if(Lc!=-1&&(Rc==-1||Lc<=Rc)){
            cout<<"L "<<Lc<<endl;
            l+=Lc;
        }else if(Rc!=-1){
            cout<<"R "<<Rc<<endl;
            r-=Rc;
        }else{
            cout<<"F"<<endl;
            l=r+1;
        }
    }
    return 0;
}

::::

然后要优化了。

仔细观察发现，我可以同时从两端向内推进，每次检查左端和右端的新位置呀。这样，一旦找到匹配，立即选择该侧就可以了。

于是乎，就过了：

::::success[AC 代码（赛后自测现场版）]

#include <iostream>
//wo chang chang zhui yi guo qu,bu tangweihang
using namespace std;
const int N=1e6+5;
int a[N];
int main(){
    freopen("eat.in","r",stdin);
    freopen("eat.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);
    int C,n,m;cin>>C>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    int L=1,R=n;
    while(m--){
        if(L>R){cout<<"F"<<endl;continue;}
        long long p,x;cin>>p>>x;
        int k=R-L+1,pl=p%k;
        int ls=0,rs=0,ok=0;
        while(ls+rs<k){
            int iL=ls, posL=L+iL, jL=(iL+pl)%k, othL=L+jL;
            if((long long)a[posL]*a[othL]==x){
                cout<<"L "<<ls+1<<endl;
                L+=ls+1; ok=1; break;
            }
            int iR=k-1-rs, posR=R-rs, jR=(iR+pl)%k, othR=L+jR;
            if((long long)a[posR]*a[othR]==x){
                cout<<"R "<<rs+1<<endl;
                R-=rs+1; ok=1; break;
            }
            ++ls; ++rs;
        }
        if(!ok){
            cout<<"F"<<endl;
            L=R+1;
        }
    }
    return 0;
}

码风不佳，勿喷 ::::

后话：

本题对于不会双指针的小学生，可以写几个特殊性质。有满多分的！