【牛客】牛客小白月赛92 题解 A - F

2024-04-29 14:20:04
开发
26

在这里插入图片描述

A - 获得木头（签到）

输出 n * 4 / 2 * 4 即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	cout << n * 4 / 2 * 4;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

B - 采矿时间到！（排序）

这题一开始没注意只能上下走不能左右走，wa麻了

首先在体力允许的条件下，把第2层和第4层的矿石全挖走

之后还是在体力允许的情况下，记录一下挖走每个第1层和第5层的矿石需要多少体力，如果在同列的第2层和第4层有矿石的话，只用消耗1体力，没有就要消耗2体力，放在vector里面排个序，从小往大取直到体力小于0

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void solve()
{
	int n, h;
	cin >> n >> h;
	vector<vector<char>> g(6, vector<char>(n + 1));
	for (int i = 1; i <= 5; i ++ )
		for (int j = 1; j <= n; j ++ )
			cin >> g[i][j];
	int ans = 0;
	for (int i = 2; i <= 4; i += 2)
		for (int j = 1; j <= n; j ++ )
		{
			if (h <= 0) break;
			if (g[i][j] == '*')
			{
				h -- ;
				ans ++ ;
			}
		}
	if (h > 0)
	{
		vector<int> v;
		for (int i = 1; i <= n; i ++ )
		{
			if (g[1][i] != '*') continue;
			if (g[2][i] == '*') v.push_back(1);
			else v.push_back(2);
		}
		for (int i = 1; i <= n; i ++ )
		{
			if (g[5][i] != '*') continue;
			if (g[4][i] == '*') v.push_back(1);
			else v.push_back(2);
		}
		sort(v.begin(), v.end());
		for (auto t : v)
			if (h >= t)
			{
				h -= t;
				ans ++ ;
			}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

C - 耕种时间到！（模拟）

纯模拟，用 ans[i] 表示第 i 时间的 x 数量

首先把原本就是 x 的记录到 ans[0] 中

之后把所有除以3上取整相同的数存进一个map里，因为之后他们的变化都是相同的

然后将每个map里的数一直除以3上取整，答案存进 ans[idx] 里，idx 表示操作的次数，最后取最大值即可

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, x;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	cin >> x;
	map<int, int> mp;
	vector<int> ans(60);
	for (int i = 0; i < n; i ++ )
	{
		if (a[i] == x) ans[0] ++ ;
		bool tmp = a[i] % 3;
		a[i] = a[i] / 3 * 3 + tmp * 3;
		mp[a[i]] ++ ;
	}
	for (auto &t : mp)
	{
		mp[(int)ceil(1.0 * t.first / 3)] += t.second * 2;
		t.second = 0;
	}
	for (auto t : mp)
	{
		int num = t.first, cnt = t.second;
		if (cnt == 0) continue;
		int idx = 1;
		while (num >= x)
		{
			if (num == x)
			{
				ans[idx] += cnt;
				break;
			}
			num = ceil(1.0 * num / 3);
			cnt *= 2;
			idx ++ ;
		}
	}
	int maxx = 0;
	for (auto t : ans) maxx = max(maxx, t);
	cout << maxx << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

D - 探索的时光（公式化简）

把平方拆开，因式分解一下就很简单了

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	int sum = 0, tmp1 = 0, tmp2 = 0;
	for (int i = 1; i <= n; i ++ )
	{
		sum += a[i];
		tmp1 += a[i] * i;
		tmp2 += i * i * a[i];
	}
	int ans = INF;
	for (int i = 1; i <= n; i ++ )
	{
		ans = min(ans, i * i * sum - 2 * i * tmp1 + tmp2);
	}
	cout << ans << '\n';
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

E - 来硬的（dp）

首先从数据范围一看就容易猜到是dp，让你用两个for循环更新的

然后设计状态 dp[i][j][0/1] 表示前 i 个物品，至少获得 j 个矿石的最短时间，0表示还没用技能，1表示已经用了技能

状态转移：

dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][max((i64)0, j - a[i].first)][0] + a[i].second)
dp[i][j][1] = min({dp[i - 1][j][1], dp[i - 1][max((i64)0, j - a[i].first)][1] + a[i].second, dp[i - 1][max((i64)0, j - 2 * a[i].first)][0] + a[i].second / 2})

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<PII> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i].first >> a[i].second;
	vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, INF)));
	dp[0][0][0] = 0;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 0; j <= m; j ++ )
		{
			dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][max((i64)0, j - a[i].first)][0] + a[i].second);
			dp[i][j][1] = min({dp[i - 1][j][1], dp[i - 1][max((i64)0, j - a[i].first)][1] + a[i].second, dp[i - 1][max((i64)0, j - 2 * a[i].first)][0] + a[i].second / 2});
		}
	}
	cout << min(dp[n][m][1], dp[n][m][0]) << '\n';
}


signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

F - 快快乐乐剪羊毛（扫描线？）

枚举每个羊对不同偏移量的价值影响

先把整个草皮挪到所有羊的右边，此时价值为1

然后慢慢把草皮往左移，什么时候一只羊的价值会发生变化呢？当一只羊从一块草皮挪到另一块草皮的时候会发生变化，此时偏移量记作 x - w[j - 1] ，价值的变化量是两块草皮的价值之差

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> w(n + 1), v(n + 2);
	for (int i = 1; i <= n; i ++ )
	{
		cin >> w[i];
		w[i] = w[i - 1] + w[i];
	}
	for (int i = 1; i <= n; i ++ ) cin >> v[i];
	map<int, vector<int>> mp;
	for (int i = 1; i <= m; i ++ )
	{
		int x; cin >> x;
		for (int j = 1; j <= n + 1; j ++ )
		{
			mp[x - w[j - 1]].push_back(v[j] - v[j - 1]);
		}
	}
	set<int> st;
	int res = 0;
	st.insert(res);
	for (auto t : mp)
	{
		for (auto tt : t.second)
		{
			res += tt;
		}
		st.insert(res);
	}
	cout << st.size() << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

原文地址:https://blog.csdn.net/dhxbshbdjzxy/article/details/138300912 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1784829985891160064.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部