奋斗的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

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依

SQL Server配置管理器无法打开的四种解决方法

《SQLServer配置管理器无法打开的四种解决方法》本文总结了SQLServer配置管理器无法打开的四种解决方法,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录方法一:桌面图标进入方法二:运行窗口进入检查版本号对照表php方法三:查找文件路径方法四:检查 S

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2