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这个关系)，再然后,就想到了打表
- 建立哈希表，存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
- 从小到大遍历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这个关系)，再然后,就想到了打表
- 建立哈希表，存储小于n的数c,假设e = c^2 + d^2,则h[e] = c,从小到大遍历c, d只存储先出现的(因为字典序小)
- 从小到大遍历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;
}
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, [])
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();}
}
算法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 '#';
}
};
题目描述
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
题目描述
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
题目描述
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
```
