hdu1864题目链接 题意：中文题目，不多说了。 思路：正解是01背包，呵呵呵。 出题人是傻逼吗？ 不给数据范围？ 以及，正解的01背包基于所有的发票额度的只有2位小数。这是让人猜？ 本来看到这题这么恶心时不打算写的... 写了的原因纯粹是为了吐槽傻逼出题人.. 简直是我做得最垃圾的题目之一。 /* *********************************************** Author :111qqz Created Time :2016年11月16日 星期三 14时13分28秒 File Name :code/hdu/1864.cpp …

题目链接 题意： 给出n个银行 ，以及抢劫每个银行可以得到的价值和被抓的概率，不同银行之间被抓的概率是相互独立的，现在给出安全概率p，只有当概率从小于安全概率时才是安全的，问最多能抢劫多少价值。 思路：一开始很直接就想到把概率算成容量， 于是就成了经典的01背包，然后发现概率是double型。。。想当然得以为最多是2位小数，于是都*100转化成了整数做01背包。 然而正确思路是，把银行价值看成背包容量，而背包价值是概率！ 将危险的概率转化成安全概率（1-危险概率=安全概率) 然后做01背包。 然后从大到小扫一遍价值，第一个大于安全概率的就是答案。 注意精度。 /* …

前几天忘记什么原因，把gnome的什么东西搞坏了，干脆就换了kde. 然后发现kde太多细节，而且换了kde之后，关机键是失灵的.....我也不知道为什么，总之是各种难用。 本打算就换回gnome好了。。不过想起gnome下的那个（kde下也有）不定时键盘卡死，以至于出现了好几次代码写到一半，没法保存的情况..... 于是想了想... ubuntu反人类还是算了.... mint可以应该可以（如果驱动没问题...）不过我印象里mint的内核才3+...? 好菜啊。。。。 其实另一台本上的fedora22用起来没啥问题....无奈2016款的x1c无法安装... 于是想到了deepin... 看了下评价还不错...而且我也快过了爱折腾 …

kde好难用啊.... 换回了gnome.

题目链接 题意：给出n(n<=1E3)个字符，字符可能为'D','I','?'，第i位对应的字符分别表示，第i位大于第i+1位，第i位小于第i+1位，或者不确定。 现在问满足该字符串的 1..n的排列的方案数。结果9+7 思路：没有太多思路，参考了题解 主要是状态表示没有想到，后面的状态转移方程倒是不难。 思路是，dp[i][j]表示长度为i，最后一位的相对大小为j的方案数。 考虑转移：如果第i-1个位置的字符为‘I’，那么所有比j小的都可以转移到j，也就是dp[i][j] = dp[i-1][1] + dp[i-1][2] + ... + dp[i-1][j-2] + dp[i-1][j-1]; 如果第i-1个位置的字符 …

题目链接 题意：问长度为n的“波浪”型排列（即1..n每个数出现一次）有多少。波浪型的含义是，“高低高”或者“低高低” 思路：我们考虑当前已经知道i-1个数的波浪型的排列的方案数，那么当第i个数到来时，第i个数一定是最大的。 那么将i插入到某个位置，必须满足该位置前面必须以“高低”结尾，该位置后面必须以“低高”结尾才合法。（特别地，允许前面或者后面为空，这点体现在初始化上） 因此我们分别考虑，用dp[i][0]表示有i位且最后结尾为“高低”的方案数，dp[i][1]表示有i位且最后结尾为“低高”的方案数。 此时我们的情况是，已经有i-1个数，我要把第i个数插在某个位置。 这个位置是不确定的，因为我们需要枚举插入的位置（表现为，枚举插 …

题目连接 题意：给出n(n<=200000)个数，问所有区间[l,r]中mex的和。 （一个区间mex的定义为，这个区间中没有出现的最小的非负数） 思路：我们观察到mex(1,i)随着i增大，是不减的。(单调是线段树查询区间的时候非常好用的东西,这也是次题的突破口) mex(1,i)可以O(n)维护出 现在我们考虑左端点向右移动对答案的影响。 当i移动到i+1时，此时序列中少了a[i]，设r为最小的x，满足a[x]=a[i]，那么当右断点在区间[r+1,n]，mex值是没有改变的。 当右端点属于[i+1,r-1]时，mex大于a[i]的会变成a[i]。 由于我们知道从1到某区间的mex值是单调的，那么mex大于a[i]的点必然 …

感冒也好得差不多了。 纠结也纠结够了吧。 退役个毛线啊。 寒假还要去叉姐的camp呢.. 好了，继续。

1009: [HNOI2008]GT考试 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description 　阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am. A1和X1可以为 0 Input 　第一行输入N,M,K.接下来一行输入M位的数。 …

题目链接 题意：问长度为n，每个位置由且仅有‘H’和'T'组成的序列中，至少有连续k个‘H’出现的方案数。 思路：不会做，参考了题解 不过没有完全搞懂。 根据题解，正面考虑比较麻烦，所以反面考虑。[j] dp[i][j]表示长度为i，前面最后连续的‘H’的个数不超过j个的方案数。 考虑转移方程为： 总的情况为：dp[i][j] = dp[i-1][j] * 2; 但是其中有多考虑的情况，就是第i位是'H'，且i位之前的最后j个位置都是'H'（即从i-j位到第i-1位都是‘H’，此时第i-j-1位必然是'T'） 有i个硬币时，如果i 如果i > j + 1，dp[ i ] [ j ] = dp [ i - 1 ] [ j ] * …