01-22 21:18 已编辑圣芙蕾雅学园 C++ 发布于香港

关注

牛客寒假营第一场题解

寒假营第一场题解

Easy：A、B、D、G

Mid：E、H、J、M

Hard：C、F、I

AK：K、L

前言

感觉难度挺大的，甚至从简单题开始就不是很简单。

大部分题目我都不会做，全靠猜结论，猜着猜着就莫名其妙过了。

我是在某一天 27 点开始打的，用了 3 个小时打到 30 点就写完了前 12 题，剩下一个 L ，不过这个 L 也有了大致的思路，但是实在太困了就先放着了。中间由于太困了，犯了非常多唐氏错误，导致浪费了不少时间且罚时爆炸，包括但不限于：变量名写错，复制粘贴只改一半，循环写反， $O(nlog)$ 写成 $O(n^2)$ 。一小时不到就写完了前 8 题， 0 罚时，然后半小时才写完 C ，然后又调了 10 分钟 5 发罚时才过， 10 分钟写完 F 倒是一发过了，但是我记得中间也写的很唐， I 题 20 分钟写完然后调了 40 分钟怒吃 8 发罚时， K 题 20 分钟写完调 10 分钟 2 发罚时，感觉很大的原因是太困了，脑子不清醒。

签到题中只有 G 稍微有意思一些。

前期题中没有有趣的题。

三个中期题都比较有趣。

后期题中 L 比较有趣。

总结就是一句话：叫小苯的傻逼题太多了导致的。（PS：这句话有 3 个意思）

以我对出题人的了解，这场和原本预想的不太一样，本来以为这场会更多有趣的题目，而且还会有计算几何，结果并不是很有趣，不过好消息是也没有寄算寄何。

原本这一场不在第一场，但是我写完那一场之后觉得那一场很不适合放在第一场（会是哪一场呢？），于是将两场交换了一下。（但是感觉这一场也很不对劲啊！）

大家第二场加油，还没做完第二场题目，一言难尽，哈哈。

A 茕茕孑立之影

构造，数论

如果数组中有 1 ，那么肯定无解。

否则，一个很大的质数肯定不会是数组中的数的倍数，因此我们选择一个比较大的质数即可。

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        int ans = 1e9 + 7;
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            if(x == 1) ans = -1;
        }
        cout << ans << endl;
    }
}

B 一气贯通之刃

图论

简单路径不能经过一个点两次，因此如果一个点有 3 条或者更多条边，就一定会有走不到的边。

因此这棵树一定会是一条链，那么我们只需要找到链的两个端点即可。

如果你知道点的度数的话应该很容易想到：链端点（即树的叶子节点）的度数是为 1 的，非端点（非叶子节点）的度数为 2 。

因此我们只要计算每个点的度数，答案就是度数为 1 的两个点（并且度数为 1 的点有且只有两个）。

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> in(n + 1);
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        in[u]++;
        in[v]++;
    }
    vector<int> ans;
    for(int i = 1; i <= n; i++){
        if(in[i] == 1) ans.push_back(i);
        if(in[i] > 2){
            cout << -1 << endl;
            return 0;
        }
    }
    for(auto &i : ans){
        cout << i << " ";
    }
    cout << endl;
}

D 双生双宿之决

模拟、排序

按照题目描述模拟即可。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n);
        for(auto &i : a){
            cin >> i;
        }
        ranges::sort(a);
        int ans = 1;
        if(n & 1) ans = 0;
        else{
            int r = n + 1 >> 1;
            int l = r - 1;
            if(a[0] != a[l]) ans = 0;
            if(a[n - 1] != a[r]) ans = 0;
            if(a[l] == a[r]) ans = 0;
        }
        if(ans) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

G 井然有序之衡

思维、排序

首先我们需要发现，操作是不会影响数组总和的，因此数组总和必须等于 $\sum_{i=1}^n i$ 才有可能有解。

由于有操作次数的限制，我们应该要将最小值变成 1 ，次小值变成 2 ，……，最大值变成 $n$ ，因此我们需要先将数组进行排序。

因为数组总和不能变，加一减一次数应当一致，所以 $\sum_{i=1}^n a_i - i$ 应该为 0 。

操作次数就是 $(\sum_{i=1}^n |a_i - i|) / 2$ （即加一或者减一的次数）。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    a[0] = -2e9;
    ranges::sort(a);
    auto sum = 0ll;
    auto ans = 0ll;
    for(int i = 1; i <= n; i++){
        sum += a[i] - i;
        if(a[i] < i) ans += i - a[i];
    }
    if(sum) ans = -1;
    cout << ans << endl;
}

