作者：指針不指南嗎
專欄：藍橋杯倒計時沖刺??馬上就要藍橋杯了，最后的這幾天尤為重要，不可懈怠哦??
1.湊數(shù)
-
題目
鏈接： 4941. 湊數(shù) - AcWing題庫
初始時，n=0。
每一輪操作都要依次完成兩個步驟：
- 第一步，任選一個非負整數(shù) a，將 n 增加 a，這一步所需付出的代價為 a。
- 第二步，將 n 乘以 2，這一步無需付出任何代價。
你可以不斷重復(fù)上述操作。
給定一個整數(shù) x，你的任務(wù)是使 n 在某一步操作后（不一定是某一輪結(jié)束后）恰好等于 x 且付出的總代價盡可能少。
請你計算，為了完成任務(wù)所需付出的最小總代價。
例如，如果 x=5，則最佳操作方案為：
- 第 1 輪操作中，第一步，將 n 增加 1（付出代價 1），使得 n 變?yōu)?1，第二步，將 n 乘以 2，使得 n 變?yōu)?2。
- 第 2 輪操作中，第一步，將 n 增加 0（付出代價 0），則 n 仍然為 2，第二步，將 n 乘以 2，使得 n 變?yōu)?4。
- 第 3 輪操作中，第一步，將 n 增加 1（付出代價 1），使得 n 變?yōu)?5。此時 n 等于 x 成立，任務(wù)完成。
- 付出的最小總代價為 2。
再例如，如果 x=8，則最佳操作方案為：
- 第 1 輪操作中，第一步，將 n 增加 1（付出代價 1），使得 n 變?yōu)?1，第二步，將 n 乘以 2，使得 n 變?yōu)?2。
- 第 2 輪操作中，第一步，將 n 增加 0（付出代價 0），則 n 仍然為 2，第二步，將 n 乘以 2，使得 n 變?yōu)?4。
- 第 3 輪操作中，第一步，將 n 增加 0（付出代價 0），則 n 仍然為 4，第二步，將 n 乘以 2，使得 n 變?yōu)?8。此時 n 等于 x 成立，任務(wù)完成。
- 付出的最小總代價為 1。
輸入格式
一個整數(shù) x。
輸出格式
一個整數(shù)，表示所需付出的最小總代價。
數(shù)據(jù)范圍
前 3 個測試點滿足 1≤x≤10。
所有測試點滿足 1≤x≤ 1 0 9 10^9 109 。輸入樣例1：
5輸出樣例1：
2輸入樣例2：
8輸出樣例2：
1 -
第一次 AC 4/10
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; if(n%2==0||n==1) cout<<1; else cout<<2; return 0; } -
題解1 轉(zhuǎn)換思路，倒推，偶數(shù)沒有代價，奇數(shù)的代價+1
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int ans=0; while(n) { ans+=n%2; n/=2; //偶數(shù)沒有代價，奇數(shù)代價+1 } cout<<ans; return 0; } -
題解2 模擬二進制，計算二進制中1出現(xiàn)的次數(shù)
step1: (n+a1)*2
step2: ((n+a1)* 2+a2)* 2
step3: (((n+a1)* 2+a2)* 2+a3)*2
ans=a1+a2+a3
發(fā)現(xiàn)t應(yīng)該是多個2的多次冪的相加，馬上就能聯(lián)想到二進制，而答案就是a1 + a2 + … + an，而且二進制每個位是0/1，所以只需要統(tǒng)計1的數(shù)量即可
#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int ans=0; while(n) { ans++; n&=(n-1); //這里是計算 n 二進制中1的個數(shù) } //執(zhí)行一次x = x&(x-1)，會將x用二進制表示時最右邊的一個1變?yōu)?，因為x-1將會將該位(x用二進制表示時最右邊的一個1)變?yōu)? cout<<ans; return 0; } -
反思
- 第一次，直接不斷地乘2，錯以為每個偶數(shù)都可以包含在內(nèi)，4*2=8，6就沒有包含進去；
- 題解轉(zhuǎn)換思維，從后往前推，這樣結(jié)果 x 一定包含在內(nèi)，此過程中偶數(shù)沒有代價，奇數(shù)代價+1；
- 模擬二進制，計算一個數(shù)二進制中 1 的個數(shù)，又學到了
while(n) { ans++; n&=(n-1); //這里是計算 n 二進制中1的個數(shù) }
2.砝碼稱重
-
題目
鏈接： 4942. 砝碼稱重 - AcWing題庫
給定一個天平和 101 個砝碼。
101 個砝碼的重量依次為 n 0 , n 1 , n 2 , … , n 100 n^0,n^1,n^2,…,n^{100} n0,n1,n2,…,n100 克，其中 n 是一個不小于 2 的整數(shù)。
請你判斷，我們能否利用給定天平和砝碼對重量為 m 克的物品進行稱重。
注意，天平的兩端都可以放入砝碼。
具體來說，你的任務(wù)是判斷是否可以在天平的左盤放入重量為 m 克的物品以及一些砝碼（也可以不放砝碼），并在天平的右盤放入一些砝碼，從而使得天平的兩端可以保持平衡。
不要求用到所有砝碼，挑選合適的砝碼使用即可。
例如，如果 n=3,m=7，則我們可以在天平的左盤放入重量為 7 克的物品以及重量為 3 克的砝碼，并在天平的右盤放入重量為 1,9 克的砝碼，這樣可以使得天平兩端保持平衡。
輸入格式
共一行，包含兩個整數(shù) n,m。
輸出格式
如果可以對重量為 m 克的物品進行稱重，則輸出
YES，否則輸出NO。數(shù)據(jù)范圍
前 5 個測試點滿足 2≤n≤100，1≤m≤100。
所有測試點滿足 2≤n≤ 1 0 9 10^9 109，1≤m≤ 1 0 9 10^9 109 。輸入樣例1：
3 7輸出樣例1：
YES輸入樣例2：
100 99輸出樣例2：
YES輸入樣例3：
100 50輸出樣例3：
NO -
第一次 AC 8/21
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; for(int i=0;i<101;i++) for(int j=0;j<=i;j++) { if(pow(n,i)-pow(n,j)==m||pow(n,i)==m) //這里考慮的太簡單，天平的一個盤子上既可以放物品，也可以放砝碼，我忽略掉 { puts("YES"); return 0; } } puts("NO"); return 0; } -
騙分——新方法 AC 17/21
#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin>>n>>m; puts("YES"); return 0; } //滿意 -
題解
假設(shè)存在m使得等式成立那么一定有
m + n的k1 + n的k2 + n的k3 + … = n的k4 + n的k5 + …如果k都不是0的話，將m移到等式的一邊，另一邊都是n的k次冪相加，那么m一定可以被n整除。 設(shè)為條件1
但是k是可以為0的，所以可能等式兩邊存在1， 那么m等于n的k次冪相加再 + 1 或 -1 ，那么對m進行+1或-1可以讓他繼續(xù)滿足條件1，如此循環(huán)，如果m + 1 或 -1都無法滿足條件1。說明m無法湊成多個n的k次冪相加減，等式無法成立，就無解。
否則操作到最后，m會變成n的0次= 1。思路就是：如條件1滿足，我們就等式兩邊除以n。 如果出現(xiàn)了n的0次冪，就+1或-1消去，此時的m還是滿足條件的。
如果條件1不滿足，而且對m + 1 或 -1 都無法滿足條件1， 那么m就無法被n的不同次冪的砝碼在等式中拼湊
出來。#include<bits/stdc++.h> using namespace std; int m, n; int main() { cin >> n >> m; while(m > 1) { // cout << m << endl; if(m % n == 0) m /= n; else if((m + 1) % n == 0) m++; else if((m - 1) % n == 0) m--; else { cout << "NO"; return 0; } } cout << "YES"; return 0; } -
反思
學到新技能——騙分，yes or no 二選一，運氣好的話，拿一半多得分文章來源：http://www.zghlxwxcb.cn/news/detail-403276.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-403276.html
到了這里，關(guān)于藍橋杯刷題沖刺 | 倒計時6天的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
