Codeforces Round 957 (Div. 3)

推荐个C++编程仓库模板
https://github.com/yxc-s/programming-template

A. Only Pluses

总结：为什么优先增加最小的数，它们的乘积会是最优的呢？可以这么理解，假如只有两个数a和b，b>a，那么a + 1，就增加一份b。如果b + 1，只能增加1份a。因为 b > a，所以增加小的数是最优的。

void solve(){
	vector<int> a;
	for (int i = 0; i < 3; ++i){
		int t;
		cin >> t;
		a.push_back(t);
	}
	for (int i = 0; i < 5; ++i){
		auto it = min_element(a.begin(), a.end());
		(*it) ++;
	}
	int res = 1;
	for (auto x : a){
		res *= x;
	}

	cout << res << endl;
}

B. Angry Monk

题意：有个长度n和k个片段，问k个片段拼接成n的最小操作次数。 操作1：合并两个片段（必须有一个片段长度为1）， 操作2： 分解为两个片段（分解为长度为1和长度-1的两个片段）

思路：贪心思想，最长的片段作为基础片段，其他长度的片段都要经历分解+组合两种操作（除长度为1的片段外），直接计数即可。

总结：习惯了n作为数组长度了，这次输入的长度为k，还wa了，哎。

void solve(){
	int n, k;
	cin >> n >> k;

	long long ans = 0;
	int maxn = 0;
	vector<int> a(k);
	for (int i = 0; i < k; ++i){
		cin >> a[i];
		maxn = max(maxn, a[i]);
	}
	bool ok = true;
	for (int i = 0; i < k; ++i){
		if (a[i] == maxn && ok == true){
			ok = false;
		}
		else{
			ans += (a[i] - 1) + a[i];
		}
	}

	cout << ans << '\n';
}

C. Gorilla and Permutation

题意：构造一个长度为n的排列，使这个排列的sigma(f[i] - g[i]) 最大。
f[i] : 在1~i的所有数中，>=k的所有数的和
g[i] : 在1~i的所有数种, <= m的所有数的和

思路： 优先让满足f条件的数早出现（越大越早），让满足g条件的数晚出现（越小越早）。

void solve(){
	int n, m, k;
	cin >> n >> k >> m;

	for (int i = n; i >= m; --i){
		cout << i << ' ';
	}
	for (int i = m - 1; i > k; --i){
		cout << i << ' ';
	}
	for (int i = 1; i <= k; ++i){
		cout << i << " \n"[i == k];
	}
}

D. Test of Love
题意：给定一个长度为n的字符串(1~n)，问能否从位置0移动到位置n + 1。字符串包含"L", "W", "C"，还有数字k和m。m表示当前只有在0或者L上面，能向右跳跃的最大距离。k表示在移动过程中只能在W上k次。C是障碍，可以跳过，但是不能站上去。

思路：分情况讨论。 从右往左记录距离当前位置最近的L的位置，用next数组表示。维护一个变量rightmost，表示当前位置~rightmost之间的位置都可以去（初始时为m）。
case 1: 如果rightmost >= next[i]， i = next[i], 更新rightmost。（跳到下一个L位置）
case 2: 如果当前在陆地上，从当前能跳的最右边的距离往左找，找到第一个W（能到达的最右边的water），如果k <= 0或者没找到W, 无解
case 3: 如果当前在水里(W)，k <= 0或者下一个字母是C，无解。

总结：一眼感觉应该用dp，感觉应该是当前能到达，所需要的最小k。但是看了一下感觉k的范围有点大，不太好维护，可能是状态想错了。 回头需要补一下dp的思路。 然后赛时用的方法是穷举所有情况，其实在cf的题目中，很多题目都是这样的思路，考虑所有情况，都安排好，需要注意的就是要理解整个程序的过程，思考出所有可能的现象。

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;

    s = ' ' + s;
    s += "L";

    vector<int> next(n + 2);
    next[n + 1] = n + 1;
    for (int i = n; i >= 0; --i){
        next[i] = next[i + 1];
        if (s[i + 1] == 'L'){
            next[i] = i + 1;
        }
    }

    int rightmost = m;
    bool in_water = false;
    for (int i = 0; i <= n; ){
        if (next[i] <= rightmost){
            i = next[i];
            rightmost = i + m;
            in_water = false;
        }
        else {
            if (in_water){
                if (s[i + 1] == 'C' || k <= 0){
                    cout << "NO\n";
                    return;
                }
                else{
                    i ++;
                    k --;
                    rightmost = i + 1;
                    in_water = true;
                }
                
            }
            else if (k > 0){
                bool ok = false;
                for (int j = i + m; j > i; --j){
                    if (s[j] == 'W'){
                        i = j;
                        in_water = true;
                        ok = true;
                        rightmost = i + 1;
                        k --;
                        break;
                    }
                }
                if (!ok){
                    cout << "NO\n";
                    return;
                }
            }
            else{
                cout << "NO\n";
                return;
            }
        }
    }

    cout << "YES\n";

}

上面写完还剩一个多小时，为了避免熬夜坐牢，直接睡觉去了。

E. Novice's Mistake

题意：给定一个n，求所有满足条件的a和b。 条件：n重复a次后去掉后面b位 == a * n - b

赛时思路：设n的位数为x,看了样例后发现n重复i次后（ni），满足a * x - b == i * x，对于一个固定的重复次数i，可以知道b = a * x - i * x。那么a * n - b == ni.substr(a - b) ==> a * n - a * x + i * x, 而i应该不会超过6，所以算的速度很快。 但是这么算有一个问题，就是n可能重复的不是整数次，比如10重复2.5次是10101，所以根据上面的思路，样例3没过去，晚点再重新补好了。