1221. 四平方和

问题描述

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多 4 个正整数的平方和。如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

例如：

• (5 = 0^2 + 0^2 + 1^2 + 2^2)
• (7 = 1^2 + 1^2 + 1^2 + 2^2)

对于一个给定的正整数，可能存在多种平方和的表示法。要求对 4 个数排序，满足 (0 \leq a \leq b \leq c \leq d)，并对所有的可能表示法按 (a)、(b)、(c)、(d) 为联合主键升序排列，最后输出第一个表示法。

输入格式

输入一个正整数 (N)。

输出格式

输出 4 个非负整数，按从小到大排序，中间用空格分开。

数据范围

(0 < N < 5\times10^6)

输入输出样例

输入样例

5

输出样例

0 0 1 2

问题思路

问题代码

暴力做法如下

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin>>n;//得到我们要计算的数字
    //题目要求我们以字典序输出，那么我们从a开始到d进行for循环
    for(int a=0;a*a<=n;a++){
        for(int b=a;a*a+b*b<=n;b++){
            for(int c=b;a*a+b*b+c*c<=n;c++){
                int t=n-a*a-b*b-c*c;
                int d=sqrt(t);//注意这个地方必须是int d，如果是提前定义的int的话，比如d=sqrt(t)
                //那么这个时候，就会出现问题
                if(d*d==t){
                    printf("%d %d %d %d\n",a,b,c,d);
                    return 0; 
                }
            }
        }
        
    }
}

二分做法

//由于题目要求最终的输出结果满足字典序，所以我们采用以下的方法
//首先要计算出c和d的值，并将这些值（c，d，c*c+d+d）保存下来，并通过某种手段，将保存下来的数据，按照c*c+d*d的大小排列
//随后计算a和b的值，通过与n值相减，从而得到应有的c*c+d*d的值
//之后，经过二分的处理，更快的得到c和d

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>


using namespace std;
const int N=5e6+10;

struct sum{
    int s,c,d;
    bool operator< (const sum &t)const{
        if (s!=t.s) return s<t.s;//这里的条件只能是不等于，这样写的目的就是为了简化代码
        if(c!=t.c) return c<t.c;
        return d<t.d;
    }
}su[N];
int m;//记录保存下来有多少个c和d组合
int main(){
    int n;
    cin>>n;
    for(int c=0;c*c<=n;c++){
        for(int d=c;c*c+d*d<=n;d++){
            //计算出所有结果，保存
            su[m++]={c*c+d*d,c,d};
        }
    }
    sort(su,su+m);
    //接下来进行c和d的枚举
    for(int a=0;a*a<=n;a++){
        for(int b=0;b*b+a*a<=n;b++){
            int t=n-a*a-b*b;//对于二分，这个t就是我要查找的x值
            int l=0,r=m-1;
            while(l<r){
                int mid=l+r>>1;
                if(su[mid].s>=t) r=mid;
                else l=mid+1;
            }
            if(su[l].s==t) {
                printf("%d %d %d %d",a,b,su[l].c,su[l].d);
                return 0;
            }
            
        }
    }
    
    
    return 0;
}

哈希表

//哈希表的方法，是在二分的基础上再进行修改，在二分的解决方法中，我们创建了一个struct sum 结构体
//而在这里我们通过使用unorderer_map中的结构，便不再需要创建结构体了
//并且也不在需要对结果相同的c和d进行保存，只需要保存遍历到的第一个
//不在需要对保存过来的进行计数，因为，不需要再进行手动排序
//由于哈希表是字典的结构，所以我们让key值为c*c+d*d，另外创建一个pair结构，用来保存c和d

//哈希表做法
#include<iostream>
#include <cstdio>
#include<cstring>
#include<algorithm>
#include <unordered_map>

#define x first
#define y second

using namespace std;


typedef pair<int,int> PII;
unordered_map<int,PII> S;


int main(){
    int n;
    cin>>n;
    for(int c=0;c*c<=n;c++){
        for(int d=c;c*c+d*d<=n;d++){
            int t=c*c+d*d;
            if(S.count(t)==0) S[t]={c,d};
        }
    }
    
    for(int a=0;a<=n;a++)
        for(int b=a;b<=n;b++){
            int t=n-a*a-b*b;
            if(S.count(t)){
                printf("%d %d %d %d",a,b,S[t].x,S[t].y);
                return 0;
            }
        }
    
    return 0;
}

1227. 分巧克力

问题描述

儿童节那天有 $K$ 位小朋友到小明家做客，小明拿出珍藏的 $N$ 块巧克力招待他们。其中第 $i$ 块巧克力是 $H_i\times W_i$ 的方格组成的长方形。

