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 < n; i++){
int u, v;
cin >> u >> v;
b[u].push_back({v, i});
b[v].push_back({u, i});
}
dfs(1, 0);
for(int i = 1; i <= 20; i++){
for(int j = 1; j <= n; j++){
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
cnt[u]++;
cnt[v]++;
cnt[lca(u, v)] -= 2;//lca结点的边不能加所以要减去两次。
}
dfs2(1, 0);
int ans = -1;
for(int i = 1; i <= n; i++){
if(cnt[i] == m && fb[i] > ans){
ans = fb[i];
}
}
cout << ans << '\n';
return 0;
}
5.F-过桥_牛客小白月赛40 (nowcoder.com)
只有两千个点，最多总共有2000 * 2000的边，并且边权是1。所以思路很简单就是纯正的最短路，并且直接用bfs就能解决。因为边权是1。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
vector<int>b[N];
int dis[N], a[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
if(a[i] > 0){
for(int j = i + 1; j <= min(a[i] + i, n); j++){
b[i].push_back(j);
}
}
else{
for(int j = 1; j <= max(a[i] + i, 1); j++){
b[i].push_back(j);
}
}
}
// for(int i = 1; i <= n; i++){
// for(auto v : b[i]){
// cout << v << " ";
// }
// cout << '\n';
// }
queue<int>q;
q.push(1);
for(int i = 2; i <= n; i++) dis[i] = -1;
while(!q.empty()){
int u = q.front();
q.pop();
for(int v : b[u]){
if(dis[v] == -1){
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
cout << dis[n] << '\n';
return 0;
}
6.J-小游戏_牛客小白月赛30 (nowcoder.com)
纯正的dp。
首先定义dp[i]为取到大小为i的数的分数的最大值。
dp[i] 可以从dp[i - 1]转移过来但是本身的权值无法获得。
dp[i] 也可以从dp[i - 2]转移过来但是可以获得本身的权值。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int cnt[N];
int f[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int m = 0;
for(int i = 1; i <= n; i++){
int x;
cin >> x;
cnt[x]++;
m = max(m, x);
}
int ans = 0;
for(int i = 1; i <= m; i++){
f[i] = cnt[i] * i;
if(i - 1 >= 0){
f[i] = max(f[i], f[i - 1]);
}
if(i - 2 >= 0){
f[i] = max(f[i], f[i - 2] + cnt[i] * i);
}
ans = max(ans, f[i]);
}
cout << ans << '\n';
return 0;
}
6.C-dd爱科学2.0_牛客小白月赛34 (nowcoder.com)
依旧还是dp。就考虑当前串变成的串。
dp[i][j]表示到第i个字符 且第i个字符是j的时候所需要的最小权值。
那么dp[i][j]可以从 dp[i - 1][1] ~ dp[i - 1][j]传递过来。
但是也可以通过优化就直接dp[i][j] = min(dp[i][1] ~ dp[i][j]);
#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 29;
const int N = 1e6 + 10;
int n, dp[N][30];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
char c;
int x;
for(int i = 1; i <= n; i ++) dp[i][0] = inf;
for(int i = 1; i <= n; i ++) {
cin >> c;
x = c - 'A' + 1;
for(int j = 1; j <= 26; j ++) {
dp[i][j] = abs(x - j) + dp[i - 1][j];
dp[i][j] = min(dp[i][j], dp[i][j - 1]);
}
}
cout << dp[n][26] << '\n';
return 0;
}
7.E-小红的rpg游戏_牛客小白月赛41 (nowcoder.com)
暴力判断还是挺好想的吧，总共就只有是个怪物。直接二进制枚举。考虑哪些点是可以踩的，哪些点是不可以踩的.
如果可以踩的消耗的血量大于h也就不行了。
最后就直接bfs求出到终点的最小步数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 55;
char mp[N][N];
int dis[N][N];
bool st[N][N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, h;
cin >> n >> m >> h;
vector<pair<int,int>>a;
int cnt = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> mp[i][j];
if(mp[i][j] >= '0' && mp[i][j] <= '9'){
a.push_back({i, j});
cnt++;
}
}
}
int tot = 1 << cnt;
int ans = 1 << 29;
vector<int>dx{1, -1, 0, 0};
vector<int>dy{0, 0, 1, -1};
for(int i = 0; i < tot; i++){
int sum = 0;
for(int j = 0; j < cnt; j++){
if(i & (1 << j)){
st[a[j].first][a[j].second] = 1;
sum += mp[a[j].first][a[j].second] - '0';
}
else{
st[a[j].first][a[j].second] = 0;
}
}
if(sum >= h) continue;
memset(dis, -1, sizeof(dis));
queue<pair<int,int>>q;
q.push({1, 1});
dis[1][1] = 0;
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int nx = dx[i] + x;
int ny = dy[i] + y;
if(nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '*' || dis[nx][ny] != -1) continue;
if(mp[nx][ny] == '.' || st[nx][ny]){
dis[nx][ny] = dis[x][y] + 1;
q.push({nx, ny});
}
}
}
if(dis[n][m] != -1) ans = min(ans, dis[n][m]);
}
cout << (ans == (1 << 29) ? -1 : ans) << '\n';
return 0;
}
8.蓝桥杯2023年第十四届省赛真题-异或和之和 - C语言网 (dotcpp.com)
考虑异或的性质，只要某位上1的个数为奇数即可。
考虑按位统计结果,固定右边如果此时（1 - i）某位上1的个数是奇数则找前面位置1 - j（j < i）的个数是偶数个的。
滑动的左边可以考虑直接前缀和统计个数即可。就是code中c数组。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int a[N], num[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int ans = 0;
for(int i = 0; i < 21; i++){
int cnt = 0, res = 0, lst = 0;
vector<int>c(2, 0);
for(int j = 1; j <= n; j++){
if(a[j] & (1 << i)){
num[j] = ++cnt;
c[cnt & 1] += (j - lst);
lst = j;
res += c[cnt & 1];
}
else{
res += c[num[lst] & 1];
}
}
ans += res * (1 << i);
}
cout << ans << '\n';
system("pause");
return 0;
}