蓝桥杯训练赛（3）_个正整数n表示三角形的高,即三角形占几行,0

目录

7-1 缩位求和

7-2 等腰三角形

7-3 结账问题

7-4 航班时间

7-5 全球变暖

7-6 完全二叉树的权值

7-7 小朋友崇拜圈

*7-8 倍数问题

7-9 递增三元组

*7-10 螺旋折线

*7-11 日志统计

*7-12 乘积最大

*7-13 耐摔指数

*7-14 三体攻击

---

7-1 缩位求和

-第九届蓝桥省赛-C组

在电子计算机普及以前，人们经常用一个粗略的方法来验算四则运算是否正确。

比如：248×15=3720

把乘数和被乘数分别逐位求和，如果是多位数再逐位求和，直到是 1 位数，得

2 + 4 + 8 = 14 ==> 1 + 4 = 5;

1 + 5 = 6

5 * 6

而结果逐位求和为 3

5∗6 的结果逐位求和与 3 符合，说明正确的可能性很大！！（不能排除错误）

请你写一个计算机程序，对给定的字符串逐位求和。

输入格式:

一个由数字组成的串，表示 n 位数。 1≤n≤1000

输出格式:

一位数，表示反复逐位求和的结果。

输入样例:

35379

输出样例:

9

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
string n;
int sum, res;
 
int main()
{
    cin >> n ;
 
    for(int i=0; i<n.size(); i++ ) sum += n[i] - '0';
 
    while(sum>=10)
    {
        res = 0;
        while(sum)
        {
            res += sum%10;
            sum /= 10;
        }
        sum = res;
    }
 
    cout << sum ;
 
    return 0;
}

7-2 等腰三角形

-第九届蓝桥省赛-C组

本题目要求你输出一个由数字组成的等腰三角形。

具体的步骤是：

先用 1,2,3,… 的自然数拼一个足够长的串。 用这个串填充三角形的三条边。从上方顶点开始，逆时针填充。 比如，当三角形高度是 8 时：

输入格式:

一个正整数 n，表示三角形的高度。 3<n<300

输出格式:

输出，用数字填充的等腰三角形。

为了便于测评，我们要求空格一律用 . 代替。

具体，可参照样例。

输入样例:

在这里给出一组输入。例如：

5

输出样例:

在这里给出相应的输出。例如：

....1
...2.1
..3...2
.4.....1
567891011

 代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const int N = 2010;
 
int n;
char s[4], num[N];
char g[N][N];
int t, k=1;
 
void init()
{
    for(int i=1; i<=600; i++)
    {
        t=i;
        if(t<10)
            num[k++] = t + '0';
        else
        {
            int a=0;
            while(t) s[a++] = t%10 + '0', t /= 10;
 
            for(int i=a-1; i>=0; i--) num[k++] = s[i];
        }
    }
}
 
int main()
{
    cin >> n;
 
    init();
    memset(g, '.', sizeof g);
 
    k = 1;
    int x = 4*(n-1) ;
 
    for(int i=1; i<=n; i++)
    {
        if(i<n)
        {
            g[i][n-i+1] = num[k++];
        }
        else
        {
            int z=2*n-1, t=1;
            while(z--) g[n][t++] = num[k++];
        }
        if(i>1) g[i][n+i-1] = num[x--];
 
    }
 
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n+i-1; j++)
            printf("%c",g[i][j]);
        if(i<n) printf("\n");
    }
 
    return 0;
}

7-3 结账问题

-第九届蓝桥省赛-A组

几个人一起出去吃饭是常有的事。但在结帐的时候，常常会出现一些争执。 现在有 n 个人出去吃饭，他们总共消费了 S 元。其中第 i 个人带了 ai 元。幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？

　　为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是1分钱的整数倍。你需要输出最小的标准差是多少。

　　标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :

输入格式:

第一行包含两个整数 n、S；　　第二行包含 n 个非负整数 a1, ..., an。

对于 10% 的数据，所有 ai 相等；

对于 30% 的数据，所有非 0 的 ai 相等；

对于 60% 的数据，n ≤ 1000；

对于 80% 的数据，n ≤ 10^5；

对于所有数据，n ≤ 5 × 10^5, 0 ≤ ai ≤ 10^9，0 ≤S ≤ 10^18

输出格式:

