【CodeForces】Round 1017 (Div. 4)记录

题目链接：Codeforces Round 1017 (Div. 4)

A. Trippi Troppi

输入示例：

7
united states america
oh my god
i cant lie
binary indexed tree
believe in yourself
skibidi slay sigma
god bless america

输出示例：

usa
omg
icl
bit
biy
sss
gba

参考代码：

#include <bits/stdc++.h>
using namespace std;

int n;
string ans[10000];

void PrientAns()
{
	for (int i = 0; i < n; i++)
	{
		cout << ans[i] << endl;
	}
}

int main()
{
	cin >> n;
	int count = 0,index = 0;
	string tempAns;

	for (int i = 0; i < n * 3; i++)
	{
		string tempStr;
		cin >> tempStr;

		if (count < 2)
		{
			tempAns += tempStr[0];
			count++;
		}
		else if (count == 2)
		{
			tempAns += tempStr[0];
			ans[index] = tempAns;
			tempAns.clear();
			index++;
			count = 0;
		}
	}

	PrientAns();
	return 0;
}

B. Bobritto Bandito

输入示例：

4
4 2 -2 2
4 1 0 4
3 3 -1 2
9 8 -6 3

输出示例：

-1 1
0 1
-1 2
-5 3

题目解析：把题目结构一下就行了，输入的是m、n、l、r，分别对应总天数、目标天数、总天数下的左区间和总天数下的右区间。其实根本不需要这么多参数，两个就行了，一个是n目标天数，一个是l，因为一定包含0而l和r的间隔一定等于m，所以知道l就能知道l和r，然后再选一个间隔为n且在l和r区间内的数作为答案即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;

int n;
int days[2000], offsetDay[2000];
//string ansLeft[2000], ansRight[2000];

void PrientAns()
{
	for (int i = 0; i < n; i++)
	{
		int left = 0, right = 0;

		if (offsetDay[i] == 0)
		{
			//没有偏移
			left = 0; 
			right = days[i];
		}
		else if (-offsetDay[i] >= days[i])
		{
			//偏移量大于目标天数，可以所有感染向左
			left = -days[i]; 
			right = 0;
		}
		else
		{
			//偏移量小于目标天数，感染需要向右分布部分
			left = offsetDay[i];
			right = days[i] + offsetDay[i];
		}

		cout << left << " " << right << endl;
	}
}

int main()
{
	cin >> n;
	int count = 0, index = 0;
	int tempNum;

	for (int i = 0; i < n * 4; i++)
	{
		cin >> tempNum;

		if (count == 0)
		{
			count++;
		}
		else if (count == 1)
		{
			days[index] = tempNum;
			count++;
		}
		else if (count == 2)
		{
			offsetDay[index] = tempNum;
			count++;
		}
		else
		{
			count = 0;
			index++;
		}
	}

	PrientAns();
	return 0;
}

C. Brr Brrr Patapim

输入示例：

3
3
1 6 2
6 2 4
2 4 3
1
1
2
2 3
3 4

输出示例：

5 1 6 2 4 3 
2 1 
1 2 3 4 

参考代码：

#include <bits/stdc++.h>
using namespace std;

int t, n, g[1601][1601], j, i, x[1601], h[1601], p;

int main()
{
	cin >> t;
	while (t > 0)
	{
		t--;
		cin >> n;
		for (int i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
			{
				cin >> g[i][j];
				x[i + j] = g[i][j];
				h[g[i][j]]++;
			}
		for (p = 1; p <= 2 * n; p++)
		{
			if (h[p] == 0)
				x[1] = p;
			h[p] = 0;
		}
		for (p = 1; p <= 2 * n; p++)
		{
			cout << x[p] << " ";
		}
		cout << endl;
	}
}

D. Tung Tung Sahur

输入示例：

5
R
RR
LRLR
LRLR
LR
LLLR
LLLLLRL
LLLLRRLL
LLRLRLRRL
LLLRLRRLLRRRL

输出示例：

YES
YES
NO
NO
YES

题目解析：如果按照递归模拟的思路去做时间复杂度应该过不了，就不考虑这个办法了。这里参考了用另一种思路，先定义输入的字符串为s1和s2，s1，我们以示例中的第四个输入为例子，LLLLLRL为s1，以LLLLRRLL为s2，需要将s1和s2按照L和R分割，将s1分割成LLLLL、R、L，分别为x、y、z，将s2分割成LLLL、RR、LL，这三段分别为，a、b、c。如果a和x的关系为a >= x && a <= x * 2则对b和y判断，全部通过则为yes，否则为no。

参考代码：

#include <bits/stdc++.h>
using namespace std;

int t, n;
string s1, s2;

int main()
{
	cin >> t;
	while (t--)
	{
		cin >> s1;
		cin >> s2;

		while (s1.size())
		{
			int pos = 0;
			while (pos < s1.size() && s1[pos] == s1[pos + 1])
			{
				pos++;
			}
			int num = pos + 1;
			char c = s1[pos];
			int k = 0;
			while (k < s2.size() && s2[k] == c)
			{
				k++;
			}
			if (k >= num && k <= 2 * num)
			{
				s2.erase(0, k);
			}
			else
				break;
			s1.erase(0, num);
		}
		if (!s1.size() && !s2.size())
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
}