前言

F不会，剩下的感觉写的也挺丑陋，如果有问题欢迎大家指出

题解

A.数数

埃氏筛的写法，可以枚举所有质数，给因子中有该质数的数字标记+1，

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> cnt(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!cnt[i]) {
            for (int j = i; j <= n; j += i) {
                cnt[j] += 1;
            }
        }
    }

    int ans = 0;
    for (int i = 2; i <= n; i++) {
        if (cnt[i] > 1) {
            ans++;
        }
    }

    std::cout << ans << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.三位出题人

本题可能最大的阻力是读题吧，就是某一道题不可以被所有人一起看，也不允许某一道题没有人看，那对于每一道题而言，可以被做，那就是，这个数就是，由于有道题，再对这个数求个

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int mod = 1e9 + 7;

i64 ksm (i64 a, i64 b) {
    i64 res = 1;
    while(b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }

    return res;
}

void solve() {
    i64 n, m;
    std::cin >> n >> m;
    std::cout << ksm((ksm(2, m) - 2 + mod) % mod, n) << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

C.和天下

就是一个拆位来做的东西啊，可能是实现起来的时候把大家卡柱了。先考虑一下版本当的时候，是不是只要是任意两个按位与起来大于就可以建边，这个东西实现的时候就是枚举每一位嘛，如果某些数的该二进制位上的数是就把他们放到同一个集合里面他们之间可以两两建边，给大家写一段伪代码参考一下

std::vector<std::vector<int> > a(35);
    for (int j = 0; j <= 32; j++) {
        for (int i = 1; i <= n; i++) {
            if ((a[i] >> j) & 1) {
                v[j].push_back(a[i]);
            }
        }
    }

    for (int i = 0; i <= 32; i++) {
        for (int j = 1; j < v[i].size(); j++) {
            merge(v[i][j], v[i][j - 1]);
        }
    }

再来看本题不就是把变了嘛，但思路不变啊，如果的二进制串是，最高位在这位，那假设有和这两个数，他们的最高位在这位，这两个数按位与运算之后的数是不是一定大于了，那你可能会问了，那最高位与的最高位在同一个位置的怎么办，那我们就继续去看下一位嘛，比如的二进制串是，你有两个数是和，发现了什么，这两个数虽然最高位与的相同，但次高位比的大，这个时候我们其实可以就不管位上的那个，把这些数的下一个的位置看做是最高位的位置，在实现的时候可以把这三个数直接减去，这样就可以做到消除最高位相同的影响了啊，剩下的不就回到了hard版本开始的时候，看看那些数的二进制位置上有是比中的“最高位”的位置还高，实现起来可以参考我的代码

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, k;
    std::cin >> n >> k;
    
    std::vector<i64> a(n + 1);
    std::vector<int> p(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];

        p[i] = i;
        cnt[i] = 1;
    }

    auto find = [&] (auto self, int x) ->int {
        if (x == p[x]) {
            return x;
        }
        else {
            return p[x] = self(self, p[x]);
        }
    };

    auto merge = [&] (int u, int v) -> void {
        int fx = find(find, u), fy = find(find, v);
        if (fx != fy) {
            p[fx] = fy;
            cnt[fy] += cnt[fx];
        }
    };

    if (k == 0) {
        std::cout << n << '\n';
        return;
    }

    int target = 0;
    for (int i = 63; i >= 0; i--) {
        if ((k >> i) & 1) {
            target = i;
            break;
        }
    }

    // std::cout << target << '\n';
	//这里是在k不改变的情况下，有那些数进行按位与操作之后的大小比k大
    std::map<int, std::vector<int> > mp;
    for (int i = 1; i <= n; i++) {
        for (int j = 63; j > target; j--) {
            if ((a[i] >> j) & 1) {
                mp[j].push_back(i);
            }
        }
    }
	//这里是有哪些数的最高位1，小于等于k的最高位1的时候
    std::vector<int> vis(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = target; j >= 0; j--) {
            if (((k >> j) & 1) == 0) {
                if ((a[i] >> j) & 1 && vis[i]) {
                    mp[j].push_back(i);
                }
            }

            if (vis[i] && ((k >> j) & 1) && (((a[i] >> j) & 1) == 0)) {
                vis[i] = 0;
            }
        }
    }

    std::vector<int> v;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            v.push_back(i);
        }
    }


    for (int i = 1; i < v.size(); i++) {
        merge(v[i], v[i - 1]);
    }
    
    for (auto [it, v] : mp) {
        for (int i = 1; i < v.size(); i++) {
            merge(v[i], v[i - 1]);
        }
    }

    int ans = -1;
    for (int i = 1; i <= n; i++) {
        ans = std::max(ans, cnt[i]);
    }

    std::cout << ans << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

D.搬家

这个算是很板的倍增题吧，首先用双指针实现从任意一个位置开始装满一个箱子会到哪个位置，然后就是倍增的板子，最后算答案的时候就枚举看看从哪个位置开始装的东西最多，且不会超过，这个不知道还能说点什么了，大家不会的可以先去学一下倍增的思想。代码仅供参考

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;

    std::vector<i64> a(n + 1);
    for (i64 i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    i64 sum = 0;
    i64 logn = 31 - __builtin_clz(n);
    std::vector<std::vector<i64> > nxt(logn + 5, std::vector<i64> (n + 2));
    i64 l = 1, r = 1;
    while (l <= r && l <= n) {
        if (r == n + 1) {
            nxt[0][l] = r;
            sum -= a[l];
            l++;
            continue;
        }
        sum += a[r];
        while(sum > k) {
            nxt[0][l] = r;
            sum -= a[l];
            l++;
        }
        r++;
    }

    nxt[0][n + 1] = n + 1;

    for (i64 i = 1; i <= logn; ++i) {
        for (i64 j = 1; j <= n + 1; ++j) {
            nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
        }
    }

    i64 ans = -1;
    for (i64 i = 1; i <= n; i++) {
        i64 num = m, tmp = 0, l = i;
        for (i64 j = logn; j >= 0; j--) {
            if (num >= (1 << j)) {
                num -= (1 << j);
                tmp += nxt[j][l] - l;
                l = nxt[j][l];
                if (l == n + 1) break;
            }
        }
        ans = std::max(ans, tmp);
    }

    std::cout << ans << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}
}

