《算法笔记》3.1小节——入门模拟->简单模拟

前言

算是记录一下刷题的过程吧，也巩固总结一下。
这是算法笔记配套习题集的练习，链接:http://codeup.cn/contest.php?cid=100000575
整理下今上午刚做的这一小节的题，以下代码均已通过测试。

正文

问题 A: 剩下的树

题目描述

有一个长度为整数L(1<=L<=10000)的马路，可以想象成数轴上长度为L的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2，…，L共L+1个位置上有L+1棵树。
现在要移走一些树，移走的树的区间用一对数字表示，如 100 200表示移走从100到200之间（包括端点）所有的树。
可能有M(1<=M<=100)个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

输入

两个整数L(1<=L<=10000)和M(1<=M<=100)。
接下来有M组整数，每组有一对数字。

输出

可能有多组输入数据，对于每组输入数据，输出一个数，表示移走所有区间的树之后剩下的树的个数。

样例输入

4 2
1 2
0 2
11 2
1 5
4 7
0 0

样例输出

2
5

思路:

这里注意树的坐标点从0开始编号，用tree数组表示对应点是否有树，故数组tree空间为10001。
对于重叠区间，直接用数组标记即可。

题解:

#include<cstdio>
#include<cstring>
int main(){
    int L,M,a,b;
    int tree[10001];
    while(scanf("%d%d",&L,&M)&&(L||M)){
    memset(tree,0,sizeof(tree));
    for(int i=0;i<=L;i++){
        tree[i]=1;
    }
    for(int i=0;i<M;i++){
        scanf("%d%d",&a,&b);
        for(int j=a;j<=b;j++){
            tree[j]=0;
        }
    }
    int sum=0;
    for(int i=0;i<=L;i++){
        sum+=tree[i];
    }
    printf("%d\n",sum);
    }
    return 0;
}
/**************************************************************
    Problem: 1814
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 B: A+B

题目描述

给定两个整数A和B，其表示形式是：从个位开始，每三位数用逗号","隔开。
现在请计算A+B的结果，并以正常形式输出。

输入

输入包含多组数据数据，每组数据占一行，由两个整数A和B组成（-10^9 < A,B < 10^9）。

输出

请计算A+B的结果，并以正常形式输出，每组数据占一行。

样例输入

-234,567,890 123,456,789
1,234 2,345,678

样例输出

-111111101
2346912

思路

以字符串读入，再遍历其中的每个字符，若是数字字符，则转为数字进行运算，注意判断是否为负数

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
int main(){
    char str1[20],str2[20];
    int len1,len2;
    while(scanf("%s%s",str1,str2)!=EOF){
        len1=strlen(str1);
        len2=strlen(str2);
        int sum1=0,sum2=0,sum=0;
        for(int i=0;i<len1;i++){
            if(str1[i]>='0'&&str1[i]<='9'){
                sum1=sum1*10+str1[i]-'0';
            }
        }
        if(str1[0]=='-'){
            sum1=-sum1;
        }
        for(int i=0;i<len2;i++){
            if(str2[i]>='0'&&str2[i]<='9'){
                sum2=sum2*10+str2[i]-'0';
            }
        }
        if(str2[0]=='-'){
            sum2=-sum2;
        }
        sum=sum1+sum2;
        printf("%d\n",sum);
    }
    return 0;
}
/**************************************************************
    Problem: 1817
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 C: 特殊乘法

题目描述

写个算法，对2个小于1000000000的输入，求结果。特殊乘法举例：123 * 45 = 14 +15 +24 +25 +34+35
输入
两个小于1000000000的数

输出

输入可能有多组数据，对于每一组数据，输出Input中的两个数按照题目要求的方法进行运算后得到的结果。

样例输入

24 65
42 66666
3 67

样例输出

66
180
39

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
int main(){
    char str1[15],str2[15];
    int len1,len2;
    while(scanf("%s%s",str1,str2)!=EOF){
        len1=strlen(str1);
        len2=strlen(str2);
        int sum=0;
        for(int i=0;i<len1;i++){
            for(int j=0;j<len2;j++){
                sum+=(str1[i]-'0')*(str2[j]-'0');
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}
/**************************************************************
    Problem: 1906
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 D: 比较奇偶数个数

题目描述

第一行输入一个数，为n，第二行输入n个数，这n个数中，如果偶数比奇数多，输出NO，否则输出YES。

输入

输入有多组数据。
每组输入n，然后输入n个整数（1<=n<=1000）。

输出

如果偶数比奇数多，输出NO，否则输出YES。

样例输入

1
67
7
0 69 24 78 58 62 64

样例输出

YES
NO

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
int main(){
    int n,a[1000],odd,even;
    while(scanf("%d",&n)!=EOF){
        memset(a,0,sizeof(a));
        odd=0;even=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            if(a[i]%2)odd++;
            else even++;
        }
        if(even>odd)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}
/**************************************************************
    Problem: 2036
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 E: Shortest Distance

题目描述

The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

输入

Each input file contains one test case. For each case, the first line contains an integer N (in [3, 105]), followed by N integer distances D1 D2 … DN, where Di is the distance between the i-th and the (i+1)-st exits, and DN is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (<=10⁴), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 10⁷.

输出

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

样例输入

5 1 2 4 14 9
3
1 3
2 5
4 1

样例输出

3
10
7

思路:

这个任务非常简单:给定高速公路上的N个出口，形成一个简单的循环，你应该告诉任何一对出口之间最短的距离。
每个输入文件包含一个测试用例。对于每种情况，第一行包含一个整数N (in[3,105])，然后是N个整数距离D1 ,D2…DN，其中Di为第i个出口到(i+1)个出口的距离，DN为第n个出口到第1个出口的距离。一行中的所有数字都用空格隔开。第二行给出一个正整数M(<=10⁴)，后面有M行，每个行包含一对出口编号，条件是出口编号从1到n，保证总往返距离不超过 10⁷。

读懂题目意思就很容易想到，无非就是看从a出口到b出口走的距离近还是从b出口到a出口走的近。注意最后一个出口与第一个出口连起来的。还要尤其注意Di为第i个出口到(i+1)个出口的距离

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
void swap(int* x,int* y){
    int temp=*x;
    *x=*y;
    *y=temp;
}
int main(){
    int N,dis[100000];
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        scanf("%d",&dis[i]);
    }
    int M,a,b;
    scanf("%d",&M);
    for(int i=0;i<M;i++){
        scanf("%d%d",&a,&b);
        if(a>b)swap(&a,&b);
        int sum1=0,sum2=0;
        for(int j=a-1;j<=b-2;j++){
            sum1+=dis[j];
        }
        for(int k=b-1;k<=N-1;k++){
            sum2+=dis[k];
        }
        if(a>1){
            for(int i=0;i<=a-2;i++){
                sum2+=dis[i];
            }
        }
        printf("%d\n",(sum1>sum2)?sum2:sum1);
    }
     
    return 0;
}
/**************************************************************
    Problem: 6116
    User: 2516085027
    Language: C++
    Result: 正确
    Time:588 ms
    Memory:1388 kb
****************************************************************/

