A
有没有一种可能,你离AC这道题只是差了一点小学数学?
首先,我们令真正能使用的攻击魔法卡数为atk,显然atk=min(n,m+1)
(以下出现的攻击序列,用a表示攻击,用r表示恢复魔法值)
当我们一定要用atk张卡进行攻击时,要造成伤害最高就要尽可能把攻击卡放在后面,即按照rrr...aaa...的方式攻击,伤害用等差数列公式计算为dam=((1+m)+(m+atk))*atk/2。而要造成的伤害最小,则相反,要在魔法值支持的情况下尽可能把攻击卡放在前面,即按照ararar...的方式攻击,伤害为dam=(1+(2*atk-1))*atk/2=atk*atk。易知,通过改变a和r的位置,在上限和下限之间的值都是能打出来的。
还没完,我们现在把上一段的“一定要用atk张卡”改为“可以用atk张卡”,那么就要考虑atk减小,而m不变的区间,下限仍然是同样的公式,上限因为攻击卡全部往后挪一位而+1*atk。
接下来打表(在数学上去证明当然更严谨)验证这些区间是连起来的,能够覆盖[1,伤害上限](1e9的数据如果挨个区间去算必定超时),为了让结论更泛用,让m为最小值,即atk-1。
for(int i=1;i<=100;i++){
atk=i;m=atk-1;
printf("%d %d %d\n",atk*atk,(1+2*m+atk)*atk/2,(1+2*m+atk)*atk/2+atk);
}
由此发现有两个特例:atk==2&&m==1&&x==3和atk==3&&m==2&&x==8(x为弟弟的血量),这两个特例中弟弟的血量都小于伤害上限,却不能被正好斩杀,需要特判。
代码:
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int mod=1e9+7;
const int N=1e5+7;
typedef long long ll;
#define int unsigned long long
void solve(){
int n,m,atk,dam;
cin>>n>>m;
atk=min(m+1,n);
dam=(1+m+atk+m)*atk/2;
int k,x;
cin>>k;
while(k--){
cin>>x;
if(atk==2&&m==1&&x==3)cout<<"NO"<<endl;
else if(atk==3&&m==2&&x==8)cout<<"NO"<<endl;
else if(dam>=x)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
signed main()
{
ios;
int t=1;
//cin>>t;
while(t--){
solve();
}
}