A题:

简单的计算题,开long double防止精度问题;

#include<bits/stdc++.h>

using i64  = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    int n; std::cin >> n;
    
    long double pie = 3.14159265358979;
    long double ans = ((double)n / 2.0) * ((double)n / 2.0) * pie;

    printf("%.13Lf", ans);

    return 0;
}

B题:

简单计数题,根据查询直接计算就可以;

#include<bits/stdc++.h>

using i64  = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    int h, w; std::cin >> h >> w;
    int q; std::cin >> q;
    
    while(q--){
        int chose, x; std::cin >> chose >> x;

        if(chose == 1){
            std::cout << x * w << '\n';
            h -= x;
        }else{
            std::cout << x * h << '\n';
            w -= x;
        }
    }

    return 0;
}

C题:

简单题,用一个滑动窗口统计对应字母数量即可;

#include<bits/stdc++.h>

using i64  = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    int n, l, r; std::cin >> n >> l >> r;
    std::string s; std::cin >> s;

    std::map<char, int> cnt;

    for(int i = l;i <= r;i++) cnt[s[i]]++;
    i64 ans = 0;
    for(int i = 0;i < n;i++){
        if(i != 0){
            if(i + l >= n) break;

            cnt[s[i + l - 1]]--;

            if(i + r < n) cnt[s[i + r]]++;
        }

        ans += cnt[s[i]];
    }

    std::cout << ans;
    return 0;
}

D题:

这题太阴了,这题是数据量在1e6有简单做法(O(n)),但是一开始走了O(1)做法卡了半天;

由题目,可以看出来这道题的规律, x在偶数时形成的图像全局来看就是一个正方形,且边长为 |x|×2+1;根据这个就可以遍历一轴来计算黑点;代码ai跑的,如下:

#include <iostream>
#include <algorithm>

using namespace std;

// 计算 [l, r] 区间内有多少个偶数喵
long long count_even(long long l, long long r) {
    if (l > r) return 0;
    auto f = [](long long x) {
        if (x >= 0) return x / 2;
        return (x - 1) / 2;
    };
    return f(r) - f(l - 1);
}

int main() {
    // 优化输入输出速度喵
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long L, R, D, U;
    if (!(cin >> L >> R >> D >> U)) return 0;

    long long total_black = 0;

    for (long long x = L; x <= R; ++x) {
        long long X = x >= 0 ? x : -x;
        
        // 计算与 [-X, X] 的区间交集喵
        long long inter_l = max(D, -X);
        long long inter_r = min(U, X);
        
        // 第一部分：在 [-X, X] 内部的 y
        if (inter_l <= inter_r) {
            if (X % 2 == 0) {
                total_black += (inter_r - inter_l + 1);
            }
        }
        
        // 第二部分：在 [-X, X] 下方的 y
        if (D < -X) {
            long long bottom_r = min(U, -X - 1);
            total_black += count_even(D, bottom_r);
        }
        
        // 第三部分：在 [-X, X] 上方的 y
        if (U > X) {
            long long top_l = max(D, X + 1);
            total_black += count_even(top_l, U);
        }
    }

    cout << total_black << "\n";
    return 0;
}

实际上可以吧坐标都转化到第一象限来计算,所以只考虑一象限用容斥定理来做这道题就行;对于坐标 x1,\ x2,\ y1,\ y2,记 f(x, y)为点 (0, 0) 到点 (x,y)的黑点个数,化坐标后就可以这样计算:

sum = f(x2, y2) - f(x2, y1 - 1) - f(x1 - 1, y2) + f(x1 - 1, y1 - 1)

所以重点放在坐标变化和 f的计算上,发现实际上任意的一象限坐标对应的 f(x, y)都是一个正方形加上一个矩形,那么计算也就解决了,如下:

正方形为{(0, 0)} × {(m, m)};矩形为{(m, m)} × {(x, y)}或{(y, x)}    
std::function<i64(i64, i64)> getSum = [&](i64 x, i64 y) ->i64 {
        if(x < 0 || y < 0) return 0;

        i64 m = std::min(x, y);

        i64 k = (m / 2) + 1;
        i64 ans = k * (2 * k - 1);//等差数列求和

        if(x > y){
            ans += (y + 1) * ((x / 2) - m / 2);计算矩形内的黑点数
        }else if(y > x){
            ans += (x + 1) * ((y / 2) - m / 2);
        }

        return ans;
    };

坐标的变化,就是把其他象限的部分折到第一象限,只考虑边界就会简单很多,如下:

    std::function<std::vector<std::pair<i64, i64>>(i64, i64)> getq = [&](i64 px, i64 ix) ->std::vector<std::pair<i64, i64>> {
        std::vector<std::pair<i64, i64>> now;

        if(px >= 0) now.push_back({px, ix});
        else if(ix < 0) now.push_back({-ix, -px});
        else{
            now.push_back({1, -px});
            now.push_back({0, ix});
        }

        return now;
    };

最后O(1)计算答案即可,代码如下:

#include<bits/stdc++.h>

using i64  = long long;

int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    
    i64 x1, x2, y1, y2; std::cin >> x1 >> x2 >> y1 >> y2;

    std::function<std::vector<std::pair<i64, i64>>(i64, i64)> getq = [&](i64 px, i64 ix) ->std::vector<std::pair<i64, i64>> {
        std::vector<std::pair<i64, i64>> now;

        if(px >= 0) now.push_back({px, ix});
        else if(ix < 0) now.push_back({-ix, -px});
        else{
            now.push_back({1, -px});
            now.push_back({0, ix});
        }

        return now;
    };

    std::function<i64(i64, i64)> getSum = [&](i64 x, i64 y) ->i64 {
        if(x < 0 || y < 0) return 0;

        i64 m = std::min(x, y);

        i64 k = (m / 2) + 1;
        i64 ans = k * (2 * k - 1);

        if(x > y){
            ans += (y + 1) * ((x / 2) - m / 2);
        }else if(y > x){
            ans += (x + 1) * ((y / 2) - m / 2);
        }

        return ans;
    };

     std::function<i64(i64, i64, i64, i64)> query = [&](i64 px, i64 ix, i64 py, i64 iy){
        i64 sum = getSum(ix, iy) - getSum(px - 1, iy) - getSum(ix, py - 1) + getSum(px - 1, py - 1);
        return sum;
    }; 

    auto gx = getq(x1, x2);
    auto gy = getq(y1, y2);

    i64 ans = 0;
    for(const auto& i : gx){
        for(const auto& j : gy){
            ans += query(i.first, i.second, j.first, j.second);
        }
    }

    std::cout << ans;
    return 0;
}