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

可定

发布于 2020-04-20 14:58:20

1.1K0

发布于 2020-04-20 14:58:20

文章被收录于专栏：细嗅蔷薇细嗅蔷薇

http://codeup.cn/contest.php?cid=100000575

Problem A: 剩下的树

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 4797 Solved: 1914

Description

有一个长度为整数L(1<=L<=10000)的马路，可以想象成数轴上长度为L的一个线段，起点是坐标原点，在每个整数坐标点有一棵树，即在0,1,2，...，L共L+1个位置上有L+1棵树。

 现在要移走一些树，移走的树的区间用一对数字表示，如 100 200表示移走从100到200之间（包括端点）所有的树。

 可能有M(1<=M<=100)个区间，区间之间可能有重叠。现在要求移走所有区间的树之后剩下的树的个数。

Input

两个整数L(1<=L<=10000)和M(1<=M<=100)。

 接下来有M组整数，每组有一对数字。

Output

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

Sample Input

Sample Output

2
5

代码（C语言）

所有区间都重叠时才会AC，想想为什么？

#include<cstdio>
int main(){
    int L,M;
    while(1){
        scanf("%d%d",&L,&M);
        if(L||M){//L、M不全为0
            int a,b,left=L,right=0;
            for(int i=0;i<M;++i){
                scanf("%d%d",&a,&b);
                if(left>a) left=a;
                if(right<b) right=b;
            }
            printf("%d\n",L-right+left);//输出剩下的树
        }
        else break;//L、M均为0时结束程序
    }
    return 0;
}

#include<cstdio>
#include<cstring>
int main(){
    int L,M;
    while(1){
        scanf("%d%d",&L,&M); 
        if(L||M){//L、M不全为0
            int trees[L+1],left,right,rest=L+1;//用数组保存每棵树的状态，数组元素为0表示存在，为1表示不存在
            memset(trees,0,sizeof(trees));//数组置0，表示所有树木均存在
            for(int i=0;i<M;++i){
                scanf("%d%d",&left,&right);//输入区间的左右边界
                for(int j=left;j<=right;++j){//判断区间内树木的状态
                    if(!trees[j]) --rest,trees[j]=1;//为0则表示存在，移走后剩余树木减1，并标记为不存在
                }
            }
            printf("%d\n",rest);//输出剩余树木
        }
        else break;//L、M均为0时结束程序
    }
}

代码3还没写完

#include<cstdio>
int main(){
    int a=0,b=0;//移走的树，以左到右
    int M,L;
    int n=2;
    int trees[10020];
    int abs_num=0;//左右端点之差
    memset(trees,0,sizeof(a));
    fill(trees,1,L);//标记为1，表示树存在
    scanf("%d",&L);
    scanf("%d",&M);
    while(scanf("%d%d",&a,&b)!=EOF){
        for(int i = 0; i < M; i++){
            abs_num = b-a;
            for(int j = 0; j < abs_num;j++){
            trees[a+j] = 0;
            }
        }
    }
}

Problem B: A+B

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 3417 Solved: 1554

Description

给定两个整数A和B，其表示形式是：从个位开始，每三位数用逗号","隔开。

现在请计算A+B的结果，并以正常形式输出。

Input

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

Output

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

Sample Input

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

Sample Output

-111111101
2346912

代码（C++）

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
char A[15],B[15];
long trans(char *arr,int length)
{
    long num=0,j=1;
    for(int i=length-1;i>=0;i--)
    {
        if(arr[i]>='0' && arr[i]<='9')
        {
            num = num + (arr[i] - '0')*j;
            j*=10;
        }
    }
    if(arr[0]=='-')
        num = -num;
    return num;
}
int main()
{
    long a,b;
    while(scanf("%s%s",A, B) != EOF)
    {
        int lenA = strlen(A);
        int lenB = strlen(B);
        a = trans(A,lenA);
        b = trans(B,lenB);
        printf("%ld\n",a+b);
    }
    return 0;
}

