题解 | #打靶#_牛客博客

A 打靶

首先是如果 $Y$ 已经大于 $X$ 了，那显然不行。如果 $Y$ 小于等于 $X$ ,则考虑剩余天数 $n-m$ 是否大于等于缺少的分数

void sol(){
    int n,m,x,y;cin>>n>>m>>x>>y;
    cout<<(n-m>=y-x&&x<=y?"Yes":"No")<<endl;
}

B 小蓝的疑惑

根据唯一分解定理 $a=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}p_{3}^{\alpha_{3}}...p_{k}^{\alpha_{k}}$ , $b=p_{1}^{\beta_{1}}p_{2}^{\beta_{2}}p_{3}^{\beta_{3}}...p_{k}^{\beta_{k}}$

而 $\gcd(a,b)=p_{1}^{\min(\alpha_{1},\beta_{1})}p_{2}^{\min(\alpha_{2},\beta_{2})}p_{3}^{\min(\alpha_{3},\beta_{3})}...p_{k}^{\min(\alpha_{k},\beta_{k})}$ , $lcm(a,b)=p_{1}^{\max(\alpha_{1},\beta_{1})}p_{2}^{\max(\alpha_{2},\beta_{2})}p_{3}^{\max(\alpha_{3},\beta_{3})}...p_{k}^{\max(\alpha_{k},\beta_{k})}$

那么要求 $a$ 最小， $a$ 就只能是 $\gcd(a,b)$ 了，此时 $b$ 就是 $lcm$ 。

void sol(){
    int x,y;cin>>x>>y;
    if(y%x!=0) return cout<<-1<<endl,void();
    cout<<x<<" "<<y<<endl;
}

C k级序列

根据题意可以得到，每一个 $b_i$ 范围为 $[\max(a_i-k,b_{i-1}),a_i k]$ , 所以我们只需要让每一个 $b_i$ 在可以取的范围中取最小值，这样后续的 $b_i$ 可选的范围才会最大。

void sol(){
    int n,k;cin>>n>>k;
    vector<ll> a(n+1),b(n+1);
    b[0]=-1e18;

    rep(i,1,n) cin>>a[i];

    rep(i,1,n) {
        ll l=max(b[i-1],a[i]-k),r=a[i]+k;
        if(l>r) return cout<<"No"<<endl,void();
        b[i]=l;
    }

    cout<<"Yes"<<endl;
}

D Reverse

打比赛时有点脑淤血，居然把题目看成了每次询问最长的 $1$ 串长度了，等发现读错题时代码都要写完了。

分类讨论一下：

$s_l==1 \quad s_r==1$ 那么区间两端如果有 $1$ 串被破坏，也能立刻跟翻转过来的 $1$ 接上，形成新的 $1$ 串，所以数量是不会变的
$s_l==0 \quad s_r==0$ 那么区间两端不会有 $1$ 串被破坏，所以数量不会变
$s_l==1 \quad s_r==0$ 如果 $L$ 端有 $1$ 串被破坏，那么数量会加一，而如果 $R$ 端之外恰好有 $1$ 那么会跟翻转过来的 $1$ 串连接，此时数量减一。
$s_l==0 \quad s_r==1$ 分析同上一情况

void sol(){

    int n,q;cin>>n>>q;
    string s;cin>>s;
    s+='0';

    int cnt=0;
    rep(i,1,n) if(s[i]=='0'&&s[i-1]=='1') cnt++;


    while(q--) {
        int L,R;cin>>L>>R;
        L--,R--;
        if(s[L]==s[R]) 
            cout<<cnt<<endl;
        else if(s[L]=='0') {
            int ans=cnt;
            if(L>0&&s[L-1]=='1') ans--;
            if(R<n-1&&s[R+1]=='1') ans++;
            cout<<ans<<endl;
        }
        else if(s[R]=='0') {
            int ans=cnt;
            if(L>0&&s[L-1]=='1') ans++;
            if(R<n-1&&s[R+1]=='1') ans--;
            cout<<ans<<endl;
        }
    }
}

E Dog vs Cat

分类讨论一下：

如果 $n==1$ ，那么当 $a_i==0$ 时 Dog 必胜。而 $a_1!=0$ 时根据 $a_1$ 的奇偶，如果是奇数的话，就会是 Cat 最终把 $a_1$ 变成 $0$ ，此时 Cat 必输，反之 Dog 必输。
如果 $n==2$ , 如果 $a_1!=a_2$ 那么除非差值等于 $1$ ，这样 Cat 可以先手将两个数变为相等，此时 Cat 必胜，否则 Cat 将无法操作，Dog 必胜。需要注意的是当两个数分别为 $0,1$ 时， Cat 也无法操作。
如果 $n>2$ :
- $0$ 的个数 $cnt0$ 已经满足 $cnt0*2 \ge n$ 。此时 Cat 无法操作，所以 Dog 必胜。
- $cnt0*2 < n$ ，那局面会最终变成 $\left\lceil \frac{n}{2} \right\rceil-1$ 个 $0$ ，剩余都为 $1$ ，此时操作的人无法操作，另一个人必胜，判断到达此局面的奇偶即可。

void sol(){
    int n;cin>>n;

    vector<ll> a(n+1);
    rep(i,1,n) cin>>a[i];

    if(n==1) {
        if(a[1]==0) cout<<"Dog"<<endl;
        else cout<<(a[1]%2==1?"Dog":"Cat")<<endl;
    }
    else if(n==2) {
        if(abs(a[1]-a[2])!=1||max(a[1],a[2])==1) cout<<"Dog"<<endl;
        else cout<<"Cat"<<endl;
    }
    else {
        int cnt=count(all(a),0)-1;
        ll sum=-n+((n+1)/2-1);//减去 1 的数量
        for(int x:a) sum+=x;

        if(cnt*2>=n) cout<<"Dog"<<endl;
        else cout<<(sum%2==1?"Dog":"Cat")<<endl;
    }
}

F 小蓝的构造

对于数据只有 $40$ 的题目，我们可以考虑暴搜或者考虑二进制枚举。但是直接枚举的话 $2^{40}$ 的解空间又太大了，所以我们需要根据题目中的约束条件进行剪枝，缩小解空间。

若我们只枚举前一半的字符串，那么在已经确定了一半字符的情况下根据 $f(n-1)$ 就可以确定最后一个字符，此时再根据 $f(n-2)$ 就能确定倒数第二个字符。以此类推，我们就会发现前一半的字符串就已经决定了后一半字符串，而枚举前一半字符串的计算量仅为 $2^{\frac{n}{2}}$ 确定后一半字符串的复杂度为 $(\frac{n}{2})^2$ ,算一算最大也只有约为 $400*1e6=4e8$ ,此时已经非常可做了。

void sol(){
    int n;cin>>n;
    vector<int> f(n);
    rep(i,1,n-1) cin>>f[i];
    
    string s;
    auto check=[&](int fl)->bool {
        s=string(n,'0');
        rep(i,0,(n-1)/2+1) if(fl>>i & 1) s[i]='1';

        per(len,n-1,1) {
            int cnt=0;
            for(int i=0,j=len;j<n;i++,j++) 
                if(s[i]=='0'&&s[j]=='1') cnt++;       

            if(cnt!=f[len]) {
                if(len>=(n-1)/2+1&&cnt==f[len]-1&&s[0]=='0') s[len]='1';
                else return false;
            }
        }

        return true;
    };

    for(int i=0;i<(1<<((n-1)/2+1));i++) 
        if(check(i)) return cout<<s<<endl,void();

    cout<<-1<<endl;
}