Educational Codeforces Round 158 (Rated for Div. 2)

基本情况

A题很水，几分钟秒了。

B题想到一个解，被自己 hack 掉之后没有重新想，一直想在自己一开始的基础上改好，结果最后B都没拿下。

B. Chip and Ribbon

我的思路

其实也是找规律，根本没严谨地证明正确性。不应该一条路走到黑的。

找到第一个比上一个小的数，再找到最后一个这样的数，求两者差值。

毫无逻辑，就只是刚好通过样例了，我手造一堆数据 hack 了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

int t, n;
long long ans = 0, cnt;
int c[N];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> t;
	while (t--)
	{
		int l = 0;
		ans = 0;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> c[i];
			if (c[i] && !l)
				l = i;
		}
		if (n == 1)
		{
			cout << c[1] - 1 << endl;
		}
		else
		{
			if (l != 1)
			{
				ans++;
			}
			bool is_end = true;
			bool is_cnt = false;
			for (int i = l + 1; i <= n; i++)
			{
				int temp = c[i - 1];
				if (i - 1 == l && c[i - 1] == 1)
				{
					if (c[i] < c[i  - 1])
						is_cnt = true;
					continue;
				}
				while (c[i] < c[i - 1])
				{
					is_cnt = true;
					i++;
					if (i == n + 1)
					{
						is_end = false;
						break;
					}
				}
				ans += temp - c[i - 1];
			}
			if (is_end)
			{
				if (!(ans == 1 && l != 1 && !is_cnt))
				{
					ans += c[n];
				}
			}
			cout << ans << endl;
		}

	}
	return 0;
}

正解思路

At first, let's change the statement a bit: instead of teleporting our chip into cell \(x\), we create a new chip in cell \(x\) (it means that the chip does not disappear from the cell where it was located). And when we want to move a chip, we move any chip to the next cell. Then, \(c_i\) will be the number of times a chip appeared in the cell \(i\), and the problem will be the same: ensure the condition on each \(c_i\) by "creating" the minimum number of chips.

Let's look at value of \(c_1\). If \(c_1>1\), we have to create at least \(c_1−1\) new chips in cell \(1\). Let's create that number of chips in that cell.

Then, let's see how we move chips from the cell \(i\) to the cell \((i+1)\). If \(c_i≥c_{i+1}\), then all chips that appeared in the cell \((i+1)\) could be moved from the \(i\)-th cell, so we don't need to create any additional chips in that cell.

But if \(c_i<c_{i+1}\), then at least \(c_{i+1}−c_i\) chips should be created in the cell \((i+1)\), since we can move at most \(c_i\) chips from the left.

So, for every \(i\) from \(2\) to \(n\), we have to create \(\max(0, c_i - c_{i-1})\) chips in the \(i\)-th cell; and the number of times we create a new chip in total is

\[c_1 - 1 + \sum\limits_{i=2}^{n} \max(0, c_i - c_{i-1}) \]

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000;
 
int t;
 
int main() {
    cin >> t;
    for (int tc = 0; tc < t; ++tc) {
        int n;
        cin >> n;
        vector <int> cnt(n);
        long long res = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            cin >> cnt[i];
            if (cnt[i] > cur) 
                res += cnt[i] - cur;
            cur = cnt[i];
        }
        
        cout << res - 1 << endl;
    }
    return 0;
}