NEUQ2020-ACM实验班-训练002

痛定思痛。 2021-09-07 06:00 389阅读 0赞

# 数字三角形+字母塔+字母表+Matrix+ Jumping Frog（跳蛙）+求两圆相交的面积+看电影+谷歌的招聘+汉诺塔问题+表达式求值 #

### 文章目录 ###

*  数字三角形+字母塔+字母表+Matrix+ Jumping Frog（跳蛙）+求两圆相交的面积+看电影+谷歌的招聘+汉诺塔问题+表达式求值
 *   *  7-1 数字三角形 (10分)
     *  7-2 字母塔 (10分)
     *  7-3 字母表 (10分)
     *  7-4 Matrix (10分)
     *  7-5 Jumping Frog（跳蛙） (10分)
     *  7-6 求两圆相交的面积 (10分)
     *  7-7 看电影 (10分)
     *  7-8 谷歌的招聘 (10分)
     *  7-9 汉诺塔问题 (10分)
     *  7-10 表达式求值 (10分)

## 7-1 数字三角形 (10分) ##

> 观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。
> 
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70]
> 
> 在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。  
> **输入格式:**
> 
> 第一个行包含R(1≤ R≤1000)，表示行的数目。
> 
> 后面每行为这个数字金字塔特定行包含的整数。
> 
> 所有的被供应的整数是非负的且不大于100。  
> **输出格式:**
> 
> 单独的一行，包含那个可能得到的最大的和。  
> **输入样例:**
> 
> 5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11
> 
> **输出样例:**
> 
> 86

题解：

#include<iostream>
    using namespace std;
    int a[1001][1001];//存放数塔
    int main()
    { 
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        { 
            for(int j=1;j<=i;j++)cin>>a[i][j];
        }
        for(int i=n-1;i>=1;i--)
        { 
            for(int j=1;j<=i;j++)
            { 
                a[i][j]+=max(a[i+1][j],a[i+1][j+1]);//自底向上找最大值更新数塔
            }
        }
        cout<<a[1][1];
        return 0;
    }

## 7-2 字母塔 (10分) ##

> 请编写程序，显示字母塔。 输入格式
> 
>     高度(不超过 26 的正整数)
> 
> **输出格式**
> 
>     显示指定高度的字母塔
> 
> **输入样例**
> 
> 5
> 
> **输出样例**
> 
>     A    
>        ABA   
>       ABCBA  
>      ABCDCBA 
>     ABCDEDCBA

题解：

//其实很简单，多试几次就好了
    #include<iostream>
    using namespace std;
    int main()
    { 
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        { 
            char x='A';
            for(int j=n-i;j>0;j--)cout<<" ";
            for(int j=1;j<=i;j++)
            { 
                cout<<x;
                x=x+1;
            }
            x=x-1;
            for(int j=1;j<i;j++)
            { 
                x=x-1;
                cout<<x;
            }
            cout<<endl;
        }
    }

## 7-3 字母表 (10分) ##

> 我们定义一个小写字符串是“按字母表的”，当且仅当它删除掉一些字符后，可以变为”abcdefghijklmnopqrstuvwxyz”。  
> 给定一个长度为n的小写字母字符串，至少插入多少个字符才能使其变成“按字母表的”。 输入格式:
> 
> 输入第一行为一个整数T（1<=T<=100），代表测试数据的组数，随后T行，每行都是由小写字母’a’-'z’组成的一串字符s  
> (1=<|n|<=50)。  
> **输出格式:**
> 
> 输出为了让s变成“按字母表的”，至少要插入的字符个数，每组输出占一行。  
> **输入样例:**
> 
> 2 xyzabcdefghijklmnopqrstuvw aiemckgobjfndlhp
> 
> **输出样例:**
> 
> 3 20

题解：

