全国服务热线:4008-888-888

技术知识

mac抠图软件-非典型算法题,用程序和电脑玩一个

--------

mac抠图软件

-------

大伙儿好,欢迎阅读文章周末优化算法题专题。

今日挑选的优化算法题是来自contest 1407赛事的C题,这题全场根据6700余人。根据的人数尽管多,可是这题真的不简易,想出优化算法来不太非常容易。抛开难度不提,这道题十分十分成心思,老实巴交说这类方式的题型我也是第一次见。

题型连接:contest/1407/problem/C

空话很少说,大家来看题型。

这题是一道非典型的优化算法题,与其说是一道优化算法题不如说更好像一个手机游戏。手机游戏的目地是猜一个1至n这n个数组成的排序,大家需要根据键入和輸出和系统软件开展互动,从系统软件处获得更多的信息内容,最后给出猜想的結果。

最先系统软件会给定一个整数金额n,表明这个排序由n个数据组成,这n个数据由前n个正整数金额组成,也就是1到n这n个数据。以后大家能够根据輸出一个指令的方式向系统软件开展发问,发问的方法是? x y。系统软件财务会计算排序之中第x个数对第y个数取模的結果开展回到(排序的下标从1刚开始),也就是回到的值。

系统软件数最多接纳2n次了解,当大家早已猜出全部排序以后,輸出这个排序。在其中。

这个样例要倒过来看,第一个键入的3表明n。接着就先看輸出再看键入。这个样例要猜的結果是[1, 3, 2],最先了解了num[1]对num[2]取余的結果,系统软件回到是1。接着了解num[3]对num[2]取余的結果,答案是2。接着了解num[1]%num[3]和num[2]%num[1],得到的結果各自是1和0。最后大家依据这些信息内容猜想出了这个排序是[1, 3, 2],根据! 1 3 2的方式开展回到。

那道题以后大家最先能够发现,n明确了以后这n个数也就明确了。由于n最大,别的数对n取模都是它自身。因此大家需要先找到n的部位。

可是n的部位其实不好找,想来想去仅有一种方法,就是当出現两个数的余数是n-1的情况下,便可以明确这两个数一个是n-1此外一个是n。可是很显著,这样做大家没法在要求步数内解出来。由于n个数两两组成一共有贴近种,可是题型限制大家数最多只能了解2n次。

很明显,先找到n再找寻别的值是不好的。

既然这个念头不好,我又刚开始找起了别的方式。大家求了x % y的結果以后,到底有甚么用呢?这个結果究竟有木有别的信息内容呢?

大家来简易剖析一下,大家假定x % y = 1,那末这能表明甚么吗?很显著,不可以表明甚么,由于将会性太多了。1对别的数取模都等于1,x % (x-1)也等于1。但倘若x % y (n/2) 呢?实际上就可以表明难题了。由于x和y的范畴是[1, n],如今两个数取模以后的結果超过n的一半,很显著表明x就是这个結果,y是比x更大的数。也有一种状况是x % y = 0,这类状况大家尽管没法明确x和y的值,可是能够了解x一定是y的倍数且x y。

尽管了解这些,但還是不足解开难题,依然需要看运气,由于大家其实不能确保在查寻次数内恰好便可以找到全部比二分之n大的数。可是这一段剖析其实不是无用的,大家能够在此基本上更进一步。大家求了x和y的余数以后能够再求一下y和x的余数,假定x % y = a, y % x = b,根据剖析a和b大家可以得到甚么結果呢?

最先大家能够毫无疑问a和b不会相同,缘故也很简易,由于x和y一定不等(排序中的数各不同样)。大家何不假定x y,那末y % x =b = y,x % y = a y。假如a和b相同的话,那末就有 y y,这明显是不了立的。因此能够毫无疑问a和b一定不等。其次从上面的证实大家也看得出来,在x y时,那末一定能够得到a b。由于a = x % y y,b = y % x = y。也就是说大家能够根据a和b的关联分辨x和y的关联,不但这般,还能够明确y的值。

到这里间距解出这道题早已十分贴近了,只差临门一脚,可是这里我還是走了弯路。我那时候的念头是把这些数两两配对,这样便可以明确出在其中的一半。以后大家再把解不出来的数再开展配对,直到最终只剩余一个数为止。后来发现也有反例,例如[1, 3, 2, 4, 5],在这个事例之中1和3配对,2和4配对,5落单。大家還是没方法解出来。

我在这里苦思冥想了很久,后来才发现答案远在天上近在眼下,解法实际上十分简易。大家只需要从前往后面遍历维护保养一个最大值便可。大家假定最大值是id,但凡遇到小于id的数,都能够根据它和id取模的結果求出来。假如遇到了比id更大的数,一样能够根据取模的結果求出id。因此到最终的情况下,大家能够求出除最大值别的的全部数,这个剩余的数就是n。

想通了真的十分十分简易,说穿了一钱不值得,可是要靠自身想搞清楚還是不太非常容易的。而且这道题的题型方式也很新颖,十分十分趣味,合适在周末一玩。

最终,大家来看编码:

import sys

今日的难题到这里就完毕了,衷心祝福大伙儿每天都有一定的收获。假如还喜爱今日的內容的话,请来一个三连适用吧~(点赞、关心、转发)

原文连接,求个关心

本文应用 mdnice 排版

- END -

---------

mac抠图软件

------------


在线客服

关闭

客户服务热线
4008-888-888


点击这里给我发消息 在线客服

点击这里给我发消息 在线客服