当前位置:网站首页>Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】
If one dimension and two dimensions are OK, you can jump directly
One dimensional difference
First, give an original array a:a[1], a[2], a[3], a[n];
Then we construct an array b : b[1] ,b[2] , b[3], b[i];
bring a[i] = b[1] + b[2 ]+ b[3] +, + b[i]
a An array is b Array prefix and array , In turn, we put b The array is called a Differential array of arrays .
Consider constructive difference b Array
The most direct way
as follows :
a[0 ]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
…
b[n] = a[n] - a[n-1];
Yes b Array , By prefix and operation , You can go to O(n) Get... In time a Array .
One dimensional difference —— The template questions AcWing 797. Difference
Give interval [l, r] Add to each number in c:b[l] += c, b[r + 1] -= c
Example
AcWing797. Difference
Enter a length of n Integer sequence of . Next input m Operations , Each operation contains three integers l,r,c, Indicates that... Will be in the sequence [l,r] Add... To each number between c.
Please output the sequence after all operations .
Input format
The first line contains two integers n and m.
The second line contains n It's an integer , Represents a sequence of integers .
Next m That's ok , Each line contains three integers l,r,c, Represents an operation .
Output format
All in one line , contain n It's an integer , Represents the final sequence .
Data range
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤ The value of an element in an integer sequence ≤1000
sample input :
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
sample output :
3 4 5 3 4 2
#include<bits/stdc+. and >
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i]-a[i-1]; // Build a differential array
}
int l,r,c;
while(m--)
{
scanf("%d%d%d",&l,&r,&c);
b[l]+=c; // Put... In the sequence [l, r] Add... To every number between c
b[r+1]-=c;
}
for(int i=1;i<=n;i++)
{
a[i]=b[i]+a[i-1]; // Prefixes and operations
printf("%d ",a[i]);
}
return 0;
}
Two dimensional difference
author :z When the forest is deep, see the deer
If extended to 2D , We need to add... To the value of each element in the selected submatrix of the two-dimensional array c, Whether it can also achieve O(1) Time complexity of . The answer is yes , Consider two-dimensional difference .
a[][] An array is b[][] Array prefix and array , that b[][] yes a[][] The differential array of
Original array : a[i][j]
Let's construct a differential array : b[i][j]
bring a Array a[i][j] yes b The upper left corner of the array (1,1) To the lower right corner (i,j) The sum of the elements of the enclosed rectangle .
How to construct b Array? ?
Let's think backwards .
Same as one-dimensional difference , We construct a two-dimensional difference fraction group to Let the original two-dimensional array a Add... To each element in the selected neutron matrix c The operation of , Can be O(n*n) The time complexity is optimized to O(1)
Known original array a The selected submatrix in is With (x1,y1) It's the upper left corner , With (x2,y2) Is the rectangular area enclosed by the lower right corner ;
Always remember ,a An array is b Array prefix and array , For example, yes. b Array of b[i][j] Modification of , Will affect a Array from a[i][j] And every number from now on .
Suppose we have constructed b Array , Analogy to one-dimensional difference , We do the following
Add... To the value of each element in the selected submatrix c Time complexity o(1)
b[x1][y1] + = c;
b[x1,][y2+1] - = c;
b[x2+1][y1] - = c;
b[x2+1][y2+1] + = c;
Every time the b The array does the above , Equivalent to : Time complexity o(n2)
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
a[i][j]+=c;
Let's draw a picture to understand the process :
b[x1][ y1 ] +=c ; Corresponding graph 1 , Let the whole a The elements of the blue rectangular area in the array are added c.
b[x1,][y2+1]-=c ; Corresponding graph 2 , Let the whole a Subtract... From the elements of the green rectangular area in the array c, Keep its elements unchanged .
b[x2+1][y1]- =c ; Corresponding graph 3 , Let the whole a Subtract... From the area of the purple rectangle in the array c, Keep its elements unchanged .
b[x2+1][y2+1]+=c; Corresponding graph 4, Let the whole a The element of the red rectangular area in the array plus c, The in red is equivalent to being subtracted twice , One more time c, To restore it .
We encapsulate the above operations into an insert function :
void insert(int x1,int y1,int x2,int y2,int c)
{
// Yes b The array performs an insert operation , It is equivalent to a Array (x1,y1) To (x2,y2) The elements between are added c
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
We can imagine a Array is empty , that b The array is also empty at first , But actually a The array is not empty , So every time we let (i,j) From the upper left corner to (i,j) Is the element in the upper right corner area ( It's actually the area of a small square ) To insert c=a[i][j], Equivalent to the original array a in (i,j) To (i,j) Within the scope of Combined with the a[i][j] , So execute n*m Insert operations , We successfully built the differential b Array .
This is called saving the country by curve .
The code is as follows :
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
insert(i,j,i,j,a[i][j]); // Build a differential array
}
}
Two dimensional difference —— The template questions AcWing 798. Difference matrix
Give (x1, y1) It's the upper left corner ,(x2, y2) Add... To all elements of the submatrix in the lower right corner c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
Example
AcWing 798. Difference matrix
Enter a n That's ok m The integer matrix of columns , Input again q Operations , Each operation contains five integers x1,y1,x2,y2,c, among (x1,y1) and (x2,y2) Represents the upper left and lower right coordinates of a submatrix .
For each operation, add the value of each element in the selected sub matrix c.
Please output the matrix after all operations .
Input format
The first line contains integers n,m,q.
Next n That's ok , Each row contains m It's an integer , Represents an integer matrix .
Next q That's ok , Each row contains 5 It's an integer x1,y1,x2,y2,c, Represents an operation .
Output format
common n That's ok , Each row m It's an integer , Represents the final matrix after all operations are completed .
Data range
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤ The values of the elements in the matrix ≤1000
sample input :
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
sample output :
2 3 4 1
4 3 4 1
2 2 2 2
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 10;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
int main()
{
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
insert(i, j, i, j, a[i][j]); // Build a differential array
}
}
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
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]; // Two dimensional prefixes and
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
Three dimensional difference
Observe one dimension
b[l] = s[l] - s[l-1]
+s[l] , -s[l-1]
A two-dimensional
b[i][j] = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1]
-s[i-1][j] , -s[i][j-1] , +s[i][j] , +s[i-1][j-1]
If there is an odd number minus one, it is negative , Even minus one is positive
0 0 { s[ i - 0 ][ j - 0 ] = s[ i ][ j ] } +1
0 1 { s[ i - 0 ][ j - 1 ] = s[ i ][ j - 1] } -1
1 0 { s[ i - 1 ][ j- 0 ] = s[ i - 1 ][ j ] } -1
1 1 { s[ i - 1][ j - 1 ]} -1
If will be located (x1, y1) and (x2, y2) Add c:
b[x1][y1] += c; //00
b[x1][y2+1] -= c; //01
b[x2+1][y1] -= c; //10
b[x2+1][y2+1] += c; //11
In the same way
The three dimensional
b[i][j][k] = s[i][j][k] - s[i-1][j][k] - s[i][j-1][k] + s[i-1][j-1][k]- s[i][j][k-1] + s[i-1][j][k-1] + s[i][j-1][k-1] - s[i-1][j-1][k-1];
Will be located at (x1, y1, z1) and (x2, y2, z2) Add c:
b[x1 ][y1 ][z1 ] += c; // 000
b[x1 ][y1 ][z2 + 1] -= c; // 001
b[x1 ][y2 + 1][z1 ] -= c; // 010
b[x1 ][y2 + 1][z2 + 1] += c; // 011
b[x2 + 1][y1 ][z1 ] -= c; // 100
b[x2 + 1][y1 ][z2 + 1] += c; // 101
b[x2 + 1][y2 + 1][z1 ] += c; // 110
b[x2 + 1][y2 + 1][z2 + 1] -= c; // 111
Example
AcWing 1232. Three body attack
The triad will attack the earth .
To defend against attack , The earth people sent A×B×C warship , Line up in space A layer B That's ok C The cube of columns .
among , The first i Layer j Xing di k The ships of the line ( It's a warship (i,j,k)) The life value of is d(i,j,k).
The triad will launch a war against the earth m round “ Cube attack ”, Each attack deals the same damage to all warships in a cube .
In particular , The first t Round attack 7 Parameters lat,rat,lbt,rbt,lct,rct,ht describe ;
All satisfied i∈[lat,rat],j∈[lbt,rbt],k∈[lct,rct] The warships of (i,j,k) Will receive ht The damage of .
If a warship's total cumulative damage exceeds its defense , Then this warship will explode .
Earth Commander wants you to tell him , After which attack did the first warship explode .
Input format
The first line includes 4 A positive integer A,B,C,m;
The second line contains A×B×C It's an integer , Among them the first ((i−1)×B+(j−1))×C+(k−1)+1 The number is d(i, j, k);
The first 3 To the first m+2 In line , The first (t − 2) Line inclusion 7 A positive integer lat, rat, lbt, rbt, lct, rct, ht.
Output format
The warship that outputs the first explosion exploded after which round of attack .
There must be such a warship .
Data range
1≤A×B×C≤106,
1≤m≤106,
0≤d(i, j, k), ht≤109,
1≤lat≤rat≤A,
1≤lbt≤rbt≤B,
1≤lct≤rct≤C
layer 、 That's ok 、 The column numbers are from 1 Start .
sample input :
2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2
sample output :
2
Sample explanation
In the 2 After a round of attack , Warship (1,1,1) A total of 2 Point injury , Exceeding its defense will lead to an explosion .
Be careful A×B×C<=1e6, Opening a three-dimensional array may timeout , Convert the corresponding three-dimensional coordinates into one-dimensional coordinates (i×B+j)×k
Too many queries , Two point solution , Find No 1 A bombed warship
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const N=2e6+10;// One more side (i,j,k,+1);
int a,b,c,m;
ll s[N];// Original array ;
ll bb[N],dp[N]; // Difference array ;
int op[N/2][7];
int d[8][4]=
{
{
0,0,0,1},{
0,0,1,-1},{
0,1,0,-1},{
0,1,1,1},
{
1,0,0,-1},{
1,0,1,1},{
1,1,0,1},{
1,1,1,-1},
};
int get(int i,int j,int k) // In the form of a one-dimensional array
{
return (i*b+j)*c+k;
}
bool check(int mid)// Judge whether it was the first one to be destroyed ;
{
memcpy(bb,dp,sizeof bb);// Copy ;
for(int i=1; i<=mid; i++)
{
// Will be located at (x1, y1, z1) and (x2, y2, z2) Between the original sequences are subtracted h:
int x1 = op[i][0], x2 = op[i][1];
int y1 = op[i][2], y2 = op[i][3];
int z1 = op[i][4], z2 = op[i][5], h = op[i][6];
bb[get(x1, y1, z1)] -= h;
bb[get(x1, y1, z2 + 1)] += h;
bb[get(x1, y2 + 1, z1)] += h;
bb[get(x1, y2 + 1, z2 + 1)] -= h;
bb[get(x2 + 1, y1, z1)] += h;
bb[get(x2 + 1, y1, z2 + 1)] -= h;
bb[get(x2 + 1, y2 + 1, z1)] -= h;
bb[get(x2 + 1, y2 + 1, z2 + 1)] += h;
}
memset(s,0,sizeof s); // The prefix sum is changed to the original array ;
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++)
for(int k=1; k<=c; k++)
{
s[get(i,j,k)]=bb[get(i,j,k)];
for(int u=1; u<8; u++)
{
int x=i-d[u][0],y=j-d[u][1];
int z=k-d[u][2],t=d[u][3];
s[get(i,j,k)]-=s[get(x,y,z)]*t;
}
if(s[get(i,j,k)]<0)
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a>>b>>c>>m;
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++)
for(int k=1; k<=c; k++)
cin>>s[get(i,j,k)];
// Difference
for(int i=1; i<=a; i++)
for(int j=1; j<=b; j++)
for(int k=1; k<=c; k++)
for(int u=0; u<8; u++) // altogether 8 In this case ;000 001 010...
{
int x=i-d[u][0],y=j-d[u][1],z=k-d[u][2],t=d[u][3];
dp[get(i,j,k)]+=s[get(x,y,z)]*t;
}
// Input m Operations ;
for(int i=1; i<=m; i++)
for(int j=0; j<7; j++)
cin>>op[i][j];
// Two points search
int l=1,r=m;
while(l<r)
{
int mid=l+r >> 1;
if(check(mid)) // If the first mid The operation has blown up , Look forward to
r=mid;
else
l=mid+1;
}
cout<<r<<endl;
return 0;
}
边栏推荐
- Find 3-friendly Integers
- Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
- 【练习4-1】Cake Distribution(分配蛋糕)
- Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
- Research Report of exterior wall insulation system (ewis) industry - market status analysis and development prospect prediction
- VS2019初步使用
- MySQL授予用户指定内容的操作权限
- [exercise-7] crossover answers
- nodejs爬虫
- China earth moving machinery market trend report, technical dynamic innovation and market forecast
猜你喜欢
渗透测试 ( 2 ) --- 渗透测试系统、靶机、GoogleHacking、kali工具
C语言是低级和高级的分水岭
【高老师UML软件建模基础】20级云班课习题答案合集
Penetration test (7) -- vulnerability scanning tool Nessus
Nodejs+vue online fresh flower shop sales information system express+mysql
渗透测试 ( 4 ) --- Meterpreter 命令详解
入门C语言基础问答
洛谷P1102 A-B数对(二分,map,双指针)
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
Frida hook so layer, protobuf data analysis
随机推荐
信息安全-威胁检测-NAT日志接入威胁检测平台详细设计
【练习-6】(Uva 725)Division(除法)== 暴力
Web based photo digital printing website
Matlab comprehensive exercise: application in signal and system
洛谷P1102 A-B数对(二分,map,双指针)
X-forwarded-for details, how to get the client IP
渗透测试 ( 4 ) --- Meterpreter 命令详解
[exercise-2] (UVA 712) s-trees
The most complete programming language online API document
[exercise-9] Zombie's Treasury test
Opencv learning log 13 corrosion, expansion, opening and closing operations
nodejs爬虫
B - 代码派对(女生赛)
信息安全-威胁检测引擎-常见规则引擎底座性能比较
0-1 knapsack problem (I)
Accounting regulations and professional ethics [3]
Penetration test (8) -- official document of burp Suite Pro
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
PySide6 信号、槽
想应聘程序员,您的简历就该这样写【精华总结】