算法竞赛进阶指南第四天-CSDN博客

本文链接：https://blog.csdn.net/weixin_60522059/article/details/128545794

本文包含三道编程题目，第一题涉及构建分形城市的位置计算，第二题是关于矩阵的前缀和求解激光炸弹影响范围，第三题讨论如何通过加减操作使序列中所有数相等，涉及差分序列分析。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目解析：很难讲清楚

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long ,long long> pll;
pll POS(int N,ll m){
    if(N==0){
        return {0,0};
    }
    ll len = 1LL << (N - 1);
    ll num = 1LL << (2 * N - 2);
    pll pos = POS(N-1,m%num);
    int j=m/num;
    ll x=pos.first; ll y=pos.second;
    if(j==0){
        return {-y-len,-x+len};
    }
    else if(j==1){
        return {x+len,y+len};
    }
    else if(j==2){
        return {x+len,y-len};
    }
    else if(j==3){
        return {y-len,x-len};
    }
}
int main(){
    int N,n;
    ll A,B;
    scanf("%d",&n);
    while(n--){
        cin>>N>>A>>B;
        pll pos1=POS(N,A-1); pll pos2=POS(N,B-1);
        double x=(double)(pos1.first-pos2.first); double y=(double)(pos1.second-pos2.second);
        printf("%.0lf\n",sqrt(x*x+y*y)*5);
    }
    return 0;
}

0x03

2.激光炸弹

基本前缀和问题，不赘述了

#include<bits/stdc++.h>
using namespace std;
const int MAX=5e3+10;
int s[MAX][MAX];
int main(){
    int N,R;
    cin>>N>>R;
    R=min(R,5001);
    int X,Y,W;
    for(int i=0;i<N;i++){
        cin>>X>>Y>>W;
        s[X+1][Y+1]+=W;
    }
    for(int i=1;i<=5001;i++){
        for(int j=1;j<=5001;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    int ans=0;
    for(int i=R;i<=5001;i++){
        for(int j=R;j<=5001;j++){
            ans=max(ans,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
        }
    }
    cout<<ans;
    return 0;
}

3.IncDec序列

想让所有数列中的数都一样，即对于其的差分序列，b1可以为任意数=a1，b2-bn必须全为0，bn+1也可以为任意数，每次加1或减1相当于让b数组中的任意两个进行操作

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int x;
    vector<int>a;
    long long zheng=0;long long fu=0;
    for(int i=0;i<n;i++){
        cin>>x;
        a.push_back(x);
    }
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]>0){
            zheng+=a[i]-a[i-1];
        }
        else if(a[i]-a[i-1]<0){
            fu+=a[i]-a[i-1];
        }
    }
    printf("%lld\n%lld",max(zheng,abs(fu)),abs(zheng-abs(fu))+1LL);
    return 0;
}