題目鏈接：點擊查看

題目大意：給出大小為 n 的一個數組 a 和一個數字 K，每個位置起始時為 0 ，現在從 i = 0 開始遞增，我們能夠進行如下操作：

選取 pos ∈ [ 1 , n ] 作為數組的下標：

a[ pos ] += k^i

什么都不做

現在給出一個目標數組，大小同樣為 n ，問能否通過適當的操作將數組 a 轉換到目標數組

題目分析：比賽的時候自暴自棄了，第一反應是模擬，在WA了一發后意識到細節過多，即使可以模擬實現的代碼復雜度也較高，于是嘗試轉變思路，然后就卡住了，對不起我真的太菜了

賽后看了大佬們的代碼，豁然開朗，這不就是一個位運算嘛。。給出的 K 我們視為進制，將每個數字都視為 K 進制下的一個數字，不難看出每個數字在 K 進制下的分解是唯一的，而題目給出的操作就是給 K 進制的某一位最多加一，換句話說，將所有數組拆為 K 進制后，如果 K 進制下每一位的出現次數都小于等于 1 的話，那么說明肯定是可行的，否則就是不可行的

代碼：

#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<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;LL n,k;int cnt[N];vector<LL>fac;void init() {memset(cnt,0,sizeof(cnt));fac.clear();fac.push_back(1);while(fac.back()<1e16)fac.push_back(fac.back()*k); }void solve(LL num) {while(num){for(int i=fac.size()-1;i>=0;i--)if(num>=fac[i]){num-=fac[i];cnt[i]++;}} }bool check() {for(int i=0;i<fac.size();i++)if(cnt[i]>1)return false;return true; }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--){scanf("%lld%lld",&n,&k);init();for(int i=1;i<=n;i++){LL num;scanf("%lld",&num);solve(num);}if(check())puts("YES");elseputs("NO");}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1312C Adding Powers(思维+位运算)的全部內容，希望文章能夠幫你解決所遇到的問題。

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