草庐IT

第十二届蓝桥杯B组C/C++省赛—H题（杨辉三角）_思维题

萌小帝 2023-04-08 原文

题目：ACWing—3421


分析

1、首先通过画图，发现杨辉三角对称，而题目要求找到数 n 最早出现的位置，那么我们可以确定，n最早出现的位置一定在左半边，而且最中间的是该行最大的数

2、通过图，我们可以发现通过行和列的枚举是不好的，看数据1e9也就是十亿，这是个很大的工程，因此我们试想可不可以从斜行来观察呢？？

  • 下图我们可以观察到，第1斜行的1=C（0,0），第二斜行的2=C（2,1），第三斜行的6=C（4,2）,第四斜行的20=C（6,3）…
  • 也就是说，如果我设共 i 斜行，那么第 i 斜行的第一个数为C（2*i，i），同时它是该斜行中最小的数字
  • 那么我们一定可以找到1e9的位置


3、1e9的位置确定

  • C（2*i，i）的计算（当然是指计算机手算的时候，代码里原始运算就好）
  • 显然C（32,16）< 1e9，而C（34,17）> 1e9，因此我们可以对前16行进行枚举

4、枚举顺序

  • 首先对于左半边杨辉三角来说，每行最大的数一定出现在该行末尾，同时它也是该数最早出现的位置
  • 因此我们不妨从第16斜行开始枚举，只要出现等于 n 的数直接返回位置即可
  • 对于查找，我们可以对每个斜行采用二分的方法查找n
  • 对于位置，我们可以在查找的时候确定，n所在行 r（不是斜行）和所在斜行 k ，然后通过等差公式 r*（r+1）/2 计算它之前数目的个数再加上 k+1

例如：n = 20 （由于推到，第一行行号为 0 ，斜行行号也是 0）

  • 查找过程我们可以确定20在第7行，实际返回 r = 6 ，在第 4 斜行 ，但此时 k 是 3，因此 k+1
  • 结果 ans = 6*7/2 + 3 + 1 = 25


5、时间复杂度分析

  • 枚举16斜行 --> O（16）
  • 二分查找 --> O（logn）
  • 综合起来，算法时间复杂度为 O（16logn）

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
LL C(int a, int b)   //计算C（a，b）
{
    LL res = 1;
    for(int i = a, j = 1; j <= b; i --, j ++)
    {
        res = res * i / j;
        if(res > n)
            return res;     // 大于n已无意义，且防止爆LL
    }
    return res;
}
bool check(int k)
{
    // 二分该斜行,找到大于等于该值的第一个数
    // 左边界2k，右边界为max(l, n)取二者最大，避免右边界小于左边界
    int l = 2 * k, r = max(n,l);
    while(l < r)
    {
        int mid = l + r >> 1;
        if(C(mid, k) >= n) r = mid;
        else l = mid + 1;
    }
    if(C(r, k) != n)
        return false;
    cout << 1ll*(r + 1) * r / 2 + k + 1 << endl;
    return true;
}
int main()
{
    cin >> n;
    // 从第16斜行枚举
    for(int i = 16; ; i--)
        if(check(i))
            break;
    return 0;
}
杨辉杨辉三角

有关第十二届蓝桥杯B组C/C++省赛—H题（杨辉三角）_思维题的更多相关文章

  1. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  2. 常见网络安全产品汇总（私信发送思维导图） - 2

    安全产品安全网关类防火墙Firewall防火墙防火墙主要用于边界安全防护的权限控制和安全域的划分。防火墙•信息安全的防护系统，依照特定的规则，允许或是限制传输的数据通过。防火墙是一个由软件和硬件设备组合而成，在内外网之间、专网与公网之间的界面上构成的保护屏障。下一代防火墙•下一代防火墙，NextGenerationFirewall，简称NGFirewall，是一款可以全面应对应用层威胁的高性能防火墙，提供网络层应用层一体化安全防护。生产厂家•联想网御、CheckPoint、深信服、网康、天融信、华为、H3C等防火墙部署部署于内、外网编辑额，用于权限访问控制和安全域划分。UTM统一威胁管理（Un

  3. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  4. 十四届蓝桥青少组模拟赛Python-20221108 - 2

    十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)

  5. 蓝桥杯 stm32 MCP4017 - 2

    本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#

  6. [蓝桥杯单片机]学习笔记——串口通信的基本原理与应用 - 2

    目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式  2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器 （3）AUXR：辅助寄存器​编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置  3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一

  7. 考勤刷卡 最大和 简单 蓝桥杯省赛 2022 - 2

    问题描述小蓝负责一个公司的考勤系统,他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。当员工刷卡时,会在后台留下一条记录,包括刷卡的时间和员工编号,只要在一天中员工刷过一次卡,就认为他到岗了。现在小蓝导出了一天中所有员工的刷卡记录,请将所有到岗员工的员工编号列出。输入格式输入的第一行包含一个正整数n,表示一天中所有员工的刷卡记录的条数。接下来n行,每行包含一条刷卡记录,每条刷卡记录的格式为:HH:MM:SSID其中HH:MM:SS表示刷卡时间,HH为一个0到23之间的两位十进制整数(可能含前导0)表示时,MM为一个0到59之间的两位十进制整数(可能含前导0)表示分,SS为一个0到59之间的

  8. ruby - 配置思维 sphinx 和飞行 sphinx 时出错 - 2

    我在Heroku上运行了Rails3应用程序。我在我的应用程序中使用ThinkingSphinx搜索引擎。为了让它与Heroku一起工作，我按照Heroku文档中的建议向我的gemfile添加了一个flying-sphinxgem。这是我的gemfile中的内容gem'thinking-sphinx','2.0.11'gem'flying-sphinx','0.7.0'按照此处提到的步骤https://devcenter.heroku.com/articles/flying_sphinx,添加flying-sphinx插件后(Herokuaddons:addflying_sphinx:

  9. 字符串的特殊读取——基于蓝桥杯两道题目（C/C++) - 2

    目录1 例题1.1 卡片换位1.2 人物相关性分析2 字符串的读取2.1 综述2.2 scanf2.3  getline/getchar/get2.4 注意2.5 说明3 C语言中字符串有关问题3.1 常用函数3.2 使用实例3.3 附一些函数先看例题1 例题1.1 卡片换位问题描述你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面3x2的格子在其中放5张牌，其中A代表关羽，B代表张飞，*代表士兵。还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。输入格式：输入两行6个字符表示当前的局面输出格式：一个整

  10. 中职组网络安全2023年山东省省赛Linux 系统渗透提权 - 2

            B-3：Linux系统渗透提权任务环境说明：服务器场景：Server2204（关闭链接）用户名：hacker密码：123456使用渗透机对服务器信息收集，并将服务器中SSH服务端口号作为flag提交；Flag：2283/tcp使用渗透机对服务器信息收集，并将服务器中主机名称作为flag提交；Flag：KipZ1eze使用渗透机对服务器信息收集&

随机推荐