跳转至

杂题

F - substr = S

已知 \(f(i)\) 为 \(i\) 的数位中含有的 \(s\) 的个数

求 \(\sum_{i=L}^Rf(i)\)

固定 \(s\) 的位置, 发现对于第 \(i\) 个符合的匹配数, 去掉 \(s\) 后, 会得到 \(i-1\).

那么可以枚举 \(s\) 的出现位置, 然后二分求最大的符合的匹配数, 然后求和即可.

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 p10[18];
string str;
i64 strll;
void solve() {
    cin >> str;
    strll = 0;
    for (auto &x : str) {
        strll = strll * 10 + x - '0';
    }
    auto get1 = [&](int idx, i64 x) -> i64 {
        x--;
        if (x < 0) return 0LL;
        if (idx + str.size() >= 18) {
            return 0x7fffffffffffffff;
        }
        if (str[0] == '0') {
            x += p10[idx];
        }
        i64 p = x % p10[idx];
        i64 q = x / p10[idx];
        return q * p10[idx + str.size()] + strll * p10[idx] + p;

    };
    auto get2 = [&](i64 x) {
        i64 ans = 0;
        for (int i = 0 ; i < 16 ; i++) {
            i64 L = 0, R = p10[16 - str.size()];
            while (L < R) {
                i64 mid = L + R + 1 >> 1;
                if (get1(i, mid) <= x) {
                    L = mid;
                } else {
                    R = mid - 1;
                }
            }
            ans += L;
        }
        return ans;
    };
    i64 L, R;
    cin >> L >> R;
    cout << get2(R) - get2(L - 1) << "\n";
}
int main() {
    p10[0] = 1;
    for (int i = 1 ; i < 18 ; i++) {
        p10[i] = p10[i - 1] * 10;
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

小Q的无敌异或 - HydroOJ

求所有子区间异或的和 和 所有子区间和的异或

\(sumxor(L,R)=a_L\oplus a_{L+1}\oplus …\oplus a_R\)

求 \(\sum_{i=1}^n\sum_{j=i}^nsumxor(i,j)\) 和 \(sumxor(\sum_{i=1}^n\sum_{j=i}^n(a_i+a_{i+1}+…+a_j))\)

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int n;
int tr[100005];
int lowbit(int x) {
    return x & -x;
}
void add(int x) {
    while (x <= n + 1) {
        tr[x] ^= 1;
        x += lowbit(x);
    }
}
int query(int x) {
    int res = 0;
    while (x) {
        res ^= tr[x];
        x -= lowbit(x);
    }
    return res;
}
int a[100005];
i64 p[100005];
i64 sum[100005], sumXor[100005];
const i64 P = 998244353;
int main() {
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        sumXor[i] = sumXor[i - 1] ^ a[i];
    }
    i64 ans1 = 0, ans2 = 0;
    { // task 1
        for (int i = 20 ; i >= 0 ; i--) {
            array<int, 2> cnt{1, 0};
            for (int j = 1 ; j <= n ; j++) {
                int k = sumXor[j] >> i & 1;
                ans1 = (ans1 + cnt[k ^ 1] * (1LL << i) % P) % P;
                cnt[k]++;
            }
        }
    }
    { // task 2
        auto get = [&](i64 x) {
            return upper_bound(p, p + n + 1, x) - p;
        };
        for (int i = 37 ; i >= 0 ; i--) {
            for (int j = 0 ; j <= n ; j++) {
                p[j] = sum[j] & ((1LL << (i + 1)) - 1);
            }
            sort(p, p + n + 1);
            fill(tr, tr + n + 2, 0);
            int res = 0;
            for (int j = 0 ; j <= n ; j++) {
                i64 k = sum[j] & ((1LL << (i + 1)) - 1);
                add(get(k));
                int t1 = query(get(k - (1LL << i)));
                int t2 = query(get(k + (1LL << i)));
                int t3 = query(get(k));
                res ^= t1 ^ t2 ^ t3;
            }
            if (res & 1) {
                ans2 |= 1LL << i;
            }
        }
    }
    cout << ans1 << " " << ans2 << "\n";
    return 0;
}

I-The Yakumo Family_2023牛客暑期多校训练营5

\(f(L,R)=a_L\oplus a_{L+1}\oplus…\oplus a_R\)

求 \(\sum_{1\le{L_1}\le{R_1}<{L_2}\leq{R_2}<{L_3}\le{R_3}<{n}}f(L_1,R_1)\times{f(L_2,R_2)}\times{f(L_2,R_2)}\) 的值

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[200005], sumXor[200005], sum[200005], f[200005];
const i64 P = 998244353;
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        sumXor[i] = sumXor[i - 1] ^ a[i];
    }
    for (int i = 1 ; i <= n ; i++) {
        sum[i] = 1;
    }
    for (int _ = 0 ; _ < 3 ; _++) {
        for (int i = 30 ; i >= 0 ; i--) {
            array<i64, 2> cnt{_ == 0, 0};
            for (int j = 1 ; j <= n ; j++) {
                int k = sumXor[j] >> i & 1;
                f[j] = (f[j] + cnt[k ^ 1] * (1LL << i) % P) % P;
                cnt[k] = (cnt[k] + sum[j]) % P;
            }
        }
        for (int i = 1 ; i <= n ; i++) {
            sum[i] = (sum[i - 1] + f[i]) % P;
            f[i] = 0;
        }
    }
    cout << sum[n] << "\n";
    return 0;
}

E-小红的循环节长度_牛客周赛 Round 6

