CodeForces Round 957 (Div3)
蒟蒻找了一些简单题做了而已，别太在意……
比赛链接
CodeForces Round 957 (Div3)
A. Only Pluses
题意
三个正整数 \(a,b,c\)，有五次操作机会。
每次操作：
- 选取 \(a,b,c\) 中任意一个数，将这个数加上一。
要求最大化 \(a\times b\times c\)。
思路
很直接的贪心题。
假设有三个正整数 \(x,y,z\)，给其中的某一个数加上一，那么其乘积就是 \((x+1)yz\) 或 \(x(y+1)z\) 或 \(xy(z+1)\)。
要使乘积最大，那么这个加一的数一定是 \(x,y,z\) 中最小的那个数。
以此类推，五次操作中，我们必须贪心地选取 \(a,b,c\) 中最小的数。
为了省时省力，我们可以用小根堆来维护。
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t,ans=1;cin>>t;
priority_queue<int,vector<int>,greater<int> >q;
while(t--){
ans=1;for(int i=1,x;i<=3;i++)cin>>x,q.push(x);
for(int i=1,t;i<=5;i++)
t=q.top(),q.pop(),t++,q.push(t);
for(int i=1;i<=3;i++)ans*=q.top(),q.pop();
cout<<ans<<endl;
}
return 0;
}
B. Angry Monk
题意
给定长度为 \(k\) 的序列 \(\{a_k\}\) 和正整数 \(n\)，保证 \(\sum a_i=n\)，每次可以进行一下两种操作：
-
选定一个 \(a_i(a_i>1)\)，将其分裂成 \(a_i-1\) 和 \(1\)。
-
选定 \(a_i\) 和 \(a_j\)，满足 \(a_i=1\)，将 \(a_i\) 和 \(a_j\) 合并为一个 \(a_j+1\)。
求将序列长度变为 \(1\) 的最小操作次数。
思路
依然是贪心。
如果两个数可以合并，当且仅当其中一个数为 \(1\)。
考虑 \(k=2\) 的情况，假设序列中两个元素为 \(p,q(p>q)\)，那么它的最小操作步数就是 \(2q-1\)，即先将 \(q\) 分裂为 \(q\) 个 \(1\)，再让这 \(q\) 个 \(1\) 与 \(p\) 合并。
以此类推，我们可以将序列先排序，把其中最小的 \(k-1\) 个元素分别分解为 \(1\)，在让它们和最大的元素合并。
这样就能做了。
但继续想想，可以想到一个公式：
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,a[100001];
void solve(){
cin>>n>>k;for(int i=1;i<=k;i++)cin>>a[i];
sort(a+1,a+k+1);
cout<<n-a[k]-(k-1)+n-a[k]<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;cin>>t;while(t--)solve();
return 0;
}
C. Gorilla and Permutation
题意
给定正整数 \(n,m,k\)，假设有一个关于 \(n\) 的排列 \(\{a_n\}\)，那么 \(f(i)=\sum_{j=1}^i a_i|a_i\ge k,g(i)=\sum_{j=1}^i a_i|a_i\le m\)。
需要求一个 \(n\) 的排列，最大化 \(\sum_{i=1}^n f(i)-\sum_{i=1}^n g(i)\)。
思路
依然是贪心。
在求两个正整数的最大差时，有一种思路就是在最大化被减数的同时最小化减数，这道题就可以用这种思路。
首先考虑如何最大化 \(\sum_{i=1}^n f(i)\)。易得我们只需要在排列前端把 \(k\) 到 \(n\) 从大到小排序即可。
其次考虑如何最小化 \(\sum_{i=1}^n g(i)\)。易得我们只需要在排列末端把 \(1\) 到 \(m\) 从小到大排序即可。
注意到 \(k>m\)，所以这两个操作并不交叉。至于那些大于 \(m\) 又小于 \(k\) 的数，随便放就行了。
直白地，对于给定的 \(n,m,k\)，我们给出的排列应当是：
代码
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;cin>>t;
while(t--){
int n,m,k;cin>>n>>m>>k;
for(int i=n;i>m;i--)cout<<i<<' ';
for(int i=1;i<=m;i++)cout<<i<<' ';
cout<<endl;
}
return 0;
}
D. Test of Love
题意
A 愿意为 B 做任何事，甚至游过鳄鱼出没的沼泽。我们决定考验一下这份爱。A 必须游过一条长 \(n\) 米的河。他需要从 \(0\) 游到 \(n+1\)。
最初，A 在左岸，需要到达右岸。它们分别位于 \(0\) 和 \(n+1\) 米。这条河可以表示为 \(n\) 段，每段长度为 \(1\) 米。每个片段要么包含一个圆木 'L'，要么包含一个鳄鱼 'C'，要么包含一个水 'W'。A 可以移动如下:
- 如果他在岸上或在圆木上，他可以向前跳不超过 \(m(1\le m\le10)\) 米。
- 如果他在水里，他只能游到下一个河段(或者如果他在第 \(n\) 米处，他只能游到河岸)。
- A 在任何情况下都不能带着鳄鱼降落在分段上
确定 A 是否能到达右岸。
思路
模拟贪心，好像很多 Div3 的题都是这样。
先来个分类讨论，假设当前为 \(i\)，假设输入的字符串为 \(c\)，那么：
-
\(c_i=\)'L'，那么他可以向前跳最多 \(m\) 格，因为他最多只能游 \(k\) 格，所以我们可以贪心地尽量选择圆木。如果往后的 \(m\) 格都没有圆木，那么就跳进离 \(i\) 最远的水里。如果连水都没有，只有鳄鱼，那么输出
NO。 -
\(c_i=\)'W'，那么操作就很简单了，直接从 \(i\) 开始向后枚举，如果可以到达圆木，那么就站在圆木上，如果到达不了，那么输出
NO。
我们可以把 \(c_0\) 和 \(c_{n+1}\) 看作是个圆木。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
char c[200005];
void solve(){
memset(c,0,sizeof(c));
cin>>n>>m>>k;c[0]='L',c[n+1]='L';
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=0;i<=n+1;){
bool b=0;
if(i==n+1){cout<<"YES"<<endl;return;}
if(c[i]=='W'){
for(int j=i+1,l=1;j<=n+1;l++,j++){
if(c[j]=='C'){cout<<"NO"<<endl;return;}
if(c[j]=='L'){
k-=l;
if(k<0){cout<<"NO"<<endl;return;}
i=j;break;
}
}
continue;
}
for(int j=min(i+m,n+1);j>=i+1;j--)if(c[j]=='L'){i=j;b=1;break;}
if(b)continue;
for(int j=min(i+m,n+1);j>=i+1;j--)if(c[j]=='W'){i=j;b=1;break;}
if(b)continue;
cout<<"NO"<<endl;return;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t;cin>>t;while(t--)solve();
return 0;
}