题意分析
观察棋子的跳法，不难想到斐波那契数列（本文中“斐波那契数列”均将下标视为无限延伸）。
设斐波那契数列第 $i$ 项为 $f_i$，满足 $f_i=f_{i-1}+f_{i-2}$。
因此可以想到每一个位置都对应斐波那契数列中的某一项。设位置 $i$ 的棋子数量为 $\textit{cnt}_i$。
则两种跳法对应：
-
向左跳：
\[\textit{cnt}_{p-2}\leftarrow\textit{cnt}_{p-2}+1\\ \textit{cnt}_{p-1}\leftarrow\textit{cnt}_{p-1}+1\\ \textit{cnt}_p\leftarrow\textit{cnt}_p-1\\\]可以发现，这即将 $f_p$ 转化为 $f_{p-1},f_{p-2}$。
-
向右跳：同理，将 $f_{p-1},f_{p-2}$ 转化为 $f_p$。
那么，题目即要求我们构造一组互不相邻的斐波那契数。
容易发现，这些斐波那契数的总和不变，因此可以算出来记作 $g$。
想要构造互不相邻的斐波那契数，可以考虑贪心。从大到小枚举斐波那契数 $f_k$，若 $g\geq f_k$ 就分配一个 $k$，同时令 $g\leftarrow g-f_k$。
这样贪心一定能构造一组解。考虑反证。
假设 $g\geq f_{k},g-f_k\geq f_{k-1}$。那么就有 $g\geq f_k+f_{k-1}=f_{k+1}$，那么就不会分配 $k-1,k$ 而是分配 $k+1$。
又因为 $f_i$ 有无穷多个，因此这样一定可以分配完 $g$。
当然，在实际代码中，下标非负。因此需要一个偏移量。
同时，这题需要一个高精度。
AC 代码
复制了一个完整的高精度模板，因此有些长。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
struct BigIntTiny {
int sign;
std::vector<int> v;
BigIntTiny() : sign(1) {}
BigIntTiny(const std::string &s) { *this = s; }
BigIntTiny(int v) {
char buf[21];
sprintf(buf, "%d", v);
*this = buf;
}
void zip(int unzip) {
if (unzip == 0) {
for (int i = 0; i < (int)v.size(); i++)
v[i] = get_pos(i * 4) + get_pos(i * 4 + 1) * 10 + get_pos(i * 4 + 2) * 100 + get_pos(i * 4 + 3) * 1000;
} else
for (int i = (v.resize(v.size() * 4), (int)v.size() - 1), a; i >= 0; i--)
a = (i % 4 >= 2) ? v[i / 4] / 100 : v[i / 4] % 100, v[i] = (i & 1) ? a / 10 : a % 10;
setsign(1, 1);
}
int get_pos(unsigned pos) const { return pos >= v.size() ? 0 : v[pos]; }
BigIntTiny &setsign(int newsign, int rev) {
for (int i = (int)v.size() - 1; i > 0 && v[i] == 0; i--)
v.erase(v.begin() + i);
sign = (v.size() == 0 || (v.size() == 1 && v[0] == 0)) ? 1 : (rev ? newsign * sign : newsign);
return *this;
}
std::string to_str() const {
BigIntTiny b = *this;
std::string s;
for (int i = (b.zip(1), 0); i < (int)b.v.size(); ++i)
s += char(*(b.v.rbegin() + i) + '0');
return (sign < 0 ? "-" : "") + (s.empty() ? std::string("0") : s);
}
bool absless(const BigIntTiny &b) const {
if (v.size() != b.v.size()) return v.size() < b.v.size();
for (int i = (int)v.size() - 1; i >= 0; i--)
if (v[i] != b.v[i]) return v[i] < b.v[i];
return false;
}
BigIntTiny operator-() const {
BigIntTiny c = *this;
c.sign = (v.size() > 1 || v[0]) ? -c.sign : 1;
return c;
}
BigIntTiny &operator=(const std::string &s) {
if (s[0] == '-')
*this = s.substr(1);
else {
for (int i = (v.clear(), 0); i < (int)s.size(); ++i)
v.push_back(*(s.rbegin() + i) - '0');
zip(0);
}
return setsign(s[0] == '-' ? -1 : 1, sign = 1);
}
bool operator<(const BigIntTiny &b) const {
return sign != b.sign ? sign < b.sign : (sign == 1 ? absless(b) : b.absless(*this));
}
bool operator==(const BigIntTiny &b) const { return v == b.v && sign == b.sign; }
BigIntTiny &operator+=(const BigIntTiny &b) {
if (sign != b.sign) return *this = (*this) - -b;
v.resize(std::max(v.size(), b.v.size()) + 1);
for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) {
carry += v[i] + b.get_pos(i);
v[i] = carry % 10000, carry /= 10000;
}
return setsign(sign, 0);
}
BigIntTiny operator+(const BigIntTiny &b) const {
BigIntTiny c = *this;
return c += b;
}
void add_mul(const BigIntTiny &b, int mul) {
v.resize(std::max(v.size(), b.v.size()) + 2);
for (int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) {
carry += v[i] + b.get_pos(i) * mul;
v[i] = carry % 10000, carry /= 10000;
}
}
BigIntTiny operator-(const BigIntTiny &b) const {
if (b.v.empty() || b.v.size() == 1 && b.v[0] == 0) return *this;
if (sign != b.sign) return (*this) + -b;
if (absless(b)) return -(b - *this);
BigIntTiny c;
for (int i = 0, borrow = 0; i < (int)v.size(); i++) {
borrow += v[i] - b.get_pos(i);
c.v.push_back(borrow);
c.v.back() -= 10000 * (borrow >>= 31);
}
return c.setsign(sign, 0);
}
BigIntTiny operator*(const BigIntTiny &b) const {
if (b < *this) return b * *this;
BigIntTiny c, d = b;
for (int i = 0; i < (int)v.size(); i++, d.v.insert(d.v.begin(), 0))
c.add_mul(d, v[i]);
return c.setsign(sign * b.sign, 0);
}
BigIntTiny operator/(const BigIntTiny &b) const {
BigIntTiny c, d;
BigIntTiny e=b;
e.sign=1;
d.v.resize(v.size());
double db = 1.0 / (b.v.back() + (b.get_pos((unsigned)b.v.size() - 2) / 1e4) +
(b.get_pos((unsigned)b.v.size() - 3) + 1) / 1e8);
for (int i = (int)v.size() - 1; i >= 0; i--) {
c.v.insert(c.v.begin(), v[i]);
int m = (int)((c.get_pos((int)e.v.size()) * 10000 + c.get_pos((int)e.v.size() - 1)) * db);
c = c - e * m, c.setsign(c.sign, 0), d.v[i] += m;
while (!(c < e))
c = c - e, d.v[i] += 1;
}
return d.setsign(sign * b.sign, 0);
}
BigIntTiny operator%(const BigIntTiny &b) const { return *this - *this / b * b; }
bool operator>(const BigIntTiny &b) const { return b < *this; }
bool operator<=(const BigIntTiny &b) const { return !(b < *this); }
bool operator>=(const BigIntTiny &b) const { return !(*this < b); }
bool operator!=(const BigIntTiny &b) const { return !(*this == b); }
};
typedef long long ll;
constexpr const int N=10000,D=1000;
int n;
int a[N+1];
ll cnt[N+D+D+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=D;
int pl;
cin>>pl;
cnt[a[i]]+=pl;
}
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
BigIntTiny f1=1,f2=1,g=0;
for(int i=0;i<=a[n];i++){
if(cnt[i]){
g+=f2*cnt[i];
}
BigIntTiny tmp=f2;
f2+=f1;
f1=tmp;
}
int p=a[n];
while(f2<g){
BigIntTiny tmp=f2;
f2+=f1;
f1=tmp;
p++;
}
vector<int>ans;
for(;p>0;p--){
if(g>=f2){
g=g-f2;
ans.push_back(p);
}
BigIntTiny tmp=f1;
f1=f2-f1;
f2=tmp;
}
sort(ans.begin(),ans.end());
for(int i:ans){
cout<<i-D+1<<' ';
}
cout<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