E 双生双宿之错

思维、贪心、三分、排序

假设我们确定了双生数组的两种元素分别为 $x$ 和 $y$ ，令 $x<y$ 。

那么如果数组是有序的，我们显然应该将前一半变成 $x$ ，后一半变成 $y$ ，操作次数为 $\sum_{i=1}^{n/2} |a_i - x| + \sum_{i=n/2+1}^n |a_i-y|$ 。

如何求出确定 $x$ 和 $y$ 可以使得操作次数最小呢？

观察上述式子，前一半和后一半计算权值时是独立的，我们可以把这个数组分成左右两个部分，分别求值。

现在问题变成了：将一个数组的所有数都变成 $t$ 的最小操作次数。

一个比较显然的结论是：取 $t$ 为这个数组的中位数。

不会证明，感性理解一下：如果所有数字都为变成了 $t$ ，现在要使得所有数字变成 $t+1$ ，需要让原本小于等于 $t$ 的数字都加一次（记个数为 $l$ ），原本大于 $t$ 的数字少加一次（记个数为 $r$ ），代价是 $l-r$ ，其中 $l+r=n$ 。那么 $t$ 最小值开始从小往上加的时候， $l$ 会在 $t$ 为中位数的时候大于等于 $r$ ，代价就变成了非负整数。

如果不知道上述中位数结论或者推导的话，这个函数是满足三分性的，也可以使用三分暴力计算。

我们左右两边分别贪心的结果可能会使得 $x=y$ ，因此我们需要让 $x-1$ 或者 $y+1$ ，最后取其中的较小值。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        ranges::sort(a);
        auto get = [&](auto x, auto y){
            auto ans = 0ll;
            for(int i = 1; i <= n / 2; i++){
                ans += abs(a[i] - x);
            }
            for(int i = n / 2 + 1; i <= n; i++){
                ans += abs(a[i] - y);
            }
            return ans;
        };
        auto check = [&](int x, int y){
            auto t = 0ll;
            if(a[x] != a[y]) t = get(a[x], a[y]);
            else t = min(get(a[x] - 1, a[y]), get(a[x], a[y] + 1));
            return t;
        };
        int t = n >> 1;
        int x = 0, y = 0;
        if(t & 1){
            x = t + 1 >> 1;
            y = t + x;
        }
        else{
            x = t >> 1;
            y = t + x + 1;
        }
        cout << check(x, y) << endl;
    }
}

H 井然有序之窗

构造、贪心

一个比较经典的贪心， $i$ 这个数必须在所有 $l \leq i,r \ge i$ 的区间中选到，如果有多种选择，选择 $r$ 最小的区间一定不会使得答案变劣。

一个例子：有两个区间 $[1,1],[1,2]$ ，我们 1 如果在第二个区间中选，会导致 2 这个数无法选到。

我们可以使用优先队列维护右端点最小的区间，对区间按左端点排序后，可以从前往后将左端点小于 $i$ 的区间加入优先队列，然后取出右端点最小的区间。

若右端点小于 $i$ ，理论上应该将这个区间丢弃，找到第一个满足右端点大于等于 $i$ 的区间，但由于区间不能浪费，因此此时一定无解。若优先队列为空，同样无解。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    deque<array<int, 3>> a(n);
    int pt = 0;
    for(auto &[l, r, i] : a){
        cin >> l >> r;
        i = ++pt;
    }
    ranges::sort(a);
    vector<int> ans(n + 1);
    set<array<int, 3>> st;
    for(int i = 1; i <= n; i++){
        while(a.size() && a[0][0] <= i){
            auto [l, r, i] = a[0];
            st.insert({r, l, i});
            a.pop_front();
        }
        if(!st.size()){
            cout << -1 << endl;
            return 0;
        }
        auto [r, l, j] = *st.begin();
        st.erase(st.begin());
        if(r < i){
            cout << -1 << endl;
            return 0;
        }
        ans[j] = i;
    }
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
}

J 硝基甲苯之袭

因数分解、打表、质数筛

这题不会，打了个表猜了个结论，然后就过了。

我们发现 $x,y(x<y)$ 满足 $x \oplus y = gcd(x,y)$ ，当且仅当 $y=x+gcd(x,y)$ ，且 $x$ 是偶数。

