Eous的小站
日记

日记

Fri Nov 29 2024
5 分钟
life 日记
1031 字

今天也是终于不用考试了，可以改改题了。

上午#

CF1970E Trails solution#

因为走到无论哪一个房子，第二天都得走回来。把从这一天下午湖到房子的路和第二天上午从房子到湖的路一起考虑。设 dpi,0dp_{i,0} 表示上午走过了短路，也就是下午走什么路都行；dpi,1dp_{i,1} 表示上午没走过短路，也就是下午必须走短路。那么有dp方程：

dpi,0=dpi−1,0×(∑j=1msj(sj+lj))+dpi−1,1×(∑j=1msj2)dpi,1=dpi−1,0×(∑j=1mlj(sj+lj))+dpi−1,1×(∑j=1msjlj)dp_{i, 0} = dp_{i - 1, 0} \times \left(\sum\limits_{j = 1}^{m}s_{j}(s_{j} + l_{j})\right) + dp_{i - 1, 1} \times \left(\sum\limits_{j = 1}^{m}s_{j}^{2}\right)\\ dp_{i, 1} = dp_{i - 1, 0} \times \left(\sum\limits_{j = 1}^{m}l_{j}(s_{j} + l_{j})\right) + dp_{i - 1, 1} \times \left(\sum\limits_{j = 1}^{m}s_{j}l_{j}\right)

（啊其实是我从题解上扒下来的，因为我懒得打 Latex 了）

可以变成矩阵形式：

(∑j=1msj(sj+lj)∑j=1msj2∑j=1mlj(sj+lj)∑j=1msjlj)(dpi−1,0dpi−1,1)=(dpi,0dpi,1)\begin{pmatrix} \sum\limits_{j = 1}^{m}s_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}^{2} \\ \sum\limits_{j = 1}^{m}l_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}l_{j} \end{pmatrix} \begin{pmatrix} dp_{i - 1,0} \\ dp_{i - 1,1} \end{pmatrix} = \begin{pmatrix} dp_{i,0} \\ dp_{i,1} \end{pmatrix}

而 (dpi−1,0dpi−1,1)\begin{pmatrix} dp_{i - 1,0} \\ dp_{i - 1,1} \end{pmatrix} 又能变成 (∑j=1msj(sj+lj)∑j=1msj2∑j=1mlj(sj+lj)∑j=1msjlj)(dpi−2,0dpi−2,1)\begin{pmatrix} \sum\limits_{j = 1}^{m}s_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}^{2} \\ \sum\limits_{j = 1}^{m}l_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}l_{j} \end{pmatrix} \begin{pmatrix} dp_{i - 2,0} \\ dp_{i - 2,1} \end{pmatrix} ，所以有

(dpn,0dpn,1)=(∑j=1msj(sj+lj)∑j=1msj2∑j=1mlj(sj+lj)∑j=1msjlj)n−1(dp1,0dp1,1)\begin{pmatrix} dp_{n,0} \\ dp_{n,1} \end{pmatrix} = \begin{pmatrix} \sum\limits_{j = 1}^{m}s_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}^{2} \\ \sum\limits_{j = 1}^{m}l_{j}(s_{j} + l_{j}) & \sum\limits_{j = 1}^{m}s_{j}l_{j} \end{pmatrix} ^ {n - 1} \begin{pmatrix} dp_{1,0} \\ dp_{1,1} \end{pmatrix}

我们就可以用矩阵快速幂来写啦。最后统计答案就是把每一个屋子作为终点的方案统计出来。

然后上午切了一道水紫，用 STL string 就能过，不过是2003年的题，那个时候还只有 c++98

下午#

CF2014F Sheriff’s Defense#

一道简单的树形dp，设 dpu,0dp_{u,0} 表示不选 uu 这个点，uu 及其子树的最大答案，dpu,1dp_{u,1} 表示选 uu 这个点的最大答案。设 vv 为 uu 的子节点，分两种情况讨论：

  • 不选 uu ，则这样子对子树没有影响，子节点选或不选都可以。有dp方程：dpu,0=∑vmax(dpv,0,dpv,1)dp_{u,0} = \sum\limits_{v}max(dp_{v,0},dp_{v,1})
  • 选 uu ，如果子树不选，对子树没有影响，而如果子树选的话，那么他们就会相互影响，答案就要减掉一个 2×c2\times c 。有dp方程：dpu,1=∑vmax(dpv,0,dpv1−2×c)dp_{u,1} = \sum\limits_{v}max(dp_{v,0},dp_{v_1} - 2 \times c)

然后这道题就解完了，实在是简单的一道树形dp（虽然我还是看了题解）,但是我T了一次，死因：memset。
如图：上面是用 for 循环初始化，而下面是用 memset 初始化。

他们那些打 NOIp 的，今天下午放学就能回家，明天下午还不用来，而我们这些菜狗，不仅要上晚自习，明天下午还要考 NOIp 真题。我的评价是：都怪我 T2 贪心没打出来，不然就有提高1=还能去 NOIp 。亏麻了。

晚上：#

回来先和 hrl 打了两把斗地主，虽然只有两个人，但是还是打上了。第一局的地主牌是 A,2,小王,大王 。我深度怀疑没洗匀（啊其实就是没洗匀），但是就这地主牌，他居然没赢？？！也是会打。然后 yzp 说他去年没考过初赛，心态爆炸了，于是，yzp 和 wgc 就此开始了讲述自己的OI生涯（啊我也讲了的）但是讲到一半，江雨航和 hrl 就拉着我去斗地主了。然后打到一半，祝老来了，于是我们就没打了，开始写题。

CF2022C Gerrymandering#

设 dpi,0dp_{i,0} 表示前 ii 列都考虑了，dpi,1dp_{i,1} 表示还多考虑了下一列的上面那栋房子，dpi,2dp_{i,2} 表示多考虑了下一列的下面那栋房子。然后就是十分弱智但是考耐心的转移。没甚说的。但是这么恶心的代码我居然一遍过了，码力也是十分可以。

今天切了 1111 道题，也是十分可以，于是我打算休息一下。我看了一下，怎么拿 c++ 发 udp 包，但是代码又要在 Visual Studio 里才能跑。我还是学学 python 吧。