【赛题整理】[ARC100]C~E

整理 ARC100 的 C~E。F题由于太神仙被我拿出去单列了一篇。

写完才发现,这仨题也太水了吧?一点意思都没有啊?不管了,能水一篇是一篇。

C

给定一个长为 $n$ 的序列 $\{A\}$,找一个 $b$ 使得下式最小:

根据小学生结论,一条数轴上离每个点距离和最小的那个点就是这些点最中间那个点。证明的话用微扰法就可以发现这是个下凸函数。

nmd,一开始记成了平均数WA了两次,实际上应该是中位数啦。

1
2
3
4
5
6
7
8
9
10
11
int main(){
cin >> n ; int p ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), k[i] = base[i] - i ;
sort(k + 1, k + n + 1) ;
if (n & 1) p = k[n / 2 + 1] ;
else p = (k[n / 2] + k[n / 2 + 1]) / 2 ;
for (int i = 1 ; i <= n ; ++ i)
ans += 1ll * abs(base[i] - p - i) ;
cout << ans << endl ; return 0 ;
}

D

给定一个序列。要求把这个序列分成连续的四份,记这四份内数字和分别为 $a,b,c,d$ ,最小化 $a,b,c,d$ 的极差。

znm,长得一脸可三分的样子然而并不可三分,因为很容易知道在这种多峰函数三分本质上和爬山没啥区别。可能会有什么神必的退火或者遗传做法。但是个人感觉这个数据范围似乎不是很允许。

考虑暴力怎么做。尝试去枚举中间的第二段的右端点,这样再去枚举 $a,c,d$ ,复杂度是 $O(n^3)$ 的。

观察题目所给的性质。发现所有数都 $>0$。于是考虑枚举第二段的时候,对于一个与自己极差最小的第一段,由于第二段数一直在增多,所以第一段的右端点下标必然是不降的;对于第三、四段,这个性质同样成立。

于是可以想到枚举第二段,第一段和第三段都变成了 $O(1)$ 。最终复杂度 $O(n)$ 。

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
int n ;
ll ans ;
ll S[4] ;
ll minx ;
ll maxx ;
ll sum[N] ;
ll base[N] ;

ll gt(ll x){
return x < 0 ? -x : x ;
}
void chkmin(ll x){
minx = x >= minx ? minx : x ;
}
void chkmax(ll x){
maxx = x >= maxx ? x : maxx ;
}
int main(){
cin >> n ;
ans = (1ll << 62) ;
for (int i = 1 ; i <= n ; ++ i){
scanf("%lld", &base[i]) ;
sum[i] = sum[i - 1] + base[i] ;
}
int l = 2, r = 4 ;
S[0] = base[1] ; S[2] = base[3] ;
S[1] = base[2] ; S[3] = sum[n] - sum[3] ;
for (int i = 3 ; i <= n ; ++ i){
while (l < i && gt(S[0] - S[1]) > gt(S[0] + base[l] - S[1] + base[l])){
S[0] += base[l], S[1] -= base[l], ++ l ;
}
while (r <= n && gt(S[3] - S[2]) > gt(S[2] + base[r] - S[3] + base[r])){
S[2] += base[r], S[3] -= base[r], ++ r ;
}
minx = (1ll << 61) ; maxx = -(1ll << 61) ;
for (int j = 0 ; j <= 3 ; ++ j) chkmin(S[j]), chkmax(S[j]) ;
ans = min(ans, maxx - minx) ; S[1] += base[i] ; S[2] -= base[i] ;
//for (int j = 0 ; j <= 3 ; ++ j) cout << S[j] << " " ; puts("") ;
}
cout << ans << endl ; return 0 ;
}

E

给定一个长度为 $2^k-1$ 的序列 $\{a_n\}$。对于每个 $1\leq p\leq 2^k-1$ ,求

$k\leq 18$

发现似乎是在做一个FMT,但是直接转移最大值需要 $k ^2$ 甚至更高的代价。所以考虑对于每个集合 $s$ 记一下这个集合中的最最大数和次大数,不难发现这样转移是方便的。复杂度 $2^kk$ 。

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
ll ans ;
int m, n ;
pint f[N] ;
ll base[N] ;

bool comp(int x, int y){
return base[x] > base[y] ;
}
int main(){
cin >> m ; n = (1 << m) - 1 ;
for (int i = 0 ; i <= n ; ++ i){
cin >> base[i] ;
f[i] = make_pair(i, n + 1) ;
}
base[n + 1] = -1 ;
for (int i = 0 ; i <= n ; ++ i)
for (int j = 0 ; j < m ; ++ j)
if (!((1 << j) & i)){
int k = (1 << j) | i ;
int t[4] = {fr(i), sc(i), fr(k), sc(k)} ;
sort(t, t + 4, comp) ; unique(t, t + 4) ;
f[k] = make_pair(t[0], t[1]) ;
}
for (int i = 1 ; i <= n ; ++ i){
ans = max(ans, base[fr(i)] + base[sc(i)]) ;
cout << ans << endl ;
}
}