因此我们枚举每个偶数 $x$ ，和 $x$ 的因子 $t$ 得到 $y=x+t$ ，判断上述式子是否合法，若合法统计答案即可。

正常的做法是，枚举 $x$ 和 $x$ 的因子 $t$ ，那么 $y=x \oplus t$ ，再检查 $gcd(x,y)=t$ 是否合法，若合法统计答案。

时间复杂度 $O(n\sqrt n)$ ，使用质数筛大概可以优化到 $O(nlogn)$ 。

update：评论区补充

事实上无需判断 $x$ 奇数还是偶数，只是满足要求的恰好 $x$ 都为偶数，编程中不判断这点也可以 $gcd(x,y)=x \oplus y (y>x)$ 等价于 $gcd(x,y)=y-x$ 1.证明 $x,y$ 二进制位数相等假设不相等，那么 $x^y$ 一定大于 $min(x,y)$ ，因为异或的位数等于 $x,y$ 中位数多的那个. 则 $gcd(x,y)<=min(x,y)<x \oplus y$ ，与 $gcd(x,y)=x \oplus y$ 矛盾 2.在 $x,y$ 二进制位数相等且 $y>x$ 的基础上，显然 $x \oplus y=y-x$

作者：20211491425洪一桐链接：https://www.nowcoder.com/discuss/711277141064687616?toCommentId=21160802

#include<bits/stdc++.h>

using namespace std;

int main(){
    const int N = 2e5 + 1;
    int n;
    cin >> n;
    vector<int> a(N * 2 + 1);
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[x]++;
    }
    auto ans = 0ll;
    auto get = [&](int x, int y){
        y += x;
        if((x ^ y) == gcd(x, y)) ans += 1ll * a[x] * a[y];
    };
    for(int i = 2; i <= N; i += 2){
        for(int j = 1; j * j <= i; j++){
            if(i % j) continue;
            get(i, j);
            if(j * j != i) get(i, i / j);
        }
    }
    cout << ans << endl;
}

M 数值膨胀之美

STL、排序，枚举

要使得数组极差变小，显然需要先让最小值乘以 2 ，然后是次小值，……，以此类推。

从第 $k$ 小值操作到第 $k+1$ 小值是一个区间，会使得这个区间所有数都乘以 2 ，并且一个数最多只会乘一次。

我们可以维护一个已经乘过 2 的区间，那么新的区间一定会和这个区间相交（第 $k$ 小值一定在区间内，第 $k$ 小值到第 $k+1$ 小值的区间至少在第 $k$ 小值处相交）。因此区间永远都是连续的，而且会越来越大，那么区间扩张就是线性的，我们可以暴力维护这个区间扩张的操作。

由于从第 $k$ 小值操作到第 $k+1$ 小值时，可能会是数组的最大值变大，因此我们需要在每次乘以 2 操作后计算数组的极差。

此时我们需要一个容器：每次操作可以在容器中删除一个数，并插入一个数。符合条件的容器有许多，我们选择的是 $multiset$ 。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<pair<int, int>> b;
    multiset<int> st;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b.push_back({a[i], i});
        st.insert(a[i]);
    }
    ranges::sort(b);
    auto [l, r] = b[0];
    st.extract(l);
    st.insert(l * 2);
    int ans = *st.rbegin() - *st.begin();
    l = r;
    for(auto &[_, i] : b){
        if(i >= l && i <= r) continue;
        for(int j = l - 1; j >= i; j--){
            st.extract(a[j]);
            st.insert(a[j] * 2);
            ans = min(ans, *st.rbegin() - *st.begin());
        }
        l = min(l, i);
        for(int j = r + 1; j <= i; j++){
            st.extract(a[j]);
            st.insert(a[j] * 2);
            ans = min(ans, *st.rbegin() - *st.begin());
        }
        r = max(r, i);
    }
    cout << ans << endl;
}

C 兢兢业业之移

构造、思维

我们需要把所有的 1 都推到左上角，那么可以先把所有的 1 往最上方推，再把所有的 1 往最左边推，此时所有的 1 就会变成一个类似上三角矩阵的阶梯。

接下来我们就应该将右边多出的 1 和下边多出的 1 放进左上角，从边缘的 1 开始，往中间靠即可。