提示：input的逗号可不用处理。

另外，需要搞懂arri-'0'是什么意思。(已解决：使其数字化，而不是原来的字符串)

Problem C: 特殊乘法

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 2171 Solved: 1393

Description

写个算法，对2个小于1000000000的输入，求结果。特殊乘法举例：123 * 45 = 1_4 +1_5 +2_4 +2_5 +3_4+3_5

Input

两个小于1000000000的数

Output

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

Sample Input

24 65
42 66666
3 67

Sample Output

66
180
39

代码（C++）

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
char a[15],b[15];
int num1[15],num2[15];
void trans(char *arr,int *num){
    int len = strlen(arr);
    for(int i=0;i<len;i++){
        num[i] = arr[i] - '0';
    }
}
int main()
{
    while(scanf("%s%s",a, b) != EOF){
        int mul=0;
        trans(a,num1);
        trans(b,num2);
        int lena = strlen(a);
        int lenb = strlen(b);
        for(int i=0;i<lena;i++)
        for(int j=0;j<lenb;j++){
            mul += (num1[i]*num2[j]);
        }
        printf("%d\n",mul);
    }
    return 0;
}

Problem D: 比较奇偶数个数

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 2353 Solved: 1322

Description

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

Input

输入有多组数据。

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

Output

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

Sample Input

1
67
7
0 69 24 78 58 62 64

Sample Output

YES
NO

代码（C++）

#include<cstdio>
int main(){
    int num;
    int n = 0;
    while(scanf("%d",&n)!=EOF){
        int count_odd = 0,count_even = 0;
        for(int i = 0; i < n; i++){
            scanf("%d",&num);
            if(num%2 == 0)count_even++;
            else count_odd++;
        }
        if(count_even > count_odd) printf("NO");
            else printf("YES");
    }
    return 0;
}

Problem E: Shortest Distance (20)

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 2717 Solved: 1040

Description

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.

Input

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 (<=104), 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 107.

Output

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

Sample Input

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

Sample Output

3
10
7

注意：题意为，给出N个出口之间的距离，然后输入M对出口，计算这M对出口之间的最短距离，这一题不能在给定出口对时再依次累加两个出口之间的距离，一般来说，存在查询的题目都是静态查询，即查询的结果在输入结束时已经得出，或者经过简易的计算就可以得出，动态查询就是根据查询的内容再开始计算，在之前并没有对数据进行处理，很明显，动态查询在查询数目很多时，很容易超时，所以出现查询的题目，首先想到的应该是尽量减少从查询输入到输出结果之间的处理时间。

首先，在输入每个边的时候，就计算两个量，一个是这个环的总距离，这个用一个sum累加就可以实现，另一个，是第一个顶点距离各个顶点的距离，用一维数组实现，每个顶点的值等于输入的距离加上上一个顶点的值，初始将1这个顶点的值置为0，因为1到1本身就是0嘛。

然后，根据输入的两个顶点，将它们和顶点1之间的距离相减，就得到了其中一个距离，另一个距离通过环的总距离减去这个距离就能得到了，然后比较两个的大小，输出最小的，然后就完成啦ヽ(￣▽￣)ﾉ

代码（C++）

#include <cstdio>
int main(){
    int circle[100000],distance[100000];
    distance[1]=0;
    int n,m,sum=0;
    scanf("%d",&n);
    int b,e,low,high,dis1,dis2;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&circle[i]);
        sum+=circle[i];
        distance[i+1]=distance[i]+circle[i];
    }
    scanf("%d",&m);
    for(int j=0;j<m;j++)
    {
        scanf("%d%d",&b,&e);
        low=(b<e?b:e);
        high=(b>e?b:e);
        dis1=distance[high]-distance[low];
        dis2=sum-dis1;
        if(dis1<dis2)
            printf("%d\n",dis1);
        else
            printf("%d\n",dis2);
    }
    return 0;
}

Problem F: A+B和C (15)

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 3886 Solved: 1288

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

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

