很神奇但是经典的构造,学习一下。
注意到题目给的操作很像斐波那契。但是难点是如何将 \(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;
}
- Calculator AtCoder Regular Contest 112calculator atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest