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's Blog » 河南农大算法训练赛三月周赛-0310
 河南农业大学训练赛题解