//当作最长上升子序列
    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    string q;
    ll dp[105];
    int main()
    { 
    	int t;
    	cin>>t;
    	while(t--)
    	{ 
    		cin>>q;
            for (int i=0;i<105;i++)
    		{ 
    			dp[i] = 1;
    		}
    		for (int i=0; i <q.size(); i++)
    		{ 
    			for (int j=0;j<i;j++)
    			{ 
    				if (q[i]>q[j])
    				{ 
    					dp[i]=max(dp[i], dp[j]+1);
    				}
    			}
    		}
    		sort(dp,dp+105);
    		cout<<26-dp[104]<<endl;		
    	}
    	return 0;
    }

## 7-4 Matrix (10分) ##

> Give you an N \* N matrix, fill in the number of 1 to N \* N in order,  
> for example N = 5, the matrix is as follows
> 
> ![4AD3FD2F-DDE7-4113-BF7D-E71E57273309.png][]
> 
> Now let you connect the midpoints of the adjacent two sides, and then  
> only keep the numbers they enclose in the closed graphics area, then  
> the matrix becomes
> 
> ![7C32F25E-1E11-4AFE-BF4A-1484A911688C.png][]
> 
> Now ask you for the sum of all the elements of the changed matrix.  
> **输入格式:**
> 
> Input the first line of an integer T (1 <= T <= 100) Next, there is a  
> group test data, and each set of test data is input with an integer N  
> (3 <= N <= 10000) Guaranteed input n is odd  
> **输出格式:**
> 
> For each set of test data, output the corresponding answer  
> **输入样例:**
> 
> 在这里给出一组输入。例如：
> 
> 2 3 5
> 
> **输出样例:**
> 
> 在这里给出相应的输出。例如：
> 
> 25 169

题解：

//找规律水题
    #include<iostream>
    using namespace std;
    int main()
    { 
        long long  n;
        cin>>n;
        while(n--)
        { 
            long long  m;
            cin>>m;
            cout<<(1+m*m)/2*(1+m*m)/2<<endl;
        }
    }

## 7-5 Jumping Frog（跳蛙） (10分) ##

> A frog is located at the coordinate (x1,y1). He wants to go to the  
> coordinate (x2,y2). He will perform one or more jumps to reach his  
> destination. The rule of the jumping is as follows:
> 
> 青蛙位于坐标（x1，y1）处，他想转到坐标（x2，y2），他将进行一次或多次跳跃以到达目的地。跳跃规则如下：
> 
> Suppose the frog is located at the coordinate (x,y); then he can jump  
> to the following foursquares:
> 
> 假设青蛙位于坐标（x，y）处；然后他可以跳到以下四个方格：
> 
>     (x+y,y)
>     (x-y,y)
>     (x,y+x)
>     (x,y-x)
> 
> **The Problem: (存在的问题:)**
> 
> Given the coordinates (x1,y1) and (x2,y2), you need to determine if it  
> is possible for the frog to travel from (x1,y1) to (x2,y2) through a  
> series of jumps as described.
> 
> 给定坐标（x1，y1）和（x2，y2），您需要确定青蛙是否有可能通过一系列跳跃从（x1，y1）移动到（x2，y2）。 The Input:
> 
> The first input line contains an integer, n (1 ≤ n ≤ 100), indicating  
> the number of test cases.
> 
> 第一个输入行包含一个整数n(1≤n≤100)，表示测试用例的数量。
> 
> Each test case consists of four integers (between -1,000,000,000 to  
> \+1,000,000,000 inclusive) separated by a single space denoting x1, y1, x2 and y2, respectively.
> 
> 每个测试用例由四个整数(从-1,000,000,000到+1,000,000,000之间)组成，它们之间由一个单独的空格分隔，分别表示x1、y1、x2和y2。  
> **The Output:**
> 
> For each test case, output 1 if the frog can travel from (x1,y1) to  
> (x2,y2) through a series of jumps as described or 0 otherwise.
> 
> 对于每个测试用例，如果青蛙可以通过描述的一系列跳跃从(x1,y1)移动到(x2,y2)，则输出1，否则输出0。  
> **Sample Input:**
> 
> 3  
> \-6 8 17 25 13 17 -16 11 0 0 5 6
> 
> **Sample Output:**
> 
> 0 1 0

