当前位置:网站首页>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;
}
边栏推荐
- 差分(一维,二维,三维) 蓝桥杯三体攻击
- Cost accounting [24]
- [exercise-4] (UVA 11988) broken keyboard = = (linked list)
- 【练习-5】(Uva 839)Not so Mobile(天平)
- 【练习-7】Crossword Answers
- Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
- Penetration test (7) -- vulnerability scanning tool Nessus
- [exercise-3] (UVA 442) matrix chain multiplication
- 初入Redis
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
猜你喜欢
Pyside6 signal, slot
[analysis of teacher Gao's software needs] collection of exercises and answers for level 20 cloud class
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Record of force deduction and question brushing
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
Essai de pénétration (1) - - outils nécessaires, navigation
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
Information security - Analysis of security orchestration automation and response (soar) technology
【练习-5】(Uva 839)Not so Mobile(天平)
Nodejs+vue online fresh flower shop sales information system express+mysql
随机推荐
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
Opencv learning log 13 corrosion, expansion, opening and closing operations
Essai de pénétration (1) - - outils nécessaires, navigation
Frida hook so layer, protobuf data analysis
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
Information security - threat detection - detailed design of NAT log access threat detection platform
1010 things that college students majoring in it must do before graduation
【练习-9】Zombie’s Treasure Chest
信息安全-威胁检测引擎-常见规则引擎底座性能比较
HDU - 6024 Building Shops(女生赛)
Shell脚本编程
入门C语言基础问答
Pyside6 signal, slot
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
frida hook so层、protobuf 数据解析
If you want to apply for a programmer, your resume should be written like this [essence summary]
Borg Maze (BFS+最小生成树)(解题报告)
C 基本语法
Penetration testing (5) -- a collection of practical skills of scanning King nmap and penetration testing tools
Common configuration files of SSM framework