Educational codeforces round 132 A-D problem solution

Personal thinking , For record only , You can refer to , Welcome to exchange .

Address of the competition ： Portal

---

A. Three Doors

Portal

【 The question 】 There are three numbers 1,2,3 The door of , Behind at least two doors are hidden keys that can open a certain door , Please hold it at the beginning n Can you open all doors with the key of Door No .

【 Ideas 】 Directly simulate the process of opening the door , See code for details .

【 Code 】

void solve()
{
	int x, a[5];
	bool b[5] = { 0 };
	cin >> x;
	for (int i = 1; i <= 3; ++i)
	{
		cin >> a[i];
	}
	while(1)
	{
		if (b[x] == 0 && x)
		{
			b[x] = 1;
			x = a[x];
		}
		else
		{
			break;
		}
	}
	bool ans = 1;
	for (int i = 1; i <= 3; ++i)
	{
		if (b[i] == 0)
		{
			ans = 0;
		}
	}
	cout << (ans ? "YES\n" : "NO\n");
	return;
}

---

B. Also Try Minecraft

Portal

【 The question 】 Given each x The height of the ground at the coordinates , It is known that only x Strike x-1 or x+1 It's about , From high to low, the blood volume equal to the height difference will be deducted , And nothing will happen from low to high . inquiry q How much blood will be deducted from one point to another .

【 Ideas 】 In fact, the problem is to require the sum of the interval of blood deduction value . Therefore, as long as the prefix sum of cumulative blood deduction from left to right and the suffix sum of cumulative blood deduction from right to left are obtained first during preprocessing , You can get the answer quickly when you ask .

【 Code 】

using ll = long long;

int n, m;
ll a[200005], prelr[200005], prerl[200005];
int s, t;

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		prelr[i] = prelr[i - 1] + max(0ll, a[i - 1] - a[i]);
	}
	for (int i = n; i >= 1; --i)
	{
		prerl[i] = prerl[i + 1] + max(0ll, a[i + 1] - a[i]);
	}
	for (int i = 1; i <= m; ++i)
	{
		cin >> s >> t;
		if (s < t)
		{
			cout << prelr[t] - prelr[s] << '\n';
		}
		else
		{
			cout << prerl[t] - prerl[s] << '\n';
		}
	}
	return;
}

---

C. Recover an RBS

Portal

【 The question 】 Given an inclusion ”?” The bracket sequence of . Ask for general ”?” Is there and only one way to replace with parentheses and legitimize the sequence of parentheses .

【 Ideas 】 In the process of reading the parenthesis sequence, it can be determined continuously according to the rules of the legal parenthesis sequence ”?” Replace with parentheses , Finally, see if you are completely sure . See code for details .

【 Code 】

void solve()
{
	string s;
	cin >> s;
	if (s.size() % 2)
	{
		cout << "NO\n";
		return;
	}
	int lef = 0, rig = 0, que = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		if (s[i] == '(')
		{
			lef++;
		}
		else if (s[i] == ')')
		{
			rig++;
		}
		else if (s[i] == '?')
		{
			que++;
		}

		if (lef > s.size() / 2)
		{
			cout << "NO\n";
			return;
		}
		if (rig > que + lef)
		{
			cout << "NO\n";
			return;
		}
		if (rig > lef)
		{
			que--;
			lef++;
		}
		if (que == 1 && lef == rig)
		{
			que--;
			lef++;
		}
		if (lef == s.size() / 2)
		{
			rig += que;
			que = 0;
		}
	}
	cout << (que == 0 ? "YES\n" : "NO\n");
	return;
}

---

D. Rorororobot

Portal

【 The question 】 There is a square map and a robot . There are obstacles piled down in each column of the map . inquiry q Time 「 Every time the robot moves k Whether it can just reach the end without encountering obstacles 」.

【 Ideas 】 Obviously, the best mobile solution is to go up to the top, then left and right to the target column, and then down . Just judge whether you will encounter obstacles when you are left or right , You need to know the maximum value of the interval , use ST Table can meet the requirements of time complexity .

【 Code 】

int a[200005];
int n, m, q, k;
int x11, x22, y11, y22;
int st[200005][32];

void build_st()
{
	for (int i = 0; i <= log2(m); ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (i == 0)
			{
				st[j][i] = a[j];
			}
			else
			{
				st[j][i] = st[j][i - 1];
				if (j + (1 << (i - 1)) <= m)
				{
					st[j][i] = max(st[j][i], st[j + (1 << (i - 1))][i - 1]);
				}
			}
		}
	}
	return;
}

int query(int lef, int rig)
{
	int len = int(log2(rig - lef + 1));
	return max(st[lef][len], st[rig - (1 << len) + 1][len]);
}

void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		cin >> a[i];
	}
	build_st();
	cin >> q;
	for (int i = 1; i <= q; ++i)
	{
		cin >> y11 >> x11 >> y22 >> x22 >> k;
		if (abs(x22 - x11) % k || abs(y22 - y11) % k)
		{
			cout << "NO\n";
			continue;
		}
		y11 += (n - y11) / k * k;
		int maxh = query(min(x11, x22), max(x11, x22));
		if (maxh >= y11)
		{
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
	}
	return;
}

---

（ It's another low-level mistake that leads to a free hand , It's easy to get stuck in some strange places when you are nervous , Good breath .）