目錄

P1031 [NOIP2002 提高組] 均分紙牌

原題鏈接 :

題面 :?

?思路 :

代碼 :?

P1036 [NOIP2002 普及組] 選數(shù)

原題鏈接 :

題面 :?

思路 :

代碼 :?

P1060 [NOIP2006 普及組] 開心的金明

原題鏈接 :?

題面 :?

?思路 :?

01背包例題 :

代碼 :??

P1100 高低位交換

原題鏈接 :?

題面 :?

?思路 :

代碼 :?

P1097 [NOIP2007 提高組] 統(tǒng)計數(shù)字

原題鏈接?

題面 :?

??編輯

思路 :?

代碼 1: map + set

?代碼 2? : 數(shù)組排序

---

視頻鏈接 :?Erik_Tse

P1031 [NOIP2002 提高組] 均分紙牌

原題鏈接 :

?????????均分紙牌

題面 :?

?思路 :

? 根據(jù)貪心的思想，肯定是先將第一堆的紙牌弄成n張，再去弄后面的!

循環(huán)往后，如果當(dāng)前隊中牌數(shù)小于n,從下一堆中移差值牌數(shù)過來，

如果大于的話，就將差值牌數(shù)移給下一堆。最后一定就是滿足題目要求的!!!

所以請看代碼 :?

代碼 :?

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 102;
int n,a[N];
LL ans,sum,avg,k;
int main() {cin>>n;for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];avg = sum / n;for(int i=1;i<=n;i++){if(a[i] < avg){k = avg - a[i];a[i] += k;a[i+1] -= k;ans ++;}if(a[i] > avg){k = a[i] - avg;a[i] -= k;a[i+1] += k;ans ++; }}cout<<ans<<endl;return 0;
}

P1036 [NOIP2002 普及組] 選數(shù)

原題鏈接 :

?選數(shù)

題面 :?

思路 :

就是一個dfs找子集的問題，沒什么好說的，詳細請看代碼?!!!

實現(xiàn)組合型枚舉例題 :?實現(xiàn)組合型枚舉

代碼 :?

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 22;
int n,a[N],k;bool is_prime(int x){//判斷素數(shù)模板，要記住 if(x < 2) return false;for(int i=2;i<=x/i;i++) if(x%i == 0) return false;return true;
}LL dfs(int dep,int cnt,int sum){ if(cnt == k) return (int)is_prime(sum);//找到k個元素if(dep > n) return 0;//搜索到數(shù)組最后一個元素，退出// 子集問題，選或不選 兩個分支 :  // 選 : dfs(dep+1,cnt,sum) // 不選 : dfs(dep + 1,cnt + 1 , sum + a[dep])LL res = 0;res += dfs(dep + 1 , cnt , sum);res += dfs(dep + 1 , cnt + 1 , sum + a[dep]); return res;
}int main() {cin >> n >> k;for(int i=1;i<=n;i++) cin>>a[i];// dfs(dep,cnt,sum)// dep : 下標 // cnt : 當(dāng)前選了幾個數(shù) // sum : 當(dāng)前選數(shù)之和  cout << dfs(1,0,0) << endl;return 0;
}

P1060 [NOIP2006 普及組] 開心的金明

原題鏈接 :?

開心的金明

題面 :?

?思路 :?

本質(zhì)上就是一個01背包問題，分選和不選兩種情況!!!不懂得可以看01背包例題 :?

01背包例題 :

?2. 01背包問題 - AcWing題庫

代碼 :??

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 3e4+10;
int n , m;
int v[27],w[27];
LL dp[30][N];//表示從前i個物品中選，重前不過j的最大價值 int main() {cin >> n >> m;for(int i=1;i<=m;i++) cin >> v[i] >> w[i];// 本質(zhì) : 01背包 for(int i=1;i<=m;i++){for(int j=0;j<=n;j++){if(j < v[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + v[i]*w[i]);}}cout<<dp[m][n]<<endl;return 0;
}

P1100 高低位交換

原題鏈接 :?

高低位交換 - 洛谷

題面 :?

?思路 :

位運算，模擬即可

代碼 :?

#include<iostream>
using namespace std;
typedef long long LL;
LL x,ans,st,en;
int main()
{scanf("%lld",&x);st = x >> 16;en = x % (65536);en = (en << 16);ans = en + st;printf("%lld",ans); return 0;
}

P1097 [NOIP2007 提高組] 統(tǒng)計數(shù)字

原題鏈接?

統(tǒng)計數(shù)字

題面 :?

?

思路 :?

用map+set :?

代碼 1: map + set

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long LL;
const int N = 3e4+10;
int m,x;
unordered_map<int,int> mp;
set<int> st;int main() {cin >> m;while(m--){cin>>x;mp[x]++;st.insert(x);}for(auto it = st.begin() ; it != st.end() ; it ++){cout << *it << " " << mp[*it] << endl;}return 0;
}

?代碼 2? : 數(shù)組排序

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
#include <set>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
int n, a[N], cnt;int main() {cin >> n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++){cnt ++;if(i==n || a[i]!=a[i+1]){cout<<a[i] <<" "<<cnt<<endl;cnt = 0;}}return 0;
}