问题 F: A+B和C

题目描述

给定区间[-2³¹, 2³¹]内的3个整数A、B和C，请判断A+B是否大于C。

输入

输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。

输出

对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。

样例输入

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

样例输出

Case #1: false
Case #2: true
Case #3: true
Case #4: false

思路:

这里注意int的范围是[-2³¹,2³¹-1]，故必须把a,b,c定义为long long型数据。

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
 
int main(){
    long long a,b,c;
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        scanf("%lld%lld%lld",&a,&b,&c);
        if(a+b>c)printf("Case #%d: true\n",i+1);
        else printf("Case #%d: false\n",i+1);
    }
    return 0;
}
/**************************************************************
    Problem: 6128
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 G: 数字分类

题目描述

给定一系列正整数，请按要求对数字进行分类，并输出以下5个数字：

• A1 = 能被5整除的数字中所有偶数的和；
• A2 = 将被5除后余1的数字按给出顺序进行交错求和，即计算n1-n2+n3-n4…；
• A3 = 被5除后余2的数字的个数；
• A4 = 被5除后余3的数字的平均数，精确到小数点后1位；
• A5 = 被5除后余4的数字中最大数字。

输入

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N，随后给出N个不超过1000的待分类的正整数。数字间以空格分隔。
输出
对给定的N个正整数，按题目要求计算A1~A5并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。
若其中某一类数字不存在，则在相应位置输出“N”。

样例输入

13 1 2 3 4 5 6 7 8 9 10 20 16 18
8 1 2 4 5 6 7 9 16

样例输出

30 11 2 9.7 9
N 11 2 N 9

思路:

这里可以使用bool数组来标记某一类数字是否存在

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
const int maxlen=1000; 
int main(){
    int N,a[maxlen];
    scanf("%d",&N);
    int A1=0,A2=0,A3=0,A5=0,count=0,j=0;
    double A4=0,sum=0;
    bool flag[5]={false};
    for(int i=0;i<N;i++){
        scanf("%d",&a[i]);
        if(a[i]%5==0&&a[i]%2==0){
            A1+=a[i];
            flag[0]=true;
        }
        if(a[i]%5==1){
            A2+=pow(-1,j++)*a[i];
            flag[1]=true;
        }
        if(a[i]%5==2){
            A3++;
            flag[2]=true;
        }
        if(a[i]%5==3){
            sum+=a[i];
            count++;
            flag[3]=true;
        }
        if(a[i]%5==4){
            if(a[i]>A5){
                A5=a[i];
            }
            flag[4]=true;
        }
    }
    A4=sum/count;
    if(flag[0])printf("%d ",A1);else printf("N ");
    if(flag[1])printf("%d ",A2);else printf("N ");
    if(flag[2])printf("%d ",A3);else printf("N ");
    if(flag[3])printf("%.1f ",A4);else printf("N ");
    if(flag[4])printf("%d\n",A5);else printf("N\n");
    return 0;
}
/**************************************************************
    Problem: 6129
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1304 kb
****************************************************************/

