嘉.
2小时前
import java.io.*;

public class Main{
    static int arr[][]=new int[1010][1010];
    static int b[][]=new int[1010][1010];
    public static void main(String[] args) throws IOException {
        BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
        String s[]=r.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int m=Integer.parseInt(s[1]);
        int q=Integer.parseInt(s[2]);

        for(int i=1;i<=n;i++){
            String line[]=r.readLine().split(" ");
            for (int j = 1; j <=m ; j++) {
                Insert(i,j,i,j,Integer.parseInt(line[j-1]));
            }
        }//存储这些数字
        while(q-->0){
            String qq[]=r.readLine().split(" ");
            int x1=Integer.parseInt(qq[0]);
            int y1=Integer.parseInt(qq[1]);
            int x2=Integer.parseInt(qq[2]);
            int y2=Integer.parseInt(qq[3]);
            int c=Integer.parseInt(qq[4]);
            Insert(x1,y1,x2,y2,c);
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                System.out.print(b[i][j]+" ");
            }
            System.out.println(" ");
        }

    }


    public static void Insert(int x1,int y1,int x2,int y2,int c){
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;

    }
}



题目描述

四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多 4个正整数
的平方和。如果把 0包括进去,就正好可以表示为 4个数的平方和。比如:
    5=0^2+0^2+1^2+2^2
    7=1^2+1^2+1^2+2^2
对于一个给定的正整数,可能存在多种平方和的表示法。要求你对 4个数排序:0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列,最后输出第一个表示法。

样例

输入格式

输入一个正整数 N。

输出格式

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

数据范围

1 <= N <= 5 * 10^6

输入样例:

5

输出样例:

0 0 1 2

算法1

(枚举 + 哈希)

刚开始根据题意,直接四重循环暴力枚举a,b,c,d,意料之中的超时了,后来慢慢优化,优化成三重循环,仍然不行(当时没有理解清楚到 a <= b<= c<= d这个关系),再然后,就想到了打表

  1. 建立哈希表,存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
  2. 从小到大遍历a、b,查找1中建立的哈希表,若 h[n - a^2 - b^2]存在,则算出d,

时间复杂度 O(n)

空间复杂度 O(n)

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e8 + 10;
int h[N];
int main() {
    int n;
    cin >> n;
    //打表,找出1 - n,所有完全平方数两两之和,如果存在只记第一次出现(题目要求找出字典序小的)
    for (int i = 0; i * i * 2<= n; i++) {
        for (int j = i; j * j + i * i <= n; j++) {
            if (!h[i * i + j * j])
                h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况
        }
    }
    //0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; 
    for (int i = 0; i * i * 4 <= n; i++) {
        for (int j = i; j * j + i * i <= n / 2; j++) {
            int t = n - i * i - j * j;
            if (h[t]) {
                int c = h[t] - 1;   
                int d = (sqrt(t - c * c) + 1e-4);
                printf("%d %d %d %d", i, j, c, d);
                return 0;
            }
        }
    }
    return 0;
}



题目描述

四平方和定理,又称为拉格朗日定理:每个正整数都可以表示为至多 4个正整数
的平方和。如果把 0包括进去,就正好可以表示为 4个数的平方和。比如:
    5=0^2+0^2+1^2+2^2
    7=1^2+1^2+1^2+2^2
对于一个给定的正整数,可能存在多种平方和的表示法。要求你对 4个数排序:0≤a≤b≤c≤d
并对所有的可能表示法按 a,b,c,d为联合主键升序排列,最后输出第一个表示法。

样例

输入格式

输入一个正整数 N。

输出格式

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

数据范围

1 <= N <= 5 * 10^6

输入样例:

5

输出样例:

0 0 1 2

算法1

(枚举 + 哈希)

刚开始根据题意,直接四重循环暴力枚举a,b,c,d,意料之中的超时了,后来慢慢优化,优化成三重循环,仍然不行(当时没有理解清楚到 a <= b<= c<= d这个关系),再然后,就想到了打表

  1. 建立哈希表,存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
  2. 从小到大遍历a、b,查找1中建立的哈希表,若 h[n - a^2 - b^2]存在,则算出d,

时间复杂度 O(n)

空间复杂度 O(n)

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e8 + 10;
int h[N];
int main() {
    int n;
    cin >> n;
    //打表,找出1 - n,所有完全平方数两两之和,如果存在只记第一次出现(题目要求找出字典序小的)
    for (int i = 0; i * i * 2<= n; i++) {
        for (int j = i; j * j + i * i <= n; j++) {
            if (!h[i * i + j * j])
                h[i * i + j * j] = i + 1;//防止i = 0时在后面判断查找跳过 i = 0的情况
        }
    }
    //0<= a <= b <= c <= d,可以得出a^2 <= n / 4, a^2 + b^ 2 <= n / 2; 
    for (int i = 0; i * i * 4 <= n; i++) {
        for (int j = i; j * j + i * i <= n / 2; j++) {
            int t = n - i * i - j * j;
            if (h[t]) {
                int c = h[t] - 1;   
                int d = (sqrt(t - c * c) + 1e-4);
                printf("%d %d %d %d", i, j, c, d);
                return 0;
            }
        }
    }
    return 0;
}



题目描述

机器人正在玩一个古老的基于DOS的游戏。
游戏中有N+1座建筑——从0到N编号,从左到右排列。
编号为0的建筑高度为0个单位,编号为 i 的建筑高度为H(i)个单位。
起初,机器人在编号为0的建筑处。
每一步,它跳到下一个(右边)建筑。
假设机器人在第k个建筑,且它现在的能量值是E,下一步它将跳到第k+1个建筑。
如果H(k+1)>E,那么机器人就失去H(k+1)-E的能量值,否则它将得到E-H(k+1)的能量值。
游戏目标是到达第N个建筑,在这个过程中能量值不能为负数个单位。
现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏?