输出到标准输出。

输出最小的标准差，四舍五入保留 4 位小数。 保证正确答案在加上或减去 10^−9 后不会导致四舍五入的结果发生变化。

输入样例:

在这里给出一组输入。例如：

10 30
2 1 4 7 4 8 3 6 4 7

输出样例:

在这里给出相应的输出。例如：

0.7928

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
const int N = 502000;
 
int n;
long long s;
long double sum;
int a[N];
 
int main()
{
    cin >> n >> s ;
 
    for(int i=0; i<n; i++ ) scanf("%d",&a[i]);
 
    sort(a, a+n);
 
    long double p = s*1.0/n, p1 = p;
 
    for(int i=0; i<n; i++ )
    {
        if(a[i] <= p1)
        {
            s -= a[i];
            sum += (a[i]-p)*(a[i]-p);
            p1 = s*1.0/(n-i-1);
        }
        else sum += (p1-p)*(p1-p);
    }
 
    printf("%.4Lf", sqrt(sum/n));
 
    return 0;
}

7-4 航班时间

-第九届蓝桥省赛-A组 (100 分)

小 h 前往美国参加了蓝桥杯国际赛。

小 h 的女朋友发现小 h 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。

仔细观察后发现飞机的起降时间都是当地时间。

由于北京和美国东部有 12 小时时差，故飞机总共需要 14 小时的飞行时间。

不久后小 h 的女朋友去中东交换。

小 h 并不知道中东与北京的时差。

但是小 h 得到了女朋友来回航班的起降时间。

小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班，给定来回程的起降时间。

假设飞机来回飞行时间相同，求飞机的飞行时间。

输入格式:

一个输入包含多组数据。

输入第一行为一个正整数 T，表示输入数据组数。

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下:

h1:m1:s1 h2:m2:s2

h1:m1:s1 h3:m3:s3 (+1)

h1:m1:s1 h4:m4:s4 (+2)

第一种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间当日h2时m2分s2秒降落。

第二种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间次日h2时m2分s2秒降落。

第三种格式表示该航班在当地时间h1时m1分s1秒起飞，在当地时间第三日h2时m2分s2秒降落。

保证输入时间合法（0≤h≤23,0≤m,s≤59），飞行时间不超过24小时。

输出格式:

对于每一组数据输出一行一个时间hh:mm:ss，表示飞行时间为hh小时mm分ss秒。

注意，当时间为一位数时，要补齐前导零，如三小时四分五秒应写为03:04:05。

输入样例:

3
17:48:19 21:57:24
11:05:18 15:14:23
17:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:24
22:19:04 16:41:09 (+1)

输出样例:

04:09:05
12:10:39
14:22:05

代码如下：

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int get_time()
{
    int h1, m1, s1, h2, m2, s2, d=0;
    scanf("%d:%d:%d %d:%d:%d (+%d)",&h1, &m1, &s1, &h2, &m2, &s2, &d);
 
    int t = (h2+d*24)*3600 + m2*60 + s2 - h1*3600 - m1*60 - s1;
 
    return t;
}
 
int main()
{
    int n;
    cin >> n;
    while(n -- )
    {
        int time1 = get_time();
        int time2 = get_time();
        int time = (time1+time2)/2;
        int h = time/3600, m = time/60%60, s = time%60;
        printf("%02d:%02d:%02d\n",h, m, s);
    }
 
    return 0;
}

7-5 全球变暖

-第九届蓝桥省赛-AB组 (100 分)

你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......

.##....

.##....

....##.

..####.

...###.

.......

其中“上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。

具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。

例如上图中的海域未来会变成如下样子：

.......

.......

.......

.......

....#..

.......

.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式:

第一行包含一个整数N。 1≤N≤1000。

以下 N 行 N 列，包含一个由字符”#”和”.”构成的 N×N 字符矩阵，代表一张海域照片，”#”表示陆地，”.”表示海洋。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式:

一个整数表示答案。

输入样例:

7
.......
.##....
.##....
....##.
..####.
...###.
.......

输出样例:

1

#include <iostream>
#include <cstdio>
 
using namespace std;
 
const int N = 1010;
 
int n;
char g[N][N];
int res, f;
bool st[N][N];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
 