代码（C++）

#include <cstdio>
int main(){
    int T;
    scanf("%d",&T);
    int num=1;
    while(T--){
        long long a,b,c;
        scanf("%ld%ld%ld",&a, &b, &c);
        if(a + b > c) printf("Case #%d: true\n",num);
        else printf("Case #%d: false\n",num);
        num++;
    }
    return 0;
}

Problem G: 数字分类 (20)

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 3801 Solved: 1080

Description

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

A1 = 能被5整除的数字中所有偶数的和；

A2 = 将被5除后余1的数字按给出顺序进行交错求和，即计算n1-n2+n3-n4...；

A3 = 被5除后余2的数字的个数；

A4 = 被5除后余3的数字的平均数，精确到小数点后1位；

A5 = 被5除后余4的数字中最大数字。

Input

每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N，随后给出N个不超过1000的待分类的正整数。数字间以空格分隔。

Output

对给定的N个正整数，按题目要求计算A1~A5并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。

若其中某一类数字不存在，则在相应位置输出“N”。

Sample Input

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

Sample Output

30 11 2 9.7 9
N 11 2 N 9

代码（C++）

#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <cmath>
using namespace std;
int A[5][1005];
int num[1005];
int main()
{
    int N;
    while(scanf("%d",&N) != EOF)
    {
        int A1_even=0,A2_jiaocuo=0,A3_count=0,A4_count=0,A5_max=0;
        float A4_avg = 0;
        float A4_sum = 0;
        int flag=0;
        int A2_exist = 0;
        for(int i=0;i<N;i++)
        {
            int num;
            cin>>num;
            switch(num%5)//switch语句正合适 
            {
                case 0:
                    if(num % 2==0)
                    {
                        A1_even += num;
                    }
                    break;
                case 1:
                    A2_jiaocuo+=(num * pow((double)(-1),flag));
                    flag++;
                    A2_exist = 1;
                    break;
                case 2:
                    A3_count++;
                    break;
                case 3:
                    A4_count++;
                    A4_sum += num;
                    break;
                case 4:
                    if(A5_max < num)
                        A5_max = num;
                    break;
                default:
                    break;
            }
        //  cout<<flag<<endl;
        }
        A4_avg = A4_sum / A4_count;

        if(A1_even != 0)
            printf("%d ",A1_even);
        else
        {
            printf("N ");
        }
    //********************************A2大坑  
        if(A2_exist ==1)
        {
            printf("%d ",A2_jiaocuo);
        }   
        else
        {
            printf("N ");
        }

        if(A3_count != 0)
            printf("%d ",A3_count);
        else
        {
            printf("N ");
        }

        if(A4_count != 0)
            printf("%0.1lf ",A4_avg);
        else
        {
            printf("N ");
        }
        //行末不得有多余空格 
        if(A5_max != 0)
            printf("%d",A5_max);
        else
        {
            printf("N");
        }
        //cout<<endl;
        printf("\n");
    }
    return 0;   
} 
/*
A1~A5里有些并不是看他们本身是否为零
而是看符合他们要求的数字是否存在
比如A2就是看是否有被5除后余1的数字,如果有,那么无论A2最后的结果如何,都是输出A2本身的值而不是N
*/

Problem H: 部分A+B (15)

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 1512 Solved: 1063

Description

正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6。

现给定A、DA、B、DB，请编写程序计算PA + PB。

Input

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

Output

在一行中输出PA + PB的值。

Sample Input

3862767 6 13530293 3
3862767 1 13530293 8

Sample Output

399
0

代码（C++）

