当前位置: 首页 > news >正文

2022蓝桥杯省赛——卡片

问题描述

小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有两位同学的卡片都是一样的。

给定 n, 请问小蓝的卡片至少有多少种?

输入格式

输入一行包含一个正整数表示 n 。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

6

样例输出

3

样例说明

小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3)(1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。

评测用例规模与约定

对于 50% 的评测用例, 1≤n≤10^4 。

对于所有评测用例, 1≤n≤10^9 。

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

问题分析

这是一个组合数问题,需要注意的有两点:

  1. 两张同样的卡片也可以作为一种组合,所以跳出循环的条件是 c(k,2)+k>=n 。根据组合数的公式很容易用代码实现。
  2. 计算组合数的复杂度主要集中在求解阶乘的过程中。考虑到 n 的最大值为10^9,需要使用记忆化数组来缩短计算时间。在这类比赛中,程序处理千万级的运算量时已经很勉强了,所以我在这里将记忆化数组的长度设为10^7,即一千万。

 

 Python代码如下:

n=int(input())
dp=[-1 for i in range(10**7)]  # 阶乘数的记忆化数组# 阶乘
def fact(X):ans=1  # 阶乘结果x=Xwhile x>1:if dp[x]!=-1:  # 已知x的阶乘ans*=dp[x]dp[X]=ansreturn anselse:ans*=xx-=1dp[X]=ansreturn ans# 组合数
def c(n,m):return fact(n)/(fact(m)*fact(n-m))k=0
while c(k,2)+k<n:k+=1print(k)

可惜的是,由于无法将记忆化数组的长度设为10^9,通过率只有80%。读者如发现不足之处,欢迎批评指正。

 

相关文章:

2022蓝桥杯省赛——卡片

问题描述 小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有两位同学的卡片都是一样的。 给定 n, 请问小蓝的卡片至少有多少种? 输入格式 输入一行包含一个正整数表示 n 。 输出…...

数据结构-快速排序

一.概要 快速排序是一种基于分治思想的排序算法&#xff0c;其基本思路是选取一个基准值&#xff08;pivot&#xff09;&#xff0c;通过一趟排序将待排序列分成两个部分&#xff0c;其中左半部分都小于基准值&#xff0c;右半部分都大于基准值&#xff0c;然后对左右两部分分…...

WuThreat身份安全云-TVD每日漏洞情报-2023-04-10

漏洞名称:Apple iOS/iPadOS 越界写入 漏洞级别:高危 漏洞编号:CVE-2023-28206 相关涉及:Apple iOS <16.4.0 漏洞状态:在野 参考链接:https://tvd.wuthreat.com/#/listDetail?TVD_IDTVD-2023-08810 漏洞名称:PHPGurukul Bank Locker Management System SQL 注入 漏洞级别:高…...

IDEA中查看源码点击Download Sources时出现Cannot download sources的问题复现及解决

IDEA中查看源码点击Download Sources时出现Cannot download sources的问题复现及解决 注意&#xff1a;实验环境的IDEA版本&#xff1a;2021.3.1 1、问题描述 1.1、当想看源码时&#xff0c;点击Download Sources 1.2、此时出现了Cannot download sources 2、解决办法 2.1、…...

R+VIC模型融合实践技术应用及未来气候变化模型预测/SWAT/HSPF/HEC-HMS

在气候变化问题日益严重的今天&#xff0c;水文模型在防洪规划&#xff0c;未来预测等方面发挥着不可替代的重要作用。目前&#xff0c;无论是工程实践或是科学研究中都存在很多著名的水文模型如SWAT/HSPF/HEC-HMS等。虽然&#xff0c;这些软件有各自的优点&#xff1b;但是&am…...

Python 02 数据类型(04元组)

一、元组 元组和列表的唯一不同&#xff1a;不能直接对元组的元素进行修改&#xff0c;删除&#xff0c;添加。 不能修改 1.1 创建元组 1.1.1 创建一个空元组 touple1() # ‘() 里面没有元素&#xff0c;表示为空元组 1.1.2 元组可以容纳任意数据类型的数据的有序集合&…...

WMS:入库库作业流程状态定位

系列文章目录 例如&#xff1a;第一章 WMS&#xff1a;入库库作业流程状态定位 目录 系列文章目录 文章目录 前言 一、入库订单作业状态 二、入库任务级作业状态 1.收货作业 2.验收作业 总结 前言 WMS系统在仓储作业的管理中发挥着至关重要的作用&#xff0c;其核心优势在于强大…...

蓝易云:Linux系统【Centos7】如何配置完整的CC攻击防护策略

完整的CC攻击防护策略包括以下步骤&#xff1a; 1. 调整内核参数 在CentOS 7系统中&#xff0c;可以通过修改内核参数来增加系统对CC攻击的抵抗力。具体操作如下&#xff1a; &#xff08;1&#xff09;打开sysctl.conf文件&#xff1a; vim /etc/sysctl.conf &#xff08…...

编解码持续升级,「硬」实力铸就视频云最优解

算力时代&#xff0c;视频云需要怎样的 CPU&#xff1f; 在数据爆发式增长及算法日益精进的大背景下&#xff0c;属于「算力」的时代俨然到来。随着视频成为互联网流量的主角&#xff0c;日趋饱和的音视频场景渗透率、人类对“感官之限”的追求与突破、更多元化的场景探索及技术…...

贵金属技术分析的止损保护

前面说过我们这些小散户&#xff0c;最多也不过十几万或者几万美金的账户&#xff0c;没有必要想国际的一些大基金那样&#xff0c;又锁仓&#xff0c;又对冲什么的&#xff0c;我们资金小的投资者&#xff0c;足够灵活&#xff0c;自然有我们存活的方法。所以我们要注意发挥我…...

Python 进阶指南(编程轻松进阶):三、使用 Black 工具来格式化代码

原文&#xff1a;http://inventwithpython.com/beyond/chapter3.html 代码格式化是将一组规则应用于源代码&#xff0c;从而使得代码风格能够简洁统一。虽然代码格式对解析程序的计算机来说不重要&#xff0c;但代码格式对于可读性是至关重要的&#xff0c;这是维护代码所必需的…...

计算机应用辅导大纲及真题

00019考试 湖北省高等教育自学考试实践&#xff08;技能&#xff09;课程大纲 课程名称&#xff1a;计算机应用基础&#xff08;实践&#xff09; 课程代码&#xff1a;00019 实践能力的培养目标。 计算机应用基础&#xff08;实践&#xff09;是高等教育自学考试多…...

【Go基础】一篇文章带你全面了解学习—切片

目录 1、切片注意点 2、声明切片 3、切片初始化 4、切片的内存布局...

2022国赛28:centos8.5离线安装docker

大赛试题内容: 八、虚拟化(20分) 在Linux2上安装docker-ce,导入centos镜像。软件包和镜像存放在物理机D:\soft\DockerLinux。创建名称为skills的容器,映射Linux2的80端口到容器的80端口,在容器内安装apache2,默认网页内容为“HelloContainer”。解答过程: 下载CENTOS8镜…...

JVM专题

JVM类加载 Java里有如下几种类加载器&#xff1a; 引导类加载器&#xff1a;负责加载支撑JVM运行的位于JRE的lib目录下的核心类库&#xff0c;比如 rt.jar、charsets.jar等 扩展类加载器&#xff1a;负责加载支撑JVM运行的位于JRE的lib目录下的ext扩展目录中的JAR类包应用程序…...

蓝桥杯模板题目

A:::::::::::::::小王子单链表&#xff08;链表&#xff09; 题目描述 小王子有一天迷上了排队的游戏&#xff0c;桌子上有标号为 1−10 的 10 个玩具&#xff0c;现在小王子将他们排成一列&#xff0c;可小王子还是太小了&#xff0c;他不确定他到底想把那个玩具摆在哪里&…...

SAP IDT - Building Data Foundation

To build a Data Foundation, it can be created on a Local Project view. Right-click under Local Project → New → Data Foundation. You can select a Single-source enabled or Multi-source enabled. Follow the wizard and select the connections. Data Foundatio…...

【Python】【进阶篇】三、Python爬虫的构建User-Agnet代理池

目录三、Python爬虫的构建User-Agnet代理池3.1 自定义UA代理池3.2 模块随机获取UA三、Python爬虫的构建User-Agnet代理池 在编写爬虫程序时&#xff0c;一般都会构建一个 User-Agent &#xff08;用户代理&#xff09;池&#xff0c;就是把多个浏览器的 UA 信息放进列表中&…...

数据结构.双链表的各种操作

//双链表 //单链表无法逆向检索&#xff0c;双链表可进可退 双链表比单链表多啦一个前驱指针 //双链表查找时间复杂度都为o(n) #include<bits/stdc.h> using namespace std; typedef struct donde //创建双链表 {int data;dnode *next,*prior; //前驱和后继 }dnode,*…...

去年12月被无情辞退,三个月后我携手自动化测试神技王者归来

引言 不知不觉在软件测试行业工作了3年之久&#xff0c;虽然说我是主做的功能测试&#xff0c;但是我也一直是兢兢业业的呀&#xff0c;不曾想去年7月份无情被辞的消息让我感到一阵沉重。我曾经一直坚信自己的技能和经验足以支撑我在这个领域的未来&#xff0c;但现实却告诉我&…...

用MATLAB复现高斯光束通过双透镜系统:从ABCD矩阵到可视化光斑演变

用MATLAB复现高斯光束通过双透镜系统&#xff1a;从ABCD矩阵到可视化光斑演变 在光学工程和激光技术领域&#xff0c;理解高斯光束在复杂光学系统中的传输特性至关重要。本文将带您一步步实现高斯光束通过双透镜系统的完整MATLAB仿真&#xff0c;从ABCD矩阵理论推导到动态光斑演…...

Comsol光学仿真连续域束缚态BIC,te,tm模式耦合,透射光谱远场偏振矢量(导出数据计算)

Comsol光学仿真连续域束缚态BIC&#xff0c;te&#xff0c;tm模式耦合&#xff0c;透射光谱远场偏振矢量&#xff08;导出数据计算&#xff09;&#xff0c;所见即所得 【手指在键盘上停顿三秒】这周在实验室搞COMSOL光学仿真差点被边界条件逼疯&#xff0c;连续域束缚态(BIC)…...

Apache Spark 解第 8 章附加篇:Structured Streaming 底层机制深度剖析

...

从GigE Vision到千兆UDP:FPGA图像采集系统的灵活升级与10G MAC预留设计

从GigE Vision到千兆UDP&#xff1a;FPGA图像采集系统的灵活升级与10G MAC预留设计 在工业视觉和机器视觉领域&#xff0c;图像采集系统的带宽需求正以惊人的速度增长。随着4K、8K高分辨率相机的普及&#xff0c;以及多相机同步采集场景的增多&#xff0c;传统的千兆以太网接口…...

高效安全:从远程服务器到本地Windows的文件传输全攻略

1. 远程桌面连接&#xff1a;最直观的文件传输方式 远程桌面连接&#xff08;RDP&#xff09;是Windows系统自带的"杀手级"功能&#xff0c;我帮客户部署项目时90%的场景都会用它传文件。它的优势在于操作可视化程度高&#xff0c;就像直接在服务器桌面上操作本地文件…...

Qwen3.5-4B-Claude-Opus实战案例:用推理链输出提升技术沟通准确性

Qwen3.5-4B-Claude-Opus实战案例&#xff1a;用推理链输出提升技术沟通准确性 1. 模型介绍与核心能力 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF是一个基于Qwen3.5-4B的推理蒸馏模型&#xff0c;专门针对结构化分析、分步骤回答以及代码与逻辑类问题的处理能力进…...

机器人手臂相机 vs 抓手相机:5个关键区别与选型指南(附避坑技巧)

机器人手臂相机 vs 抓手相机&#xff1a;5个关键区别与选型指南&#xff08;附避坑技巧&#xff09; 在工业自动化领域&#xff0c;视觉引导系统如同机器人的"眼睛"&#xff0c;而相机安装位置的选择往往决定了整个系统的精度与可靠性。当工程师面对手臂相机&#xf…...

从555到正弦波:手把手教你用立创EDA仿真+打样一个2KHz波形发生器(附完整工程)

从555到正弦波&#xff1a;立创EDA全流程打造2KHz波形发生器实战指南 在电子设计领域&#xff0c;波形发生器是最基础却又最考验设计功底的经典项目之一。想象一下&#xff0c;当你亲手设计的电路板输出完美的正弦波时&#xff0c;那种成就感绝非购买现成模块可比。本文将带你用…...

亚洲美女-造相Z-Turbo惊艳案例分享:高还原度旗袍/汉服/都市职场风人像生成

亚洲美女-造相Z-Turbo惊艳案例分享&#xff1a;高还原度旗袍/汉服/都市职场风人像生成 最近在玩一个挺有意思的AI模型&#xff0c;叫“亚洲美女-造相Z-Turbo”。这名字听起来有点技术范儿&#xff0c;但说白了&#xff0c;它就是个专门生成亚洲女性人像的AI工具。 你可能用过…...

RWKV7-1.5B-g1a参数详解:为何默认top_p=0.3更适合中文生成?语言分布实证

RWKV7-1.5B-g1a参数详解&#xff1a;为何默认top_p0.3更适合中文生成&#xff1f;语言分布实证 1. 模型概述 rwkv7-1.5B-g1a是基于RWKV-7架构的多语言文本生成模型&#xff0c;特别适合中文场景下的基础问答、文案续写和简短总结任务。作为1.5B参数量的轻量级模型&#xff0c…...