求 \(\frac{p}{q}\) 的 最小循环节长度以及循环节前面的部分

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
i64 eulerPhi(i64 n) {
    i64 ans = n;
    for (int i = 2 ; 1LL * i * i <= n ; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) {
                n /= i;
            }
        }
    }
    if (n > 1) {
        ans = ans / n * (n - 1);
    }
    return ans;
}
i64 qpow(__int128 a, i64 b, i64 P, __int128 res = 1) {
    while (b) {
        if (b & 1) {
            res = res * a % P;
        }
        a = a * a % P;
        b >>= 1;
    }
    return res;
}
int main() {
    i64 p, q;
    cin >> p >> q;
    i64 k = __gcd(p, q);
    p /= k;
    q /= k;
    int cnt2 = 0, cnt5 = 0;
    while (q % 2 == 0) {
        q /= 2;
        cnt2++;
    }
    while (q % 5 == 0) {
        q /= 5;
        cnt5++;
    }
    if (q == 1) {
        cout << -1 << "\n";
    } else {
        cout << max(cnt2, cnt5) << " ";
        i64 ans = 0x7fffffffffffffff;
        i64 phi = eulerPhi(q);
        for (int i = 1 ; 1LL * i * i <= phi ; i++) {
            if (phi % i == 0) {
                if (qpow(10, i, q) == 1) {
                    ans = min<i64>(ans, i);
                }
                if (qpow(10, phi / i, q) == 1) {
                    ans = min<i64>(ans, phi / i);
                }
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

P4688 [Ynoi2016] 掉进兔子洞 - 洛谷

多次询问, 每次询问给出三个区间，三个区间的数全部拿出来, 然后删掉三个区间同时出现的数(也就是出现了 \(2\) 个 \(4\), 则删掉 \(2*3\) 个 \(4\)), 问剩下几个数.

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int n;
int a[100005];
int belong[100005], st[100005], ed[100005];
struct MO {
    int L, R, idx;
    friend bool operator<(const MO &x, const MO &y) {
        if (belong[x.L] != belong[y.L]) {
            return x.L < y.L;
        }
        if (belong[x.L] & 1) {
            return x.R < y.R;
        }
        return x.R > y.R;
    }
};
bitset<100001> bs[100000 / 3 + 1], res;
int cnt[100005];
bool vis[100005];
void add(int x) {
    res[cnt[x] + x] = 1;
    cnt[x]++;
}
void del(int x) {
    cnt[x]--;
    res[cnt[x] + x] = 0;
}
void solve(int q) {
    vector<MO> mo;
    vector<int> ans(q);
    for (int i = 0 ; i < q ; i++) {
        for (int j = 0 ; j < 3 ; j++) {
            int L, R;
            cin >> L >> R;
            mo.push_back({L, R, i});
            ans[i] += R - L + 1;
        }
    }
    sort(begin(mo), end(mo));
    fill(vis, vis + n + 1, false);
    fill(cnt, cnt + n + 1, 0);
    res.reset();
    int L = 1, R = 0;
    for (auto &[QL, QR, idx] : mo) {
        while (L > QL) {
            add(a[--L]);
        }
        while (R < QR) {
            add(a[++R]);
        }
        while (L < QL) {
            del(a[L++]);
        }
        while (R > QR) {
            del(a[R--]);
        }
        if (vis[idx]) {
            bs[idx] &= res;
        } else {
            vis[idx] = true;
            bs[idx] = res;
        }
    }
    for (int i = 0 ; i < q ; i++) {
        ans[i] -= bs[i].count() * 3;
        cout << ans[i] << "\n";
    }
}
int main() {
    int q;
    cin >> n >> q;
    {
        int B = sqrt(n);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
        }
    }
    vector<int> idx(1);
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    int B = q / 3;
    solve(B);
    solve(B);
    solve(q - 2 * B);
    return 0;
}

Problem - E - Codeforces

\(n\) 排列

问有多少子区间 \([L,R]\) 满足区间 \(\max\) 出现在区间 \(\min\) 的右侧.

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[1000005];
int miL[1000005], mxL[1000005], miR[1000005], mxR[1000005];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    { // 单调栈处理 左边小的和右边小的
        stack<int> st;
        for (int i = 1 ; i <= n ; i++) {
            miR[i] = n + 1;
        }
        for (int i = 1 ; i <= n ; i++) {
            while (!st.empty() && a[i] < a[st.top()]) {
                miR[st.top()] = i;
                st.pop();
            }
            miL[i] = st.empty() ? 0 : st.top();
            st.push(i);
        }
    }
    { // 单调栈处理 左边大的和右边大的
        stack<int> st;
        for (int i = 1 ; i <= n ; i++) {
            mxR[i] = n + 1;
        }
        for (int i = 1 ; i <= n ; i++) {
            while (!st.empty() && a[i] > a[st.top()]) {
                mxR[st.top()] = i;
                st.pop();
            }
            mxL[i] = st.empty() ? 0 : st.top();
            st.push(i);
        }
    }
    i64 ans = 0;
    for (int i = 1 ; i <= n ; i++) {
        int L = mxL[i], R = mxR[i];
        if (i - L > R - i) {
            int now = n;
            for (int j = i ; j < R ; j++) {
                now = min(now, miL[j]);
                ans += max(0, now - L);
            }
        } else {
            int now = i;
            for (int j = i ; j > L ; j--) {
                if (a[j] < a[now]) {
                    now = j;
                }
                if (now != i) {
                    ans += max(0, min(R, miR[now]) - i);
                }
            }
        }
        // cout << i << " " << ans << "\n";
    }
    cout << ans << "\n";
    return 0;
}