0722 模拟赛
这是计数专场吗，把我秒掉了。
难
原：P7050 [NWRRC2015] Concatenation
给定两个字符串 a, b，从 a 中选一段前缀，b 中选一段后缀（前后缀都可以为 空），并将选出的后缀拼在选出的前缀后面。 你需要求出有多少种本质不同的串（可以为空）。
思路
总方案数减去不合法的方案数。以 ab 和 bc 为例，abc 会重复；以 abb 和 bc 为例，abc 和 abbc 会重复。奇奇怪怪地就发现不合法的方案数就是 \(\sum_{i=a}^znum[i]*num2[i]\) 。
交易
\(n\) 天中价格为 \(1\) 金币或 \(2\) 金币，每天买入或卖出一件，或什么都不做，求有多少种价格方案使得最多能赚 \(k\) 元。
补习：卡特兰数
一种应用是从 \((0,0)\) 向上或向右走到 (n,n)，不能走到 直线 \(y=x\) 上方，计数。
发现所有走到 \(y=x\) 以上的路径关于 \(y=x+1\) 可以与一条到达 \((n-1,n+1)\) 的路径对应（？？？），易得常见公式 \(H_n={2n \choose n}-{2n \choose n-1}\)。
思路
考虑一个简化版 CF1924D，只包含 \(n\) 个左括号，\(m\) 个右括号的序列满足最长合法括号子序列长度为 \(k\)，计数。
- 从 \((0,0)\) 向上或向右走到 \((n,m)\)。
- 需要浪费掉 \(n-k\) 个左括号和 \(m-k\) 个右括号，且这 \(m-k\) 个右括号位于 \(n-k\) 个左括号之前，那么路径经过 \(y=x+(k-m)\)，且不得经过该函数右侧。
- 第二条限制可以转化为： 经过 \(y=x+(k-m)\) 的路径数减去经过 \(y=x+(k-m-1)\) 的路径数。
0723 模拟赛
今天讲题的大佬连名字都不敢提。
原来之前一直有 std 代码呀，没发现，早知道就不玩雀魂了，悲。