牛客周赛 Round 131 题解
A.ICPC Balloons
分情况模拟即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int long long
#define itn long long
#define iint long long
string s;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>s;
if(s[0]=='A') cout<<"red";
else if(s[0]=='B') cout<<"orange";
else if(s[0]=='C') cout<<"blue";
else cout<<"green";
return 0;
}
B.String Covering
很显然若有 为
，且
和
为
就不行。
模拟判断即可，时间复杂度为 ，不给代码。
C.Get The Sequence
假设当前处理 和
这两个数字，当前就分两种情况：
，就说明
可以通过疯狂减
得到，不需要额外操作。
就说明当前的
和
匹配。
可以注意到上列过程可以通过双指针实现，时间复杂度为 ，具体如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int long long
#define itn long long
#define iint long long
const int N=2e5+10;
int n,m,a[N],b[N],f[N];
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--){
memset(f,0,sizeof(f));
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
int i=1,j=1;
while(i<=n&&j<=m){
if(a[i]>=b[j]){
i++;
f[j]=1;
j++;
}else i++;
}
bool f1=1;
for(int i=1;i<=m;i++){
if(f[i]==0){
f1=0;
break;
}
}
if(f1) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
D.Longest Subsequence
可以发现，此题存在一个十分朴素的 trick，就是最长上升子序列，具体就不详细展开，时间复杂度为 ，具体如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int long long
#define itn long long
#define iint long long
const int N=2e5+10;
int n,a[N],dp[N];
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],dp[i]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){
if(abs(a[i]-a[j])==1) dp[i]=max(dp[i],dp[j]+1);
}
}
int maxn=1;
for(int i=1;i<=n;i++) maxn=max(maxn,dp[i]);
cout<<maxn<<"\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
赛时提交代码 分。
现在考虑优化。
我们设 为以
这个数为结尾的最长子序列长度，可以发现
只能从
或
转移而来，存在转移
，时间复杂度为
。
具体如下：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,a[N],dp[N];
void solve(){
cin>>n;
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
for(int i=1;i<=n;i++){
int x=a[i];
int cur=max(dp[x-1],dp[x+1])+1;
dp[x]=max(dp[x],cur);
ans=max(ans,cur);
}
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
E.Eat The Candy
存在一个很简单的想法，就是枚举 为那个糖果最多的盒子，统计它能被执行操作多少次，答案就是操作数加上
。
那操作数怎么算呢？
我们假设要统计 到
的操作数，最暴力的贪心做法就是从
扫到
，看每个
和
能执行多少次，最后累加答案，时间复杂度为
。
优化也很简单，用一个前缀数组 和一个后缀数组
预处理即可，存在转移
和
，答案为
，具体如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Int long long
#define itn long long
#define iint long long
const int N=2e5+10;
int n,a[N],f[N],g[N],b[N],c[N];
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x * f;
}
inline void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void solve(){
cin>>n;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
int ans=0;
for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i],c[i]=a[i];
for(int i=2;i<=n;i++) f[i]=f[i-1]+min(b[i],b[i-1]),b[i]-=min(b[i],b[i-1]);
for(int i=n-1;i>=1;i--) g[i]=g[i+1]+min(c[i],c[i+1]),c[i]-=min(c[i],c[i+1]);
for(int i=1;i<=n;i++) ans=max(ans,a[i]+f[i-1]+g[i+1]);
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T;
cin>>T;
while(T--) solve();
return 0;
}
