- it技术
- 高精度、前缀和、差分
A+B 高精度
#include
<bits
/stdc
++.h
>
using namespace std
;
vector
<int
> add(vector
<int
> &A,vector
<int
> &B)
{
vector
<int
> C;
int t
=0;
for(int i
=0;i
<A.size()||i
<B.size();i
++)
{
if(i
<A.size()) t
+=A[i
];
if(i
<B.size()) t
+=B[i
];
C.push_back(t
%10);
t
/=10;
}
if(t
) C.push_back(1);
return C;
}
int
main()
{
vector
<int
> A,B;
string a
,b
;
cin
>>a
>>b
;
for(int i
=a
.size()-1;i
>=0;i
--) A.push_back(a
[i
]-'0');
for(int i
=b
.size()-1;i
>=0;i
--) B.push_back(b
[i
]-'0');
vector
<int
> C=add(A,B);
for(int i
=C.size()-1;i
>=0;i
--) printf("%d",C[i
]);
return 0;
}
前缀和
一维
读入数据也是
1 to n
for(int i
=1;i
<=n
;i
++)
{
s
[i
]=s
[i
-1]+a
[i
];
}
二维
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
s
[i
][j
] = s
[i
-1][j
] + s
[i
][j
-1] - s
[i
-1][j
-1] + a
[i
][j
];
}
}
while(q
--)
{
int x1
,y1
,x2
,y2
;
scanf("%d%d%d%d",&x1
,&y1
,&x2
,&y2
);、
printf("%d\n",s
[x2
][y2
] - s
[x1
-1][y2
] - s
[x2
][y1
-1] + s
[x1
-1][y1
-1]);
}
差分
一维
#include
<bits
/stdc
++.h
>
using namespace std
;
const int
N = 1e6+10;
int a
[N];
int b
[N];
int n
,q
;
void insert(int l
,int r
,int c
)
{
b
[l
]+=c
;
b
[r
+1]-=c
;
}
int
main()
{
scanf("%d%d",&n
,&q
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]);
for(int i
=1;i
<=n
;i
++) b
[i
]=a
[i
]-a
[i
-1];
for(int i
=1;i
<=n
;i
++) insert(i
,i
,a
[i
]);
while(q
--)
{
int l
, r
,c
;
scanf("%d%d%d",&l
,&r
,&c
);
b
[l
]+=c
;
b
[r
+1]-=c
;
}
for(int i
=1;i
<=n
;i
++) a
[i
]=a
[i
-1]+b
[i
];
for(int i
=1;i
<=n
;i
++) printf("%d ",a
[i
]);
return 0;
}
二维差分
#include
<bits
/stdc
++.h
>
using namespace std
;
const int
N = 1e3+10;
int n
,m
,q
;
int a
[N][N];
int b
[N][N];
void insert(int x1
,int y1
,int x2
,int y2
,int c
)
{
b
[x1
][y1
]+=c
;
b
[x1
+1][y1
]-=c
;
b
[x1
][y1
+1]-=c
;
b
[x2
+1][y2
+1]+=c
;
}
int
main()
{
cin
>>n
>>m
>>q
;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=m
;j
++){
scanf("%d",&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
]);
}
}
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
++){
printf("%d",b
[i
][j
]);
}
cout
<<endl
;
}
return 0;
}