题解：

//由题意知他每次能移动的位移是其坐标的最大公因数的k倍，所以只要最大公因数相同即可
    #include <bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    int gcd(ll a,ll b)
    { 
        if(b==0)return a;
        else return gcd(b,a%b);
    }//gcd求最大公因数
    int main()
    { 
    	ll n,x1,x2,y1,y2;
    	cin>>n;
    	while(n--)
        { 
    		cin>>x1>>y1>>x2>>y2;
    		if(gcd(abs(x1),abs(y1))==gcd(abs(x2),abs(y2)))cout<<1<<endl;
    		else cout<<0<<endl;
    	}	
    	return 0;
    }

## 7-6 求两圆相交的面积 (10分) ##

> 给定2圆的圆心坐标和半径，计算并输出两圆相交的面积，如果是外切或不相交，则输出0，圆周率取函数值acos(-1)。  
> **输入格式:**
> 
> 输入6个整数x1 y1 r1 x2 y2 r2，分别表示两圆的圆心(x1,y1),(x2,y2)和半径r1,r2。  
> **输出格式:**
> 
> 根据圆的位置关系，输出其相交部分的面积（保留2位小数）。  
> **输入样例:**
> 
> 在这里给出2组输入。例如：
> 
> 0 0 1 2 2 1
> 
> 2 0 2 5 2 3
> 
> **输出样例:**
> 
> 在这里给出相应的输出。例如：
> 
> 0.00
> 
> 3.22

题解：附一份手写推导（还在路上）

#include<iostream>
    #include<math.h>
    using namespace std;
    int main()
    { 
        int x1,y1,r1,x2,y2,r2;
        cin>>x1>>y1>>r1>>x2>>y2>>r2;
        double d=sqrt(pow((x1-x2),2)+pow((y1-y2),2));
        if(d>=r1+r2)printf("%.2lf",0);//外切和相离
        else if(d<=r1-r2)printf("%.2lf",acos(-1.0)*r2*r2);//两圆内切，r2小
        else if(d<=r2-r1)printf("%.2lf",acos(-1.0)*r1*r1);//两圆内切，r1小
        else//相交
        { 
            double angle1=acos((r1*r1+d*d-r2*r2)/(2*r1*d));//左扇区对应角度
            double angle2=acos((r2*r2+d*d-r1*r1)/(2*r2*d));//右扇区对应角度
            double s1=angle1*r1*r1;//左扇区对应面积
            double s2=angle2*r2*r2;//右扇区对应面积
            double s3=r1*d*sin(angle1);//四边形面积
            printf("%.2lf",s1+s2-s3);
        }
    }

## 7-7 看电影 (10分) ##

> 终于到周末了，明明是特别喜欢看电影。他想在一天内尽量多的看到完整的多部电影。 现在他把他喜欢的电影的播放时间表给你，希望你能帮他合理安排。  
> **输入格式:**
> 
> 输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示明明喜欢的电影的总数。  
> 接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个电影的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。  
> 当n=0时，输入结束。  
> **输出格式:**
> 
> 对于每组输入，输出能完整看到的电影的个数。  
> **输入样例:**
> 
> 在这里给出一组输入。例如：
> 
> 12  
> 1 3  
> 3 4  
> 0 7  
> 3 8  
> 15 19  
> 15 20  
> 10 15  
> 8 18  
> 6 12  
> 5 10  
> 4 14  
> 2 9  
> 0
> 
> **输出样例:**
> 
> 在这里给出相应的输出。例如：
> 
> 5

题解：