问题 H: 部分A+B

题目描述

正整数A的“ $D_A$DA​（为1位整数）部分”定义为由A中所有 $D_A$DA​组成的新整数 $P_A$PA​。例如：给定A = 3862767， $D_A$DA​ = 6，则A的“6部分” $P_A$PA​是66，因为A中有2个6。
现给定A、 $D_A$DA​、B、 $D_B$DB​，请编写程序计算 $P_A$PA​ + $P_B$PB​。

输入

输入在一行中依次给出A、 $D_A$DA​、B、 $D_B$DB​，中间以空格分隔，其中0 < A, B < 1010。

输出

在一行中输出 $P_A$PA​ + $P_B$PB​的值。

样例输入

3862767 6 13530293 3
3862767 1 13530293 8

样例输出

399
0

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
 
int main(){
    char A[11],B[11];
    int a,b,P1=0,P2=0,len1,len2;
    scanf("%s%d%s%d",A,&a,B,&b);
    len1=strlen(A);
    len2=strlen(B);
    for(int i=0;i<len1;i++){
        if(A[i]-'0'==a){
            P1=P1*10+a; 
        }
    }
    for(int i=0;i<len2;i++){
        if(B[i]-'0'==b){
            P2=P2*10+b;
        }
    }
    printf("%d\n",P1+P2);
    return 0;
}
/**************************************************************
    Problem: 6170
    User: 2516085027
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1116 kb
****************************************************************/

问题 I: 锤子剪刀布

题目描述

大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：

现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

输入

输入第1行给出正整数N（<=105），即双方交锋的次数。随后N行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B代表“布”，第1个字母代表甲方，第2个代表乙方，中间有1个空格。

输出

输出第1、2行分别给出甲、乙的胜、平、负次数，数字间以1个空格分隔。第3行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有1个空格。如果解不唯一，则输出按字母序最小的解。

样例输入

10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J

样例输出

5
3 2
2 3 5
B B

思路:

这里要注意scanf，使用%c时会把换行和空格读入，故需要在指定位置使用getchar避免读入错误，change函数是统计胜利时，出剪刀，石头，布各自的次数。reverse函数是通过下标找到对应的字符。

题解:

#include<cstdio>
#include<cstring>
#include<cmath>
void change(char x,int count[]){
    if(x=='B')count[0]++;
    if(x=='C')count[1]++;
    if(x=='J')count[2]++;
}
char reverse(int i){
    if(i==0)return 'B';
    if(i==1)return 'C';
    if(i==2)return 'J';
}
int main(){
    int N;
    scanf("%d",&N);
    getchar();
    char a,b;
    int win=0,equal=0,defeat=0,countA[3],countB[3];
    memset(countA,0,sizeof(countA));
    memset(countB,0,sizeof(countB));
    while(N--){
        scanf("%c %c",&a,&b);
        getchar();
        if(a==b)equal++;
        else if((a=='J'&&b=='B')||
        (a=='C'&&b=='J')||
        (a=='B'&&b=='C')){
            win++;
            change(a,countA);
        }else{
            defeat++;
            change(b,countB);
        }
    }
    printf("%d %d %d\n",win,equal,defeat);
    printf("%d %d %d\n",defeat,equal,win);
    int maxA=countA[0],maxB=countB[0],Aflag=0,Bflag=0;
    for(int i=0;i<3;i++){
        if(maxA<countA[i]){
            maxA=countA[i];
            Aflag=i;
        }
        if(maxB<countB[i]){
            maxB=countB[i];
            Bflag=i;
        }
    }
    printf("%c %c\n",reverse(Aflag),reverse(Bflag));
    return 0;
}
/**************************************************************
    Problem: 6172
    User: 2516085027
    Language: C++
    Result: 正确
    Time:12 ms
    Memory:1116 kb
****************************************************************/

后记

路漫漫其修远兮
吾将上下而求索