Top

河南农大算法训练赛三月周赛-0310


A - 打理机房

题意:给一个字符串,如果大写数比小写数多,全部转化成大写,否则全部小写。

题解:遍历一遍字符串,用cnts和cntb记录大小写数量,最后对比调用strupr,strlwr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
char s[120];
int main(){
cin>>s;
int cnts=0,cntb=0;
for(int i=0;s[i];i++){
if(s[i]>='a'&&s[i]<='z')cnts++;
else if(s[i]>='A'&&s[i]<='Z')cntb++;
}
if(cntb>cnts)strupr(s);
else strlwr(s);
cout<<s<<endl;

}

B - Anoyer的生日礼物

题意:给你一个整数,如果为负数允许你从倒数第一位或者倒数第二位删除一个数字,使值最大

题解:算出删倒一和倒二的值,对比下大写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
char s[20];
int main(){
cin>>s;
bool flag=0;
if(s[0]!='-')cout<<s<<endl;
else{
int a=atoi(s+1);
int b=a%10+a/100*10,c=a/10;
if(b>c)cout<<c*-1<<endl;
else cout<<b*-1<<endl;
}
}

C - 郑州地铁新干线

题意:给你一个环,已知环上相邻两点的距离,求a到b的最短路径

题解:一共就两种路径,从a顺时针或者逆时针。都求出来比大小就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int d[120];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>d[i];
int a,b,lena=0,lenb=0;
cin>>a>>b;
if(a>b)swap(a,b);
for(int i=a-1;;i++){
if(i%n==b-1)break;
lena+=d[i%n];
}
for(int i=b-1;;i++){
if(i%n==a-1)break;
lenb+=d[i%n];
}
cout<<min(lena,lenb)<<endl;
return 0;
}

D - 区间覆盖

题意:给你n个线段,问是否有一个的线段能覆盖其他线段,能输出线段位置,不能输出-1

题解:直接模拟求,如果定义最大区间[mina,maxb],如果发现一个线段包括了这个最大区间,则flag=位置,同时更换区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
struct Node{
int a,b;
}line[maxn];
int main(){
int n,a=0,b=0,mina,maxb,flag=1;
scanf("%d",&n);
scanf("%d%d",&a,&b); //初始将第一组设成答案
mina=a,maxb=b;
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
if(a<=mina&&b>=maxb){ //如果能出现覆盖的线,flag记录位置,替换mina和maxb
flag=i+1;
mina=a,maxb=b;
}
else{
if(a<mina){ //如果出现比mina小的替换mina
flag=-1;
mina=a;
}
if(b>maxb){ //如果出现比minb大的替换minb
flag=-1;
maxb=b;
}
}

}
cout<<flag<<endl;
}

E - 电路阻抗

题意:给定电阻r0=1,通过并联串联,问最少需要多少个r0能组成a/b

题解:对a/b进行分解,等于d+c/b,因为d表示串联d个电阻,c/d表示并联了一个b/c的电子原件。对这个原件在进行分解,一直分解到c能整除b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a,b,cnt=0;
cin>>a>>b;
while(b){
cnt+=a/b;
a=a%b;
swap(a,b);
}
cout<<cnt<<endl;
}

G - XX输入法的的纠错算法

题意:单词需要校对,把错误的改成正确的,错误单词的标准是:
​ 1.有三个连续相同的字母,如www;
​ 2.有多对有两个连续相同的字母,如aamm

题解:用s2存当前去错后的串,看看压入s1[i]到s2中是否会成为一个错误单词,如果会就continue,否则压入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
char s1[maxn],s2[maxn];
int main(){
scanf("%s",s1);
int len=strlen(s1);
int top=0;
s2[top++]=s1[0];
s2[top++]=s1[1];
for(int i=2;i<len;i++){
if(s1[i]==s2[top-1]&&s2[top-1]==s2[top-2])continue; //3个相等
else if(s1[i]==s2[top-1]&&s2[top-2]==s2[top-3])continue;
s2[top++]=s1[i];
}
s2[top++]='\0';
printf("%s\n",s2);
return 0;

}

H - 简单的构造

题意:给两个数a和b,可以打乱a每位数的顺序组成一个新的数c,求满足c<=b的最大,保证结果一定存在。

题解:如果a的长度小于b,则直接输出a升序后的逆序;如果lena==lenb,遍历b,从0号位开始尽可能的让a[i]==b[i],如果发现没有a中已经没有b[i]数字
则挑一个比b[i]小的最大的数(如果发现找不到小的就返回去查),放进去。然后剩余的数字就可以从大到小放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string a,b,c;
int numa[10];
int main(){
cin>>a>>b;
int lena=a.size(),lenb=b.size();
for(int i=0;i<lena;i++){
numa[a[i]-'0']++;
}
if(lena<lenb){
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
cout<<a<<endl;
}
else{
c="";
bool flag=0;
for(int i=0;i<lenb;i++){
if(numa[b[i]-'0']){
c+=b[i];
numa[b[i]-'0']--;
}
else{
bool th=1; //标记是否替换
for(int j=b[i]-'0';j>=0;j--){
if(numa[j]){
c+=j+'0';
numa[j]--;
flag=1;
th=0;
break;
}
}
while(th){ //没有替换前面一位换个小的
for(int j=b[i-1]-'0'-1;j>=0;j--){
if(numa[j]){
c[i-1]=j+'0';
numa[j]--;
numa[b[i-1]-'0']++;
flag=1;
th=0;
break;
}
}
if(th){
c.erase(c.end() - 1); //删除最后一个字符
numa[b[i-1]-'0']++;
i-=1;
}
}
}
if(flag)break;
}
cout<<c;
if(flag){
for(int i=9;i>=0;i--){
while(numa[i]--){
cout<<i;
}
}
}
cout<<endl;
}
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址