Codeforces Round 957 (Div. 3)(A~D题)

A. Only Pluses

 思路:

优先增加最小的数，它们的乘积会是最优,假如只有两个数a和b，b>a，那么a + 1，就增加一份b。如果b + 1，只能增加1份a。因为 b > a，所以增加小的数是最优的。

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll a, b, c;
ll ans, num, sum1,sum,sum2, cnt;
ll dp[N], f1[N], f2[N];
ll mp[105][105];
bool flag, vis[N];
string s, ss;
void solve()
{
    ll x;
    vector<ll>q;
    for (int i = 1; i <= 3; i++)
    {
        cin >> x;
        q.push_back(x);
    }
    for (int i = 1; i <= 5; i++)
    {
        sort(q.begin(), q.end());
        q[0]++;
    }
    cout << q[0] * q[1] * q[2] << endl;;
}
int main()
{
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

B. Angry Monk

思路:

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

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll a, b, c;
ll ans, num, sum1,sum,sum2, cnt;
ll dp[N], f1[N], f2[N];
ll mp[105][105];
bool flag, vis[N];
string s, ss;
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> dp[i];
	}
	ans = 0;
	sort(dp + 1, dp + 1 + m);
	for (int i = 1; i < m; i++) {
		if (dp[i] != 1) {
			ans += dp[i] - 1;
		}
	}
	cout << ans + n - dp[m] << endl;
}
int main()
{
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

C. Gorilla and Permutation

思路:

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

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll a, b, c;
ll ans, num, sum1,sum,sum2, cnt;
ll dp[N], f1[N], f2[N];
ll mp[105][105];
bool flag, vis[N];
string s, ss;
void solve()
{
	cin >> n >> m >> k;
	for (int i = n; i >= k; i--) 
		cout << i << " ";
	for (int i = k - 1; i >= m + 1; i--) 
		cout << i << " ";
	for (int i = 1; i <= m; i++) 
		cout << i << " ";
	cout << endl;
}
int main()
{
	cin >> t;
	while (t--) {
		cin >> n >> m >> k;
		for (int i = n; i >= k; i--)
			cout << i << " ";
		for (int i = k - 1; i >= m + 1; i--)
			cout << i << " ";
		for (int i = 1; i <= m; i++)
			cout << i << " ";
		cout << endl;
	}
	return 0;
}

D. Test of Love

思路:

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

代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll a, b, c;
ll ans, num, sum1,sum,sum2, cnt;
ll dp[N], f1[N], f2[N];
ll mp[105][105];
bool flag, vis[N];
string s, ss;
void solve()
{
	cin >> n >> m >> k;
	cin >> s;
	s = " " + s;
	if (m > n) {
		cout << "YES" << endl;
		return;
	}
	else {
		ans = m;
		for (int i = 1; i <= n; i++) {
			if (ans <= 0) {
				cout << "NO" << endl;
				return;
			}
			if (s[i] == 'L')
				ans = m;
			if (s[i] == 'W') {
				if (k > 0) {
					if (ans > 1)
						ans--;
					else {
						ans = 1;
						k--;
					}
				}
				else
					ans--;
			}
			if (s[i] == 'C')
				ans--;
		}
	}
	if (ans > 0)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
int main()
{
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}