当前位置:网站首页>6.26cf simulation match B: solution to array reduction problem
6.26cf simulation match B: solution to array reduction problem
2022-07-04 18:53:00 【bj_ hacker】
6.26CF Simulation game B: Array reduction problem solution
Title Description
link
CF Simulation game B: Array reduction
A word description
B. Array reduction
time limit per test1 s.
memory limit per test256 MB
inputstandard input
outputstandard output
Kristina has two arrays a and b, each containing n non-negative integers. She can perform the following operation on array a any number of times:
Kristina There are two arrays a and b, Each one contains n Nonnegative integers . She can treat a The array performs the following operations any number of times :
For each non 0 Element minus 1, That is, all greater than 0 Of ai Replace with ai−1 (1≤i≤n). If ai yes 0, Its value remains unchanged .
Determine whether Kristina can get an array b from an array a in some number of operations (probably zero). In other words, can she make ai=bi after some number of operations for each 1≤i≤n?
Judge Kristina Whether it can pass several times ( It can be 0 Time ) Operation will a The array becomes b Array ? let me put it another way , Can she let ai=bi For any 1≤i≤n establish ?
For example, let n=4, a=[3,5,4,1] and b=[1,3,2,0]. In this case, she can apply the operation twice:
after the first application of the operation she gets a=[2,4,3,0];
after the second use of the operation she gets a=[1,3,2,0].
For example, for n=4, a=[3,5,4,1] and b=[1,3,2,0], She can operate twice :
After the first operation a=[2,4,3,0];
After the second operation a=[1,3,2,0].
Thus, in two operations, she can get an array b from an array a.
So after two operations , She can put a become b.
Input
The first line of the input contains an integer t (1≤t≤104) —the number of test cases in the test.
The first line contains an integer t (1≤t≤104) — Number of representative test data groups .
The descriptions of the test cases follow.
The description of each group of data is as follows .
The first line of each test case contains a single integer n (1≤n≤5⋅104).
The first line contains an integer n (1≤n≤5⋅104).
The second line of each test case contains exactly n non-negative integers a1,a2,…,an (0≤ai≤109).
The second line contains n Nonnegative integers a1,a2,…,an (0≤ai≤109).
The third line of each test case contains exactly n non-negative integers b1,b2,…,bn (0≤bi≤109).
The third line contains n Nonnegative integers b1,b2,…,bn (0≤bi≤109).
It is guaranteed that the sum of n values over all test cases in the test does not exceed 2⋅105.
Data assurance Of all test data n The sum does not exceed 2⋅105.
Output
For each test case, output on a separate line:
YES, if by doing some number of operations it is possible to get an array b from an array a;
NO otherwise.
You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).
For each group of test data , Output YES perhaps NO.
Example
inputCopy
6
4
3 5 4 1
1 3 2 0
3
1 2 1
0 1 0
4
5 3 7 2
1 1 1 1
5
1 2 3 4 5
1 2 3 4 6
1
8
0
1
4
6
outputCopy
YES
YES
NO
NO
YES
NO
Note
The first test case is analyzed in the statement.
For the first set of test data , It has been analyzed in the problem description .
In the second test case, it is enough to apply the operation to array a once.
For the second set of test data , One operation is enough .
In the third test case, it is impossible to get array b from array a.
For the third set of test data , Cannot from a become b.
Topic analysis
- This question is complex and has a lot of data , Point by point analysis
- First judgement b[i]>a[i] As long as there is one NO Next group
- b[i] Is full of 0,YES Next group
- b[i]!=0 Of a[i]-b[i] There is a difference NO Next group
- b[i]==0 Of a[i]-b[i]>(4.)NO Next group , otherwise YES Next group
Code implementation
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+10;
int t,n,cnt;
int a[maxn],b[maxn];
int main(){
scanf("%d",&t);
while(t--){
//2
int flag=1;
cnt=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
if(b[i]!=0)flag=0;
}
if(flag){
printf("YES\n");
continue;
}
//3
flag=1;
for(int i=1;i<=n;i++){
if(b[i]>a[i]){
flag=0;
break;
}
}
if(!flag){
printf("NO\n");
continue;
}
//4
flag=1;
for(int i=1;i<=n;i++){
if(b[i]!=0){
if(cnt==-1)cnt=a[i]-b[i];
else {
if(cnt!=a[i]-b[i]){
flag=0;
break;
}
}
}
}
if(!flag){
printf("NO\n");
continue;
}
//5
flag=1;
for(int i=1;i<=n;i++){
if(b[i]==0){
if(cnt<a[i]-b[i]){
flag=0;
break;
}
}
}
if(flag)printf("YES\n");
else printf("NO\n");
}
return 0;
}
边栏推荐
- 【机器学习的数学基础】(一)线性代数(Linear Algebra)(上+)
- [go language question brushing chapter] go conclusion chapter | introduction to functions, structures, interfaces, and errors
- Scala基础教程--14--隐式转换
- 【系统盘转回U盘】记录系统盘转回U盘的操作
- Scala基础教程--17--集合
- MySQL常用增删改查操作(CRUD)
- 力扣刷题日记/day8/7.1
- An example of multi module collaboration based on NCF
- File processing examples of fopen, FREAD, fwrite, fseek
- Summary of subsidy policies across the country for dcmm certification in 2022
猜你喜欢
vbs或vbe如何修改图标
[cloud native] what is the "grid" of service grid?
Li Kou brush question diary /day8/7.1
Behind the ultra clear image quality of NBA Live Broadcast: an in-depth interpretation of Alibaba cloud video cloud "narrowband HD 2.0" technology
激进技术派 vs 项目保守派的微服务架构之争
Scala基础教程--20--Akka
Load test practice of pingcode performance test
谷粒商城(一)
I wrote a learning and practice tutorial for beginners!
[HCIA continuous update] network management and operation and maintenance
随机推荐
File processing examples of fopen, FREAD, fwrite, fseek
With the stock price plummeting and the market value shrinking, Naixue launched a virtual stock, which was deeply in dispute
Behind the ultra clear image quality of NBA Live Broadcast: an in-depth interpretation of Alibaba cloud video cloud "narrowband HD 2.0" technology
Reptile elementary learning
Halcon template matching
2022 ByteDance daily practice experience (Tiktok)
ISO27001 certification process and 2022 subsidy policy summary
Redis主从复制
华为云ModelArts的使用教程(附详细图解)
The controversial line of energy replenishment: will fast charging lead to reunification?
LD_ LIBRARY_ Path environment variable setting
一、C语言入门基础
Wanghongru research group of Institute of genomics, Chinese Academy of Agricultural Sciences is cordially invited to join
NBA赛事直播超清画质背后:阿里云视频云「窄带高清2.0」技术深度解读
MXNet对GoogLeNet的实现(并行连结网络)
Mxnet implementation of googlenet (parallel connection network)
ISO27001认证办理流程及2022年补贴政策汇总
Scala基础教程--16--泛型
Interview summary of large factory Daquan II
ThreadLocal原理与使用