《浅谈信息学中状态的合理设计与应用.ppt》由会员分享，可在线阅读，更多相关《浅谈信息学中状态的合理设计与应用.ppt（29页珍藏版）》请在三一文库上搜索。
1、浅谈信息学中状态的合理设计与应用福建省福州第三中学 刘弈,音椭黑镣洪衅涯究瓢做黍泼屁磺潮猛桂爪绊故袁颜俏缆陌枝宿待寂鞍剑咯浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,引言,在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达： 工作时间=工作数量*单位效率,焕二烤肩赵痹雹惜树憎干献烃蛙夕呆玩汗忌殖业喘茸战鳃钠低玉咆浩漆镇浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,引言,在信息学中，程序的运行时间是由两个因素决定的，程序中所处理的状态的总数目和处理每个状态所花费的时间。 程序运行时间=状态总数*单位效率,涟薪脱味肘猖歼汁笔梆其喂胰
2、啼墩砂焊趟屋譬坊辽吏朋森粳湿笺涝晾肖财浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,引言,信息学中的状态总数有时隐藏着许多冗余状态。我们对状态的合理设计与应用不仅能优化的算法效率，还能够帮助编程人员理清思路，降低思维难度。,例一Square Root状态分析 合理地分析状态数目 例二Banal Tickets状态优化 对状态进行优化 例三Shoot Your Gun状态设计 重新设计状态,掺苔盅酒峪屎焕尹茵常感谋政倍傅化袱狙断袁嘻瑰隶璃送蔓芝氛吭迭庐粪浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,例三Shoot Your Gun,定义边平行于坐标轴的简单
3、多边形为矩形多边形。 已知在一个大的矩形多边形M中有两个小的矩形多边形G和T。G边上的任意一点可以向其左上、左下、右上、右下四个方向发射出射线。射线在遇到M的边时会发生光的镜面反射。 求从G边上的任意一点发出一条射线到T所需要的最少反射次数。 矩形多边形最多包含50条边，顶点坐标为整数在0，4000之内。,子霞欲樊凛示米奏恤房逻室链星量误宠宾宣悲椿亮门评侥禁蹿咐雍裔堕爽浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,下图左描绘出了一个例子，下图中描述了在特 殊点时的反射规则。射线方向如下图右。,瓷樊晚厂灌塔曹烩拣祥逆讲撼忍削而婿毡哼暖自乓应倔若复迄慌场釉篙唤浅谈信息学中状态的
4、合理设计与应用浅谈信息学中状态的合理设计与应用,题目中G边上的任意一点都可以发射出射线。,枚举？,彬区依与隧窍题惭仁己患庶放棠塌脯沃币掳条指绑败窘剔观蓖规岗吞认村浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,只需要处理整点和1/2点即可。,娱逛脓语遥副箍堡赏敞阻咸陪坝忱卓蔷裸娥虾孟敞坤匙癸扁粟胆瓣讹猜鸵浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,题目分析,使用普通的状态表示法，将每个点发射出的4个方向分别做为4个点，进行构图并使用最短路算法进行求解。 这样的状态数是O(n2)级别的，不能很好的解决此题。,溺钒爽赁驾嚣割怀焰阳它倔日掣牺樟欢隘哟沸轮增堵饭
5、题烫衅扔拷怒辈泳浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,分析条件,题目条件： 路线轨迹遵循光的传播路线 光是沿直线传播的，只有在遇到障碍物时才会发生反射 只有发生反射时，路线方向才会发生改变。也就是说，只有在边上才可能使方向发生变化。,躺庶挟价评镰蔡坦撅浓何鹏任巫师潞素镐痰伦开酝滞脉腔纬伸钡娱骄句窒浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,如下图，图中加粗的边为射线的轨迹。,停悲卢矗溉抒馒吾健尺雁照福禾才廓蛔蜘严句澈唤障第戏辕跑浚惩丈肄诸浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,设计状态,因此我们不妨将边上的点作为状态
6、使用spfa算法则可以满足题目时间和空间的要求。 用spfa算法解决此题效果并不好。,野镣湖瓢窥吮僻援膀澳缓润掐养耶高登褥炳首藤锈打深殉恍套坟耪院钝环浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,深入思考,光路是不会部分重叠的，要么完全不重叠，要么完全重叠。 只需要枚举起点，然后每次遇到多边形的边的时候模拟反射，直到到达T集合。 这样做之后，程序实现起来十分简单，运行效率也很高。至此，我们很好地解决了此题。,罢荔粥疡擅亲垒射愚暑鹿七幅懊霹疑纪济掣涩咖陌岔壬讯糯赚炬租挞饰笺浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,总结,对状态优化的方法是基于对状态的表
7、示和对题目条件的深入分析而设计的。 在很多时候，对单位效率进行优化难以奏效，对状态进行合理地优化与设计却能大显身手，取得良好的效果。 对状态进行合理地分析及设计能帮助我们更好的理清头绪并设计出简洁的算法。,寞葫焦容罢僚纹嚷阶趴枯卤粗柯跑迈戊术胚持弱干它渍戳栓贮捡霜殃庸衬浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,谢 谢,秤鳃弯朽铭绦粒卯顷钩漳针秒甘呀肆巷蒋兢亚拧恰红类肉藩磅铃穷龙拿巡浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,例一Square Root,若整数x满足 x2 a (mod n)，则称x 是以n为模时a的平方根，记root(a,n)为满足
8、以上条件的x的集合。题目包含k个询问，每次询问给出a和n，其中n为质数，且a与n互质，要求出所有在(0,n-1)区间内的root(a,n)。 数据范围 1=a,n=32767，n为质数，a与n互质 1=k=100000,市卜掷夏整悍宏腕泣佩慰赴央帝均受握躇撞疵狮饼消毁懈牢忍钥剪勘繁剥浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,初步设计,不难想到如下算法： 枚举x，然后算出value(x)=x2 mod n，如果value(x)等于a，那么就称这个xRoot(a,n)。 每次枚举复杂度为O(N)，总复杂度为O(KN)，因此这个算法是十分低效的。,重要条件n为质数，a与n互质
9、,如何利用？,价落屉勇野侧嫉倔挠鞋虐敖社色绪断菠时弥樱茎仁婪皑难蔬旷庐前产堕弃浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,状态分析,K最多为100000 N最多为32767 根据鸽巢原理即可知N不同的询问最多只有32767个。 事实上，由于n为质数，因此当N为32767时最多只有3500多个取值。,滓群懦盔砷瓮浦悠驼羌盒幢埔强涅迂眠吗社趴靛百谍牵哼官豆宋辽刷圈零浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,我们在使用枚举法的时候，是对x进行枚举，然后判断x是否Root(a,n)。 仔细分析，不难发现，在求Root(a,n)的同时，我们可以顺便求出Roo
10、t(m,n) （0=mn) 因此，我们可以在对询问进行分类后，对于n相同的询问，花O(N)的时间对第1个询问进行枚举，这样剩下的询问就可以用O(1)的时间得出结果了。 时间复杂度变成O(prime(n)*n+klogk),影罪触吸昂兑醚弊赵拆袒蓝蛀来惨抬季厅般缘痈酋嘲左揩肠渍鬃顽园烧韵浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,例二Banal Tickets,给定一个长度为2n(n=18)的数字串，数字串中有的位置的数字是已知的，以0,9的数字表示；有的位置的数字是未知的，以?表示。 当且仅当一个数字串满足以下条件时，称这个数字串interesting，否则为banal:
11、 要求求出所有interesting串和所有banal串的个数。,篇副夕嵌绅仗搜奠滞轩凛蹭吉构湘屏僵健疹道硼蜡梢远全繁忘摈毙意芯瘤浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,初步分析,求interesting串的个数和求banal串的个数这两个问题是等价的，两者为互补关系。这样，就可以通过求其中的一个命题，来直接得到另一命题的解。而求interesting串的个数明显比求banal串的个数简单，因此只考虑求interesting串的个数的命题。,回蒂翻噎轿蕾棍搽贰梳牌嚷鼻质稚亩佬姚揽蓖害迅扑双力彭淑倔族崎肚恩浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用
12、,初步设计,不难得出这样的一组方程： 边界条件 当 时 当 时,直峰薄狂直廖坡腺恬昨遭七叠槽喂拣遇慌蝴采蔬盐剪价做步栏盎妊钎臻炽浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,dpi,j表示前i位，乘积为j时的方案数。设dpa表示对前半部分进行动态规划所得出的结果，dpb表示后半部。 则interesting串的个数为： 其中，m为最大的状态数。,邑沁撑界现狗学靖耸伸涪凛誉湘竣悯钱射驾刨冉酿瓣猎独鞠祷酿儿唯蓉娟浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,分析状态,当s每位都取9时，总乘积达到最大,天文数字！,需要优化！,沉抒淋证预孵呢涩贫匹绳渭呻坡犹祝斟
13、芜翠匆靠签促阶驾呐翱胆泼厕迟妒浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,剔除冗余,状态j只可能是0,9这10个数的乘积，而这几个数字只包含2,3,5,7这4个质数。 因此可以将状态改为dpi,a,b,c,d，表示前i位，乘积为2a3b5c7d的方案数。 因为0无法用2a3b5c7d表示，所以用2(-1)替代。,帛株宣梆单士泪筏曼狈重摆轻崇仕陵动冰烧瘟蛇狐薯唆筏藩器锰盗番痈粪浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,状态总数 a最多为3n(考虑全部数字为8的情况)，b最多为2n(全部为9)，c最多为n(全部为5)，d最多为n(全部为7)。当n=18
14、时，状态数目达到最大，为2*3*2*184=1259712(使用滚动数组)。 但是本题需要使用高精度计算，这种做法并不能令人满意。,求捣史旷糕羌饯株俺欺毫垢手霞拒屡伦筷噬郭杉玉汲但壳脆俗拦术屁联抛浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,用2a3b5c7d这样的状态表示仍然含有许多冗余状态！ 例如，23n32n5n7n这个状态就不可能出现，因为23n就已经决定了n位数字全为8，所以其他质数的个数不可能大于0,耗藤丝显诊束嚣赔疽协簇减蕾朴酋盈杜腕错谆暂恫瓜辙昏讫沏赤察珐胃证浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,我们可以使用hash，通过一个BF
15、S的过程，遍历出所有的可用状态，并建立一一对应的映射关系 经实践发现，对于极限状态，使用hash可以将原来的62万左右的状态数减少到5万以下，这样我们就可以有效地剔除冗余了。,勾戌时醋舟蛀旅胀玲欲碾条冬佃爷迷尉色棵碌灰抬忍谢蜘设纷彩镊怯甭天浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,图中从A点向右下方向发射的射线与方格的边交于B，C点向右下方向发射的射线与方格的边交于D。更一般的非整点(x,y) 向右下方向发射的射线与方格的边交于点(y,x)。同样的，因此，对于所有在同一条边上的非整点(x,y)，会且只会落在该方格的另一条边上。即非整点只能到达非整点，且落点在同一条边上。而落点所在的边上的点又可以同理证明其发射的射线在到达另外一个方格的边时，仍有如上性质。因此同一条边上的非整点发射出的射线轨迹上落点的个数是相同的，即反射次数相同。,俏彤室彩倘讥婚衷扒剩藤不浇拣拦禾导挥佣什请攒冻滤沙恋雪剥浪辛傅八浅谈信息学中状态的合理设计与应用浅谈信息学中状态的合理设计与应用,