526互联

小白月赛70

发布时间 2023-04-08 15:04:29作者: NachoNeko

题目链接

https://ac.nowcoder.com/acm/contest/53366

A.小d和答案修改

字母的大小写的 ASCII 码相差32。

#include <bits/stdc++.h>

int main() {
	std::string str;
	std::cin >> str;
	for (int i = 0; i < str.size(); i ++ ) {
		if(str[i] <= 'z' && str[i] >= 'a') {
			std::cout << char(str[i] - 32);
		} else {
			std::cout << char(str[i] + 32);
		}
	}
	return 0;
}

B. 小d和图片压缩

按照题目进行模拟。

#include <bits/stdc++.h>

const int N = 10010;

int a[N][N];
std::vector<int> v[N];

int main() {
	int n,m;
	std::cin >> n >> m;
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1 ; j <= m ; j ++ ) {
			std::cin >> a[i][j];
		}
	}
	int idx = 1;
	for (int i = 1; i <= n; i += 2, idx ++ ) {
		for (int j = 1 ; j <= m - 1; j += 2 ) {
			int u = (a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1]) / 4;
			v[idx].push_back(u);
		}
	}
	for (int i = 1; i < idx; i  ++ ) {
		for (int j = 0; j < v[i].size(); j ++ ) {
			std::cout << v[i][j] << " ";
		}
		std::cout << "\n";
	}
	return 0;
}

C.小d和超级泡泡堂

用 bfs 从开始位置遍历，记录经过杂草的数量

#include <bits/stdc++.h>

int n,m;
int ans = 0;
char c[1010][1010];
bool st[1010][1010];
int dx[] = {1,-1,0,0}, dy[] = {0,0,-1,1};

void bfs(int stx,int sty) {
	std::queue<std::pair<int,int>> q;
	q.push({stx,sty});

	while(q.size()) {
		auto t = q.front();
		q.pop();
		if(st[t.first][t.second]) continue;
		st[t.first][t.second] = true;

		for (int i = 0; i < 4; i ++ ) {
			int x = t.first + dx[i];
			int y = t.second + dy[i];
			if(x > n || x < 0 || y > m || y < 0) continue;
			else {
				if(c[x][y] == '.') {
					q.push({x,y});
				} else if(c[x][y] == '!') {
					ans ++ ;
					q.push({x,y});
					c[x][y] = '.';
				}
			}
		}
	}
	return ;
}

int main() {
	std::cin >> n >> m;
	int stx, sty;
	for (int i = 1; i <= n; i ++ ) { 
		for (int j = 1; j <= m; j ++ ) {
			std::cin >> c[i][j];
			if(c[i][j] == '@') {
				stx = i, sty = j;
			}
		}
	}
	bfs(stx,sty);
	std::cout << ans << "\n";
	return 0;
}

D.小d和孤独的区间

假设某个 1 的左侧连续 0 的个数为 a，右侧连续 0 的个数为 b。

那么包含这个 1 且和为 1 的区间总数为 (a + 1) * (b + 1)。

将所有 1 的位置记录，并处理即可得到答案，最左侧和最右侧增加两个1方便计算。

#include <bits/stdc++.h>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	std::vector<long long> a;

	a.push_back(0);

	for (int i = 0; i < n; i ++ ) {
		int u;
		std::cin >> u;
		if(u == 1) {
			a.push_back(i+1);
		}
	}

	a.push_back(n+1);

	long long ans = 0;
	for (int i = 1; i < a.size() - 1; i ++ ) {
		ans += (a[i] - a[i-1]) * (a[i+1] - a[i]);
	}

	std::cout << ans << "\n";
	return 0;
}

E.小d的博弈

首先进行打表，观察规律。

#include <bits/stdc++.h>

int dp[100][100];

