CF717B

link

算法1

dp!

时间复杂度$O(n^2)$,空间复杂度$O(n)$

算法二

贪心!

显然这题就是求一棵二叉树,每个点到左儿子距离为$c_0$,右儿子为$c_1$,使每个叶子到根节点的距离和最小。

扩展$n-1$次,每次用优先队列找到到根距离最小的叶子扩展到两边。

时间复杂度$O(n\log n)$,空间复杂度$O(n)$。

算法三

类似于NOIp2016蚯蚓用3个队列优化一发。

时间复杂度$O(n)$,空间复杂度$O(n)$。

算法四

原题出题人的算法。

用map一次扩展多个距离相同的点。

能AC但是是假算法出题人没卡。

时间复杂度$O(n)$,空间复杂度$O(n)$。

算法五

我们二分最后一次扩展的点离原点的距离w。

check的时候,考虑所有$<w$的$c_0x+c_1y$,他会被得到$\binom{x+y}{y}$次, 那就会扩展$\binom{x+y}{y}$次。

设$c_0\le c_1$,那么显然$w\le 26c_1$。当$w\ge 26c_1$时,所有深度$\le 26$的点都会被扩展,一共$2^{27}-1>10^8$。

然后就可以枚举$\min\{x,y\}\le 26$

最后计算答案的时候,考虑一次扩展对答案的贡献:$d+c_0+c_1$,其中d是这个点到原点的距离。

首先计算$<w$的$c_0x+c_1y$的贡献(以及扩展次数),剩下次数全都是$w$。

非常优秀。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: B.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const signed inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1.0);
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
template<class T>ll dcmp(T a,T b){return a>b;}
template<ll *a>ll cmp_a(ll x,ll y){return a[x]<a[y];}
#define min mmin
#define max mmax
#define abs aabs
namespace io {
const ll SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; ll f, qr;
// getchar
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
// prll the remaining part
inline void flush () {
fwrite (obuf, 1, oS - obuf, stdout);
oS = obuf;
}
// putchar
inline void putc (char x) {
*oS ++ = x;
if (oS == oT) flush ();
}
// input a signed lleger
inline void read (signed &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}

inline void read (long long &x) {
for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
}
inline void read (char &x) {
x=gc();
}
inline void read(char *x){
while((*x=gc())=='\n' || *x==' '||*x=='\r');
while(!(*x=='\n'||*x==' '||*x=='\r'))*(++x)=gc();
}
template<typename A,typename ...B>
inline void read(A &x,B &...y){
read(x);read(y...);
}
// prll a signed lleger
inline void write (signed x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}

inline void write (long long x) {
if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
while (x) qu[++ qr] = x % 10 + '0', x /= 10;
while (qr) putc (qu[qr --]);
}
inline void write (char x) {
putc(x);
}
inline void write(const char *x){
while(*x){putc(*x);++x;}
}
inline void write(char *x){
while(*x){putc(*x);++x;}
}
template<typename A,typename ...B>
inline void write(A x,B ...y){
write(x);write(y...);
}
//no need to call flush at the end manually!
struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: read;
using io :: putc;
using io :: write;
ll c0,c1,n;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lls[31];
ll C(ll a,ll b){
ll s=1,x,g;
for(ll i=1;i<=b;++i)lls[i]=i;
for(ll i=0;i<b;++i){
x=a+b-i;
for(ll j=1;j<=b;++j){
g=gcd(lls[j],x);
x/=g;
lls[j]/=g;
}
if(x>inf/s)return inf;
s*=x;
}
return s;
}
#define chk if(tmp>n)return 1
ll check(ll x){
ll tmp=x/c0+x/c1+1;
chk;
for(ll i=1;i<=26;++i){
for(ll j=i;j*c0+i*c1<=x;++j){
tmp+=C(j,i);
chk;
}
for(ll j=i+1;j*c1+i*c0<=x;++j){
tmp+=C(j,i);
chk;
}
}
return 0;
}
void Work(ll x,ll &tmp,ll &ans){
tmp=x/c0+x/c1+1;
ans=((x/c0)*(x/c0+1)*c0+(x/c1)*(x/c1+1)*c1)>>1;
ll c;
for(ll i=1;i<=26;++i){
for(ll j=i;j*c0+i*c1<=x;++j){
c=C(j,i);
tmp+=c;
ans+=c*(j*c0+i*c1);
}
for(ll j=i+1;j*c1+i*c0<=x;++j){
c=C(j,i);
tmp+=c;
ans+=c*(j*c1+i*c0);
}
}
}

int main(){
#ifdef cnyali_lk
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
#endif
read(n,c0,c1);
--n;
if(c0>c1)swap(c0,c1);
if(!c0)printf("%lld\n",n*c1);
ll l=0,r=c1*26,mid;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
ll c,s;
Work(l-1,c,s);
s+=(n-c)*l+n*(c0+c1);
printf("%lld\n",s);
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×