题目链接 题意：给出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]的点必然 …

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 ] * …

rt

题目链接 题意： F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2 求： FFFn Mod P ( 也就是 F[ F[ F[n] ] ] % P ) 思路：原来这是适牛出的题2333. 需要注意的是p可能为1，因此n==0或者1的时候，特判要输出1%p而不是1. 其他的没了。就是求斐波那契数列循环节的经典做法。 /* *********************************************** Author :111qqz Created Time :Thu 03 Nov 2016 08:09:26 AM CST File Name :1124.cpp …

题意：now he let you calculate G(n,k) .Here G(n,0) = f(n) , G(n,i) = f( G(n,i-1) ) (k >= i >= 1).其中f是斐波那契数列。 思路：其实就是hdu 4291的加强版：hdu 4291 解题报告 开一个1E4的数组存一下每一层的循环节就好了。 http://vjudge.net/contest/139429#overview 告一段落，完结撒花！ /* *********************************************** Author :111qqz Created Time :Tue 01 Nov 2016 …

题目链接 题意：求一个小数的循环节... 思路：其实直接模拟就好... 模拟竖式计算... 这里用到一个小技巧。 由于多组数据，每次都memset一个bool会很慢，导致超时。 我们可以用一个人int数组来代替每次重置的bool数组, /* *********************************************** Author :111qqz Created Time :Tue 01 Nov 2016 08:00:49 PM CST File Name :code/hdu/2522.cpp ************************************************ */ #include …

这种东西我也没什么资格评论，只是随便说说自己的感受。 之前在知乎上看到有人批判说，OI/ACM圈子的戾气，大致有两点。 一个是（装）弱，一个是膜。 第一点其实，至少我认识的大多数人，包括我在内，并不是装弱，而是真的觉得自己弱。 我觉得这也是竞赛带给我的财富之一吧，就是一个比较开阔的眼界。 更具体得说，大概就是，虽然竞赛是一个小圈子，但是我基本清楚，这个圈子里，世界最强的那批人是什么水平。 因此我也很清楚自己有多么弱小，而不会像有些人一样或者像包括我在内的许多人的小时候一样...在一个小的圈子（地理意义上） 一旦做到很高，就容易自满。 但是听到有的人批判说，这种“我好菜啊”的态度会让人没办法做好事情。 说实话，我对于这个逻辑是无法理解 …