Codeforces Round #650(Div. 3) 문제 해결

Codeforces Round #650 (Div. 3)
A.Short Substrings
제목의 대의.
원래의 문자열을 s로 설정하면 현재 s에서 전환된 t를 주고 원래의 문자열 s를 출력할 수 있습니다. 그 중에서 t=s[0]s[1s[2]s[2]s[3]s[n-1]s[n-1]s[n-1]s[n]
문제풀이의 방향
쉽게 얻을 수 있는 s=t[i% 2==0] + t[t.length()-1]
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int l = s.length();
		for (int i = 0; i < l; ++i) {
			if (i % 2 == 0) cout << s[i];
		}
		cout << s[l - 1] << '
';
	}
	return 0;
}

B.Even Array
제목의 대의.
n 길이의 수조 a를 드리면 수조 중의 임의의 두 수를 교환할 수 있습니다. 최소한 몇 번을 교환하면 임의의 i가 a[i]%2==i%2가 될 수 있는지 물어보세요. 만족하지 못하면 출력-1
문제풀이의 방향
분명히 교환해야 할 것은 a[i]% 2!=i% 2의 수, 홀수와 짝수의 개수를 합산합니다. 만약 같으면 최소 홀수와 짝수의 개수를 합산합니다. 그렇지 않으면 출력-1
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 0; i < n; ++i) cin >> a[i];
		int x = 0, y = 0;
		for (int i = 0; i < n; ++i) {
			if (a[i] % 2 == i % 2) continue;
			else {
				if (a[i] % 2 == 0) ++x;
				else ++y;
			}
		}
		if (x == y) cout << x << '
';
		else cout << "-1
";
	}
	return 0;
}

C.Social Distance
제목의 대의.
0과 1로 구성된 문자열을 드리겠습니다. 두 개의 1 사이의 0은 k보다 작으면 안 됩니다. 0의 최대 개수는 1로 바꿀 수 있는지 물어보세요.
문제풀이의 방향
먼저, 가장 특수한 상황1을 고려하여 1이 없으면 첫 번째 문자를 1로 하고 나머지 n-1 문자는 k+1마다 1을 가질 수 있다. 그러면 답은 (n-1)/(k+1)+1이다. 그리고 일반적인 상황을 고려하여 두 개의 1 사이의 0의 수를 통계한 다음에 2*(k-1)를 뺀다. 이 두 개의 1과 인접한 2*(k-1)의 0은 1이 없기 때문에 답안에 기여하지 않는다. 그러면 나머지 0은 상황1이다.맨 앞의 0과 맨 뒤의 0을 고려하면 상황 1로 변환할 수 있다
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		++k;
		string s;
		cin >> s;
		vector<int> v;
		for (int i = 0; i < n; ++i) {
			if (s[i] - '0' == 1) v.push_back(i);
		}
		int len = v.size();
		int res = 0;
		for (int i = 1; i < len; ++i) {
			int tmp = v[i] - v[i - 1] - 2 * k + 1;
			if (tmp <= 0) continue;
			res += ((tmp - 1) / k) + 1;
		}
		if (!len) {
			res += ((n - 1) / k) + 1;
		}
		else if (len) {
			res += max(v[0] / k, 0) + max((n - v[len - 1] - 1) / k, 0);
		}
		cout << res << '
';
	}
	return 0;
}

D.Task On The Board
제목의 대의.
문자열 s를 드리겠습니다. s를 일부 문자를 삭제하고 다시 배열한 후에 문자열 t, 구조수 그룹 b, b[i]=sum(abs(i-j))를 얻을 수 있습니다. 그 중에서 i와 j는 t[j]>t[i]를 만족시키고 t의 길이 m와 t로 구성된 b수 그룹을 알려주세요. 임의의 t가 상기 조건을 충족시키도록 하세요.
문제풀이의 방향
먼저 생각하기 쉽다. b수조에서 0의 일정한 알파벳 서열이 가장 크다. 이런 아래에 j를 표시한 다음에 나머지 위치 i의 수를 abs(i-j)를 빼면 반드시 0을 얻을 수 있다. 그러면 이것은 바로 하위 문제의 해답이다. 마지막으로 알파벳 서열의 상대적인 크기에 따라 s에서 해당하는 알파벳을 찾으면 된다.
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	register int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int m;
		cin >> m;
		for (register int i = 0; i < m; ++i) {
			cin >> a[i];
		}
		int b[50] = { 0 }, c[50] = { 0 };
		for (int i = 0; i < s.length(); ++i) {
			++b[s[i] - 'a'];
		}
		bool vis[110] = { false };
		string t = s.substr(0, m);
		char cc = 'z';
		vector<int> v[30];
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < m; ++j) {
				if (vis[j]) continue;
				if (!a[j]) {
					vis[j] = true;
					v[cc - 'a'].push_back(j);
					++c[cc - 'a'];
				}
			}
			for (int j = 0; j < m; ++j) {
				if (vis[j]) continue;
				for (int k = 0; k < v[cc - 'a'].size(); ++k) {
					a[j] -= abs(j - v[cc - 'a'][k]);
				}
			}
			cc = cc - 1;
		}
		int cnt = 'z' - 'a' + 1;
		for (int i = 'z' - 'a'; i >= 0; --i) {
			if (!v[i].size()) continue;
			for (int j = cnt - 1; j >= 0; --j) {
				if (c[i] <= b[j]) {
					cnt = j;
					break;
				}
			}
			for (int j = 0; j < v[i].size(); ++j) {
				t[v[i][j]] = cnt + 'a';
			}
		}
		cout << t << '
