題目描述

小 D 最近在網(wǎng)上發(fā)現(xiàn)了一款小游戲。游戲的規(guī)則如下：

• 游戲的目標是按照編號 1→n1 \rightarrow n1→n 順序殺掉 nnn 條巨龍，每條巨龍擁有一個初始的生命值 aia_iai? 。同時每條巨龍擁有恢復能力，當其使用恢復能力時，它的生命值就會每次增加 pip_ipi? ，直至生命值非負。只有在攻擊結束后且當生命值 恰好 為 000 時它才會死去。

• 游戲開始時玩家擁有 mmm 把攻擊力已知的劍，每次面對巨龍時，玩家只能選擇一 把劍，當殺死巨龍后這把劍就會消失，但作為獎勵，玩家會獲得全新的一把劍。 小 D 覺得這款游戲十分無聊，但最快通關的玩家可以獲得 ION2018 的參賽資格， 于是小 D 決定寫一個笨笨的機器人幫她通關這款游戲，她寫的機器人遵循以下規(guī)則：

• 每次面對巨龍時，機器人會選擇當前擁有的，攻擊力不高于巨龍初始生命值中攻擊力最大的一把劍作為武器。如果沒有這樣的劍，則選擇 攻擊力最低 的一把劍作為武器。

• 機器人面對每條巨龍，它都會使用上一步中選擇的劍攻擊巨龍固定的 xxx 次，使巨龍的生命值減少 x×ATKx \times ATKx×ATK 。

• 之后，巨龍會不斷使用恢復能力，每次恢復 pip_ipi? 生命值。若在使用恢復能力前或某一次恢復后其生命值為 000 ，則巨龍死亡，玩家通過本關。

那么顯然機器人的攻擊次數(shù)是決定能否最快通關這款游戲的關鍵。小 D 現(xiàn)在得知了每條巨龍的所有屬性，她想考考你，你知道應該將機器人的攻擊次數(shù) xxx 設置為多少，才能用最少的攻擊次數(shù)通關游戲嗎？

當然如果無論設置成多少都無法通關游戲，輸出 ?1-1?1 即可。

輸入格式

第一行一個整數(shù) TTT，代表數(shù)據(jù)組數(shù)。

接下來 TTT 組數(shù)據(jù)，每組數(shù)據(jù)包含 555 行。

• 每組數(shù)據(jù)的第一行包含兩個整數(shù)，nnn 和 mmm ，代表巨龍的數(shù)量和初始劍的數(shù)量;

• 接下來一行包含 nnn 個正整數(shù)，第 iii 個數(shù)表示第 iii 條巨龍的初始生命值 aia_iai? ;

• 接下來一行包含 nnn 個正整數(shù)，第 iii 個數(shù)表示第 iii 條巨龍的恢復能力 pip_ipi? ;

• 接下來一行包含 nnn 個正整數(shù)，第 iii 個數(shù)表示殺死第 iii 條巨龍后獎勵的劍的攻擊力;

• 接下來一行包含 mmm 個正整數(shù)，表示初始擁有的 mmm 把劍的攻擊力。

輸出格式

一共 TTT 行。

第 iii 行一個整數(shù)，表示對于第 iii 組數(shù)據(jù)，能夠使得機器人通關游戲的最小攻擊次數(shù) xxx ，如果答案不存在，輸出 ?1-1?1。

輸入輸出樣例

輸入 #1 2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1 輸出 #1 59 -1

說明/提示

第一組數(shù)據(jù)：

• 開始時擁有的劍的攻擊力為 {1,9,10}\{1,9,10\}{1,9,10}，第 111 條龍生命值為 333，故選擇攻擊力為 111 的劍，攻擊 595959 次，造成 595959 點傷害，此時龍的生命值為 ?56-56?56，恢復 14 次后生命值恰好為 000，死亡。

• 攻擊力為 111 的劍消失，拾取一把攻擊力為 777 的劍，此時擁有的劍的攻擊力為 {7,9,10}\{7,9,10\}{7,9,10}，第 2 條龍生命值為 555，故選擇攻擊力為 777 的劍，攻擊 595959 次，造成 413413413 點傷害，此時龍的生命值為 ?408-408?408，恢復 686868 次后生命值恰好為 000，死亡。

• 此時擁有的劍的攻擊力為 {3,9,10}\{3,9,10\}{3,9,10}，第 333 條龍生命值為 777，故選擇攻擊力為 333 的劍，攻擊 595959 次，造成 177177177 點傷害，此時龍的生命值為 ?170-170?170，恢復 171717 次后生命值恰好為 0，死亡。

• 沒有比 595959 次更少的通關方法，故答案為 595959。

第二組數(shù)據(jù)： 不存在既能殺死第一條龍又能殺死第二條龍的方法，故無法通關，輸出 ?1-1?1。

【子任務】

測試點編號nnnmmmpip_ipi?aia_iai?攻擊力其他限制

