1.H-卷王之王_牛客小白月赛36 (nowcoder.com)
首先你发现是对一个数字成倍的增加,所以每个数字他最多加32次。
那么就可以考虑直接加就行,然后用一个优先队列存一下就行.
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
priority_queue<pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > >q;
vector<int>a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
q.push({a[i], i});
}
for(int i = 0; i < m; i++){
int x;
cin >> x;
if(!x) continue;
vector<pair<int,int> >v;
while(!q.empty() && q.top().first <= x){
auto t = q.top();
t.first += x;
v.push_back(t);
q.pop();
}
for(auto t : v){
q.push(t);
}
}
while(!q.empty()){
auto t = q.top();
a[t.second] = t.first;
q.pop();
}
for(int i = 0; i < n; i++){
cout << a[i] << ' ';
}
return 0;
}
2.E-分组_牛客小白月赛40 (nowcoder.com)
对于明显的提示直接考虑二分即可。
二分最大组的人数。再看组数是否满足就行。
#include<bits/stdc++.h>
using namespace std;
int n, m;
map<int,int>mp;
bool check(int maxmx){
int tot = 0;
for(auto [x, y] : mp){
if(y){
tot += y / maxmx + (y % maxmx != 0);
}
}
return tot <= m;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 0; i < n; i++){
int x;
cin >> x;
mp[x]++;
}
int l = 1, r = n;
int ans = -1;
while(l <= r){
int mid = l + r >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
cout << ans << '\n';
return 0;
}
3.蓝桥杯2023年第十四届省赛真题-砍树 - C语言网 (dotcpp.com)
树上差分的题。但是需要将每个边归属到儿子结点。也就是fb数组。
对于没对(a, b)直接考虑a 到 b 的路径上的所有边的权值加1。这个用差分解决就行。
然后看边的权值是否等于m，如果等于m便是可以的。记得输出的是最大值。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<pair<int,int>>b[N];
int fa[N][21], deep[N], fb[N];
int cnt[N];
void dfs(int u, int f){
deep[u] = deep[f] + 1;
fa[u][0] = f;
for(auto [v, id] : b[u]){
if(v == f) continue;
dfs(v, u);
fb[v] = id;
}
}
void dfs2(int u, int f){
for(auto [v, id] : b[u]){
if(v == f) continue;
dfs2(v, u);
cnt[u] += cnt[v];
}
}
int lca(int x, int y){
if(deep[x] < deep[y]) swap(x, y);
int z = deep[x] - deep[y];
for(int j = 0; j <= 20 && z; j++, z /= 2){
if(z & 1){
x = fa[x][j];
}
}
if(x == y) return x;
for(int j = 20; j >= 0; j--){
if(fa[x][j] != fa[y][j]){
x = fa[x][j];
y = fa[y][j];
}
}
return fa[x][0];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 1; i