操作次数大概是：每个 1 都会从最底下移动到最上方，从最右边移动到最左边，次数是 $2n$ ，再从边角往中间靠又需要 $2n$ ，共 $4n$ ， 1 的个数为 $n^2/4$ ，乘起来就是 $n^3$ 。

理论次数超过了题目的要求，但实际上不可能每一个 1 都要走这么多次，就比如有一个 1 从右下角走到左上角走了 $2n$ 步，必然会使得其他的 1 不需要走 $2n$ 步，每个 1 走的步数都是不独立的，因此实际次数不会超过题目的要求。

时间复杂度 $O(n^4)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector s(n + 2, string(n + 2, '1'));
        for(int i = 1; i <= n; i++){
            cin >> s[i];
            s[i] = "1" + s[i] + "1";
        }
        vector<vector<int>> ans;
        auto go = [&](int x, int y, char c){
            int dx = 0;
            dx -= c == 'U';
            dx += c == 'D';
            dx += x;
            int dy = 0;
            dy -= c == 'L';
            dy += c == 'R';
            dy += y;
            swap(s[x][y],s[dx][dy]);
            ans.push_back({x,y,dx,dy});
        };
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = i; k >= 1; k--){
                    if(s[k][j] == '1' && s[k - 1][j] == '0'){
                        go(k, j, 'U');
                    }
                    else break;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = j; k >= 1; k--){
                    if(s[i][k] == '1' && s[i][k - 1] == '0'){
                        go(i, k, 'L');
                    }
                    else break;
                }
            }
        }
        for(int i = n / 2; i >= 1; i--){
            for(int j = n; j > n / 2; j--){
                if(s[i][j] == '0') continue;
                int x = 0, y = 0;
                for(int k = 1; k <= n / 2; k++){
                    for(int l = 1; l <= n / 2; l++){
                        if(s[k][l] == '1') continue;
                        x = k;
                        y = l;
                        break;
                    }
                }
                for(int k = i; k < x; k++){
                    go(k, j, 'D');
                }
                for(int k = j; k > y; k--){
                    go(x, k, 'L');
                }
            }
        }
        for(int i = n; i > n / 2; i--){
            for(int j = n / 2; j >= 1; j--){
                if(s[i][j] == '0') continue;
                int x = 0, y = 0;
                for(int k = 1; k <= n / 2; k++){
                    for(int l = 1; l <= n / 2; l++){
                        if(s[k][l] == '1') continue;
                        x = k;
                        y = l;
                        break;
                    }
                }
                for(int k = j; k < y; k++){
                    go(i, k, 'R');
                }
                for(int k = i; k > x; k--){
                    go(k, y, 'U');
                }
            }
        }
        cout << ans.size() << endl;
        for(auto &i : ans){
            for(auto &j : i){
                cout << j << " ";
            }
            cout << endl;
        }
    }
}

F 双生双宿之探

前缀和、双指针

首先要观察双生数组的性质，需要观察到这样一个性质：有可能存在双生数组的区间一定是一段的只有两种数字的区间，假设区间中两种数字分别是 $x,y$ ，记这种区间为 ” $xy$ - 好区间“ 。

” $xy$ - 好区间“ 应该要是极长的，如果一个长的 ” $xy$ - 好区间“ 包含了另一个短的 ” $xy$ - 好区间“ ，我们需要舍去短的那一个，在长的那一个中进行计算。（不要问为什么）

我们将所有极长好区间排序后会发现，连续的 3 个好区间中，第 1 个和第 3 个一定是不相交的（假设第一个区间是 $x,y$ ，第二个区间是 $y,z$ ，第三个区间要和第一个区间相交的话一定会有 $x,y,z$ 三种数字）。也就是说，这些极长的好区间的总长度不超过 $2n$ 。

一个 ” $xy$ - 好区间“ 中有多少个双生数组呢？

假设一个数组只有 1 和 -1 ，那么双生数组在这里的定义就等价于区间和为 0 的区间。

这个问题又该如何解决呢？

我们记数组前缀和为 $f$ ，那么 $f_r-f_l=0$ 当且仅当 $f_r=f_l$ ，那么用一个容器记录 $f_r$ 有多少个，就可以知道以 $r$ 为结尾的好区间有多少个。

那么我们把 ” $xy$ - 好区间“ 中等于 $x$ 的数变成 1 ，等于 $y$ 的数变成 -1 ，就可以用上述方法计算双生数组中的个数了。

