2024.11.23模拟赛(*^▽^*)

标签：状态 困困 2024.11 23 T2 转移 困困困 特殊 模拟

加密版：困困，困困困困困。困困困困困困困困困困困困困困困困困，困困困困困困困困困困困。困困困，困困困困困困困困困困，困困困困困困困困困困困困困困困困困困困困困，困困。困困困困，困困困困！

今天，模拟赛还没开始多久，就闻到了弥漫在空气中的糊味。于是，整个机房一起（?）冲到操场 看热闹 观察情况，不过十分钟后也差不多回去了。然后就开始打。T1题意叙述不清+简单，我都怀疑我是不是想假了；T2刚开始想成贪心了，但总感觉不对劲，及时换成了\(dp\)；T3？我不道啊，推了下样例一不小心性质就出来了，打了特殊样例，但是我为什么不打暴力！！！为什么啊wwwwww；真是\(dij\)打多了，看到T4就想到\(dij\)的暴力写法了，然后又手推了下特殊样例，虽然时间耗得多了点，但分到手了。最后T1 100分，T2 70分，T3 12分，T4 30分，总分212，未挂分。

作业小链接

---

---

T2【自行车】

题目大意：

解题思路：

容易想到\(dp\)转移方程：

\[f_{i,j}=\begin{cases} f_{i-1,\ j-1}+1,a_{i}\neq b_{j}\\ min(f_{i-1,\ j}\ ,f_{i,\ j-1})+1,a_{i}= b_{j} \end{cases}\]

但这样的转移是\(O(n^{2})\)，考虑优化。

显然，我并没有想出怎样优化

我们可以注意力惊人地注意到，满足\(a_{i}=b_{j}\)状态的只有\(n\)个，我们称它是特殊状态，称\(a_{i}\neq b_{j}\)是普通状态。

经过思考，我们会发现：对于普通状态\(f_{i,j}\)，它一定是从\(f_{i-1,j-1}\),\(f_{i-2,j-2}\)…一直到特殊状态\(f_{i-t,j-t}\)。也就是说，每个普通状态一定是通过某个特殊状态+某个固定值转移而来的。

所以，只要处理出所有特殊状态的值，就可以得到答案了。考虑设状态\(f_{k}\) 表示对于\(k=a_{i}=b_{j}\) 的特殊状态的转移答案。注意到在上述从普通业主那个题

标签：状态,困困,2024.11,23,T2,转移,困困困,特殊,模拟
From： https://www.cnblogs.com/Myyy-L/p/18564867