为公平起见，小明要从这 $N$ 块巧克力中切出 $K$ 块形状为正方形、边长为整数且大小相同的巧克力分给小朋友们。

例如，一块 $6\times 5$ 的巧克力可以切出 $6$ 块 $2\times 2$ 的巧克力或者 $2$ 块 $3\times 3$ 的巧克力。

小朋友们希望得到的巧克力尽可能大，需要计算出能切出的正方形巧克力的最大边长。

输入格式

• 第一行包含两个整数 $N$ 和 $K$。
• 以下 $N$ 行每行包含两个整数 $H_i$ 和 $W_i$。

输入保证每位小朋友至少能获得一块 $1\times 1$ 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

数据范围

• $1\le N,K\le 10^5$
• $1\le H_i,W_i\le 10^5$

输入输出样例

输入样例

2 10
6 5
5 6

输出样例

2

问题思路

问题代码

#include<iostream>
#include <cstdio>
#include<cstring>
#include <algorithm>

using namespace std;

const int N=1e5+10;
int H[N],W[N];
int n,k;
//最后至少要有k块巧克力

int check(int mid){
    int res=0;//局部变量必须赋值
    for(int i=0;i<n;i++){
        res+=(W[i]/mid)*(H[i]/mid);//结果是最后能得到的分割后巧克力数量
    }
    return res;
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d %d",&H[i],&W[i]);
    //完成输入
    
    int l=1,r=1e5;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)>=k){
            //check函数的结果是返回当前能够切割出巧克力的数量
            //说明此时，巧克力的大小还可以扩大
            l=mid;
        }
        else r=mid-1;
    }
    cout<<r<<endl;
    
    return 0;
    
}

795. 前缀和

问题描述

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l, r。对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。

输入格式

第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。

输出格式

共 m 行，每行输出一个询问的结果。

数据范围

• (1\leq l\leq r\leq n)
• (1\leq n,m\leq 100000)
• (-1000\leq) 数列中元素的值 (\leq 1000)

输入样例

5 3
2 1 3 6 4
1 2
1 3
2 4

输出样例

3
6
10

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int N=1e5+10;
int a[N],s[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){ 
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    while(m--){
        int a,b;
        cin>>a>>b;
        cout<<s[b]-s[a-1]<<endl;
        
    }
    return 0;
}

796. 子矩阵的和

子矩阵和查询问题

问题描述

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

输入格式

1. 第一行包含三个整数n，m，q 。
2. 接下来n行，每行包含m个整数，表示整数矩阵。
3. 接下来q行，每行包含四个整数x1,y1,x2,y2，表示一组询问。

输出格式

共q行，每行输出一个询问的结果。

数据范围

• 1≤n,m≤1000
• 1≤q≤200000
• 1≤x1≤x2≤n
• 1≤y1≤y2≤m
• -1000≤矩阵内元素的值≤1000

输入样例

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

输出样例

17
27
21

题目思路

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3+10;
int a[N][N],s[N][N];

int main(){
    int x1,y1,x2,y2,n,m,q;
    scanf("%d%d%d", &n, &m, &q);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }//完成前缀和的模板
    while(q--){
        //随后根据题目所给的x1x2x3x4进行计算
        cin>>x1>>y1>>x2>>y2;
        printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
    }
   
    return 0;
}

99. 激光炸弹

题目描述

地图上有 $N$ 个目标点，用整数 $X_i,Y_i$ 表示目标在地图上的位置，每个目标都有一个价值 $W_i$。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含 $R\times R$ 个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和 $x$，$y$ 轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数 $N$ 和 $R$，分别代表地图上的目标数目和正方形包含的横纵位置数量，数据用空格隔开。

接下来 $N$ 行，每行输入一组数据，每组数据包括三个整数 $X_i,Y_i,W_i$，分别代表目标的 $x$ 坐标，$y$ 坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

• $0\le R\le 10^9$
• $0<N\le 10000$
• $0\le X_i,Y_i\le 5000$
• $0\le W_i\le 1000$

输入样例

2 1
0 0 1
1 1 1

输出样例

1

题目代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N=5e3+10;
int s[N][N];

int main(){
    int n,r;
    cin>>n>>r;
    r=min(r,5001);
    int x_max=r,y_max=r;
    while(n--){
        int x,y,w;
        
        scanf("%d %d %d",&x,&y,&w);
        x++,y++;
        s[x][y]+=w;
        x_max=max(x_max,x),y_max=max(y_max,y);
    }
    //完成所有的输入，之后再遍历一遍，计算出来前缀和的模板
    
     for (int i = 1; i <= x_max; i ++ )
        for (int j = 1; j <= y_max; 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<=x_max;i++){
        for(int j=r;j<=y_max;j++){
           res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
        }
    }
    cout<<res;
    return 0;
}