Educational Codeforces Round 154 (Rated for Div. 2) C题题解
C. Queries for the Array 题解
[C. Queries for the Array]:
nums[]
存当前数组,len
表示当前数组长度
nums[i]=1
时表示 $1{\sim}i$ 的数据是递增的
nums[i]=0
时表示 $1{\sim}i$ 的数据增减性不确定,即可能递增可能递减
nums[i]=-1
时表示 $1{\sim}i$ 的数据是递减的
当 s[i]=='+'
时,如果原数组是降序,那么加完新元素后的新数组也是降序的,即 s[len]=-1
当 s[i]=='-'
时,如果原数组是升序的,那么删完后还是升序,即 s[len]=1
,由于还得 s[len]=0
防止影响后续的判断
当 s[i]=='1'
时,若 s[len]==-1
即降序,则输出 $NO$ ,否则 s[len]=1
表示升序
当 s[i]=='0'
时,若 s[len]==1
即升序,则输出 $YES$ ,否则 s[len]=-1
表示降序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| #include<iostream> #include<vector> #include<cstring> using namespace std;
const int N=2e5+10;
int nums[N]; int idx; int main() { int T; cin>>T; while (T--) { memset(nums,0,sizeof(nums)); int len=0; string str; cin>>str; nums[0]; for(auto i:str) { if(i=='+') { len++; if(nums[len-1]==-1) { nums[len]=-1; } }
if(i=='-') { len--; if(nums[len+1]==1) { nums[len]=1; }
nums[len+1]=0; }
if(i=='1') { if(nums[len]==-1) { cout<<"NO"<<endl; goto End; }
nums[len]=1; }
if(i=='0') { if(nums[len]==1||len<=1) { cout<<"NO"<<endl; goto End; }
nums[len]=-1; } } cout<<"YES"<<endl;
End:; } return 0; }
|