博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
关于两容器倒水问题的感悟(ACM)
阅读量:7056 次
发布时间:2019-06-28

本文共 562 字,大约阅读时间需要 1 分钟。

hot3.png

纯个人感悟,解释错误的地方希望可以指出来,谢谢!这里是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的最大公约数的倍数才有解。

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

转载于:https://my.oschina.net/wizardpisces/blog/101141

你可能感兴趣的文章
SHELL学习——判断
查看>>
用Python做科学计算
查看>>
Unity3d中C#使用指针(Unsafe)的办法
查看>>
Win10下用Anaconda安装TensorFlow
查看>>
http_load压力测试工具
查看>>
我的友情链接
查看>>
sokect网络编程
查看>>
ios 实现选中时阴影效果
查看>>
Post XML到一个服务器上
查看>>
linux基本网络配置
查看>>
深圳高交会
查看>>
Java中设置classpath、path、JAVA_HOME的作用
查看>>
MySQL数据库管理之日常操作
查看>>
连续潜在变量---核PCA
查看>>
lucene 3.5.0 入门笔记
查看>>
AD域桌面重定向_无权限访问桌面
查看>>
DSPLINK 介绍
查看>>
css笔试题整理(其他)
查看>>
oracle锁及oracle查找锁定表信息
查看>>
我的友情链接
查看>>