洛谷题单
二叉堆（优先队列）（三道简单题）
P3378 【模板】堆 - 洛谷
priority_queue相关知识
priority_queue<int> q;//这是一个大根堆q，（从大到小输出）
priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q（记得加空格）
//操作
q.top()//取得堆顶元素，并不会弹出 ,O(1)
q.pop()//弹出堆顶元素 O(logn)
q.push()//往堆里面插入一个元素O()
q.empty()//查询堆是否为空，为空则返回1否则返回0
q.size()//查询堆内元素数量
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
priority_queue<int,vector<int>,greater<int> > q;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,op,x;cin >> n;while(n--){cin >> op;if(op==1){cin >> x;q.push(x);}if(op==2){cout << q.top() << endl;}if(op==3){q.pop();}}
}
P1801 黑匣子 - 洛谷
开两个堆，一个大根堆，一个小根堆
当到要第i小元素时，b中存着前i-1小的元素，因为每次只会把最大值给s
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
priority_queue<int, vector<int>, greater<int>> s;
priority_queue<int> b;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;vector<int> a(n + 1), u(m + 1);for (int i = 1; i <= n;i++){cin >> a[i];}for (int i = 1; i <= m;i++){cin >> u[i];}int p = 0;for (int i = 1; i <= m;i++){while(p<u[i]){p++;b.push(a[p]);s.push(b.top());b.pop();}cout << s.top() << endl;b.push(s.top());s.pop();}
}
P1090 [NOIP 2004 提高组] 合并果子 - 洛谷
合成一堆，花费最小的体力值，每次选择最小两个合并
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
priority_queue<int, vector<int>, greater<int>> q;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n;cin >> n;for (int i = 0; i < n;i++){int x;cin >> x;q.push(x);}int sum = 0;while(q.size()>1){int a, b;a = q.top();q.pop();b=q.top();q.pop();sum += a + b;q.push(a + b);}cout << sum << endl;
}
二叉堆（较难）
P2168 [NOI2015] 荷马史诗 - 洛谷(哈夫曼树)
依题意
对于任意的 \(1\leq i,j\leq n\) ，\(i\neq j\)，都有：\(s_i\) 不是 \(s_j\) 的前缀。
所以用哈夫曼树
知识点
重载运算符bool operator<(const node &x)const{
if(w!=x.w)return w > x.w;return h > x.h;
}
C++11 及以上支持`{}`形式的聚合初始化：
node{w, 0LL};// 等价于：创建一个node对象，直接给成员赋值：w=传入的w，h=0LL
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
struct node{LL w, h;bool operator<(const node &x)const{if(w!=x.w)return w > x.w;return h > x.h;}
};
priority_queue<node> q;//小根堆
LL ans;int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);LL n, k;cin >> n >> k;for (int i = 1; i <= n;i++){LL w;cin >> w;q.push(node{w, 0LL});}while((q.size()-1)%(k-1)!=0)//k叉哈夫曼树处理方法q.push(node{0LL, 0LL});while(q.size()>=k){LL h = 0, w = 0;for (int i = 1; i <= k;i++){node t = q.top();q.pop();h = max(h, t.h);w += t.w;}ans += w;q.push(node{w, h + 1});}cout << ans << endl<< q.top().h << endl;
}
CF
Problem - C - Codeforces（1400）
一道思维题
因为\(1\leq x_1\leq x_2\leq x_3\) ,所以\(x=x_1+x_2+x_3\) ，能分成满足\(x_1,x_3\) 有最大公约数
要枚举公倍数
然后计算满足的数量
首先倍数是一定满足的
如果不是倍数的话，当\(i\)为最大公约数时，\(x\) 必须大于等于\(4i\)，因为这样才能分成\(x=i+i+2i\) ,这是符合题意的不是倍数的最小值了
然后可删除数为k，所以计数，比较即可
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;void solve()
{int n,k;cin >> n >> k;vector<int> cnt(n + 1), s(n + 1);for (int i = 0,x; i < n;i++){cin >> x;cnt[x]++;s[x]++;}for (int i = n-1; i >= 0;i--){s[i] += s[i + 1];}int ans = 0;for (int i = 1; i <= n;i++){int res = 0;if(i<=n)res += cnt[i];if(i*2<=n)res += cnt[i * 2];if(i*3<=n)res += cnt[i * 3];if(i*4<=n)res += s[i * 4];if(res+k>=n){ans = max(ans, i);}}cout << ans << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}
牛客周赛
第一次AK！！！
存个F题代码，一道区间dp，暑假刷的区间dp居然有机会见到，太感动了
F-竹摇清风拂面_牛客周赛 Round 124
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 998244353;
const int N=2e5+10;
LL f[505][505];
LL inf = 1e18;void solve()
{int n;cin >> n;vector<LL> a(n+1);string s;cin >> s;s = " " + s;for (int i = 0; i <= n;i++){for (int j = 0; j <= n;j++){f[i][j] = inf;}}for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <=n; i++){//f[i][i + 1] = a[i] * a[i + 1];//f[i][i] = 0;f[i][i - 1] = 0;f[i][i - 2] = 0;}for (int len = 2; len <= n;len+=2){for (int i = 1; i + len - 1 <= n;i++){int l = i, r = i + len - 1;for (int k = l; k <= r;k++){if(s[l]==s[k]){f[l][r] = min(f[l][r], f[l+1][k-1] + f[k + 1][r] + a[l] * a[k]);}}}}if(f[1][n]==inf){cout << -1 << endl;return;}cout << f[1][n] << endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin >> T;while (T--){solve();}
}