20191107模拟-ntf

ntf的场

PBak的那些场

题意:求多少个A、B各n+m个,且能拆分为n个AB序列和m个BA序列,的合法序列个数,$n,m \le 1e3,数据组数 \le 25$

请先思考后再展开

一个最基本的是判断一个序列是否能拆,其实是可以贪的但不知道为啥被我叉了

就是把m个BA取出来,那么剩下的A肯定尽量左B尽量右,所以取出左边的m个B和右边的m个A,这样就能唯一对应了

想到这个其实就没了,可以直接设$dp(i,j)表示放了i个A和j个B$,思考一下是可以转移的
$$
\\下一个放A:dp(i+1,j)+=dp(i,j)[i+1 \le n]+dp(i,j)[i+1>n且min(j,m)>i-n]
\\下一个放B:dp(i,j+1)+=dp(i,j)[j+1>m且min(i,n)-max(0,j-m)>0]+dp(i,j)[j+1 \le m]
$$

1
2
3
4
5
6
7
memset(f,0,sizeof f);f[0][0]=1;
fo(i,0,n+m) fo(j,0,n+m) if(f[i][j])
{
if(i+1<=n or min(j,m)>i-n) add(f[i+1][j],f[i][j]);
if(j+1<=m or min(i,n)-max(0,j-m)>0) add(f[i][j+1],f[i][j]);
}
write2(f[n+m][n+m]);

孤立无援的造型神

题意:给出一个$n \le 6e3$的排列,问有多少个子序列,设长度为L,则需要满足「存在一个从第一个元素开始的上升子序列长度>L/2.0」、「存在一个从第一个元素开始的下降子序列长度>L/2.0」、「不存在长度>2的连续单调子序列」,64MB

请先思考后再展开

很明显这个子序列长度为奇数,且一定是像龙卷风一样,依次上下且每次幅度都更大

如果设$f(i,j,0/1)=最后位置为i,倒数第二个值为j,序列长度的奇偶性$,时间就是$O(n^2)$,然而这样的空间也是$O(n^2)$的,你发现我们现在在按照x坐标排序

这道题当时就觉得好像和去年雅礼noip赛很像,就算那种:明明和正解复杂度一样,但是卡我一手空间的感受

然而已经忘记当时是怎么做的了……upd:不是很像,而是就是

另一种不显然的做法是按照y排序,具体而言就是每次增大长度时,从高到低枚举i,在从低到高枚举比i小的j,然后在左侧那个向右侧那个转移

不想写了

CF717A Festival Organization

之前做过,没做出来惭愧啊

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8f96e42f.html
转载请注明出处,谢谢!