文档章节

关于两容器倒水问题的感悟(ACM)

吟啸_徐行
 吟啸_徐行
发布于 2013/01/09 19:59
字数 392
阅读 304
收藏 0
点赞 0
评论 0

纯个人感悟,解释错误的地方希望可以指出来,谢谢!这里是ACM的题目感悟,可惜不记得题目了,晕!估计做ACM的都见过容器倒水问题和捕捉神兽问题,以下就是这两个问题分析后的感悟:

两个杯倒水问题中,能否到处满意的水可以这样判断:

   抓神兽的问题中,将直线转化为2倍直线长度的圆考虑,也就是求神兽每次跳跃的n在长度为m的圆中能否跳到距标记起点position长度的地方(求余),现在的问题其实转化为求mn的最大公约数问题(因为:设m=a*y1,n=a*y2(这里a为最大公约数,y1y2互质,y1,y2的线性差可以构造出任意的整数),若是能到达position,则(t*n)%m=position(t,x为未知的整数)即:t*a*y2=a*y1*x+position(x为未知的整数),即:t*y2=y1*x+position/a)若要求t有解则a一定能被position整除,即:position要是m,n的最大公约数的倍数才有解。

  类似的可以推广到两容器倒水问题(将一个容器的水不停的往另一个容器倒的类似捕神兽的圆圈问题),也可以用所求水的容积是否为两容器的最大公约数的倍数(当然,所求体积不能大于最大容器的容量)。

© 著作权归作者所有

共有 人打赏支持
吟啸_徐行
粉丝 18
博文 108
码字总数 15604
作品 0
深圳
程序员
校园招聘面试总结

一直想写一篇文章来总结一下今年的校园招聘面试,工作这么多年了,还是第一次参加校园招聘,很有 纪念意义,当年作为学生参加校园招聘的场景还是历历在目,没想到转眼间好几年就这样过去了,...

mjhuang ⋅ 2014/06/11 ⋅ 2

关于TCP流模式与UDP数据报文模式区别

“TCP是一种流模式的协议,UDP是一种数据报模式的协议”,这句话相信大家对这句话已经耳熟能详~但是,“流模式”与“数据包模式”在编程的时候有什么区别呢?以下是我的理解,仅供参考! 1、...

长平狐 ⋅ 2012/09/03 ⋅ 0

怎么用一个6升和5升的容器,称出3升的水

怎么用一个6升和5升的容器,称出3升的水 5升装满倒进6升桶 5-0 6-5 5升桶装满倒进6升桶 5-4 6-6 6升倒掉,5倒进6升桶 5-0 6-4 5装满倒进6升桶 5-3 6-6 完毕...

beves ⋅ 2011/09/25 ⋅ 5

热门智力题 过桥问题和倒水问题

热门智力题 过桥问题和倒水问题 过桥问题和倒水问题都是笔试面试中的热门智力题,不但微软、GOOGLE、百度、腾讯等公司采用,甚至在IQ测试与公务员考试中都能见到。本文不但教你如何快速用手算...

长平狐 ⋅ 2012/12/10 ⋅ 0

制作花肥方法大全 WYF收集整理

豆渣沤肥——无臭!简单!零技术! 之所以豆渣沤肥让花友执着,是因为豆渣里富含蛋白质,可以降解成植物需要的氮,作为一种有机肥料还能改善土壤,复杂的成分可以给植物提供多种元素。但是也...

wx5a0cd1844a571 ⋅ 2017/11/17 ⋅ 0

程序员们,那些年吹过的牛逼都实现了吗?

有一部分程序员中的老司机,他们善于找各种借口,少干活,少背锅,多拿钱。但是,更多的程序员坦诚、直白、意气用事。 那些年吹过的牛逼都实现了吗?还是随风而去? 这个功能简单,一天就能搞...

王练 ⋅ 2017/03/13 ⋅ 21

C++ 控制台无法输入字符串

今天抱着试试的心态参加学校“ACM”预先赛,想着要用前几天刚学的C++试试,没想到却让一个小问题把我给卡住了,三道题只做出了一道,其它两道不是算法不知道,而是编程语言不熟悉导致的,觉得...

曾赛 ⋅ 2009/05/27 ⋅ 0

中国计算机学会YOCSEF TDS《专题探索班》,新一代人工智能的基础与前瞻