代码1

   #include <iostream>
    #include <stdlib.h>
    #include <cstring>
    using namespace std;
    char A[15],B[15];

    //就简单模拟，字符串遍历，匹配相应的数，按照位数累积即可
    int main()
    {
        int a,b;
        while(scanf("%s%d%s%d",&A, &a, &B, &b) != EOF)
        {
            int lena = strlen(A);
            int lenb = strlen(B);
            int numa=0,numb=0;
            int weight = 1,weightb = 1;
            for(int i=0;i<lena;i++)
            {
                if((A[i]-'0') == a)
                {
                    numa = numa * 10 + a;
                }
            }
            for(int j=0;j<lenb;j++)
            {
                if((B[j]-'0') == b)
                {
                    numb = numb * 10 + b; 
                }
            }
            printf("%d\n",numa+numb);
        }
        return 0;
    }

代码2

#include <iostream>
#include <stdlib.h>
#include <cstring>
using namespace std;
char A[15],B[15];
//法一竟然GG，不晓得要闹哪样
    /*
    int main()
    {
        char a,b;
        while(scanf("%s%s%s%s",&A, &a, &B, &b) != EOF)
        {
            int lena = strlen(A);
            int lenb = strlen(B);
            int numa=0,numb=0;
            int weight = 1,weightb = 1;
            for(int i=0;i<lena;i++)
            {
                if(A[i] == a)
                {
                    numa = numa * 10 + (a - '0');
                }
            }
            for(int j=0;j<lenb;j++)
            {
                if(B[j] == b)
                {
                    numb = numb * 10 + (b - '0'); 
                }
            }
            printf("%d\n",numa+numb);
        }
        return 0;
    }
    */

Problem I: 锤子剪刀布 (20)

Time Limit: 1.000 Sec Memory Limit: 32 MB

Submit: 2287 Solved: 950

Submit Creator:Imported

Description

大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势。

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

Input

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

Output

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

Sample Input

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

Sample Output

5 3 2
2 3 5
B B

代码（C++）

//题目较为繁琐，根据题意模拟
#include <iostream>
#include <stdlib.h>
#include <cstring>
/*
思路：每次输入进行比较。甲负的次数就是乙赢的次数，不用额外记录。最后输出甲乙获胜最多的手势，因为要考虑解不唯一，所以我采用把结果枚举。按字典序，J次数必须大于B和C，C次数必须大于B，可以大于等于B，B大于等于B、J就行。

注意：scanf会把'\n'读入，所以可能输入五组数据，就跳出结果了，要用getchar()来吸收。另外，判断要用if-else，不能用多个if，而没有else，这样会记录次数出现错误。
*/
using namespace std;

int main()
{
    int jiasu=0,jiafa=0,jiaeq=0;
    int jiac=0,jiaj=0,jiab=0,yic=0,yij=0,yib=0;
    int N;
    scanf("%d",&N);
    while(N--)
    {
        getchar();
        char a,b;
        scanf("%c %c",&a,&b);
            if(a == b)
                jiaeq++;
            //甲赢 
            else if(a == 'C' && b =='J')
            {
                jiasu++;
                jiac++;
            }
            else if(a == 'J' && b=='B')
            {
                jiasu++;
                jiaj++;
            }
            else if(a == 'B' && b=='C')
            {
                jiasu++;
                jiab++;
            }
            //乙赢 
            else if(a == 'J' && b=='C')
            {
                jiafa++;
                yic++;
            }
            else if(a == 'B' && b=='J')
            {
                jiafa++;
                yij++;
            }
            else if(a == 'C' && b=='B')
            {
                jiafa++;
                yib++;
            }
        //  cout<<jiasu<<endl;
    }
    printf("%d %d %d\n",jiasu,jiaeq,jiafa);
    printf("%d %d %d\n",jiafa,jiaeq,jiasu);
    //会有多种情况，判断字母序输出
    if(jiaj > jiab && jiaj > jiac)
    {
        printf("%c ",'J');
    }
    else if(jiac>jiab)
    {
        printf("%c ",'C');
    }
    else
    {
        printf("%c ",'B');
    }
    if(yij > yib && yij > yic)
    {
        printf("%c ",'J');
    }
    else if(yic>yib)
    {
        printf("%c ",'C');
    }
    else
    {
        printf("%c ",'B');
    }
    printf("\n");
    return 0;
}