acwing 第35场周赛
这次周赛有三道题:字符串模拟,枚举,枚举
acwing 4212.字符串比较
题目描述
解题思路
将大写字母全部转换为小写字母,然后遍历字符串比大小
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
char a[N],b[N];
int flag=0;
int main(){
scanf("%s",&a);
scanf("%s",&b);
for(int i=0;i<N-2;i++){
if(!a[i]&&!b[i]) break;
if(a[i]<'a') a[i]+='a'-'A';//转换为小写字母
if(b[i]<'a') b[i]+='a'-'A';
if(a[i]!=b[i]){
if(a[i]>b[i]) flag=1;
else flag=-1;
break;
}
}
printf("%d",flag);
return 0;
}
acwing 4213. 最小结果
题目描述
解题思路
题目的输入相对固定,四个数三个操作符,而且只有加和乘,所以我们直接暴力枚举
按乘号的个数分情况讨论,主要是枚举1个和2个乘号的情况
当然也可以用dfs
注意事项
枚举的情况很多,尤其要注意输入有可能为0
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a[10],ans=0;//每个数最大是1000,4个1000相乘会爆int
char op[4];
int mult=0;
bool cmp(int x,int y){
return x<y;
}
int main(){
for(int i=1;i<=4;i++) scanf("%lld",&a[i]);
sort(a+1,a+5,cmp);
for(int i=1;i<=3;i++){
cin>>op[i];
if(op[i]=='*') mult++;
}
if(mult==0) for(int i=1;i<=4;i++) ans+=a[i];
else if(mult==1) {
if(a[1]==0) {
if(op[1]=='*') ans=a[2]+a[3];
else if(op[2]=='*') ans=a[2];
else ans=0;
}
else{
if(op[3]=='*'){
ans=a[1]*(a[2]+a[3]+a[4]);
}
else{
a[1]*=a[2];
a[2]=0;
for(int i=1;i<=4;i++) ans+=a[i];
}
}
}
else if(mult==2){
if(op[1]=='+') ans=(a[3]+a[4])*a[1]*a[2];
else if(op[2]=='+') ans=(a[2]*a[3]+a[4])*a[1];
else{
if(a[2]==0) ans=0;//说明a[1],a[2]都是0
else if(a[2]*a[3]>a[4]) ans=a[1]*a[4]+a[2]*a[3];
else ans=a[1]*a[2]*a[3]+a[4];
}
}
else{
ans=a[1];
for(int i=2;i<=4;i++) ans*=a[i];
}
printf("%lld",ans);
return 0;
}
acwing 4214. 三元组
题目描述
解题思路
从一堆数中找出满足条件的三个数i,k,j,那就是枚举
但是普通的三层循环时间复杂度是O(n^3)的,会超时
所以进阶一下,还是枚举,不过我们先把第二个数k确定,在去枚举左边的最小值l 和右边的最小值r
最后记录l+c[k]+r就行了
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3010,INF=0x3f3f3f3f;
int s[N],c[N];
int ans=INF;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
int sum=0;
for(int k=1;k<=n;k++){//i是第一个数,k是第二个数,j是第三个数
int l=INF,r=INF;
for(int i=1;i<k;i++) if(s[i]<s[k]) l=min(l,c[i]);
for(int j=k+1;j<=n;j++) if(s[j]>s[k]) r=min(r,c[j]);
ans=min(ans,l+c[k]+r);
}
if(ans==INF) ans=-1;
printf("%d",ans);
return 0;
}