1	≤105\le 10^5≤105	=1=1=1	=1=1=1	≤105\le 10^5≤105	=1=1=1	無
2	≤105\le 10^5≤105	=1=1=1	=1=1=1	≤105\le 10^5≤105	=1=1=1	無
3	≤105\le 10^5≤105	=1=1=1	=1=1=1	≤105\le 10^5≤105	≤105\le 10^5≤105	無
4	≤105\le 10^5≤105	=1=1=1	=1=1=1	≤105\le 10^5≤105	≤105\le 10^5≤105	無
5	≤103\le 10^3≤103	≤103\le 10^3≤103	≤105\le 10^5≤105	≤105\le 10^5≤105	≤105\le 10^5≤105	特性 1、特性 2
6	≤103\le 10^3≤103	≤103\le 10^3≤103	≤105\le 10^5≤105	≤105\le 10^5≤105	≤105\le 10^5≤105	特性 1、特性 2
7	≤103\le 10^3≤103	≤103\le 10^3≤103	≤105\le 10^5≤105	≤105\le 10^5≤105	≤105\le 10^5≤105	特性 1、特性 2
8	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
9	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
10	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
11	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
12	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
13	=1=1=1	=1=1=1	≤108\le 10^8≤108	≤108\le 10^8≤108	≤106\le 10^6≤106	特性 1
14	=105=10^5=105	=105=10^5=105	=1=1=1	≤108\le 10^8≤108	≤106\le 10^6≤106	無特殊限制
15	=105=10^5=105	=105=10^5=105	=1=1=1	≤108\le 10^8≤108	≤106\le 10^6≤106	無特殊限制
16	≤105\le 10^5≤105	≤105\le 10^5≤105	所有 pip_ipi? 是質數(shù)	≤1012\le 10^{12}≤1012	≤106\le 10^6≤106	特性 1
17	≤105\le 10^5≤105	≤105\le 10^5≤105	所有 pip_ipi? 是質數(shù)	≤1012\le 10^{12}≤1012	≤106\le 10^6≤106	特性 1
18	≤105\le 10^5≤105	≤105\le 10^5≤105	無特殊限制	≤1012\le 10^{12}≤1012	≤106\le 10^6≤106	特性 1
19	≤105\le 10^5≤105	≤105\le 10^5≤105	無特殊限制	≤1012\le 10^{12}≤1012	≤106\le 10^6≤106	特性 1
20	≤105\le 10^5≤105	≤105\le 10^5≤105	無特殊限制	≤1012\le 10^{12}≤1012	≤106\le 10^6≤106	特性 1

特性 1 是指：對于任意的 iii，ai≤pia_i \le p_iai?≤pi?。

特性 2 是指：lcm?(pi)≤106\operatorname{lcm}(p_i) \le 10^6lcm(pi?)≤106，即所有 pip_ipi? 的 最小公倍數(shù) 不大于 10610^6106。

對于所有的測試點，T≤5T \le 5T≤5，所有武器的攻擊力 ≤106\le 10^6≤106，所有 pip_ipi? 的最小公倍數(shù) ≤1012\le 10^{12}≤1012。

保證 T,n,m T, n, m T,n,m 均為正整數(shù)。

【提示】

你所用到的中間結果可能很大，注意保存中間結果的變量類型。

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<set> #pragma GCC optimize(2) using namespace std; typedef long long LL; const int maxn = 1e5 + 10 ; LL a[maxn],p[maxn],atk[maxn],x,y,d; multiset<LL> sw;inline LL read() {LL w=1,s=0; char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')w=-1; ch=getchar();}while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}return w*s; } void ext_gcd(LL a,LL b,LL &d,LL &x,LL &y) {if (b==0){d=a;x=1;y=0;return;}ext_gcd(b,a%b,d,y,x); y-=a/b*x; }inline LL ksc(LL x,LL y,LL p){LL z=(long double)x/p*y;LL res=(unsigned long long)x*y-(unsigned long long)z*p;return (res+p)%p; }int main() {LL T,n,m,k,mx,c;T=read();begin:while(T--){n=read();m=read();sw.clear();register multiset<LL>::iterator it;for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) p[i]=read();for(int i=1;i<=n;i++) atk[i]=read();for(int i=1;i<=m;i++)sw.insert(read());mx=c=0;m=1;for(int i=1;i<=n;i++){it=sw.upper_bound(a[i]);if(sw.begin()!=it) it--;k=*it;sw.erase(it);sw.insert(atk[i]);mx=max(mx,(a[i]-1)/k+1);//更新限制k%=p[i];a[i]%=p[i];if(!k && !p[i]) continue;ext_gcd(k,p[i],d,x,y);p[i]/=d;a[i]=ksc(a[i]/d,(x%p[i]+p[i])%p[i],p[i]);ext_gcd(m,p[i],d,x,y);if((a[i]-c)%d){puts("-1");goto begin;}m=m/d*p[i];c=(c+ksc( ksc(m/p[i],((a[i]-c)%m+m)%m,m) , (x%m+m)%m , m))%m;}if(c>=mx) printf("%lld\n",c);else printf("%lld\n",c+m*((mx-c-1)/m+1));}return 0; }

?

?

轉載于:https://www.cnblogs.com/hfang/p/11256752.html

總結

以上是生活随笔為你收集整理的P4774 [NOI2018]屠龙勇士的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。