round126-div2

codeforces › div2
,

A

秒切，注意使用long long。

B

题目链接
本题在比赛时候卡了好久…想的有些复杂了…最后算出来的时间复杂度比给出的答案小一些，但给出的答案写的真的很简单。
该题的关键找到操作的基本特征：一个较为小的操作肯定不会有任何一个加法操作在乘法操作之后。可以通过移位来去理解这个特点。
后面，我想到了一组有意义的加法操作（能够更接近正确答案的）应该是加上当前数的最低1的数值，下面给出我的解答：

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
#include <bits/stdc++.h>
using namespace std;
const int mod = 32768;
const int N = 32769;
int n;
int lowbit(int x) {
	return x & -x;
}
int level[N];
int f[N];

int main() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	#endif
	scanf("%d", &n);
	memset(f, -1, sizeof f);
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < 16; ++j) {
			if((1 << j) & i) {
				level[i] = j + 1;
				break;
			}
		}
	}
	f[0] = 0;
	while(n--) {
		int a;
		scanf("%d", &a);
		int t = a;
		if(f[a] != -1) {
			printf("%d ", f[a]);
			continue;
		}
		int res = 17;
		for(int k = 0; k <= 16; a += lowbit(a)) {
			res = min(res, k + 16 - level[lowbit(a)]);
			k += lowbit(a);
		}
		f[t] = res;
		printf("%d ", res);
	}
	return 0;
}

首先，我没有想到在加上一次lowbit(x)之后还需要继续去判断是否还要再加lowbit(x+lowbit(x))，因此当时一直WA。
其次，在后面做的时候我忽略了x=0的情况，导致一直TLE。
虽然这个时间复杂度会较低一些，但实际上直接进行遍历也不会有很大问题，只是常数稍大一些：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }.toIntArray()

    for (v in a) {
        var ans = 20
        for (cntAdd in 0..15) {
            for (cntMul in 0..15) {
                if (((v + cntAdd) shl cntMul) % 32768 == 0)
                    ans = minOf(ans, cntAdd + cntMul)
            }
        }
        print("$ans ")
    }
}

给大佬跪了…大佬的代码永远是这么优雅。

C

原题链接
首先需要判断的问题是：是否树最终需要生长到最初所有树的最大高度？答案是否定的，例如$[1,1,1,1,1,2]$，就是一个反例，因此应该查找的是$\max$和$\max+1$两种情况的最小值。
找到一个最小时间就可以使用二分的方法来查找。
给出我的代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N = 300001;
int a[N], n, t;
typedef long long LL;
int main() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	#endif
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n); 
		for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
		LL mx = *max_element(a+1, a+1+n);
		LL res = 1e18+1;
		for(LL m = mx; m <= mx + 1; ++m) {
			LL l = 0, r = 1e18;
			while(l < r) {
				LL mid = (l + r) >> 1;
				// cnt1 -> even, cnt2 -> odd
				LL cnt1 = (mid) / 2, cnt2 = (mid + 1) / 2;
				bool flag = true;
				for(int i = 1; i <= n; ++i) {
					LL tt = (LL)m - (LL)a[i];
					if(tt / 2 <= cnt1) {
						cnt1 -= tt / 2;
						tt = tt % 2;	
					} else {
						tt -= cnt1 * 2;
						cnt1 = 0;
					}
					if(tt > cnt2) {
						flag = false;
						break;
					} else {
						cnt2 -= tt;
					}
				}
				if(flag) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			res = min(res, l);
		}
		printf("%lld ", res);
	}
	return 0;
}

D

我只能想到$O(nk)$的解。下面给出官方网站上的题解。

Let’s solve the problem greedily. But not from the beginning, because if we solve it from the beginning, we can’t be sure what option is more optimal for the next elements (e.g. for the second element it is not clear if we need to add $2$ to it starting our segment from the first position or add $1$ to it starting our segment from the second position). So, let’s solve the problem from right to left, then anything becomes clearer.

Actually, let’s operate with the array $b$ and decrease its elements instead of using some other array. Let’s carry some variables: $sum$, $cnt$ and the array $closed$ of length $n$ (along with the answer). The variable $sum$ means the value we need to subtract from the current element from currently existing progressions, $cnt$ is the number of currently existing progressions, and $closed_i$ means the number of progressions that will end at the position $i+1$ (i.e. will not add anything from the position $i$ and further to the left).

When we consider the element $i$, firstly let’s fix $sum$ (decrease it by $cnt$). Then, let’s fix $cnt$ (decrease it by $closed_i$). Then, let’s decrease $b_i$ by $sum$, and if it becomes less than or equal to zero, just proceed. Otherwise, the number by which we can decrease the $i$-th element with one progression, equals to $el=\min(k,i+1)$ (zero-indexed). Then the number of progressions we need to satisfy this element is $need=⌈b_i/el⌉$. Let’s add this number to the answer, increase $sum$ by $el⋅need$, increase $cnt$ by $need$, and if $i−el≥0$ then we need to end these progressions somewhere, so let’s add $need$ to $closed_{i−el}$.

第一段比较好懂，按下不表。
需要设置三个变量：$sum$，$cnt$，和数组$closed$。我们把一次等差数列的相加称为”一次转化“。
$sum$表示的是在当前已经增加的转化操作中，当前元素需要减去的值。
$cnt$表示的是循环到该变量，计算出的需要转换的次数。那么对于前一个变量来说，考虑新加入的转化之前，需要考虑前面所有转化导致他变化的值，也就是$sum-cnt$（因为是等差数列）。
$closed_i$表示的是在$i+1$时仍然作用的转化，并在$i$处无法作用的转化数量。这个是用于更新当前的$cnt$值，也正是由于该数组，可以让原本的$O(nk)$降至$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
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

    int n, k;
    scanf("%d %d", &n, &k);
    vector<long long> b(n);
    for (auto &it : b) {
        scanf("%lld", &it);
    }
    
    vector<long long> closed(n);
    long long sum = 0, cnt = 0, ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        sum -= cnt;
        cnt -= closed[i];
        b[i] -= sum;
        if (b[i] <= 0) {
            continue;
        }
        int el = min(i + 1, k);
        long long need = (b[i] + el - 1) / el;
        sum += need * el;
        cnt += need;
        ans += need;
        if (i - el >= 0) {
            closed[i - el] += need;
        }
    }
    printf("%lld\n", ans);
    return 0;
}