当前位置:   article > 正文

蓝桥杯第一场算法双周赛(1~3题)_第1场小白入门赛-蓝桥云课2.构造数字【算法赛]-蓝!2.构造数字【算法赛]问题

第1场小白入门赛-蓝桥云课2.构造数字【算法赛]-蓝!2.构造数字【算法赛]问题

本人能力有限,只做出前三题。有时间会看一下后面三题。
前两题很简单,直接上代码,第三题用到了二分法(有详解)。

1. 三带一【算法赛】

问题描述

小蓝和小桥玩斗地主,小蓝只剩四张牌了,他想知道是否是“三带一”牌型。所谓“三带一”牌型,即四张手牌中,有三张牌一样,另外一张不与其他牌相同,换种说法,四张手牌经过重新排列后,可以组成 A A A B AAAB AAAB 型。

输入格式

第一行输入一个整数 T T T ,代表斗地主的轮数。接下来 T T T 行,每行输入一个长度为 4 4 4 的字符串,代表小蓝的手牌。字符 { 'A','2','3','4','5','6','7','8','9','X','J','Q','K' } 对应代表牌面 { A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , J , Q , K A, 2, 3, 4, 5, 6, 7, 8, 9,10, J, Q, K A,2,3,4,5,6,7,8,9,10,J,Q,K } 。牌面中不包含大小王。

输出格式

输出 T T T 行,每行一个字符串,如果当前牌是“三带一”牌型,输出 Yes ,否则输出 No

样例输入

    5
    AAAA
    33X3
    JQKX
    6566
    KKKQ
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

样例输出

    No
    Yes
    No
    Yes
    Yes
  • 1
  • 2
  • 3
  • 4
  • 5
说明“四炸”牌型不属于“三带一”牌型。

评测数据范围

数据范围: 1 ≤ T ≤ 50 1 \le T \le 50 1T50 。字符中只包含:{ A , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , X , J , Q , K A, 2, 3, 4, 5, 6, 7, 8, 9, X, J, Q, K A,2,3,4,5,6,7,8,9,X,J,Q,K } 。

AC代码

只需要判断是否存在三个相同字符即可。

signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        map<char, int> m;
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i++)
        {
            m[s[i]]++;
        }
        bool f = false;
        for (auto i : m)
        {
            if (i.second == 3)
            {
                cout << "Yes" << endl;
                f = true;
                break;
            }
        }
        if (!f) cout << "No" << endl;
    }
    return 0;
}
  • 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

2. 数树数【算法赛】

问题描述

小蓝最近学了二叉树,他想到了一个问题。
给定一个层数为 n n n 的满二叉树,每个点编号规则如下:具体来说,二叉树从上向下数第 p p p 层,从左往右编号分别为: 1 , 2 , 3 , 4... 2 p − 1 1,2,3,4...2^{p-1} 1,2,3,4...2p1 。\n\n小蓝给你一条从根节点开始的路径,他想知道到达的节点编号是多少。例如:路径是 r i g h t − l e f t right-left rightleft ,那么到达的节点是 1 − 2 − 3 1-2-3 123 ,最后到了三号点。

输入格式

第一行输入两个整数 n , q n,q n,q n n n 表示完全二叉树的层数, q q q 代表询问的路径数量。接下来 q q q 行,每行一个字符串 S S S S S S 只包含字符 { 'L','R' },'L' 代表向左,R 代表向右。

输出格式

输出 q q q 行,每行输出一个整数,代表最后到达的节点编号。

样例输入

3 6 R L LL LR RL RR

样例输出

2 1 1 2 3 4

说明

2 ≤ n ≤ 20 , 1 ≤ q ≤ 1 0 3 , 1 ≤ ∣ S ∣ < n 2 \le n \le 20, 1 \le q \le 10^3, 1 \le |S| \lt n 2n20,1q103,1S<n
完全二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 K K K ,且节点总数是 2 k − 1 2^k-1 2k1 ,则它就是满二叉树。

思路

简单提示一下,多花几层二叉树,观察一下就可以发现,走R的话是当前结点编号* 2,走L的话,是2* 当前结点编号-1。

AC代码

signed main()
{
    int n, t;
    cin >> n >> t;
    while (t--)
    {
        int k = 1;
        string s;
        cin >> s;
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == 'R') k *= 2;
            else k = 2*k - 1;
        }
        cout << k << endl;
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

3. 分组【算法赛】

问题描述

蓝桥小学要进行弹弹球游戏,二年级一班总共有 n n n 个同学,要求分成 k k k 个队伍,由于弹弹球游戏要求队员的身高差不能太大,小蓝是班长,他对这个事情正在发愁,他想问你,如何最小化每个组之间的身高极差。具体的,假设分成了 k k k 个组,第 i i i 组最高的人身高是 H x i Hx_i Hxi ,最矮的是 H n i Hn_i Hni,你被要求最小化表达式: $\underset{1 \leq i \leq k}{\max} (Hx_i-Hn_i) $ 。直白来说,你需要将 n n n 个元素分出 k k k 组,使得最大的极差尽可能小。你需要输出这个最小化后的值。

输入格式

第一行输入两个整数 n , k n, k n,k
第二行输入 n n n 个整数: h 1 , h 2 , h 3 . . . h n h_1, h_2,h_3...h_n h1,h2,h3...hn ,分别代表 n n n 个人的身高。

输出格式

输出一个整数,代表最小值。

样例输入

5 3
8 4 3 6 9
  • 1
  • 2

样例输出

1
  • 1

说明

样例分组情况:{ 3 , 4 3,4 3,4 } ,{ 6 6 6 } ,{ 8 , 9 8,9 8,9 } 。

评测数据规模

数据范围: 1 ≤ k ≤ n ≤ 1 0 5 , 1 ≤ h i ≤ 1 0 9 1\le k \le n \le 10^5, 1 \le h_i \le10^9 1kn105,1hi109

解题思路

读了一遍题,没什么思路,再读一遍,观察数据,可以发现最小的极差和最大的极差都是可以确定的,最小的就是0,很好理解,最大的就是h[n-1] - h[0](或者无脑一些直接1e9)。这样大的数据范围,立马就想到用二分来做。这里,我们二分的是可能的最小化极差。然后就该构造二分答案的check()函数了,在二分的过程中,我们必须保证分成的组数为k,那如何实现呢?

只需将排序后的数组进行遍历,记录当前组的最矮身高,如果当前成员身高在该组中与最矮成员身高差大于mid,则将其重新分一组。最后看组数是否小于等于k

为什么要小于等于k呢?而不是大于等于?

极差相同的情况下,分的组越少,说明情况越乐观,如过满足cnt<=k,说明mid符合条件,我们还能进一步缩小右侧范围,看看比mid小的部分能否满足条件(我们的目标就是要找到max极差的最小化的值),反之,缩小左侧范围即可。

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define endl '\n'
typedef long long ll;

const int N = 100010;
int h[N];
int n, k;
bool check(int m)
{
    int cnt = 1;//组数
    int minh = h[0];//当前组最小的身高
    for (int i = 1; i < n; i++)
    {
        if (h[i]-minh > m)//当前成员身高在该组中与最矮成员身高差过大,将其新分一组
        {
            cnt++;
            minh = h[i];
        }
    }
    if (cnt <= k) return true; //组数越少,极差越小
    else return false;
    //return cnt<= k;
}

signed main()
{
    
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    sort(h, h + n);
    int l = 0, r = 1e9;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l;
    
    return 0;
}
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/440764
推荐阅读
相关标签
  

闽ICP备14008679号