序列中排列存在类DP问题+结合组合数学和拆贡献：1014T4
序列中排列存在类dp问题+结合组合数学和拆贡献：1014T4
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133833513
http://47.92.197.167:5283/contest/412/problem/4
赛时就想到枚举开头来拆贡献。
先说一下，对于A我们不关心具体的值，我们只关心哪些位置相等，哪些位置不等，最后乘上一个系数就行
然后对于序列是否存在排列类问题有个常见的dp套路，而且我们可以观察特殊性质 
表示前 个最后 个不同，转移相信大家都会
然后考虑有重复元素，有两种情况，但我们只关心左右最长无重复串
对于这种情况，左右分别乘贡献然后乘起来
对于这种情况：
我不会，但是数据没卡。
对于后面一段dp其实dp的初始状态可以改变
具体乘上什么系数我不会，长大后学
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-22
【NOIP2021 数列】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15590387.html 题目链接 首先dp得从低位向高位枚举，因为高位无论如果使用 2ai2^{a_i}2ai 都对低位二进制1的个数无影响，满足dp的无后效性。 设 dp(k,i,x,y)dp(k, i, x, y)dp(k,i,x,y) 为 SSS 从低的高二进制的前 kkk 位中，用了数列 aaa 的前 iii 项，且此时 SSS 中共有 xxx 个二进制位为1，第 i+1i+1i+1 位进了 yyy 过去。 则： dp(k,i,x,y...
2022-01-07
【P6191 [USACO09FEB]Bulls And Cows S】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15774893.html 题目链接 题目 一年一度的展会要来临了，Farmer John 想要把 NNN（1≤N≤100,0001 \leq N \leq 100,0001≤N≤100,000）只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗；假如两只公牛在这一行中靠的太近，他们就会吵架，以至于斗殴，破坏这和谐的环境。 John 非常的足智多谋，他计算出任何两只公牛之间至少要有 KKK（0≤K<N0 \leq K \lt ...
2021-12-07
【HDU 5794 A Simple Chess】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15659222.html 题目链接 题目 There is a n×m board, a chess want to go to the position (n,m) from the position (1,1). The chess is able to go to position (x2,y2) from the position (x1,y1), only and if only x1,y1,x2,y2 is satisfied tha...
2021-11-15
【洛谷P1350 车的放置】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15558415.html 题目链接 设 dp(i,j)dp(i, j)dp(i,j) 为前 iii 行放 jjj 个棋子的方案数， lenilen_ileni 为第 iii 行的列数。 类似背包的思想，每一行放或不放： dp(i,j)=dp(i−1,j)+dp(i−1,j−1)×(leni−(j−1))dp(i, j)=dp(i-1, j)+dp(i-1, j-1)\times(len_i-(j-1)) dp(i,j)=dp(i−1,j)+dp...
2021-12-15
【AGC001E E - BBQ Hard】 题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15694554.html 题目链接 题目 Snuke is having another barbeque party. This time, he will make one serving of Skewer Meal. He has a stock of N Skewer Meal Packs. The i-th Skewer Meal Pack contains one skewer, Ai pieces of beef and Bi...
2021-12-01
【Loj #10099. 「一本通 3.6 例 2」矿场搭建】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15630249.html 题目链接 我们先对于有向图缩点，变成一棵树。 然后我们对于每个树上且在原图中的分割点节点所对应原图中的连通块考虑。 假设这里没有割点，很明显，只需要放2个出口即可。 如果有一个割点，说明这个点是树上的叶子节点，需要放1个出口。 如果有两个或以上的割点，无论哪个割点被割，都可以往另一个方向逃，所以这个连通块不用放。 Code 1234567891011121314151617181920212223242526272829...