时间复杂度 $O(nlogn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        vector<int> f(n + 1);
        auto ans = 0ll;
        for(int i = 1; i <= n; i++){
            set<int> st;
            map<int, int> mp;
            mp[0]++;
            f[i - 1] = 0;
            for(int j = i; j <= n; j++){
                st.insert(a[j]);
                if(st.size() > 2){
                    i = j;
                    st.clear();
                    for(; i >= 1; i--){
                        st.insert(a[i]);
                        if(st.size() > 2) break;
                    }
                    break;
                }
                f[j] = f[j - 1];
                if(a[j] == a[i]) f[j]++;
                else f[j]--;
                ans += mp[f[j]];
                mp[f[j]]++;
                if(j == n) i = n;
            }
        }
        cout << ans << endl;
    }
}

I 井然有序之桠

构造、打表、贪心

乱写的，然后过了。

首先排列权值最大的排列肯定是 $1,2,3,......,n-1,n$ ，排列权值为 $S=\sum_{i=1}^n i$ 。

要使得权值为 $k$ ，就需要使得权值减少 $S-k$ ，记为 $d$ 。

从大到小枚举 $x$ ，交换 $x$ 和 $x-1$ 可以使得权值减少 $(x+x-1)-(1+1) = 2x-3$ ，如果 $d \ge 2x-3$ ，直接贪心减去并交换即可，否则就跳过。

在上述过程中，如果某个时刻发现 $d<x$ ，我们就可以直接交换 1 和 $d+1$ 了， $(d+1+1)-(1+1) = d$ ，因为此时小于等于 $x$ 的数字一定没有被交换过。

测试几个样例发现，这种方法当且仅当 $k = n + 2$ 且 $n$ 为偶数时无解，但这个时候真的无解吗？

打表后发现当 $n=4,k=6$ 时， $[3,4,1,2]$ 是一个合法的解，并且在 $n \ge 6,k=n+2$ 且 $n$ 为偶数时，第 5 位之后的位置都是奇偶位两两交换，因此只需要将前 4 个数字变成 $[3,4,1,2]$ 即可。

时间复杂度 $O(n)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        auto k = 0ll;
        cin >> n >> k;
        vector<int> a(n + 1);
        vector<int> in(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            in[a[i]] = i;
        }
        if(k < n){
            cout << -1 << endl;
            continue;
        }
        vector<int> b(n + 1);
        iota(b.begin(), b.end(), 0);
        auto sum = 1ll * n * (n + 1) / 2;
        int x = n;
        while(sum > k && x > 1){
            if(sum - k <= x - 1){
                int t = sum - k;
                sum = k;
                swap(b[1], b[t + 1]);
            }
            int t = x + x - 3;
            if(sum - t >= k){
                sum -= t;
                swap(b[x], b[x - 1]);
                x -= 1;
            }
            x -= 1;
        }
        if(sum != k){
            b[1] = 3;
            b[2] = 4;
            b[3] = 1;
            b[4] = 2;
            sum = k;
        }
        vector<int> c(n + 1);
        for(int i = 1; i <= n; i++){
            c[in[i]] = b[i];
        }
        for(int i = 1; i <= n; i++){
            cout << c[i] << " ";
        }
        cout << endl;
    }
}

K 硝基甲苯之魇

数论、前缀和、二分、ST表、线段树

最暴力的想法是：枚举每一个区间，求出区间的 $gcd$ 和异或和，但很显然过不去。

如何快速求出一个区间的 $gcd$ 呢？常用的做法是用ST表或者线段树。

用前缀和可以快速求出一个区间的异或和。

虽然优化了一些，但是枚举的复杂度过高，很显然我们还是过不去。

接下来要观察到一个最大公约数的性质，以一个位置为右端点 $r$ ，那么区间 $[l,r](l \in [1,r]),A=max_{i=1}^r$ 中，不同的 $gcd$ 最多只有 $logA$ 种。并且这些区间按从小到大排好序后，每个区间的最大公约数一定是非降序的。

那我们从左往右枚举右端点 $r$ ， $gcd$ 相同的左端点就会处于一个连续的区间中，那么我们就可以通过通过二分的方式得到这个区间的左右端点，记为 $[l_1,l_2]$ 表示 $[l,r](l \in [l_1,l_2])$ 这些区间的区间 $gcd$ 都为 $G$ 。

得到的这些区间跟我们的题目有什么关系呢？