人工智能诞生于上世纪60年代,其初衷是让机器像人一样认知、思考和学习,经过60年的发展,尤其是近年随着大数据和机器学习的快速发展,人工智能展现了很多全新的变化,正在加速迈向“2.0时代...

c9yv2cf9i06k2a9e ⋅ 2017/12/11 ⋅ 0

忆杨绛 悟人生

晚上下班途中翻开新浪热门微博,便看到有杨绛先生去世的消息,前些日子看了几篇文章,还特意搜了下这位老人,当时出现了好多关于他的杰出作品、艺术人生,而今天主页上都是关于缅怀的消息,即...

爱自由鹏 ⋅ 2016/05/25 ⋅ 0

现代应用架构中的配置管理面临的挑战

现代应用架构中的配置管理面临的挑战 摘要:过去15年中,互联网产业开始蓬勃发展,基于互联网的各类应用大放异彩,而在信息技术上,企业应用架构也逐渐从传统的ERP,JavaEE集中式应用开始走向...

配置管理 ⋅ 01/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CENTOS7防火墙命令记录

安装Firewall命令: yum install firewalld firewalld-config Firewall开启常见端口命令: firewall-cmd --zone=public --add-port=80/tcp --permanent firewall-cmd --zone=public --add-po......

cavion ⋅ 20分钟前 ⋅ 0

【C++】【STL】利用chromo来测量程序运行时间与日志时间打印精确到微秒

直接上代码吧,没啥好说的。头疼。 #include <iostream>#include <string>#include <ctime>#include <sstream>#include <iomanip>#include <thread>#include <chrono>using ......

muqiusangyang ⋅ 23分钟前 ⋅ 0

Mac环境下svn的使用

在Windows环境中,我们一般使用TortoiseSVN来搭建svn环境。在Mac环境下,由于Mac自带了svn的服务器端和客户端功能,所以我们可以在不装任何第三方软件的前提下使用svn功能,不过还需做一下简...

故久呵呵 ⋅ 33分钟前 ⋅ 0

破解公司回应苹果“USB限制模式”:已攻破

本周四,苹果发表声明称 iOS 中加入了一项名为“USB 限制模式”的功能,可以防止 iPhone 在连接其他设备的时候被破解,并且强调这一功能并不是针对 FBI 等执法部门,为的是保护用户数据安全。...

六库科技 ⋅ 35分钟前 ⋅ 0

MyBtais整合Spring Boot整合,TypeHandler对枚举类(enum)处理

概要 问题描述 我想用枚举类来表示用户当前状态,枚举类由 code 和 msg 组成,但我只想把 code 保存到数据库,查询处理,能知道用户当前状态,这应该怎么做呢?在 Spring 整合MyBatis 的时候...

Wenyi_Feng ⋅ 53分钟前 ⋅ 0

synchronized与Lock的区别

# <center>王梦龙的读书笔记第一篇</center> ## <center>-synchronized与Lock的区别</centre> ###一、从使用场景来说 + synchronized 是能够注释代码块、类、方法但是它的加锁是和解锁使用一......

我不想加班 ⋅ 今天 ⋅ 0

VConsole的使用

手机端控制台打印输出,方便bug的排查。 首先需要引入vconsole.min.js 文件,然后在文件中创造实例。就能直接使用了。 var vConsole = new VConsole(); vConsole的文件地址...

大美琴 ⋅ 今天 ⋅ 0

Java NIO之字符集

1 字符集和编解码的概念 首先,解释一下什么是字符集。顾名思义,就是字符的集合。它的初衷是把现实世界的符号映射为计算机可以理解的字节。比如我创造一个字符集,叫做sex字符集,就包含两个...

士别三日 ⋅ 今天 ⋅ 0

Spring Bean基础

1、Bean之间引用 <!--如果Bean配置在同一个XML文件中,使用local引用--><ref bean="someBean"/><!--如果Bean配置在不同的XML文件中,使用ref引用--><ref local="someBean"/> 其实两种......

霍淇滨 ⋅ 今天 ⋅ 0

05、基于Consul+Upsync+Nginx实现动态负载均衡

1、Consul环境搭建 下载consul_0.7.5_linux_amd64.zip到/usr/local/src目录 cd /usr/local/srcwget https://releases.hashicorp.com/consul/0.7.5/consul_0.7.5_linux_amd64.zip 解压consu......

北岩 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部