Educational Codeforces Round 84(Rated for Div.2) 부분 문제 해결

카탈로그

Educational Codeforces Round 84 (Rated for Div. 2)

A. Sum of Odd Integers

B. Princesses and Princes

C. Game with Chips

D. Infinite Path

E. Count The Blocks

Educational Codeforces Round 84 (Rated for Div. 2)
A. Sum of Odd Integers
제목:\(n\) 를\(k\) 개의 다른 홀수의 합으로 표시할 수 있는지 묻습니다.
분석: 우선\(n\)과\(k\) 패리티가 일치해야 합니다.그 다음에\(n\) 가\(1+3+5+\cdots+(2k-1)=k^2\보다 작은지 확인하십시오.

#include 
#define SIZE 300010
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define eps 1e-3
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll t, n, k, a[SIZE];

int main() {
	io(); cin >> t;
	while (t--) {
		cin >> n >> k;
		if (n < k * k || (n - k) % 2) cout << "NO
";
		else cout << "YES
";
	}
}

B. Princesses and Princes
제목: 제목이 너무 길어서 안 쓸게요.
욕심을 부리면 된다.

#include 
#define SIZE 300010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
vector vec[SIZE];
vector vis;
int n, t;

int main() {
	io(); cin >> t;
	rep(ii, 1, t) {
		cin >> n;
		vis.clear(); vis.resize(n + 1);
		int tp = 0, to = 0;
		rep(i, 1, n) {
			bool f = true;
			int k; cin >> k;
			vec[i].resize(k);
			rep(j, 0, (k - 1)) cin >> vec[i][j];

			for (auto j : vec[i]) {
				if (!vis[j]) {
					vis[j] = true; f = false;
					++tp; break;
				}
			}
			if (f) to = i;
		}
		if (tp == n) cout << "OPTIMAL
";
		else {
			cout << "IMPROVE
";
			cout << to << ' ';
			rep(i, 1, n) {
				if (vis[i]) continue;
				cout << i << '
';
				break;
			}
		}
	}
}

C. Game with Chips
제목:\(n\times m\)의 격자맵에\(k\) 개의 바둑알이 있고 좌표는\((sx i,sy i)\) 이며 각 바둑알에는 대응하는 필수 점 좌표가 있습니다\((fx i,fy i)\).현재 당신은 최대\(2nm\)번의 이동 기회가 있습니다. 매번 이동할 때마다 바둑알을 전체적으로 상하 좌우 네 방향 중 하나로 단위를 이동할 수 있습니다. (바둑알이 경계에 도달하면 이동하지 않고 바둑알이 중첩될 수 있습니다) 모든 바둑알이 반드시 통과해야 할 지점에 도달할 수 있는 방안을 제시합니다.
분석: 모든 바둑알을 왼쪽 상단으로 직접 이동한 다음\(S\)형으로 바둑판을 훑어봅니다.

#include 
#define SIZE 210
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, m, k;
string s;
struct Point {
	int x, y;
}p[SIZE];
 
int main() {
	io(); cin >> n >> m >> k;
	rep(i, 1, (k + k)) cin >> p[i].x >> p[i].y >> p[i].x >> p[i].y;
	rep(i, 1, (n - 1)) s.push_back('U');
	rep(i, 1, (m - 1)) s.push_back('L');
	int f = 1;
	rep(i, 1, n) {
		rep(j, 1, (m - 1)) {
			if (f) s.push_back('R');
			else s.push_back('L');
		}
		s.push_back('D');
		f ^= 1;
	}
	cout << s.length() << '
' << s;
}

D. Infinite Path
제목:\(1,2,\cdots,n\)의 배열\(p i\)를 지정하고 위치\(i\)는\(c i\)로 염색합니다.무한 경로를 정의하는 것은 다음과 같다. 이런 무한 서열이 존재한다\(i,p[i],p[p[i]],...p^{(n)}[p[i]]\), 이 서열에 대응하는 모든 위치의 색깔이 같다.재정의\(k\) 단계 교체란 각 위치\(i\),\(k\) 차 교체를 한 후 얻은 서열(즉\(i\) 교체는\(p[i]\), 다시\(p[p[i]]]]\cdots\)로 교체하는 것을 말한다.적어도 몇 단계의 교체를 진행한 후, 적어도 무한한 경로가 존재한다고 묻는다.
분석: 우선\(p\)는 하나의 배열이기 때문에\(i,p[i])\)로 가장자리를 만들면 여러 개의 유방향 고리로 구성된 그림을 얻을 수 있기 때문에 본 문제의 관건은 하나의 큰 고리가 어떤 상황에서 작은 고리로 분리되는지 하는 것이다.이 중 하나의 링에\(m\)개의 점이 있다고 가정하고 링의 어느 시작점\(s\)에서 출발하여\(k\)차 교체를 진행한 후 그 링의 점 집합은\((s+ck)\%m(c\in Z)\(매번 교체는 어느 점\(i\)을\(p[i]\)로 이동한다)로 바뀐다.또한\(k\)가\(m\)의 인자가 아니라면 동일한 의미에서 고리는 분열되지 않는다는 것을 알아차린다.\(k\) 가\(m\) 인자이고\(pk=m\) 라면 링은\(k\) 개의\(p\) 점으로 구성된 작은 링으로 분열됩니다.따라서 우리는\(k\)의 모든 인자 고리에 대해 동색 여부를 판단하면 된다.
제목에 제시된\(k\leq 2e5\) 때문에 한 수의 최대 인자 수는\(160\)를 초과하지 않기 때문에\(O(160n)\) 이 과정을 시뮬레이션할 수 있습니다.

#include 
#define SIZE 300010
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define eps 1e-3
#define mp make_pair
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int t, n, ans;
int p[SIZE], c[SIZE];
 
int main() {
	io(); cin >> t;
	rep(ii, 1, t) {
		cin >> n; ans = n;
		rep(i, 0, (n - 1)) cin >> p[i], --p[i];
		rep(i, 0, (n - 1)) cin >> c[i];
		rep(i, 0, (n - 1)) {
			if (p[i] == -1) continue;
			vector vec;
			for (int j = i; p[j] != -1;) {
				vec.emplace_back(c[j]);
				int to = p[j];
				p[j] = -1;
				j = to;
			}
			rep(j, 1, vec.size()) {
				if (vec.size() % j) continue;
				rep(s, 0, (j - 1)) {
					bool f = true;
					for (int k = s; k < vec.size(); k += j) {
						if (vec[k] != vec[s]) {
							f = false;
							break;
						}
					}
					if (f) {
						ans = min(ans, j);
						break;
					}
				}
			}
		}
		cout << ans << '
';
	}
}

E. Count The Blocks
제목: 모든 숫자의 길이가 다른 연속 구간수를 통계합니다.예를 들어\(0111223\)에는\(2\) 세그먼트 길이가\(1\)인 구간,\(1\) 세그먼트 길이가\(2\)인 구간,\(1\) 세그먼트 길이가\(3\)인 구간이 있습니다.(숫자가 부족하면\(n\) 비트에서 리딩 제로를 추가해야 함)
분석: 법칙을 찾아라!\(a[1]=10,a[2]=180,a[3]=2610,a[i]=20a[i-1]-100a[i-2](i>3)\) .

#include 
#define SIZE 300010
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define int long long
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
const int P = 998244353;
int n, a[SIZE];

signed main() {
	io(); n = 300000ll;
	a[0] = 10ll; a[1] = 180ll; a[2] = 2610ll;
	rep(i, 3, n) a[i] = ((20ll * a[i - 1] - 100ll * a[i - 2]) % P + P) % P;
	cin >> n;
	for (int i = n; i; --i) cout << a[i - 1] % P << ' ';
}