现在已知 $[l_1,l_2],G$ ，我们需要求出左端点在 $[l_1,l_2]$ 区间内，右端点为 $r$ 的所有区间中有多少个区间的异或和为 $G$ 。

用 $f_r$ 表示前 $r$ 个数的异或和，那么 $f_r \oplus f_{l-1} = G \Rightarrow f_{l-1}=f_r \oplus G = X$ ，我们只要算 $[l_1,l_2]$ 中有多少个位置的 $f_l=X$ 即可。

区间某个数出现次数可以使用 $map$ 套 $vector$ 解决，预处理时用 $map$ 将 $X$ 的每一个下标放进一个 $vector$ 中并排好序，查询时在 $X$ 对应的 $vector$ 中找到第一个大于等于左端点和最后一个小于等于右端点的位置做差即可。

时间复杂度 $O(nlog^2n)$ 。

#include<bits/stdc++.h>

using namespace std;

template <typename T>
class ST{
public:
    const int n;
    vector<vector<T>> st;
    ST(int n = 0, vector<T> &a = {}) : n(n){
        st = vector(n + 1, vector<T>(22 + 1));
        build(n, a);
    }

    inline T get(const T &x, const T &y){
        return gcd(x, y);
    }

    void build(int n, vector<T> &a){
        for(int i = 1; i <= n; i++){
            st[i][0] = a[i];
        }
        for(int j = 1, t = 2; t <= n; j++, t <<= 1){
            for(int i = 1; i <= n; i++){
                if(i + t - 1 > n) break;
                st[i][j] = get(st[i][j - 1], st[i + (t >> 1)][j - 1]);
            }
        }
    }

    inline T find(int l, int r){
        int t = log(r - l + 1) / log(2);
        return get(st[l][t], st[r - (1 << t) + 1][t]);
    }
};

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1);
        map<int, vector<int>> mp;
        mp[0].push_back(0);
        vector<int> f(n + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            f[i] = f[i - 1] ^ a[i];
            mp[f[i]].push_back(i);
        }
        ST<int> st(n, a);
        auto sum = 0ll;
        for(int i = 1; i <= n; i++){
            int L = i - 1;
            while(L >= 1){
                int l = 1, r = L;
                int g = st.find(L, i);
                while(l < r){
                    int mid = l + r >> 1;
                    if(st.find(mid, i) == g) r = mid;
                    else l = mid + 1;
                }
                auto &v = mp[g ^ f[i]];
                int le = ranges::lower_bound(v, l - 1) - v.begin();
                int ri = ranges::lower_bound(v, L) - v.begin();
                sum += ri - le;
                L = l - 1;
            }
        }
        cout << sum << endl;
    }
}

L 一念神魔之耀

构造、思维、数论

不太懂，乱写了一发过了。

先猜一下，如果 $gcd(x,y)=g=1$ 时一定有解。（别问）

我们显然可以将前 $l-x+1$ 位都变成 1 ，然后再想办法把后 $x-1$ 位变成 0 。

再猜一下，我们可以把连续 $g$ 位进行翻转，并且不会影响到其他的位。

具体实现流程是：先将前 $x$ 位翻转，此时需要将前 $d=x-g$ 位翻转，若 $d \ge y$ ，则翻转前 $y$ 位， $d := d - y$ ，否则在前面多翻转 $x$ 位， $d:=d+x$ ，一直往复总有一次会将 $d$ 变为 0 。

还猜一下，上述往复次数不会超过 $2l$ 。

那么此时就是，从后往前，若某一位是 0 ，则翻转这一位往前共 $g$ 位，并且这次枚举只需要枚举到 $l-x+1$ 即可（又是猜的）。

至于中间翻转的过程，由于数据范围不大，直接暴力枚举即可。

然后就过了。。。。。。

次数：一开始从左往右推需要 $l$ 次，后续 $x$ 位，每一位推需要 $2l$ 次，共需要 $(2x+1)l$ ，由于 $x \le l / 3,2x+1<l$ ，所以 $(2x+1)l<l^2$ 。