';
	}
	return 0;
}

E.Necklace Assembly
제목의 대의.
문자열 s를 드리겠습니다. 가능한 한 많은 문자를 골라서 목걸이를 만들 수 있도록 합니다. 시계 바늘을 따라 k회 회전한 후 원래의 목걸이와 동일하게 하십시오.
문제풀이의 방향
목걸이에 순환절이 존재한다고 생각하기 쉬워요. 목걸이 길이가 L이고 순환절 길이가circlelen, 순환절 개수는circlenum의 경우: L% circlelen == 0 k % circle_len == 0 circle_num = L/circle_L이 고정된 상황에서 순환절의 길이가 클수록 순환절의 개수가 적을수록 더 많은 s에서 순환절의 개수보다 많은 문자가 목걸이에 나타날 수 있다. 상기 요구를 충족시키려면 max(circle len) = gcd(L,k)에 a[i]를 문자 i가 s에 나타난 횟수로 설정하면 문자 i는 이 목걸이의 한 순환절에 a[i]/circlenum회 만약sum(a[i]/circle num)*circlenum>=L이면 길이 L이 요구에 부합됨을 의미한다.L이 최대 s.length()이므로 가능한 L을 작은 크기에서 큰 크기로 반복하면 됩니다.
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
inline int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x % y);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		int a[50] = { 0 };
		for (int i = 0; i < n; ++i) {
			++a[s[i] - 'a'];
		}
		int res = 0;
		for (int i = 1; i <= n; ++i) {
			int circle_len = gcd(i, k);
			int circle_num = i / circle_len;
			int tmp_c = 0;
			for (int j = 0; j < 26; ++j) {
				tmp_c += a[j] / circle_num;
			}
			if (tmp_c * circle_num >= i) {
				res = max(res, i);
			}
		}
		cout << res << '
';
	}
	return 0;
}

F.Flying Sort (Easy Version)
제목의 대의.
수조 a를 드리겠습니다. 임의의 숫자를 수조의 시작이나 끝으로 이동할 수 있습니다. 최소한 몇 번을 이동하면 숫자의 비체감 수조에 같은 요소가 없고,lengthof(a)<=3000
문제풀이의 방향
먼저 a수 그룹을 상대적인 크기(예를 들어 4 7 2 3 8, 3 4 1 2 5)로 비추고 나서 우리는 어떤 숫자가 이동할 필요가 없는지 반대로 생각했다. 하위 서열에서 연속적으로 증가하는 최대 길이는 이동할 필요가 없는 최대 길이이고 나머지 요소는 모두 이동해야 한다는 것을 발견했다. 상기 예에서 345는 1 2를 맨 앞쪽으로 이동하면 된다. 그러면 가장 긴 연속적으로 증가하는 하위 서열인 Max를 찾을 수 있다. 답은 n - Max이다.
AC 코드

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn], b[maxn];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i) {
			cin >> a[i];
			b[i] = a[i];
		}
		sort(b + 1, b + n + 1);
		for (int i = 1; i <= n; ++i) {
			a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
		}
		int k = 1, Max = 0;
		while (k <= n) {
			int len = 0;
			for (int i = 1; i <= n; ++i) {
				if (a[i] == k) {
					++k, ++len;
				}
			}
			Max = max(Max, len);
		}
		cout << n - Max << '
';
	}
	return 0;
}