Starter190-MX PARR EZ/HARD · znzryb
## 思路讲解
[https://www.codechef.com/viewsolution/1165824691](https://www.codechef.com/viewsolution/1165824691)
简单的后缀最大判断。
困难版的题意稍微有点难懂，但是总的来说就是你不是找出来一个M吗，这个最大格挡序列可不可以包含i？
那么代码分析我放在这个链接里了，反正都是chinglish，都是读的懂的。
[https://www.codechef.com/viewsolution/1166105552](https://www.codechef.com/viewsolution/1166105552)
那么正向的贪心操作怎么样复制到这个逆向那？我认为这个是这道题目比较值得学习的点。
```cpp
ROF(i,N,1){
if(opx+1>=B[i] && opx<X){
opx++;
++sans;
suf[i]=sans;
Ans[i]=true;
}else{
suf[i]=suf[i+1];
}
}
```
## AC代码
[https://www.codechef.com/viewsolution/1165824691](https://www.codechef.com/viewsolution/1165824691)
::: EZ源代码
```cpp
// Problem: Parry It! (Easy) 招架！（简单）
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/MXPARREZ
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*
*/
ll mxA[MAXN];
inline void init(){
FOR(i,0,N+5){mxA[i]=0;}
}
inline void solve(){
cin>>N>>X;
init();
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N){
cin>>B[i];
}
ROF(i,N,1){
mxA[i]=max(mxA[i+1],A[i]);
}
ll opx=X,ans=0;
FOR(i,1,N){
if(opx<A[i]){
cout<<0<<"\n";
return;
}else if(opx>=B[i]){
if(opx-1>=mxA[i+1]){
opx--;
++ans;
}
}
}
cout<<ans<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
AC https://www.codechef.com/viewsolution/1165824691
*/
```
:::
[https://www.codechef.com/viewsolution/1166105552](https://www.codechef.com/viewsolution/1166105552)
::: HD源代码
```cpp
// Problem: Parry It! (Hard) 招架！（困难）
// Contest: CodeChef - START190
// URL: https://www.codechef.com/problems/MXPARR
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e9)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,Q,X,K,lT,A[MAXN],B[MAXN];
/*
*/
ll mxA[MAXN],Xv[MAXN]; // smxA[MAXN];
ll suf[MAXN],pre[MAXN];
inline void init(){
FOR(i,0,N+5){
mxA[i]=0;
// smxA[i]=0;
suf[i]=0;
pre[i]=0;
}
}
inline void solve(){
cin>>N>>X;
init();
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N){
cin>>B[i];
}
ROF(i,N,1){
mxA[i]=max(mxA[i+1],A[i]);
}
// FOR(i,1,N){smxA[i]=max(smxA[i-1],A[i]);}
ll opx=X,ans=0,first=N;
vector<bool> Ans(N+5,false);
FOR(i,1,N){
if(opx<A[i]){
FOR(i,1,N)cout<<0;
cout<<"\n";
return;
}else if(opx>=B[i]){
if(opx-1>=mxA[i+1]){
opx--;
++ans;
Ans[i]=true;
first=min(first,(ll)i);
}
}
pre[i]=ans;
Xv[i]=opx;
}
if(ans==0){
cout<<string(N,'0')<<"\n";
return;
}
// #ifdef LOCAL
// FOR(i,1,N){debug(i);debug(Xv[i]);}
// #endif
opx=X-ans;ll sans=0;
ROF(i,N,1){
if(opx+1>=B[i] && opx<X){
opx++;
++sans;
suf[i]=sans;
Ans[i]=true;
}else{
suf[i]=suf[i+1];
}
}
FOR(i,first+1,N){
if(Ans[i]) continue;
// if(B[i]<mxA[i+1]) continue; // B[i]<mxA[i+1] 即会导致fail
if(B[i]>X) continue;
if(pre[i]>=ans-suf[i]-1){
if(X-max((ll)0,ans-suf[i]-1)>=B[i]) Ans[i]=true;
}
}
#ifdef LOCAL
debug(ans);
debug(sans);
FOR(i,1,N){
debug(i);
debug(suf[i]);
}
FOR(i,1,N){
debug(i);
debug(pre[i]);
}
#endif
FOR(i,1,N){
cout<<Ans[i];
}
cout<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>lT;
while(lT--){
solve();
}
// solve();
return 0;
}
/*
WA
https://www.codechef.com/viewsolution/1165848655
hack:
1
6 10
1 1 1 1 1 1
10 9 8 10 9 8
WA:111001
AC:111111
*/
```
:::
## 心路历程（WA，TLE，MLE……）