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;
}原文地址：https://blog.csdn.net/sin1810335764/article/details/140425416
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！