int dfs(int x,int y) {
	if(x > y) std::swap(x,y);

	if(dp[x][y] != 0) return dp[x][y];

	for (int i = 1; i <= x; i ++ ) {
		if(i == x - i) continue;
		if(dfs(std::min(i,x-i),y) == -1) {
			dp[x][y] = 1;
			return 1;
		}
	}
	for (int i = 1; i <= y; i ++ ) {
		if(i == y - i) continue;
		if(dfs(x,std::min(i,y-i)) == -1) {
			dp[x][y] = 1;
			return 1;
		}
	}
	return -1;
}
int main() {
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= n; j ++ ) {
			std::cout << ((dfs(i,j) == 1) ? 'o' : 'x');
		}
		std::cout << "\n";
	}
	return 0;
}

输入 n=30，打表结果如下：

可以观察到当横纵坐标 + 1 的二进制位数相同时 Bob 赢，否则 Alice 赢 。

#include <bits/stdc++.h>

int GetLength(int u) {
	int res = 0;
	while (u) {
		u /= 2;
		res ++;
	}
	return res;
}

void solve() {
	int n,m;
	std::cin >> n >> m;

	if(GetLength(n + 1) == GetLength(m + 1)) {
		puts("Bob");
	} else {
		puts("Alice");
	}
	
	return ;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t;
	std::cin >> t;
	while(t -- ) {
		solve();
	}

	return 0;
}

E.小d和送外卖

用 siz[root] 表示以 root 为根的子树中有多少订单数。

用 dp[root][i] 表示以 root 为根的子树中，选择 j 个订单取消，能够节省多少距离。

花费最少 = 总花费 - 最大节省距离

花费 = (子树中的订单数 - 1) * 2

状态转移方程为：

\(temp[i + j] = max(temp[i + j], dp[u][i] + dp[to][j] + 2 * (j && j == siz[to]));\)

如：

由于后续的状态会用到原先的状态，所以不能一开始就更新，用 temp 存储更新的值，类似于背包的滚动数组。

temp[i + j]：表示当前子树删掉 i + j 个订单的最大节省距离

dp[u][i]：表示在以 u 为根的树中删掉 i 个订单（由于是从前向后扫描，所以只删掉前几个树中的订单）

dp[to][j]：表示删除以 to 为根的子树中 j 个订单

2 * (j && j == siz[to]：若把 to 子树的所有订单都删除，那么即可把 u -> to 的边删掉

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10;

int n,m;
int st[N];
int ans = -2;
int siz[N],dp[N][55]; 
std::vector<int> e[N];

void dfs1(int u,int fa) {
	for (int i = 0; i < e[u].size(); i ++ ) {
		int to = e[u][i];
		if(to == fa) continue;
		dfs1(to, u);
		siz[u] += siz[to];
	}
}

void dfs2(int u,int fa) {
	ans += 2ll * (siz[u] > 0);
	for (int k = 0; k < e[u].size(); k ++ ) {
		int to = e[u][k];
		if(to == fa) continue;
		dfs2(to, u);
		std::vector<int> temp(m + 10);
		for (int i = 0 ; i <= std::min(m, siz[u]); i ++ ) {
			for (int j = 0 ; j <= std::min(m, siz[to]); j ++ ) {
				if(i + j <= m) {
					temp[i + j] = std::max(temp[i + j], dp[u][i] + dp[to][j] + 2 * (j && j == siz[to]));
				}
			}
		}
		for (int i = 0 ; i <= std::min(m, siz[u]); i ++ ) dp[u][i] = temp[i];
	}
	return ;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;

	for (int i = 1; i <= n - 1; i ++ ) {
		int a,b;
		std::cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}

	int k;
	std::cin >> k;
	for (int i = 1; i <= k; i ++ ) {
		int b;
		std::cin >> b;
		siz[b] ++ ;
	}

	dfs1(1,-1);
	dfs2(1,-1);

	ll res = 0;
	for (int i = 0; i <= m; i ++ ) res = std::max(res, (ll)dp[1][i]);
		
	std::cout << ans - res << "\n";

	return 0;
}

参考

[1] 小白月赛 70 比赛题目讲解