周赛2的全部题解

A.小红的环形字符串

对于环形的问题我们通常采用的方法是破环成链,我们直接对原字符串变成2倍即可,然后我们考虑不同位置的点为端点看满足为目标串的数量即可

string s,a;
int main ()
{
    cin>>s>>a;
    int n=s.size(),m=a.size();
    s=s+s;
    int ans=0;
    for(int i=0;i<n;i++){
        int cnt=0;
        for(int j=0;j<m;j++){
            if(s[i+j]==a[j])cnt++;
        }
        if(cnt==m) ans++;// 完全相同
    }
    cout<<ans<<endl;
    return 0;
}

B.相邻的不同数字的标记

考虑是否合并,假设我们i和i-1的颜色不同那么我们合并的话就是从i-2的权重转移过来，如果我们不合并是从i-1的权重转移而来，所以我们定义为i结尾个位置的最大权重为多少

char s[N];
int f[N];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>(s+1);
    int ans=0;
    for(int i=2;i<=n;i++){
        f[i]=f[i-1];
        if(s[i]!=s[i-1]) f[i]=max(f[i],f[i-2]+a[i]+a[i-1]);
    }
    cout<<f[n]<<endl;
    return ;
}

C.小红的俄罗斯方块

这道题是一个很明显的模拟题，我们不妨用一个数组的大小来表示每一个位置的高度 对于四个不同的状态我们要看对应落下来的时候对这个位置的带来的影响,是否改变了他的最高位置,按照题意细心模拟即可

int a[N];
void solve()
{
    cin>>n; int now;
    for(int i=1;i<=n;i++){
        int w,x; cin>>w>>x;
        if(w==0){
            
            now=max(a[x],a[x+1]);
            a[x]=now+3;
            a[x+1]=now+1;
            
        }else if(w==90){
            
           now=max({a[x]+1,a[x+1],a[x+2]});
           a[x]=a[x+1]=a[x+2]=now+1;
            
        }else if(w==180){
            
            now=max(a[x],a[x+1]+2);// 考虑待来的作用
            a[x]=a[x+1]=now+1;
            
        }else{
            now=max({a[x],a[x+1],a[x+2]});
            a[x]=a[x+1]=now+1;
            a[x+2]=now+2;
        }
        
    }
    for(int i=1;i<=8;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return ;
}

D.小红打怪

我们对于由多次查询的问题一般都要通过给定的数据进行预处理使得，我们能对给定的查询能够在o(1)或者o(log2(n))的时间复杂度给出答案，这题也不例外,我们每次查询给的是学瓶的量也就是我们最后可以由多少血，所以我们需要预处理出来最优的杀敌策略,打死一个怪使得我扣的血越少我就越先杀他,如果我们能求出来每一个怪对我的伤害值我就可以通过排序+前缀和，每次对应血使用二分找到对应怪即可,所以现在只需要解决杀一个怪带来的扣血,我们可定优先使用技能然后一个周期为4的伤害值在这个周期能会收到3次伤害,如果还有剩余血量就考虑是不是能一刀杀了，细节处理一下即可

void solve()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        int tim=a/4*3+(a%4<=2?0:1);
        if(a%4==0) tim=a/4*3-1;// 特别处理%4==0的考虑完整的杀了之后不会被砍
        s[i]=tim*b;
    }
    // 对于a = 4
    // 2 x 1 x 1 2刀 
    sort(s+1,s+1+n);
    for(int i=1;i<=n;i++){
        s[i]+=s[i-1];
    }
    
    cin>>q;
    while(q--){
        int x; cin>>x;
        x*=k;
        x+=m;
        int num=lower_bound(s+1,s+1+n,x)-s-1;
        cout<<num<<" ";
    }
    cout<<endl;
    return ;
}