題目鏈接：點擊查看

題目大意：給出一個基數 p ，再給出 n 個指數 k ，換句話說，現在有一個長度為 n 的序列，每個元素都是 p^k[ i ] ，現在需要將這個序列分到兩個集合中，使得兩個集合元素和之差的絕對值最小，輸出這個絕對值

題目分析：首先需要知道的是，題意給出了基數和指數，換句話說所有的數字都是在 p 進制下進行的，因為之前在 cf 上也做過一個類似的題，就是讓最大的單獨一組，剩下最小的都在一組是最優的，而在這個題目中，可以先對指數進行降序排序，設答案為 ans，初始時為 0 ，一個顯然的貪心策略是：

ans == 0 ，ans就加上當前的數

ans > 0 ，ans就減去當前的數

因為所有的情況都是在 p 進制下進行的，所以每次操作的 ans 保證了一定是非負的，這樣貪心去模擬就好了

其實這個題目的難點是在于模擬上，而不是前面的貪心，因為每個元素都非常大，顯然是無法直接維護這個 ans ，但是我們發現，只需要判斷 ans 是否為 0 即可，所以這里可以偷個懶，利用雙哈希取模，這樣就可以判斷 ans 是否為 0 了，不過常用的一些哈希值很容易被作者想到，從而出一些針對的數據，所以我選了一個比較不錯的 mod = 999999998

然后說一下正解，因為所有的數都是基于 p 進制下的，舉個例子就能講清楚了，假設此時的 p = 4 ，而最大的 k 是 100 ，第一步操作 ans = 0，執行操作 1 ，所以此時 ans = 4^100，接下來需要一個 4^100 來中和 ans ，或者 4 個 4^99 來中和，或者 16 個 4^98，因為我們已經排好序了，如果接下來的一個數時 4^99 的話，那么執行操作 2 中和結束后，得到的是：ans = 3 * 4^99，換句話說，此時還需要 3 個 4^99，或者需要 12 個 4^98 ....以此類推，這樣我們只需模擬上述過程即可

注意一個小細節，就是對應著樣例的第三個，那就是第一個 k = 100 ，而第二個 k = 1，中間跨過了 99 個 k ，此時為了中和一開始的 5^100，需要 5^99?個 5^1 來中和，顯然 5^99 也過于龐大了，所以需要增加一個對應的剪枝，那就是如果當前需要中和的個數比數據范圍 1e6 還大，那剩下的所有數肯定都用來中和是最優的，同時因為 2^20 > 1e6，所以每次更新需要中和的個數的時候，至多到 20 就足夠了

代碼：

正解

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod=1e9+7;int k[N];LL q_pow(LL a,LL b) {LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,p;scanf("%d%d",&n,&p);for(int i=1;i<=n;i++)scanf("%d",k+i);sort(k+1,k+1+n,greater<int>());LL ans=0,remain=0;bool flag=false;k[0]=k[1];for(int i=1;i<=n;i++){if(k[i]!=k[i-1]){int t=min(k[i-1]-k[i],20);assert(t>0);while(t--){remain*=p;if(remain>N){flag=true;break;}}}if(remain>0||flag){remain--;ans=(ans-q_pow(p,k[i])+mod)%mod;}else{remain++;ans=(ans+q_pow(p,k[i]))%mod;}}printf("%lld\n",ans);}return 0; }

哈希：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;const int mod1=1e9+7;const int mod2=999999998;int k[N];LL q_pow(LL a,LL b,LL mod) {LL ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n,p;scanf("%d%d",&n,&p);for(int i=1;i<=n;i++)scanf("%d",k+i);sort(k+1,k+1+n,greater<int>());LL ans1=0,ans2=0;for(int i=1;i<=n;i++){if(!ans1&&!ans2){ans1=(ans1+q_pow(p,k[i],mod1))%mod1;ans2=(ans2+q_pow(p,k[i],mod2))%mod2;}else{ans1=(ans1-q_pow(p,k[i],mod1)+mod1)%mod1;ans2=(ans2-q_pow(p,k[i],mod2)+mod2)%mod2;}}printf("%lld\n",ans1);}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1362E Johnny and Grandmaster(贪心+模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

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