奋斗的demon——基本计数方法(实践一)

2023-12-23 18:50

本文主要是介绍奋斗的demon——基本计数方法(实践一),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天demon要应用昨天的理论练习:

大白老师布置了2个基本计数类型题目(象棋中的皇后,数三角形,有多少个0)

1个容斥原理题目(拉拉队)

1个二项式系数题目(超级平均数)

【例1.1 象棋中的皇后】(基本计数原理)

【题目描述】

    你可能知道象棋怎么下以及皇后的移动规则。当两个皇后在同一行、同一列或同一条斜线上时,她们就会互相攻击。假设两个这样的皇后(一黑一白)被放在一个2×2的棋盘上,她们可以有12种互相攻击的方式,请看下图:

给出一个N×M的棋盘,计算有多少种放法能使两个皇后互相攻击。

【输入】

    输入至多包含5000行。每一行有两个非负整数N、M(0<M, N≤106)。输入以两个N=M=0为结束标志,这一行不需要处理。

【输出】

    对于输入的每一行,输出一行。这一行包含一个整数,它表示放法的种数。所有的输出数据都在带符号的64位整数内。

【样例输入】

2 2

100 223

2300 100000

【样例输出】

12

10907100

11514134000

【分析】

因为只有两个皇后,因此相互攻击的方式只有两个皇后在同一行、同一列或同一对角线3种情况。这三种情况没有交集,因此可以使用加法原理。设在同一行放两个皇后的方案为A(n,m),同一列放两个皇后的方案数为B(n,m),同一对角线放两个皇后的方案数为D(n,m),则答案为A(n,m)+B(n,m)+D(n,m)。

A(n,m)的计算用乘法原理:放白后有n*m种方法,放黑后有m-1种方法。A(n,m)=n*m*(m-1)。

B(n,m)=A(n,m)。

D(n,m)比较复杂。假设n≤m,所有/向的对角线,从左到右的长度依次为:1,2,3,...,n-1,n,n,n,...n,n-1,n-2,...,2,1(其中n有m-n+1个)

因为还有\方向的对象线,所以结果*2。

D(n,m)=2*(2*Σ(i=1~n-1)i*(i-1)+(m-n+1)*n*(n-1))=2*(n*(n-1)(2*n-4)/3+(m-n+1)*n*(n-1))=2*n*(n-1)*(3*m-n-1)/3。

其中Σ(i=1~n-1)i*i=n*(n-1)*(2*n-1)/6,

Σ(i=1~n-1)i=n*(n-1)/2

小tips:使用64位无符号整数保存n,m,最大可以保存2^64-1>1.8*10^19,因为这道题的运算结果种不会出现负数,使用无符号64位整数保险。

 

【例1.2 数三角形】

【题目描述】给定边长1,2,3,...n的n条边,现在要在里面任意选取三条边构成三角形,求一共可以构成多少个三角形?

【样例输入】

5

8

【样例输出】

3

22

【分析】

首先三重循环O(n^3)的时间,肯定超时。

所以我们换一个角度看问题,加法原理:

 

我们先定义一个函数f(n):当最大编程为n时所能构成的三角形数目。

对于三角形的三边而言,我们可以设定为x,y,z。并且我们假设x是最大边。那么我们有y+z>x,因此可以推出x-y<z<x。

根据这个不等式我们有,当y=1时,显然无解;当y=2时,有一个解;当y=3时,有两个解;·····当y=x-1时有x-2个解。根据等差数列求和公式我们有一共有

0+1+2+······+(x-2)=(x-1)(x-2)/2。但是我们需要注意,这里包含了y=z情况。那么我们需要减去从y=x/2+1开始到y=x-1为止,此时我们多计数了(x-1)-(x/2+1)+1=(x-1)/2个解,而且除此之外,我们对于每一个y我们都有重复计数,因为前后是对称的。所以我们最后还要除以2得到最终结果。

最终结果为:

          

那么最后的递推式我们可以写为:

          

核心代码:f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2。

【例1.3 有多少个0】(整数区间分解,统计)

【题目描述】输入两个非负整数m和n(m≤n<2^31),求将m~n的所有整数写出来,一共要写多少个数字0?

【分析】假设f(x)表示从0到x需要写多少个0,于是给出区间[m,n]就有答案f(n)-f(m-1)。而f(x)如何求呢?枚举每个位置上可能为0的情况,计算组成方法。

 

#include  <iostream>
unsigned long long m, n;
using namespace std;
long long f(long long left) {if (left < 0) return 0;long long ans = 1, mid, right = 0, j = 1;while (left >= 10) {mid = left % 10; left /= 10;if (mid) ans += left * j;else ans += (left - 1) * j + right + 1;right = right + mid * j;j *= 10;}return ans;
}int main() {while (cin>>m>>n && n != -1 || m != -1) {cout<<f(n)-f(m-1)<<endl;}return 0;
}


明天继续......

 

这篇关于奋斗的demon——基本计数方法(实践一)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/529096

相关文章

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

虚拟机Centos7安装MySQL数据库实践

《虚拟机Centos7安装MySQL数据库实践》用户分享在虚拟机安装MySQL的全过程及常见问题解决方案,包括处理GPG密钥、修改密码策略、配置远程访问权限及防火墙设置,最终通过关闭防火墙和停止Net... 目录安装mysql数据库下载wget命令下载MySQL安装包安装MySQL安装MySQL服务安装完成

SpringBoot整合(ES)ElasticSearch7.8实践

《SpringBoot整合(ES)ElasticSearch7.8实践》本文详细介绍了SpringBoot整合ElasticSearch7.8的教程,涵盖依赖添加、客户端初始化、索引创建与获取、批量插... 目录SpringBoot整合ElasticSearch7.8添加依赖初始化创建SpringBoot项

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标(连接、查询、资源、复制),支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤

Nginx安全防护的多种方法

《Nginx安全防护的多种方法》在生产环境中,需要隐藏Nginx的版本号,以避免泄漏Nginx的版本,使攻击者不能针对特定版本进行攻击,下面就来介绍一下Nginx安全防护的方法,感兴趣的可以了解一下... 目录核心安全配置1.编译安装 Nginx2.隐藏版本号3.限制危险请求方法4.请求限制(CC攻击防御)

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、