如何做网站销售,江苏省备案网站,企业网站建设的文章,wordpress thread comment虽然是简单的dp #xff0c;but真的太难想到了#xff0c;而且我的码力。。。
Train Tracking 2
【题目描述】 每天特快列车都会经过农场。列车有N节车厢#xff08;1≤N≤105#xff09;#xff0c;每节车厢上有一个1到109之间的正整数编号#xff1b;不同的车厢可能会…虽然是简单的dp but真的太难想到了而且我的码力。。。
Train Tracking 2
【题目描述】 每天特快列车都会经过农场。列车有N节车厢1≤N≤105每节车厢上有一个1到109之间的正整数编号不同的车厢可能会有相同的编号。 平时Bessie会观察驶过的列车记录车厢的编号。但是今天雾实在太浓了Bessie一个编号也看不见幸运的是她从城市里某个可靠的信息源获知了列车编号序列的所有滑动窗口中的最小值。具体地说她得到了一个正整数K以及N−K1个正整数c1,…,cN1−K其中ci是车厢i,i1,…,iK−1之中编号的最小值。
帮助Bessie求出满足所有滑动窗口最小值的对每节车厢进行编号的方法数量。由于这个数字可能非常大只要你求出这个数字对10^97取余的结果Bessie就满意了。
Bessie的消息是完全可靠的也就是说保证存在至少一种符合要求的编号方式。
【输入输出格式】 输入的第一行包含两个空格分隔的整数N和K。余下的行包含所有的滑动窗口最小值c1,…,cN1−K每行一个数。
输出一个整数对每节车厢给予一个不超过109的正整数编号的方法数量对10^97取余的结果满足车厢i,i1,…,iK−1之中编号的最小值等于ci对于1≤i≤N−K1均成立。
【输入输出样例】 输入 4 2 999999998 999999999 999999998 输出 3 【分析】 1999999998 999999999 999999999 999999998 2999999998 999999999 1000000000 999999998 3999999998 1000000000 999999999 999999998
【解题思路】 首先你嘚想到相邻的ijijij如果它们的最小值不一样那么一定可以固定一个点
egiii到ik−1ik-1ik−1的最小值4,j4,j4,j到jk−1jk-1jk−1的最小值333iii小于jjj即ji1ji1ji1这个时候就固定了jk−1jk-1jk−1得是333
从中我们的启发是什么
把c值相同的连续区间单独拎出来
cici1ci2...cjvcici1ci2...cjvcici1ci2...cjv
这一段代表的区间总长为j−ikj−ikj−ik证明一下iii到jjj区间长为j−i1j-i1j−i1没问题
那么jjj包含的区间长是kkk加在一起再减去一个重复的jjj就是j−ikj-ikj−ik继续
所有的数都大于等于vvv同时每kkk个中就有至少一个vvv
有一个直接的dp设dp[i]dp[i]dp[i]表示最后一个vvv在iii位置时的合法方案数ppp为1e9−v1e9−v1e9−v
那么有转移dp[i]∑ji−ki−1pi−j−1∗f[j]dp[i]∑ ji−k i−1p^i−j−1*f[j]dp[i]∑ji−ki−1pi−j−1∗f[j]
这样是O(nk)O(nk)O(nk)的会TLE
稍微改变一下错位相消就变成了
dp[i](p1)*f[i−1]−p^k∗f[i−k−1]
在这里要解释一下首先如果有最小值是xxx那么方案数就是(1e9−x1)j−i1(1e9-x1)^{j-i1}(1e9−x1)j−i1减去不合法的方案数
在[ij][ij][ij]区间不合法的方案数其实是所有取值全都大于了vvv没有一个是vvv其实也就是(1e9−x1)j−i1(1e9-x1)^{j-i1}(1e9−x1)j−i1
问题是为什么要乘以dp[i−k−1]dp[i-k-1]dp[i−k−1]呢
你想想在iii不合法的方案数在i−1i-1i−1时是属于合法的方案数所以影响iii的是i−k−1i-k-1i−k−1的所有方案 因为从i−k−1i-k-1i−k−1开始往前不管选什么都与iii无关所以后面是不合法的前面不管合不合法都算不合法所以要相乘
接着就是考虑如何处理两个vvv不一样的交界处 说白了就是两个vvv谁更大相交的部分就交给谁处理 因为这就好比不等式解集的取法如果这个香蕉区间既要满足最小值为5又要满足最小值为6那坑定是选满足最小值为6啊
如果处理到iii时iii有一部分区间被前面处理过那么就要减去kkk
因为我们是循环iii是每次只加111所以当最小值不一样的时候两个区间的香蕉部分就是k−1k-1k−1又因为这k−1k-1k−1被前面处理过也就意味着iii这个点为了满足最小值也是固定的那么真正波动的有选择的长度就减去了kkk
同理如果处理到iii时发现i1i1i1的最小值更大也就意味着有k−1k-1k−1区间是后面处理i也固定下来了。长度便又减去了kkk
最后就是注意头i1i1i1和尾in−k1in-k1in−k1时的特判如果i1i1i1它就不能进行把k−1k-1k−1区间交给前面的人处理因为它前面没人如果in−k1in-k1in−k1它就不能进行把k−1k-1k−1区间交给后面的人处理因为它后面也没人了。 在这里要重点解释一下下面代码的dp初值设定早上吃饭时突然灵机乍现明白这样写的原因
为什么dp[0]和dp[1]初值是1 为什么window里i循环要从2开始 1dp[0]的情况就是这一段区间刚好就是1~k 那么当我们算到dp[k]的时候它是包含了从1~k所有都取大于min的值的不合法的方案数 而我们要减掉这些不合法的方案数也就是每一个数的取值都是min1~1e9有k个 所以不合法方案数就是1e9-(min-1)1^k也就是代码中的tp 那么这个系数是由dp[0]来提供因而要赋值成1
2dp[1]的情况就是这一段区间刚好是1~k1 而我们能进入这个函数一定要满足这个区间所有数的最小值是一样的val 所以当我们算到dp[k1]的时候 不合法的方案数2~k全都不是最小值方案数*dp[1]的方案数 那dp[1]不应该是tp吗 no~~因为我们的通向dp式dp[i-k-1]是乘以(1e9-min)的K次方而2到k全都不是最小值方案数是(1e9-min)的K-1次方dp[1]的所有方案数是1e9-min相乘刚好就是k次方 那么这时候的系数又是由dp[1]提供的就只能赋值成1
同样这也是为什么我们的i是从2开始循环为了考虑这两种情况就要给01腾位置
【代码实现】
#include cstdio
const int mod 1e9 7;
const int p 1e9;
#define MAXN 100005
#define LL long long
int n, k;
LL c[MAXN];
LL result 1;
LL dp[MAXN];LL qkpow ( LL x, LL y ) {LL res 1;while ( y ) {if ( y % 2 ) res ( res * x ) % mod;x ( x * x ) % mod;y 1;}return res % mod;
}LL window ( LL val, LL len ) {LL tmp p - val;LL tp qkpow ( tmp, k );dp[0] dp[1] 1;for ( int i 2;i len 1;i ) {dp[i] ( ( tmp 1 ) * dp[i - 1] ) % mod;if ( i - k - 1 0 ) dp[i] ( ( dp[i] - ( ( tp * dp[i - k - 1] ) % mod ) mod ) % mod ) % mod;}return dp[len 1] % mod;
}int main() {scanf ( %d %d, n, k );for ( int i 1;i n - k 1;i )scanf ( %lld, c[i] );for ( int i 1, j;i n - k 1;i j 1 ) {LL len;j i;while ( c[i] c[j 1] )j ;len j - i k;if ( i ! 1 c[i - 1] c[i] )len - k;if ( j ! n - k 1 c[j 1] c[i] )len - k;if ( len 0 )result ( result * window ( c[i], len ) ) % mod;}printf ( %lld, result % mod );return 0;
}