时间复杂度 $O(n^3)$ ，而且可以很轻松的优化成 $O(n^2)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int L, x, y;
        cin >> L >> x >> y;
        if(x > y) swap(x, y);
        string s;
        cin >> s;
        s = " " + s + " ";
        vector<pair<int, int>> ans;
        int g = gcd(x, y);
        auto ch = [&](int l, int r){
            ans.push_back({l, r});
            for(int i = l; i <= r; i++){
                s[i] ^= 1;
            }
        };
        for(int i = 1; i <= L - x + 1; i++){
            if(s[i] == '0'){
                ch(i, i + x - 1);
            }
        }
        auto get = [&](int m){
            vector<int> a(L + 1);
            for(int i=m - x + 1; i <= m - g; i++){
                a[i] ^= 1;
            }
            while(1){
                int cnt = ranges::count(a, 1);
                if(!cnt) return;
                int l = 0;
                for(int i = 1; i <= L; i++){
                    if(a[i]){
                        l = i;
                        break;
                    }
                }
                if(cnt >= y){
                    ch(l, l + y - 1);
                    for(int i = l; i <= l + y - 1; i++){
                        a[i] ^= 1;
                    }
                }
                else{
                    ch(l - x, l - 1);
                    for(int i = l - x; i <= l - 1; i++){
                        a[i] ^= 1;
                    }
                }
            }
        };
        for(int i = L; i >= L - x + 1; i--){
            if(s[i] == '0'){
                ch(i - x + 1, i);
                get(i);
            }
        }
        if(!ranges::count(s, '0')){
            cout << ans.size() << endl;
            for(auto &[x, y] : ans){
                cout << x << " " << y << endl;
            }
        }
        else cout << -1 << endl;
    }
}

全部评论

推荐最新楼层

Wh1t3zZlo

华南师范大学 C++

我宣布这才是官解另一篇题解是

12 回复分享

发布于 01-22 16:40 广东

20211491425洪一桐

辽宁大学算法工程师

我给个J题结论证明：事实上无需判断x奇数还是偶数，只是满足要求的恰好x都为偶数，编程中不判断这点也可以 gcd(x,y)=x^y (y>x) 等价于gcd(x,y)=y-x 1.证明x,y二进制位数相等假设不相等，那么x^y一定大于min(x,y),因为异或的位数等于x,y中位数多的那个. 则gcd(x,y)<=min(x,y)<x^y，与gcd(x,y)=x^y 矛盾 2.在x,y二进制位数相等且y>x的基础上，显然x^y=y-x

10 回复分享

发布于 01-22 15:31 新加坡

F1ower

扬州大学 Java

M写的比官解好，官解感觉不太能解释a[i + 1].first万一落在维护的乘2区间的情况，用multiset就很简单易懂，赞！

2 回复分享

发布于 01-21 23:17 江苏

luxcfy

河北科技大学客户端其它

同问

1 回复分享

发布于 01-21 21:23 河北

SDUwh

山东大学 C++

J好像不太用猜结论，直接暴力找也能过

1 回复分享

发布于 01-25 16:08 山东

刘曜玮666

河南工程学院数据分析师

E题最后面，x==y的时候，为什么只有 x-1或y+1，不可以x+1，或者y-1吗？

点赞回复分享

发布于 01-21 21:06 河南

LargeRice16pro

龙游奇点编程 C++

J 题算 gcd 不用时间吗？

点赞回复分享

发布于 01-21 21:42 浙江

才瓯

成都理工大学

B: 4 1 2 2 1 3 4

点赞回复分享

发布于 01-21 22:06 四川

LargeRice16pro

龙游奇点编程 C++

那 M 题，k-th 和 k+1-th 有多个，比如 1 2 5 2 4 2 请问这三个 2 被扩展的顺序是怎么样的呢？

点赞回复分享

发布于 01-21 23:30 浙江

fly_dog

常德职业技术学院 Java

大佬可以讲讲J题使用筛法做的具体思路吗

点赞回复分享

发布于 01-22 10:48 广东

Jerrycyx

成都教科院附属学校 C++

M 题 > 要使得数组极差变小，显然需要先让最小值乘以 2 ，然后是次小值，……，以此类推。这个怎么证？

点赞回复分享

发布于 01-22 10:50 四川

高槻泉_

湖南理工大学 C++

我是一个萌新很想知道M题为什么是O(nlogn),外层 for (auto &[_, i] : b) 循环的时间复杂度是 O(n)。每次内部的 for (int j = l - 1; j >= i; j--) 循环执行的操作时间复杂度是 O(log n)，且最多执行 O(n) 次。最坏的情况不是O(n平方logn)吗？

点赞回复分享

发布于 01-22 11:16 湖南

罚时天花板

安阳工学院算法工程师

J题算gcd如果开全局long long （#define long long）为什么时间上过不去啊，两个相差很多吗