【YZOJ】0821-T2(乘积最大)题解

手推几个 nn :

1
2
3
4
5
6
7
8
9
10
n=1: 1
n=2: 2
n=3: 3
n=4: 4
n=5: 2*3=6
n=6: 2*4=8
n=7: 3*4=12
n=8: 3*5=15
n=9: 2*3*4=24
n=10: 2*3*5=30

可以发现几乎就是连续自然数。

得出规律:将一个数拆成 2+...+x2+...+x 如果 arrm1>=arrmarr_{m-1} >= arr_m 则将 arrmarr_m 的值向前分配。

但是会发现最大的乘积巨大而且题目没有取模,于是需要高精度。

(比赛时候写挂了5555)

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
#include <iostream>
#include <fstream>
#include <vector>
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(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;
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)b.v.size()) * 10000 + c.get_pos((int)b.v.size() - 1)) * db);
c = c - b * m, d.v[i] += m;
while(!(c < b))
c = c - b, 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);
}
};
ifstream fin("max.in");
ofstream fout("max.out");
BigIntTiny res = 1;
int n, m, arr[10010];
int main() {
fin >> n;
if(n <= 4) {
fout << n << endl << n << endl;
//system("pause");
return 0;
}
for(int i = 2; n; i++)
if(n >= i) n -= i, arr[++m] = i;
else arr[++m] = n, n = 0;
if(arr[m - 1] >= arr[m]) {
for(int i = m - 1; i >= 1 && arr[m]; i--) arr[i]++, arr[m]--;
m--;
}
for(int i = 1; i <= m; i++) cout << arr[i] << ' ', res = res * arr[i];
fout << endl << res.to_str() << endl;
//system("pause");
return 0;
}