void dfs(int i, int j)
{
    st[i][j] = true;
 
    if(g[i][j+1]=='#' && g[i][j-1]=='#' && g[i+1][j]=='#' && g[i-1][j]=='#')
        f = 1;
 
    for(int k=0; k<4; k++)
    {
        int x=i+dx[k], y=j+dy[k];
        if(g[x][y]=='#' && !st[x][y])
            dfs(x,y);
    }
}
 
int main()
{
    cin >> n ;
 
    for(int i=0; i<n; i++ )
    {
        scanf("%s",g[i]);
    }
 
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(g[i][j]=='#' && st[i][j]==false)
            {
                f = 0;
                dfs(i,j);
                if(!f) res++;
            }
        }
    }
 
    cout << res <<endl;
 
    return 0;
}
 
 
 

7-6 完全二叉树的权值

-第十届蓝桥省赛-B组 (100 分)

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1,A2,⋅⋅⋅AN，如下图所示：

现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大？

如果有多个深度的权值和同为最大，请你输出其中最小的深度。

注：根的深度是 1。

输入格式:

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅AN。

1≤N≤10^5 , −10^5≤Ai≤10^5

输出格式:

输出一个整数代表答案。

输入样例:

在这里给出一组输入。例如：

7
1 6 5 4 3 2 1

输出样例:

在这里给出相应的输出。例如：

2

 代码如下：

#include <iostream>
#include <climits>
#include <cstdio>
 
using namespace std;
 
const int N = 500010;
 
int n;
int a[N];
int max1 = INT_MIN;
int res;
 
int main()
{
    cin >> n ;
 
    for(int i=1; i<=n; i++ ) scanf("%d",&a[i]);
 
    for(int i=1, d=1; i<=n; i*=2, d++ )
    {
        long long sum=0;
        for(int j=i; j<=i*2-1 && j<=n; j++ )
        {
            sum += a[j];
        }
        if(sum > max1)
        {
            max1 = sum;
            res = d;
        }
    }
 
    cout << res << endl;
 
    return 0;
}

7-7 小朋友崇拜圈

-第九届蓝桥省赛-C组 (100 分)

班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。

在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。

求满足条件的圈最大多少人？

小朋友编号为 1,2,3,…N。

输入格式:

第一行，一个整数 N。 3<N<10^5

接下来一行 N 个整数，由空格分开。

输出格式:

输出一个整数，表示满足条件的最大圈的人数。

输入样例:

在这里给出一组输入。例如：

9
3 4 2 5 3 8 4 6 9

输出样例:

在这里给出相应的输出。例如：

4

思路：

记录人在每条圈的序号，当再次遍历到此人时，算两序号之间的人数即可

代码如下：

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
 
const int N = 2e5 + 10, mod = 1e9 + 7;
 
int ans;
int n;
int p[N];
bool st[N];
int ac[N];
 
void dfs(int u, int cnt)
{
    ac[u] = cnt;
    st[u] = true;
    if( st[p[u]] )
    {
        ans = max(ans, ac[u] - ac[p[u]] + 1);
        return;
    }
 
    dfs(p[u], ++cnt);
    ac[u] = 0;
    st[u] = false;
}
 
void solve()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
        scanf("%d", &p[i]);
 
    for(int i = 1; i <= n; i ++ )
    {
        dfs(i, 0);
    }
 
    cout << ans << endl;
}
 
int main()
{
        solve();
 
    return 0;
}

*7-8 倍数问题

-第九届蓝桥省赛-A组 (100 分)

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。

但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。

现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数，使得这三个数的和是 K 的倍数，且这个和最大。

数据保证一定有解。

输入格式:

第一行包括 2 个正整数 n, K。

第二行 n 个正整数，代表给定的 n 个数。

1≤n≤10^5 , 1≤K≤10^3, 给定的 n 个数均不超过 10^8

输出格式:

输出一行一个整数代表所求的和。

输入样例:

4 3
1 2 3 4

输出样例:

9

7-9 递增三元组

-第九届蓝桥省赛-B组 (100 分)

给定三个整数数组

A=[A1,A2,…AN],

B=[B1,B2,…BN],

C=[C1,C2,…CN],

请你统计有多少个三元组 (i,j,k) 满足：

1≤i,j,k≤N，Ai<Bj<Ck

输入格式:

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

1≤N≤10^5 , 0≤Ai,Bi,Ci≤10^5

