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--;}}elseans--;}if (s[i] == 'C')ans--;}}if (ans > 0)cout << "YES" << endl;elsecout << "NO" << endl;
}
int main()
{cin >> t;while (t--) {solve();}return 0;
}