日常补题8.5

Loop

题意

思路

这题通过分析我们可以得知选定的右端点的位置是不固定的，所以我们完全可以预先选出k个非最大值，之后按非递减序合并原先的数组和选出的$k$个值再输出即可，选出的$k$个值我们可以使用优先队列来进行维护注意$k$值是可能大于我们的原数组长度$n$的，以及题目的输出格式问题。

代码

void run() {
	cin >> n >> k;
	rep (i, 1, n) st[i] = 0;
	rep (i, 1, n) cin >> a[i];
	int mx = -1, cnt = 0;
	rep (i, 1, n) mx = max(mx, a[i]);
	rep (i, 1, n) if (a[i] == mx) cnt ++;

	k = min(k, n - cnt);
	priority_queue<int> heap;
	int idx = 1;
	while (k) {
		if (a[idx] != mx) {
			heap.push(a[idx]);
			st[idx] = 1;
			k --;
		}
		idx ++;
	}

	vector<int> res;
	rep (i, 1, n) 
		if (!st[i]) {
			while (heap.size() && heap.top() > a[i]) {
				res.pb(heap.top());
				heap.pop();
			}
			res.pb(a[i]);
		}
	while (heap.size()) {
		res.pb(heap.top());
		heap.pop();
	}
	n = SZ(res) - 1;
	rep (i, 0, n) cout << res[i] << " \n"[i == n];
}

Chip Move

题意

思路

我们可以按每次的步数来进行$DP$ ，$dp(i)$表示到$i$位置的方案数，这样本题就可以类比成一个完全背包求方案数的模式，但是需要注意的是我们每一步都需要走一遍，每次要维护数组的一次固定的右移操作。

代码

void run() {
    cin >> n >> k;
    f[0] = 1;

    for (int i = 1; ; i ++ ) {
        int step = k + i - 1;
        rep (j, 0, n) {
            sum[j] = f[j];
            if (j >= step) sum[j] = (sum[j] + sum[j - step]) % mod;
        }
        rep (j, step, n) f[j] = sum[j - step];
        rep (j, 0, step - 1) f[j] = 0;
        rep (j, step, n) ans[j] = (ans[j] + f[j]) % mod;
        if (i * (2 * k + i - 1) > 2 * n) break;
    }
    rep (i, 1, n) cout << ans[i] << " \n"[i == n];
}