输入格式

第一行输入整数N。
第二行是N个空格分隔的整数,H(1),H(2),…,H(N)代表建筑物的高度。

输出格式

输出一个整数,表示所需的最少单位的初始能量值。

数据范围

1 ≤ N,H(i) ≤ 10^5
1 ≤ N,H(i) ≤ 105

输入样例1:

5
3 4 3 2 4

输出样例1:

4

输入样例2:

3
4 4 4

输出样例2:

4

输入样例3:

3
1 6 4

输出样例3:

3

算法1

(逆推法)

根据题意:
当前能量大于 H(i)时,E(i) = E(i - 1) + E(i - 1) - H(i),即E(i - 1) = (E(i) + H(i)) / 2
当前能量小于 H(i)时, E(i) = E(i - 1) - (H(i) - E(i - 1)), 即 E(i - 1) = (E(i) + H(i)) / 2
由此可以从最后一个状态逆推出第一个状态
值得注意的是:中间过程可能出现(E(i) + H(i)) / 2有余数,须向上取整,因为向下取整,会导致过程中出现负能量的情况

时间复杂度 O(n)

参考文献

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e6;
int h[N];
int main(){
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> h[i];
    }
    int t = 0,res;
    //假设走完后能量为0(实际上可能不为0),逆推走完前一个后剩下的能量
    for(int i = n - 1; i>= 0; i--){
        res = ceil((h[i]+t)/2.0);
        t = res;
    }
    cout << res << endl;
    return 0;
}



tt2767
12小时前
import sys


n = int(sys.stdin.read())

# def dfs(nums, buff):
#     if len(buff) == n:
#         print ' '.join(map(str, buff))
#     else:
#         for i in range(len(nums)):
#             buff.append(nums[i])
#             dfs(nums[0:i] + nums[i+1:], buff)
#             buff.pop()

# dfs(range(1, n+1), [])

def dfs(status, buff):
    if len(buff) == n:
        print ' '.join(map(lambda x: str(x+1), buff))
    else:
        for i in range(n):
            if status >> i & 1 == 0:
                buff.append(i)
                dfs(status | 1 << i, buff)
                buff.pop()

dfs(0, [])



tt2767
12小时前
import java.util.*;
import java.util.stream.*;

public class Main{

    void run(){
        int n = jin.nextInt();
        dfs(n, 0);
    }

    void dfs(int n, int status){
        if (buffer.size() == n){
            String res = String.join(" ", buffer.stream().map(x->String.valueOf(x+1)).collect(Collectors.toList()));
            System.out.println(res);
        } else {
            for (int i = 0 ; i < n ;i ++){
                if (((status >> i ) & 1)  == 0){
                    buffer.add(i);
                    dfs(n, status | ( 1 << i));
                    buffer.remove(buffer.size()-1);
                }
            }
        }
    }

    private List<Integer> buffer = new ArrayList<Integer>();
    private Scanner jin = new Scanner(System.in);    
    public static void main(String[] args) throws Exception {new Main().run();}
}




血染年华
12小时前

算法1

C++ 代码

class Solution{
    string s;
public:
    //Insert one char from stringstream
    void insert(char ch){
        s+=ch;
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        for(int i = 0; i < s.length(); i++)
        {
            char a = s[i];
            if(s.find(a)==s.rfind(a))
            {
                return a;
            }
        }
        return '#';
    }
};



Sir.Guo
14小时前

题目描述

blablabla

样例

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
    double a[12][12],sum=0;
    int m,i,j;
    char n;
    cin>>n;
    for(i=0;i<12;i++){
        for(j=0;j<12;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    int k,l;
    j=k=5;
    l=7;
    for(i=7;i<12;i++){
        for(j=k;j<l;j++){
            sum+=a[i][j];
        }
        l++;
        k--;
    }
    if(n=='S') printf("%.1lf",sum);
    if(n=='M') printf("%.1lf",sum/30);
    return 0;
}


算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



Sir.Guo
14小时前

题目描述

blablabla

样例

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
    double a[12][12],sum=0;
    int m,i,j;
    char n;
    cin>>n;
    for(i=0;i<12;i++){
        for(j=0;j<12;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    int k,l;
    j=k=1;
    l=11;
    for(i=0;i<12;i++){
        for(j=k;j<l;j++){
            sum+=a[i][j];
        }
        l--;
        k++;
    }
    if(n=='S') printf("%.1lf",sum);
    if(n=='M') printf("%.1lf",sum/30);
    return 0;
}


算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



Sir.Guo
15小时前

题目描述

blablabla

样例

blablabla
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int main()
{
    double a[12][12],sum=0;
    int m,i,j;
    char n;
    cin>>n;
    for(i=0;i<12;i++){
        for(j=0;j<12;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    int k;
    j=k=0;
    for(i=0;i<12;i++){
        for(j=0;j<k;j++){
            sum+=a[i][j];
        }
        k++;
    }
    if(n=='S') printf("%.1lf",sum);
    if(n=='M') printf("%.1lf",sum/66);
    return 0;
}


----------

### 算法1
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献

#### C++ 代码

blablabla


----------

### 算法2
##### (暴力枚举)  $O(n^2)$

blablabla

#### 时间复杂度

#### 参考文献


#### C++ 代码

blablabla
```