这是什么神仙题啊。
本题主要思路：优化转移决策，减少 dp 状态。
我们发现减一层盾其实就是给自己加攻击，所以我们将初始生命值（攻击力） \(C_H\) 和 \(C_G\) 重新表示为 \(A_1 = C_H - f_G S\)，\(A_2 = C_G - f_H S\)，让 \(F_1 = f_G\)，\(F_2 = f_H\)。
现在的点对就是 \((A_1,F_1,A_2,F_2)\)，容易发现每一维都是存在单调性的，若 \((A_1,F_1,A_2,F_2)\) 先手胜，\((A_1 + 1,F_1,A_2,F_2)\) 一定也是先手胜。
然后我们考虑减少 dp 状态。
为方便叙述，我们称破一层盾为蓄力,设 \(M = \max(A_1,F_1,A_2,F_2)\)。
首先我们能够粗略发现有些情况下决策是固定的。
-
当 \(A_1 \ge S \wedge A_2 \le S\) 时，先手必胜，因为先手只要攻击就一定能使后手攻击力小于 \(0\)。
-
当 \(A_1 \ge 0 \wedge A_2 \le 0 \wedge F_1 > 0\) 时，蓄力就能得到第一种情况。
-
当 \(A_1 \le 0\) 时，一定选择蓄力。
-
当 \(A_2 \ge S\) 时，先手一定选择攻击，因为若蓄力，后手攻击就一定会让你的蓄力次数和攻击力都减少，显然不优。
而这些就让 \(A_1,A_2 \in [0,S]\)，\(F_1,F_2 \in [0,M/S]\) 了，大大减少了 dp 状态。
然后我们还能发现，当 \(A_1,A_2 \in [0,S]\)，若先手总是蓄力，那后手一定得攻击先手，所以又有了这么一个限制 (\(d_1 = S - A_2\)，\(d_2 = S - A_1\))：
- 当 \(A_1 + d_1 F_1 \ge S\) 时，先手必胜。
对应的，若我们要使 \((A_1,F_1,A_2,F_2)\) 这个点对是有用的，我们还要让后手 \(A_2\) 满足：
- \(A_2 - A_1 + d_2 F_2 \le S\)
所以若 \(A_2 - (A_1 + F_1 d_1) + (d_2 - F_1 d_1) F_2 \ge S\)，后手必胜，不然先手就要将后手操作到 \(A_2 - A_1 + d_2 F_2 \le S\) 为止。
这时候 dp 状态又多了限制： \(d_1 F_1 \le S - A_1 = d_2\)， \(d_2 F_2 \le S + A_1 - A_2\)，大致状态数就是 \(S^2\) 再多个对数。
那如果不蓄力，而是攻击呢。具体来说，就是先手先蓄力 \(x\) 轮 \(\to\) 先手攻击后手，后手蓄力 \(\to\) 后手攻击先手，先手蓄力。
那用式子写出来？（\(A_{1/2}^{'}\) 表示先手/后手最后的攻击力，\(d_{1}^{'}\) 同理）
\(max(A_{2}^{'})\)
$= A_2 - (A_1 + x d_1) + (d_2 - x d_1) F_2 $
\(= (A_2 - A_1 + d_2 F_2) - x d_1 (F_2 + 1) \le S - x d_1 (F_2 + 1)\)
所以 \(d_{1}^{'} \ge x d_1 (F_2 + 1)\)。
那再蓄力就能使攻击力至少加 \((F_2 +1) d_1 x(F_1 - x)\)，若令 \(x = \frac{F_1}{2}\)，那就至少加 \(\frac{1}{4}(F_2 +1) d_1 F_1^2\)。
由于后手攻击了先手一次，但 \(A_2^{'} \le S\)，所以只要 \(\frac{1}{4}(F_2 +1) d_1 F_1^2 \ge 2S\)，先手必胜。
所以又有了 \((F_2 +1) d_1 F_1^2 \le 8S\) 的限制，这下状态数就只剩 \(S\) 多个对数了，时间复杂度就可以接受了。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define mkp make_pair
#define lowbit(x) x&(-x)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=x*10+(c^48); c=getchar();}
return x*f;
}
map<tuple<int,int,int>,int> mp;
int S;
inline bool dfs(int A1,int F1,int A2,int F2){
int fl=0;
while(1){
if(F1*S+A1<=0) return fl;
if(F2*S+A2<=0) return !fl;
if(A1>=S&&A2<=S) return !fl;
if(F1&&(A1>=0&&A2<=0)) return !fl;
if(A2>=S||!F1){
A2-=A1; fl=!fl;
swap(A1,A2),swap(F1,F2);
continue;
}
if(A1<=0){
if(!F2&&A2<S){
int nd=(-A1)/(S-A2)+1;
if(nd>F1) return fl;
A1+=(S-A2)*nd,F1-=nd;
continue;
}
int nd1=(-A1+S-1)/S;
int nd2=0; if(A2<=0) nd2=(-A2+S-1)/S;
int stp=min(nd1,nd2);
stp=max(stp-1,0ll);
A1+=(stp+1)*S,F1-=(stp+1);
A2+=stp*S,F2-=stp;
fl=!fl;swap(A1,A2),swap(F1,F2);
continue;
}
int d1=S-A2,d2=S-A1;
if(A1+d1*F1>=S) return !fl;
if(d2*F2>=S-A2+A1){
int t=(d2*F2+A2-A1-S)/(F2+1)/d1+1;
if(t>F1) return fl;
A1+=t*d1,F1-=t;
continue;
}
if(F1!=1&&(max({F2+1,d1,F1})>=8*S||(F2+1)*d1*F1*F1>=8*S)) return !fl;
if(mp.find({F1,A2,F2})!=mp.end()) return fl^(A1>=mp[{F1,A2,F2}]);
int l=0,r=S,res=r;
while(l<=r){
int mid=(l+r)>>1;
if(dfs(A2,F2,mid+S,F1-1)&&dfs(A2-mid,F2,mid,F1)) l=mid+1;
else r=mid-1,res=mid;
}
mp[{F1,A2,F2}]=res;
return fl^(A1>=res);
}
}
int c1,c2,f1,f2;
inline void solve(){
c1=read(),f1=read(),c2=read(),f2=read();
c1-=f2*S,c2-=f1*S;
puts(dfs(c1,f2,c2,f1)?"YES":"NO");
}
signed main(){
S=read();
int T=read();
while(T--) solve();
}
/*
1 1
1000000000000 0 1 1000000000000
*/