#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int cows[N];
double sum[N];
int n, f;
bool check(double avg)
{
    for (int i = 1; i <= n; i++ ) //初始前缀和减平均值
        sum[i] = sum[i - 1] + cows[i] - avg;
    double minv = 0;
    for (int i = 0, j = f; j <= n; i ++ , j ++ )
    {
        minv = min(minv, sum[i]); //记录最小值
        if (sum[j] - minv >= 0) return true;
    }
    return false;
}
int main()
{
    cin >> n >> f;
    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> cows[i];
        r = max(r, (double)cows[i]); //设定二分初始右边界
    }
    while (r - l > 1e-6)
    {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    printf("%d\n", (int)(r * 1000));
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
const int N = 1e5 + 10;
int n, m, p, h;
int s[N];

int main()
{
    cin >> n >> p >> h >> m;
    set<pair<int, int>> existed;
    s[1] = h;
    for (int i = 1, a, b; i <= m; i ++ )
    {
        cin >> a >> b;
        if (a > b) swap(a, b);
        if (!existed.count({a, b}))
        {
            existed.insert({a, b});
            s[a + 1] -- , s[b] ++ ;
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        s[i] += s[i - 1];
        cout << s[i] << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL n, pos, neg;
LL a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = n; i > 0; i -- ) a[i] = a[i] - a[i - 1];
    for (int i = 2; i <= n; i ++ ) 
        if (a[i] > 0)
            pos += a[i]; 
        else if (a[i] < 0)
            neg -= a[i];
    cout << max(neg, pos) << endl;
    cout << abs(neg - pos) + 1 << endl;
    return 0;
}

#include <iostream>
using namespace std;
const int N = 5e3 + 10;
int s[N][N];
int m = 5001;

int main()
{
    int cnt, r;
    cin >> cnt >> r;
    r = min(r, 5001);

    while (cnt -- )
    {
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        x ++ , y ++ ;
        s[x][y] += w;
    }

    for (int i = 1;  i <= m; i ++ )
        for (int j = 1; j <= m; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    int res = 0;
    for (int i = r; i <= m; i ++ )
        for (int j = r; j <= m; j ++ )
            res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);

    cout << res << endl;
    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
int n;

PLL calc(LL n, LL m)
{
    if (n == 0) return {0, 0};
    LL len = 1ll << (n - 1);
    LL cnt = 1ll << (2 * n - 2);
    PLL pos = calc(n - 1, m % cnt);
    int z = m / cnt;
    LL x = pos.first, y = pos.second;
    if (z == 0) return {y - len, x - len};
    if (z == 1) return {x - len, y + len};
    if (z == 2) return {x + len, y + len};
    if (z == 3) return {-y + len, -x - len};
}

int main()
{
    cin >> n;
    while (n -- )
    {
        LL A, B, N;
        cin >> N >> A >> B;
        PLL da = calc(N, A - 1);
        PLL db = calc(N, B - 1);
        double dx = da.first - db.first, dy = da.second - db.second;
        printf("%.0lf\n", sqrt(dx * dx + dy * dy) * 5);
    }
}

题目链接 acwing98/蓝书19页/POJ3889 分形之城

acwing98 分形之城
y总代码中z==3这一步 类似于z=0，1，2都是平移旋转 为何z=3时的坐标变换 多了减1。

y总的AC代码：

PLL calc(LL n, LL m)
{
    if (!n) return {0, 0};
    LL len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
    auto pos = calc(n - 1, m % cnt);
    auto x = pos.first, y = pos.second;
    auto z = m / cnt;
    if (z == 0) return {y, x};
    if (z == 1) return {x, y + len};
    if (z == 2) return {x + len, y + len};
    return {len * 2 - 1 - y, len - x - 1}; //<-------------这一步
}

#include <iostream>
using namespace std;
const int mod = 9901;
int A, B;

int qmi(int a, int k)
{
    a %= mod;
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}


int sum(int p, int k)
{
    if (k == 0) return 1;
    if (k % 2 == 0) return (p % mod * sum(p, k - 1) % mod + 1) % mod;
    else return sum(p, k / 2) % mod * (1 + qmi(p, k / 2 + 1)) % mod;//奇数向下取整 k / 2 + 1 + k / 2 = k
}

int main()
{
    cin >> A >> B;
    int res = 1;
    for (int i = 2; i <= A / i; i ++ )
    {
        int s = 0;
        while (A % i == 0)
        {
            s ++ ;
            A /= i;
        }
        if (s) res = res * sum(i, s * B) % mod;
    }
    if (!A) res = 0;
    if (A > 1) res = res * sum(A, B) % mod;
    cout << res << endl;
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int main()
{
    int d[N], f[N];
    d[1] = 1;
    memset(f, 0x3f, sizeof f);
    for (int i = 2; i <= 12; i ++ )
    {
        d[i] = d[i - 1] * 2 + 1;
    }
    f[0] = 0;
    for (int i = 1; i <= 12; i ++ )
    {
        for (int j = 0; j < i; j ++ )
            f[i] = min(f[i], f[j] * 2 + d[i - j]);
        cout << f[i] << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
const int INF = 100000;
char g[10][10];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};
void turn(int x, int y){
    for (int i = 0; i < 5; i ++ ){
        int a = x + dx[i], b = y + dy[i];
        if (a >= 0 && a < 5 && b >= 0 && b < 5)
            g[a][b] = '0' + !(g[a][b] - '0');
    }
}
int work(){
    int ans = INF;
    for (int k = 0; k < 1 << 5; k ++ ){
        int res = 0;
        char backup[10][10];
        memcpy(backup, g, sizeof g);
        for (int j = 0; j < 5; j ++ ){
            if (k >> j & 1) res ++ , turn(0, j);
        }
        for (int i = 0; i < 4; i ++ )
            for (int j = 0; j < 5; j ++ )
                if (g[i][j] == '0')
                    res ++ , turn(i + 1, j);
        bool is_successful = true;
        for (int j = 0; j < 5; j ++ )
            if (g[4][j] == '0'){
                is_successful = false;
                break;
            }
        if (is_successful) ans = min(ans, res);
        memcpy(g, backup, sizeof g);
    }
    if (ans > 6) return -1;
    return ans;
}
int main(){
    int T;  cin >> T;
    while (T -- ){
        for (int i = 0; i < 5; i ++ ) cin >> g[i];
        cout << work() << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> path;

void dfs(int u, int state)
{
    if (u == n)
    {
        for (auto x : path)
            cout << x << ' ';
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i ++ )
        //搜索顺序区别于前两题 前两题枚举的是是否选择这个数
        //本题枚举的是该位置是否有数
        if (!(state >> i & 1)) 
        {
            path.push_back(i + 1);
            dfs(u + 1, state | 1 << i);
            path.pop_back();
        }
}
int main()
{
    cin >> n;
    dfs(0, 0);
    return 0;
}