#include<iostream>
    #include<algorithm>
    using namespace std;
    struct film
    { 
        int a;
        int b;
    };
    bool cmp(film x, film y)
    { 
        return x.b < y. b;
    }
    int main()
    { 
        int n;
        while(cin>>n)
        { 
            if(n==0)break;
            int sum=0,i;
            film f[101];
            for(i=0;i<n;i++)cin>>f[i].a>>f[i].b;
            sort(f,f+n,cmp);//对结束时间进行排序
            int m=0;
            for(i=0;i<n;i++)
            { 
                if(f[i].a>=m)//从启示时间遍历
                { 
                    sum++;
                    m=f[i].b;
                }
            }
        cout<<sum<<endl;
        }
        return 0;
    }

## 7-8 谷歌的招聘 (10分) ##

> 2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com  
> 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10  
> 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。
> 
> ![prime.jpg][]
> 
> 自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e =  
> 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。
> 
> 本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。  
> **输入格式：**
> 
> 输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于 10 的正整数）。接下来一行给出一个长度为  
> L 的正整数 N。  
> **输出格式：**
> 
> 在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出  
> 404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成0002 输出，因为在原始数字中不存在这个 2 的前导零。  
> **输入样例 1：**
> 
> 20 5 23654987725541023819
> 
> **输出样例 1：**
> 
> 49877
> 
> **输入样例 2：**
> 
> 10 3 2468024680
> 
> **输出样例 2**：
> 
> 404

题解：

#include<bits/stdc++.h>
    using namespace std;
    bool isprime(int n)
    { 
        if (n<=1)//特判1不是质数
        { 
            return false;
        }
        for(int i=2;i*i<=n;i++)
        { 
            if(n%i==0)
            { 
                return false;
            }
        }
        return true;
    }
    int main()
    { 
    	int a,b,n;
    	cin>>a>>b;
        string s,s2;
        cin>>s;
    	for(int i=0;i<=a-b;i++)
        { 
    		s2=s.substr(i,b);//从下标为i开始截取长度为b位
    		n=stoi(s2);//string to int 字面意思
    		if(isprime(n))
            { 
    			cout<<s2<<endl;
    			return 0;
    		}
    	}
    	cout<<"404"<<endl;
    	return 0;
    }

## 7-9 汉诺塔问题 (10分) ##

> 汉诺塔是一个源于印度古老传说的益智玩具。据说大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘，大梵天命令僧侣把圆盘移到另一根柱子上，并且规定：在小圆盘上不能放大圆盘，每次只能移动一个圆盘。当所有圆盘都移到另一根柱子上时，世界就会毁灭。
> 
> 请编写程序，输入汉诺塔圆片的数量，输出移动汉诺塔的步骤。  
> **输入格式**
> 
>     圆盘数 起始柱 目的柱 过度柱
> 
> **输出格式**
> 
>     移动汉诺塔的步骤
>     每行显示一步操作，具体格式为：
>     盘片号: 起始柱 -> 目的柱
>     其中盘片号从 1 开始由小到大顺序编号。
> 
> **输入样例**
> 
> 3 a c b
> 
> **输出样例**
> 
> 1: a -> c 2: a -> b 1: c -> b 3: a -> c 1: b -> a 2: b -> c 1: a -> c

题解：

//运用整体思想，把最下面盘和上面所有盘看作两部分，循环递归
    #include<iostream>
    using namespace std;
    void hano(int n,char x,char y,char z)//起始柱 目的柱 过度柱 
    {  
    	if(n==1)printf("%d: %c -> %c\n",n,x,y);
    	else
        { 
    		hano(n-1,x,z,y);  
    		printf("%d: %c -> %c\n",n,x,y);
    		hano(n-1,z,y,x);
    	}
    } 
    int main(){ 
    	int n;
    	char x,y,z;
    	cin>>n>>x>>y>>z;
    	hano(n,x,y,z);	
    }

## 7-10 表达式求值 (10分) ##