E.Alice and Bod

精彩的线段树来了，我这里开了两棵线段树维护正反哈希，且在每一棵树中分别开了个懒标记，线段树中维护的数组就是每个字母对应的哈希值，比如某一个字符串那的代表的哈希值就是 + +与常规哈希不同，是把每个字母对应的位置进行哈希。然后就是维护这些东西了，在修改的时候比如是把这一段中的修改成了，那我们可以先记录一下的哈希值，然后把的哈希值赋给类似操作的字母就可以实现区间修改，我说不太明白再具体的维护方法，大家有问题可以来私信或评论。

#include<bits/stdc++.h>
#define lson (rt << 1)
#define rson (rt << 1 | 1)

using i64 = long long;
using u64 = unsigned long long;

const int mod=1610612741;
const int base=13331;

i64 ha[100005][2][26], p[100005], tmp[26];
int n, m;
std::string s;

struct treenode {
    int lz = 0;
    int len = 0;
    i64 vis[26];
    treenode (){
        for (int i = 0; i < 26; i++) {
            vis[i] = 0;
        }
    }
};

struct Segment_Tree {
    std::vector<treenode> tr;

    void init (int n, int i) {
        tr.resize((n + 1) << 2);
        build(1, 1, n, i);
    }

    treenode merge (int rt, treenode a, treenode b) {
        treenode res;
        res.lz = tr[rt].lz;
        res.len = a.len + b.len;
        for (int i = 0; i < 26; i++) {
            res.vis[i] = a.vis[i] * p[b.len] % mod + b.vis[i];
            res.vis[i] %= mod;
        }

        return res;
    }

    void change(int rt, int x) {
        tr[rt].lz += x;
        tr[rt].lz %= 26;
        for (int j = 0; j < 26; j++) {
            tmp[j] = tr[rt].vis[j];
        }
        for (int j = 0; j < 26; j++) {
            int t = (j + x) % 26;
            tr[rt].vis[t] = tmp[j];
        }
    }

    void push_down(int rt) {
        if (tr[rt].lz) {
            change(rt << 1, tr[rt].lz);
            change(rt << 1 | 1, tr[rt].lz);
            tr[rt].lz = 0;
        }
    }

    void build(int rt, int l, int r, int i) {
        tr[rt].lz = 0;
        if (l == r) {
            if (i == 0) {
                tr[rt].vis[s[l] - 'a'] = 1;
            }
            else {
                tr[rt].vis[s[n - l + 1] - 'a'] = 1;
            }
            tr[rt].len = 1;
            return;
        }

        int mid = l + r >> 1;
        build(lson, l, mid, i);
        build(rson, mid + 1, r, i);
        tr[rt] = merge(rt, tr[rt << 1], tr[rt << 1 | 1]);
    }

    void update(int rt, int l, int r, int L, int R, int x) {
        if (l >= L && r <= R) {
            change(rt, x);
            return;
        }
        push_down(rt);
        int mid = l + r >> 1;
        if (mid >= L)
            update(lson, l, mid, L, R, x);
        if (mid < R) {
            update(rson, mid + 1, r, L, R, x);
        }
        tr[rt] = merge(rt, tr[rt << 1], tr[rt << 1 | 1]);
    }

    treenode query(int rt, int l, int r, int L, int R) {
        if (l >= L && r <= R) {
            return tr[rt];
        }
        push_down(rt);
        treenode ans;
        int mid = l + r >> 1;
        if (mid >= L)
            ans = merge(rt, ans, query(lson, l, mid, L, R));
        if (mid < R)
            ans = merge(rt, ans, query(rson, mid + 1, r, L, R));
        return ans;
    }
}tr[2];

void solve() {
    std::cin >> n >> m;
    std::cin >> s;
    s = ' ' + s;

    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * base % mod;
        for (int j = 0; j < 26; j++) {
            ha[i][0][j] = (s[i] == ('a' + j));
            ha[n - i + 1][1][j] = ha[i][0][j];
        }
    }
    tr[0].init(n, 0);
    tr[1].init(n, 1);

    while(m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r;
            std::cin >> l >> r;

            auto v1 = tr[0].query(1, 1, n, l, r);
            auto v2 = tr[1].query(1, 1, n, n - r + 1, n - l + 1);
            
            bool flag = 1;
            for (int i = 0; i < 26; i++) {
                flag &= (v1.vis[i] == v2.vis[i]);
            }
            if (flag) {
                std::cout << "YES" << '\n';
            }
            else {
                std::cout << "NO" << '\n';
            }
        }
        else {
            int l, r, x;
            std::cin >> l >> r >> x;

            x %= 26;
            if (x == 0) continue;

            tr[0].update(1, 1, n, l, r, x);
            tr[1].update(1, 1, n, n - r + 1, n - l + 1, x);
        }
    }
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}