输出格式:

一个整数表示答案。

输入样例:

3
1 1 1
2 2 2
3 3 3
									 

输出样例:

27

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
const int N = 500010;
 
int n;
int a[N], b[N], c[N];
long long sum;
 
int main()
{
    cin >> n ;
    
    for(int i=1; i<=n; i++ ) scanf("%d",&a[i]);
    for(int i=1; i<=n; i++ ) scanf("%d",&b[i]);
    for(int i=1; i<=n; i++ ) scanf("%d",&c[i]);
    
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    sort(c+1, c+n+1);
    
    for(int i=1; i<=n; i++ )
    {
        int x, y;
        x = lower_bound(a+1,a+n+1,b[i])-a -1; // 返回第一次出现 大于等于 那个要查找的数的地址
        y = n -( upper_bound(c+1,c+n+1,b[i])-c ) +1;//返回第一次出现 大于 那个要查找的数的地址
        sum += (long long)x*y;
    }
    
    cout << sum << endl;
    
    return 0;
}

*7-10 螺旋折线

-第九届蓝桥省赛-B组 (100 分)

如下图所示的螺旋折线经过平面上所有整点恰好一次。

对于整点 (X,Y)，我们定义它到原点的距离 dis(X,Y) 是从原点到 (X,Y) 的螺旋折线段的长度。

例如 dis(0,1)=3,dis(−2,−1)=9

给出整点坐标 (X,Y)，你能计算出 dis(X,Y) 吗？

输入格式:

包含两个整数 X,Y。 −10^9≤X,Y≤10^9

输出格式:

输出一个整数，表示 dis(X,Y)。

输入样例:

0 1

输出样例:

3

 代码如下：

*7-11 日志统计

-第九届蓝桥省赛-B组 (100 分)

小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id
表示在 ts 时刻编号 id 的帖子收到一个”赞”。

现在小明想统计有哪些帖子曾经是”热帖”。

如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。

给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式:

第一行包含三个整数 N,D,K。

以下 N 行每行一条日志，包含两个整数 ts 和 id。

1≤K≤N≤10^5, 0≤ts,id≤10^5, 1≤D≤10000

输出格式:

按从小到大的顺序输出热帖 id。

每个 id 占一行。

输入样例:

在这里给出一组输入。例如：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例:

在这里给出相应的输出。例如：

1
3

*7-12 乘积最大

-第九届蓝桥省赛-B组 (100 分)

给定 N 个整数 A1,A2,…AN。

请你从中选出 K 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。

注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)

输入格式:

第一行包含两个整数 N 和 K。

以下 N 行每行一个整数 Ai。 1 ≤ K ≤ N ≤ 10^5, −10^5 ≤ Ai ≤ 10^5

输出格式:

输出一个整数，表示答案。

输入样例:

5 3
-100000
-10000
2
100000
10000

输出样例:

在这里给出相应的输出。例如：

999100009

*7-13 耐摔指数

-第九届蓝桥省赛-C组 (100 分)

x 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。

各大厂商也就纷纷推出各种耐摔型手机。

x 星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。

塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 2 楼。

如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指数 =7。

特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 =0。

如果到了塔的最高层第 n 层扔没摔坏，则耐摔指数 =n。

为了减少测试次数，从每个厂家抽样 3 部手机参加测试。

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？一个整数 n，表示测试塔的高度。

例如，输入的n为3，则输出2。因为测试过程如下：手机 a 从 2 楼扔下去，坏了，就把 b 手机从 1 楼扔；否则 a 手机继续 3 层扔下。

若输入n为7，则输出 3。测试过程如下：a 手机从 4 层扔，坏了，则下面有 3 层，b,c 两部手机 2 次足可以测出指数；若是没坏，手机充足，上面 5,6,7 三层 2 次也容易测出。

输入格式:

一个整数 n，表示测试塔的高度。 3≤n≤10000

输出格式:

一个整数，表示最多测试多少次。

输入样例:

在这里给出一组输入。例如：

3

输出样例:

在这里给出相应的输出。例如：

2

*7-14 三体攻击

-第九届蓝桥省赛-A组 (100 分)

 在下方的输入样例中，因为在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。故输出2。

输入样例:

2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

输出样例:

在这里给出相应的输出。例如：

2