假设下一个状态有必败。那么此时状态一定是必胜，否则此时状态一定是必败状压DP#include<iostream>#include<map>#include<string>#include<cstring>#include<cstdio>#include<...

题目链接题意：有n架飞机。每架飞机都能够选择早着陆和晚着陆两种方式之中的一个，且必须选择一种。任务就是安排全部飞机着陆时。相邻两个着陆时间间隔的最小值尽量大。思路：用二分处理最小值尽量大。该题目能够转化为是否存在一个调度方案，使得相邻两个着陆时间差总是不小于P，进一步转化为随意两个着陆时间差...

迭代加深搜索自己看的时候第一遍更本就看不懂。。是非常水，但智商捉急也是没有办法的事情。好在有几个同学已经是做过了这道题而且对迭代加深搜索的思路有了一定的了解，所以在某些不理解的地方询问了一下他们的见解，真的是非常有帮助。或许自己想要想非常久才干想明确，还会非常痛苦，略微问一下别人的想法，点上一个方向。剩下的自己就能想得...

手机在蜂窝网络中的定位是一个基本问题。如果蜂窝网络已经得知手机处于c1,c2,…,cn这些区域中的一个。最简单的方法是同一时候在这些区域中寻找手机。但这样做非常浪费带宽。因为蜂窝网络中能够得知手机在这不同区域中的概率。因此一个折中的方法就是把这些区域分成w组，然后依次訪问。比方。已知手机可能位于5个区域中，概率分别为0...

题意：　　给两个数，n,m构造一个序列，分母从1~m，并且j/i越来越接近n/m。 思路：　　如果存在j/i趋近于n/m那么则有j=n*i/m+0.5（四舍五入）。　　维护与n/m的差值即可。　　第一次写的太复杂，后来看了别人的博客，才发现原来是自己想多了。　　 代码：　　1#include<...

题意：　　现有k种邮票面额，一封信上最多贴h张邮票。　　求能贴出的最大连续区间，即[1,max_value]这个区间内的所有面额都能贴出来。　　并输出k种面额，h+k<=9. 思路：　　这是一个经典的数学问题：连续邮资问题。　　1）面额为1的邮票肯定要选进去（不然连1都贴不出来，还怎么连续）。　　　　此...

题意：　　给一个图，将其节点以任一序列排列。　　1）计算每个节点距离相邻节点的最大距离dis[i]　　2）计算出当前序列中，所有节点的dis[i]，并求出最大的dis[i]:max_dis　　求最小的max_dis，并且输出此序列。　　节点数不超过8个 思路：　　节点数不超过八个，那直接进行全排列，求解最小值...

题意：　　给w个货架，每个货架上有bi个货物，每次只能拿最上面的货物，每个货物有个价值，所有货物的售价均为10。　　问：能获得的最大利润，以及能获得这个利润需要多少个货物。（有多种组合时只需输出前10种） 思路：　　最开始我是先将最大价值预处理了出来，然后dfs查找方案数，结果超时了，后来发现复杂度是O(w*...

题目链接题意：　　在一个宽为r的房间里，有s个砝码，每个天平的一端要么挂砝码，要么挂另一个天平，并且每个天平要保持平衡。　　求使得所有砝码都放在天平上，且总宽度不超过房间宽度的最大值。 思路：　　每个节点只能有两个子节点，这是一棵二叉树的形式。　　通过枚举二叉树的形态，再枚举每一个叶子节点所放砝码，最后再计算...

题目链接题意：　　有n个任务，每个任务要在规定的时间[l,r]内完成，工作量为w，每个任务可以分开完成。　　求，使得所有任务都完成的最大速度的最小值。 思路：　　最大值最小问题，二分。　　因为是要完成所有任务，所以先按开始时间排序，接下来二分速度。　　因为任意两个任务之间的关系只有两种，1）相交或者包含2）相...

题目链接题意：　　给一个数n，每次从小于等于n的素数里选一个P，如果能被n整除，那么就n就变成n/P。 　　问：n变成1的期望。 思路：　　设小于等于n的素数有p个，其中是n的约数的有g个。　　则E[x]=1+1/p*(1-g/p)+sigma(i=0,1,2, g)num[i]*1/p。...

题目链接题意：　　你玩纸牌，如果当天晚上你赢的局数比例大于p，就去睡觉，第二天继续。如果小于等于p，就去睡觉，并且以后都不玩了。　　每晚最多玩n局，每局赢的概率为p，求玩的天数的期望。 思路：　　设dp[i][j]为玩了i局，赢了j局的概率。　　则期望E=sigma(i=0,1,2,3,4,........)...

题目链接题意：　　两个人坐火车，在某个城市到站的时间段分别为[t1,t2],[s1,s2]，停在站台的时间均为w。　　问，若两人能见面的概率。 思路：　　一道基础的几何概型，p=s(m)/s(n)。　　令x1=t1,x2=t2。　　令y1=s1,y2=s2。　　这样这四条直线就围成一个矩形，若两人见面，则应该...

题目链接题意：　　现在有k只麻球，每只麻球只能存活一天，第二天就会死去，死去之前可能生下x只小麻球(x=0,1,2,...,n 1),概率分别为P[0],P[1],...,P[n-1]。　　现求，m天之后，所有麻球全死去的概率，包括m天之前就已经全部死去。 思路:　　每只麻球都是相互独立的，那么可以...

题目链接题意：　　有个NXM的棋盘，有K种颜色，有B个不可涂色的位置，共有R种涂色方案。　　1）每个可涂色的位置必须涂上一种颜色　　2）不可涂色位置不能涂色　　3）每个位置必须从K种颜色中选出一种颜色进行涂色　　4）当前格子(x,y)上面的那个格子(x+1,y)不能同色　　　　现在已知N,K,B,R，求满足条件的最小的...