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
问题分析
这是一个组合数问题,需要注意的有两点:
- 两张同样的卡片也可以作为一种组合,所以跳出循环的条件是 c(k,2)+k>=n 。根据组合数的公式很容易用代码实现。
- 计算组合数的复杂度主要集中在求解阶乘的过程中。考虑到 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 。 输出…...
数据结构-快速排序
一.概要 快速排序是一种基于分治思想的排序算法,其基本思路是选取一个基准值(pivot),通过一趟排序将待排序列分成两个部分,其中左半部分都小于基准值,右半部分都大于基准值,然后对左右两部分分…...
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的问题复现及解决 注意:实验环境的IDEA版本:2021.3.1 1、问题描述 1.1、当想看源码时,点击Download Sources 1.2、此时出现了Cannot download sources 2、解决办法 2.1、…...
R+VIC模型融合实践技术应用及未来气候变化模型预测/SWAT/HSPF/HEC-HMS
在气候变化问题日益严重的今天,水文模型在防洪规划,未来预测等方面发挥着不可替代的重要作用。目前,无论是工程实践或是科学研究中都存在很多著名的水文模型如SWAT/HSPF/HEC-HMS等。虽然,这些软件有各自的优点;但是&am…...
Python 02 数据类型(04元组)
一、元组 元组和列表的唯一不同:不能直接对元组的元素进行修改,删除,添加。 不能修改 1.1 创建元组 1.1.1 创建一个空元组 touple1() # ‘() 里面没有元素,表示为空元组 1.1.2 元组可以容纳任意数据类型的数据的有序集合&…...
WMS:入库库作业流程状态定位
系列文章目录 例如:第一章 WMS:入库库作业流程状态定位 目录 系列文章目录 文章目录 前言 一、入库订单作业状态 二、入库任务级作业状态 1.收货作业 2.验收作业 总结 前言 WMS系统在仓储作业的管理中发挥着至关重要的作用,其核心优势在于强大…...
蓝易云:Linux系统【Centos7】如何配置完整的CC攻击防护策略
完整的CC攻击防护策略包括以下步骤: 1. 调整内核参数 在CentOS 7系统中,可以通过修改内核参数来增加系统对CC攻击的抵抗力。具体操作如下: (1)打开sysctl.conf文件: vim /etc/sysctl.conf (…...
编解码持续升级,「硬」实力铸就视频云最优解
算力时代,视频云需要怎样的 CPU? 在数据爆发式增长及算法日益精进的大背景下,属于「算力」的时代俨然到来。随着视频成为互联网流量的主角,日趋饱和的音视频场景渗透率、人类对“感官之限”的追求与突破、更多元化的场景探索及技术…...
贵金属技术分析的止损保护
前面说过我们这些小散户,最多也不过十几万或者几万美金的账户,没有必要想国际的一些大基金那样,又锁仓,又对冲什么的,我们资金小的投资者,足够灵活,自然有我们存活的方法。所以我们要注意发挥我…...
Python 进阶指南(编程轻松进阶):三、使用 Black 工具来格式化代码
原文:http://inventwithpython.com/beyond/chapter3.html 代码格式化是将一组规则应用于源代码,从而使得代码风格能够简洁统一。虽然代码格式对解析程序的计算机来说不重要,但代码格式对于可读性是至关重要的,这是维护代码所必需的…...
计算机应用辅导大纲及真题
00019考试 湖北省高等教育自学考试实践(技能)课程大纲 课程名称:计算机应用基础(实践) 课程代码:00019 实践能力的培养目标。 计算机应用基础(实践)是高等教育自学考试多…...
【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里有如下几种类加载器: 引导类加载器:负责加载支撑JVM运行的位于JRE的lib目录下的核心类库,比如 rt.jar、charsets.jar等 扩展类加载器:负责加载支撑JVM运行的位于JRE的lib目录下的ext扩展目录中的JAR类包应用程序…...
蓝桥杯模板题目
A:::::::::::::::小王子单链表(链表) 题目描述 小王子有一天迷上了排队的游戏,桌子上有标号为 1−10 的 10 个玩具,现在小王子将他们排成一列,可小王子还是太小了,他不确定他到底想把那个玩具摆在哪里&…...
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代理池 在编写爬虫程序时,一般都会构建一个 User-Agent (用户代理)池,就是把多个浏览器的 UA 信息放进列表中&…...
数据结构.双链表的各种操作
//双链表 //单链表无法逆向检索,双链表可进可退 双链表比单链表多啦一个前驱指针 //双链表查找时间复杂度都为o(n) #include<bits/stdc.h> using namespace std; typedef struct donde //创建双链表 {int data;dnode *next,*prior; //前驱和后继 }dnode,*…...
去年12月被无情辞退,三个月后我携手自动化测试神技王者归来
引言 不知不觉在软件测试行业工作了3年之久,虽然说我是主做的功能测试,但是我也一直是兢兢业业的呀,不曾想去年7月份无情被辞的消息让我感到一阵沉重。我曾经一直坚信自己的技能和经验足以支撑我在这个领域的未来,但现实却告诉我&…...
临近起飞,在哪个平台更容易捡漏特价机票?2026年实测指南
“机票越临近起飞越便宜”——这个说法你一定听过。每逢假期临近,总有人在社交媒体上分享自己“起飞前两小时抢到白菜价机票”的神奇经历。但当你真的想在清明、五一出行前“赌一把”时,往往发现价格不仅没降,反而翻倍了。那么问题来了&#…...
BiliTools:全能B站资源管理工具,让离线学习与内容备份无忧
BiliTools:全能B站资源管理工具,让离线学习与内容备份无忧 【免费下载链接】BiliTools A cross-platform bilibili toolbox. 跨平台哔哩哔哩工具箱,支持视频、音乐、番剧、课程下载……持续更新 项目地址: https://gitcode.com/GitHub_Tren…...
wan2.1-vae开源可部署:支持国产操作系统(麒麟/UOS)的适配方案
wan2.1-vae开源可部署:支持国产操作系统(麒麟/UOS)的适配方案 1. 平台介绍 muse/wan2.1-vae 文生图是基于 Qwen-Image-2512 模型的AI图像生成平台,支持中英文提示词,可生成高质量、高分辨率的图像。该平台特别针对国…...
企业级流程引擎如何重塑低代码开发?基于Vite+Vue3的可视化建模实践
企业级流程引擎如何重塑低代码开发?基于ViteVue3的可视化建模实践 【免费下载链接】vite-vue-bpmn-process 基于 Vite TypeScript Vue3 NaiveUI Bpmn.js 的流程编辑器(前端部分)。支持高度自定义🚀🚀🚀。…...
4步攻克Python代码执行可视化:开发者调试效率提升指南
4步攻克Python代码执行可视化:开发者调试效率提升指南 【免费下载链接】viztracer VizTracer is a low-overhead logging/debugging/profiling tool that can trace and visualize your python code execution. 项目地址: https://gitcode.com/gh_mirrors/vi/vizt…...
基于智能体(Agent)的自动化图像工作流:Wan2.2-I2V-A14B与任务编排
基于智能体(Agent)的自动化图像工作流:Wan2.2-I2V-A14B与任务编排 1. 引言:当图像生成遇上智能体 想象一下这样的场景:你需要为电商平台制作一组节日主题的广告图,包含特定风格的背景、商品展示和人物互动…...
vLLM-v0.17.1实操手册:Prometheus监控指标接入与告警配置
vLLM-v0.17.1实操手册:Prometheus监控指标接入与告警配置 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库,由加州大学伯克利分校的天空计算实验室(Sky Computing Lab)开发,现已发展为社区驱动的开源项目。这个框…...
小白也能懂:Qwen3-TTS-Tokenizer-12Hz的API调用与Python示例
小白也能懂:Qwen3-TTS-Tokenizer-12Hz的API调用与Python示例 1. 前言:音频编解码器能做什么? 想象一下,你录制了一段重要的会议录音,文件大小有50MB,想通过微信发给同事,却发现超过了文件大小…...
腾讯王者荣耀强化学习环境:打造专业AI训练平台的完整指南
腾讯王者荣耀强化学习环境:打造专业AI训练平台的完整指南 【免费下载链接】hok_env Honor of Kings AI Open Environment of Tencent 项目地址: https://gitcode.com/gh_mirrors/ho/hok_env 在人工智能研究领域,游戏环境一直是强化学习算法的理想…...
绿色低碳+高效交付:中集模块化数据中心用实力印证中国方案全球竞争力
随着人工智能与绿色转型成为全球经济增长核心引擎,高算力需求正推动数据中心建设向预制化、高效能方向加速演进。中集集团(000039.SZ/2039.HK)凭借工业化制造与全球交付优势,2025年在模块化数据中心(AIDC)领…...
