题解 | #打靶#

A.打靶

 判断一下最少打多少个和最大打多少个，是否包含y即可。

void solve()
{
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    if(x > y) {
        cout << "No" << '\n';
        return;
    }
    if(x + (n - m) >= y) {
        cout << "Yes" << '\n';
    }
    else {
        cout << "No" << '\n';
    }
}

B.小蓝的疑惑

 因为gcd(a,b)=x,则a和b一定是x的倍数,又因为lcm(a,b)=y。所以a直接从x的倍数开始枚举到y即可，b=x*y/a。判断一下x*y是否是a的倍数即可，并且b也要是x的倍数。否则输出-1即可。

void solve()
{
    ll x,y;
    cin >> x >> y;
    ll t = x * y,a = x;
    while(a <= y) {
        ll p = t / a;
        if(t % a == 0 && p % x == 0) {
            cout << a << ' ' << p << '\n';
            return;
        }
        a += x;
    }
    cout << -1 << '\n';
}

C.k级序列

 我们观察到每一个a[i]实际上就对应了b[i]的取值范围，又因为b序列要非递减，因此可以知道当我们这个数之前的那些位置取到的最左端满足要求的位置要比当前这个数的取值最右端还大时，这个序列就一定构造不出来。

void solve()
{
    int n,k,x;
    cin >> n >> k;
    int L = -2e9;
    bool ok = true;
    for(int i = 0;i < n;i ++) {
        cin >> x;
        if(L > x + k + 1) {
            ok = false;
        }
        L = max(L,x - k);
    }
    if(ok) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

D.Reverse

 我刚开始以为询问不独立，一直在写线段树，后面看到询问独立了就一下子想到了。
 我们翻转一段区间，其实区间内部贡献不变，只有端点贡献发生改变，由于询问独立，考虑每一次操作我们会产生哪些贡献可以O(1)得出，有以下四种情况。
  1.s[l]为'1',s[l - 1]为'1' 贡献+1
  2.s[r]为'1',s[r + 1]为'1' 贡献+1
  3.s[l]为'1',s[r + 1]为'1' 贡献-1
  4.s[r]为'1',s[l - 1]为'1' 贡献-1
 因此答案等于原答案+产生的贡献即可。

void solve()
{
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = "0" + s + "0";
    int ans = 0,pre = -1;
    for(int i = 1;i <= n;i ++) {
        if(s[i] == '1' && s[i] - '0' != pre) ans ++;
        pre = s[i] - '0';
    }
    while(q --) {
        int l,r;
        cin >> l >> r;
        int v = 0;
        if(s[r + 1] == '1' && s[r] == '1') v ++;
        if(s[l - 1] == '1' && s[l] == '1') v ++;
        if(s[l - 1] == '1' && s[r] == '1') v --;
        if(s[r + 1] == '1' && s[l] == '1') v --;
        cout << ans + v << '\n';
    }
}

E.Dog vs Cat

 题目看着看着漏了操作后，然后一直wa。
  这个题其实是一个分类讨论题。因为n=1和n=2特殊情况直接判掉即可。
   n=1:若当前数<=1或者是个奇数则Dog赢，否则Cat赢
   n=2:若两个数相等且为0则Dog赢，若最小值不是0，并且最小值等于最大值，则Cat赢。剩下的全是Dog赢
   n>2:若0的个数>=(n + 1) / 2，则没操作就输了，因此输出Dog。否则看所有数和-零的个数是奇数则Dog赢，否则Cat赢。

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    ll s = 0,c = 0;
    for(auto &x :a) {
        cin >> x;
        c += !x;
        s += max(0,x - 1);
    }
    if(n == 1) {
        if(a[0] <= 1 || a[0] % 2) {
            cout << "Dog" << '\n';
        }
        else {
            cout << "Cat" << '\n';
        }
        return;
    }
    else if(n == 2) {
        sort(a.begin(),a.end());
        if(a[0] == a[1] && !a[0]) {
            cout << "Dog" << '\n';
            return;
        }
        if(a[0] && a[0] + 1 == a[1]) {
            cout << "Cat" << '\n';
            return;
        }
        cout << "Dog" << '\n';
        return;
    }
    if(c >= (n + 1) / 2) {
        cout << "Dog" << '\n';
        return;
    }
    s += ((n + 1) / 2 - c);
    if(s & 1) {
        cout << "Dog" << '\n';
    }
    else {
        cout << "Cat" << '\n';
    }
}

F.小蓝的构造

 看到n只有40，因此想到折半状压。
 如果我们确定了前半段状态，意味着我们从大到小枚举间隔的时候，至多会有一个位置不确定，那么我们此时分类讨论即可。若当前01对已经=a[i](i为间隔)了,则我们空缺位填0即可。若当前01对+1=a[i]，则空缺位填1即可。否则不可能完成构造。我们这样是基于贪心的构造，因此我们还需要check一下相应间隔的01对数对不对。

void solve()
{
    int n;
    cin >> n;
    vector<int> cons(n + 1,-1);
    vector<int> a(n);
    for(int i = 1;i < n;i ++) {
        cin >> a[i];
    }
    int m = (n + 1) >> 1;
    auto check = [&]() {
        for(int i = n;i > m;i --) {
            cons[i] = -1;
        }
        for(int i = n - 1;i >= 1;i --) {
            int f = -1,c = 0;
            for(int j = 1;j + i <= n;j ++) {
                if(cons[j + i] == -1) {
                    f = j + i;
                }
                else {
                    if(!cons[j] && cons[j + i]) {
                        c ++;
                    }
                }
            }
            if(c == a[i]) {
                if(f != -1) cons[f] = 0;
            }
            else if(c + 1 == a[i]) {
                if(f == -1) return false;
                cons[f] = 1;
            }
            else return false;
        }
        for(int i = 1;i < n;i ++) {
            int c = 0;
            for(int j = 1;j + i <= n;j ++) {
                if(!cons[j] && cons[j + i]) c ++;
            }
            if(c != a[i]) return false;
        }
        return true;
    };
    for(int i = 0;i < (1 << m);i ++) {
        for(int j = 0;j < m;j ++) {
            if(i >> j & 1) cons[j + 1] = 0;
            else cons[j + 1] = 1;
        }
        if(check()) {
            for(int i = 1;i <= n;i ++) {
                cout << cons[i];
            }
            return;
        }
    }
    cout << -1 << '\n';
}