活動安排

題目鏈接

題解

1. 區間貪心 + 排序
2. 如果有重疊部分，每次選擇右端點較小的，可以盡可能多的選擇區間個數，如果沒有重疊部分，選擇下一個區間的右端點為基準，重復剛剛的操作

代碼

#include <iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 10;
typedef pair<int,int> PII;
PII a[N];int main()
{int n;cin >> n;for(int i = 0;i < n;i++) cin >> a[i].first >> a[i].second;sort(a,a+n);int ret = 0,r = a[0].second;for(int i = 1;i < n;i++){// 有重疊if(a[i].first < r){r = min(r,a[i].second);}else // 沒有重疊{ret++;r = a[i].second;}}// 未記錄第一個區間所以加1cout << ret + 1 << '\n';return 0;
}

哈夫曼編碼

題目鏈接

題解

1. 哈夫曼編碼，利用字符出現的頻次構建一個二叉樹，每次選擇頻次最小的兩個數構建二叉樹，根據最優二叉樹編碼
2. 把題目中數出現的頻次放入一個小根堆中，每次取兩個數相加放入堆中，然后此時也計算最短長度，直到堆中僅剩一個元素時，得到最短長度

代碼

#include <iostream>
#include<queue>
using namespace std;const int N = 2e5 + 10;
int a[N];int main()
{// 小根堆priority_queue<long long,vector<long long>,greater<long long>> pq;int n;cin >> n;for(int i = 0;i < n;i++){cin >> a[i];pq.push(a[i]);}long long count = 0;while(pq.size() != 1){long long a = pq.top();pq.pop();long long b = pq.top();pq.pop();count += a;count += b;pq.push(a + b);}cout << count << '\n';return 0;
}

奇數位丟棄

題目鏈接

題解

1. 找規律
2. 可以看出每次刪除的第一個數是2^n - 1，
求2 ^ x - 1 <= n中x的最大值就是最后剩下的數

代碼

#include <iostream>
#include<math.h>
using namespace std;int main()
{int n;while(cin >> n){int x = 0;long long ret = 1;while(ret <= n + 1){ret += pow(2,x);x++; }cout << pow(2,x-1) - 1 << '\n';}return 0;
}#include <iostream>
using namespace std;int main()
{int n;while(cin >> n){int ret = 1;while(ret - 1 <= n) ret *= 2;cout << ret / 2 - 1 << '\n';}return 0;
}