> 机器人卡多掌握了加减法运算以后，最近由学会了一些简单的函数求值。比如，它知道函数min(20, 23)的值是20, add(10,  
> 98)的值是108等等。经过训练，机器人卡多甚至会计算一种嵌套的更复杂的表达式。
> 
> 假设表达式可以简单定义为： 1、 一个正的十进制数x是一个表达式。 2、 如果x和y是表达式，则函数min(x,  
> y)也是表达式，其值为x，y中的最小数。 3、 如果x和y是表达式，则函数max(x, y)也是表达式，其值为x，y中的最大数。 4、  
> 如果x和y是表达式，则函数add(x,y)也是表达式，其值为x，y之和。 5、  
> 如果x和y是表达式，则函数sub(x,y)也是表达式，其值为x，y之差。 例如，表达式 max(add(1,2),7)的值为7。
> 
> 请你编写程序，对于给定的一组表达式，帮助Dr.Kong算出正确答案，以便校对卡多计算的正误。 **输入格式:**
> 
> 第一行：N表示要计算的表达式个数(1≤N≤10) 接下来有N行，每行是一个字符串，表示待求值的表达式。  
> （表达式中不会有多余的空格，每行不超过300个字符，表达式中出现的十进制数都不超过1000）。  
> **输出格式:**
> 
> 输出有N行，每一行对应一个表达式的值。  
> **输入样例:**
> 
> 在这里给出一组输入。例如：
> 
> 3 add(1,2) sub(1,999) add(min(1,1000),add(100,99))
> 
> **输出样例:**
> 
> 在这里给出相应的输出。例如：
> 
> 3  
> \-998 200

题解：

#include <iostream>
    #include <stack>
    #include <cstring>
     
    using namespace std;
     
    const int N = 103100;
     
    stack <int> op;
    // 存储add, max, min, sub 这些运算符
    // add = -1, sub = -2, min = -3 , max = -4
    stack <int> number;
    // 存储整数
     
    char a[N];
     
    int main()
    { 
        int T;
        cin >> T;
        for(int t=1; t<=T; t++) { 
    		memset(a,0,sizeof(a));
            cin >> a;
            int len =strlen(a); // len 字符串a 的长度
            for(int i=0; i<len; i++) { 
                if(a[i] == ')') // 找到 ')' 前面为目前的最小项
                {  // 把最小项转换成数值入栈
                    int optemp = op.top();
                    op.pop();
                    int x = number.top();
                    number.pop();
                    int y = number.top();
                    number.pop();
     
                    if(optemp == -1) number.push(x+y);
                    else if(optemp == -2) number.push(y-x);
                    else if(optemp == -3) number.push(min(x,y));
    				else if(optemp == -4) number.push(max(x,y));
                }
                else if(a[i] == 'a' && a[i+1] == 'd') // 找到add, op 入栈 -1
                    op.push( -1 );
                else if(a[i] == 's' && a[i+1] == 'u') // 找到sub, op 入栈 -2
                    op.push( -2 );
                else if(a[i] == 'm' && a[i+1] == 'i') // 找到min, op 入栈 -3
                    op.push( -3 );
    			else if(a[i] == 'm' && a[i+1] == 'a')
    				op.push( -4 );
                else if(isdigit(a[i])) {  // 找到数字，求他的值，入栈到 number
                    int temp = 0;
                   while(isdigit(a[i])) { 
                        temp = temp*10 + a[i]-'0';
                        i++;
                   }
                   i--;
                   number.push(temp);
                }
            }
            cout << number.top() << endl;
            number.pop();
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwMjE2Mjcw_size_16_color_FFFFFF_t_70]: /images/20210827/007bf1b34801404b95dd767c38cadfe7.png
[4AD3FD2F-DDE7-4113-BF7D-E71E57273309.png]: /images/20210827/7918a495d59f48dab16e80b0ecbc8065.png
[7C32F25E-1E11-4AFE-BF4A-1484A911688C.png]: /images/20210827/b83ae4d9111c47afbb7d8d5268bc0777.png
[prime.jpg]: /images/20210827/1cc08e238fa242eabc51800a0671a097.png