AtCoder Regular Contest 112 C Calculator

zltzlt / 2023-05-03 / 原文

洛谷传送门

AtCoder 传送门

很神奇但是经典的构造，学习一下。

注意到题目给的操作很像斐波那契。但是难点是如何将 \(O(\log n)\) 个斐波那契数相加。

考虑一个操作序列 \(4,3,4,3,...\)（共 \(m\) 个）。发现在第 \(i\) 个操作之前给 \(x\) 或 \(y\) 加 \(1\)，等价于最后结果加上 \(fib_{m-i}\)，是 \(x\) 还是 \(y\) 取决于剩下操作序列的数的奇偶性。

做完了？

code

// Problem: C - Calculator
// Contest: AtCoder - Tokio Marine & Nichido Fire Insurance Programming Contest 2021（AtCoder Regular Contest 122)
// URL: https://atcoder.jp/contests/arc122/tasks/arc122_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200;

ll n, m, f[maxn];
bool vis[maxn];

void solve() {
	scanf("%lld", &n);
	f[0] = f[1] = 1;
	for (m = 2;; ++m) {
		f[m] = f[m - 1] + f[m - 2];
		if (f[m] > n) {
			--m;
			break;
		}
	}
	int k = m + 1;
	for (int i = m; ~i; --i) {
		if (n >= f[i]) {
			n -= f[i];
			vis[i] = 1;
			++k;
		}
	}
	printf("%d\n", k);
	for (int i = 0; i <= m; ++i) {
		if (vis[m - i]) {
			puts(((i ^ m) & 1) ? "2" : "1");
		}
		puts((i & 1) ? "3" : "4");
	}
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}