牛客周赛 Round 2 题解

A.小红的环形字符串

思路：将s字符串扩大两倍之后，在其之中寻找有几个字串等于t字符串。

void solve() {

	string s, t;
	cin >> s >> t;

	s = s + s;
	int c = t.size();
	int n = s.size();
	int cnt = 0;
	for (int i = 0; i < n / 2; ++i) {
		string sub = s.substr(i, c);
		if (sub == t) {
			cnt++;
		}
	}

	cout << cnt << '\n';

}

B.相邻不同数字的标记

思路：(状态机)dp。

d[i][j]表示考虑前j个数字时，下标为j-1的数字是否被选上（0为没有选第j-1个数字，1为选上了第j-1个数字），注意i=1时的特例即可。

时间复杂度O(n)

const int N = 100010;

int a[N], dp[2][N]; //dp[i][j]表示前j个数字里，选没选前一个数字
bool st[N];
int n, m, k;

void solve() {

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}

	string c;
	cin >> c;
	c = "*" + c;

	for (int i = 1; i <= n; ++i) {
		dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
		if (c[i] != c[i - 1] && i != 1) dp[1][i] = max(dp[0][i - 1] + a[i] + a[i - 1], dp[1][i - 1]);
	}

	cout << max(dp[0][n], dp[1][n]) << '\n';
}

C.小红的俄罗斯方块

思路：纯模拟，找到每次要放置这个方块的位置的最高点（相对来说），分情况讨论即可。

const int N = 200010;

int n, m, k;
int h[9];

void solve() {

	int type, b;
	cin >> type >> b;

	if (type == 0) {
		int hight = max(h[b], h[b + 1]);
		h[b] = hight + 3;
		h[b + 1] = hight + 1;
	} else if (type == 90) {
		int hight;
		if (h[b] > h[b + 1] && h[b] > h[b + 2]) {
			hight = h[b];
			h[b] = hight + 2;
			h[b + 1] = hight + 2;
			h[b + 2] = hight + 2;
		} else if (h[b + 1] > h[b] + 1 && h[b + 1] > h[b + 2]) {
			hight = h[b + 1];
			h[b] = hight + 1;
			h[b + 1] = hight + 1;
			h[b + 2] = hight + 1;
		} else if (h[b + 2] > h[b] + 1) {
			hight = h[b + 2];
			h[b] = hight + 1;
			h[b + 1] = hight + 1;
			h[b + 2] = hight + 1;
		} else {
			hight = h[b];
			h[b] = hight + 2;
			h[b + 1] = hight + 2;
			h[b + 2] = hight + 2;
		}
	} else if (type == 180) {
		int hight;
		if (h[b] > h[b + 1] + 1) {
			hight = h[b];
			h[b] = hight + 1;
			h[b + 1] = hight + 1;
		} else {
			hight = h[b + 1];
			h[b] = hight + 3;
			h[b + 1] = hight + 3;
		}
	} else {
		int hight = max(h[b], h[b + 1]);
		hight = max(hight, h[b + 2]);
		h[b] = hight + 1;
		h[b + 1] = hight + 1;
		h[b + 2] = hight + 2;
	}
}

signed main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _;
	cin >> _;
	while (_--) {
		solve();
	}

	for (int i = 1; i <= 8; ++i) {
		cout << h[i] << ' ';
	}

	return 0;
}

D.小红打怪

思路：贪心、二分。

用结构体存下小怪和小红打的回合数、计算出小红和每一个小怪打架消耗的生命值，按照耗损生命值从小到大排序之后计算前缀和，二分找到每一个药瓶数对应的可以打过的怪物最大数量即可。

时间复杂度O(qlogn)

const int N = 100010;

struct mons {
	int a, b, cnt, d;
} monster[N];
int n, h, k;

void solve() {

	cin >> n >> h >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> monster[i].a >> monster[i].b;
		int t = monster[i].a % 4;
		monster[i].cnt = monster[i].a / 4 * 3 + t - (t >= 2);
		monster[i].d = monster[i].b * (monster[i].cnt - 1);
	}

	sort(monster + 1, monster + 1 + n, [](mons a, mons b) {
		return a.d < b.d;
	});

	for (int i = 1; i <= n; ++i) {
		monster[i].d = monster[i - 1].d + monster[i].d;
	}

	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;

		int hh = h + k * x;

		int l = 0, r = n + 1;
		while (l + 1 != r) {
			int mid = l + r >> 1;
			if (monster[mid].d < hh) l = mid;
			else r = mid;
		}

		cout << l << ' ';
	}
}

signed main() {

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _ = 1;
	while (_--) {
		solve();
	}

	return 0;
}