Codeforces Round #612(Div. 2) 문제 해결 보고서

문서 목록
4

[제목 링크] 4

【A.Angry Students】

【B.Hyperset】

【C.Garland】

[제목 링크]
【A.Angry Students】
[제목 대의] A와 P로 구성된 문자열이 있는데 1초에 A는 오른쪽에 있는 P를 A로 바꿀 수 있다. 마지막 P가 A가 될 때가 얼마냐고 묻는다.
[문제풀이 발상] 두 개의 A가 동시에 진행되는 것을 고려하면 두 개의 A 가운데 P의 최대 개수가 바로 답이다.
[AC 코드]

#include 
using namespace std;
#define endl '
'
inline void FistIO() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
int main() {
	FistIO();
	int t;
	cin >> t;
	while (t--) {
		int n;
		string s;
		cin >> n >> s;
		int index = 0, Max = 0;
		while (index < n) {
			while (index < n && s[index] != 'A') ++index;
			if (index >= n) break;
			++index;
			int cnt = 0;
			while (index < n && s[index] == 'P') ++index, ++cnt;
			Max = max(Max, cnt);
		}
		cout << Max << endl;
	}
	return 0;
}

【B.Hyperset】
[제목 대의] S, E, T로 구성된 여러 개의 문자열이 있는데 세 개의 다음과 같은 요구를 충족시키는 문자열은 하나의 집합으로 계산한다.
이 세 문자열의 문자는 한 글자마다 모두 같거나 모두 다르다
[문제풀이 사고방식] O(n3)의 폭력 일치법을 생각하기 쉽지만 시간이 초과될 것이 분명하다. 그러면 O(n2logn)의 방법을 고려하면 우리는 두 문자열에 따라 세 번째 문자열을 구성한 다음에 몇 개의 동일한 문자열이 있는지 보면 된다. 문자열은 맵으로 찾을 수 있다.
[AC 코드]

#include 
using namespace std;
#define endl '
'
inline void FistIO() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
string s[1510];
int main() {
	FistIO();
	register int n, l;
	cin >> n >> l;
	map<string, int> mp;
	map<int, char> check;
	check[0] = 'S';
	check[1] = 'E';
	check[2] = 'T';
	check['S'] = 0;
	check['E'] = 1;
	check['T'] = 2;
	if (n < 3) {
		cout << "0" << endl;
		return 0;
	}
	for (register int i = 1; i <= n; ++i) {
		cin >> s[i];
		++mp[s[i]];
	}
	int ans = 0;
	for (register int i = 1; i < n; ++i) {
		for (register int j = i + 1; j <= n; ++j) {
			string p;
			for (register int k = 0; k < l; ++k) {
				if (s[i][k] == s[j][k]) p += s[i][k];
				else p += check[3 - check[s[i][k]] - check[s[j][k]]];
			}
			ans += mp[p];
		}
	}
	cout << ans / 3 << endl;
	return 0;
}

【C.Garland】
[제목 대의] n개수의 배열을 몇 개의 숫자를 파내면, 파낸 숫자를 다시 채워서 복잡도를 최소화해야 한다.
복잡도 는 인접 짝수 의 다른 개수 로 정의된다
[문제풀이 사고방식]https://blog.csdn.net/qq_43402296/article/details/104046202
[AC 코드]

#include 
using namespace std;
#define N 101
#define endl '
'
const int INF = 0x3f3f3f3f;
inline void FistIO() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
int a[N], b[N];
int dp[N][N][N][2];
int main() {
	int n;
	cin >> n;
	int even = n - n / 2, odd = n / 2;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (a[i]) {
			if (a[i] & 1) --even;
			else --odd;
			b[i] = b[i - 1];
		}
		else b[i] = b[i - 1] + 1;
	}
	memset(dp, INF, sizeof(dp));
	dp[0][0][0][0] = dp[0][0][0][1] = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= even; ++j) {
			for (int k = 0; k <= odd; ++k) {
				if (j + k > b[i]) break;
				if (a[i]) {
					if (a[i] & 1) dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
					else dp[i][j][k][0] = min(dp[i - 1][j][k][1] + 1, dp[i - 1][j][k][0]);
				}
				else {
					if (!j && !k) {
						dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1);
						dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
					}
					else if (!j) {
						dp[i][j][k][0] = min(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][1] + 1);
						dp[i][j][k][1] = min(dp[i - 1][j][k][0] + 1, dp[i - 1][j][k][1]);
					}
					else if (!k) {
						dp[i][j][k][0] = min(dp[i - 1][j][k][0], dp[i - 1][j][k][1] + 1);
						dp[i][j][k][1] = min(dp[i - 1][j - 1][k][0] + 1, dp[i - 1][j - 1][k][1]);
					}
					else {
						dp[i][j][k][0] = min(dp[i - 1][j][k - 1][0], dp[i - 1][j][k - 1][1] + 1);
						dp[i][j][k][1] = min(dp[i - 1][j - 1][k][0] + 1, dp[i - 1][j - 1][k][1]);
					}
				}
			}
		}
	}
	cout << min(dp[n][even][odd][0], dp[n][even][odd][1]) <<endl;
	return 0;
}