十月日记

10.4

今天进校门并没有遇到问题

也是回到了\(505\)机房老位置

有点困，所以模拟赛打的跟⑩一样 \(awa\)

\(T1\) 想到可以二进制拆开，然后把平方转换后直接做就行，但突然一瞬，想法没了（

调了半天 \(20\) 暴力，最后才想起来异或不能取模

\(T2\) 突然想到可以可以转成\(\sum_{i=1}^{n-m+1}{x_i}=m\)
但忘了可以插板

\(T3\) 懒得想正解(也想不出来awa)，直接 \(O(qn^2)\) 了

\(T4\) 暴力

10.5

今天没歿縌毸，\(vjudge\)刷专题

锣鼓上午活了一会就似了

我这台机子过一会就没网，解决方法：重插网线或狂刷新所有页面

园子消息.msg似了，对着红点难受了下午

10.6

比亚迪暑集就打了一场模拟赛，正好是今天原

改后\(T1\) 状压，分讨失败，并将freopen注释掉了，挂\(20pts\)

\(T2\) 第二个部分分直接记录每个点的状态，查询直接暴力向前走

刚开T2：x可能为0，一定要特判

T2宝玲后：为什么全RE？

qwq

\(T3\) 不会，手膜样例2没懂，发现概率是 \(\frac{34}{432},\frac{123}{432},\frac{275}{432}\)，\(0pts\)

\(T4\) 直接输出两点之间距离，\(20pts\)

10.7

\(T1\)

赛时交成 \(T2\) 代码了，挂 \(80pts\) T_T

\(80pts\)

\(O((nm)^2)\)枚举相同颜色位置，即枚举所有四角颜色相同的矩形

用\(\frac{n\times(n+1)\times m\times(m+1)}{4}-cnt\)即可

实测随机数据下跑的飞快

但\(c_{i,j}=0,1\)正好给卡了，所以只有 \(80\)

正解

考虑固定颜色相同的同一行两个位置，\(n^2\)枚举即可

固定后，从上到下扫一遍，每次cnt++并ans+=cnt正好可以做到不重不漏

\(T2\)

正解

先想部分分，由于时间与时间之间相互独立所以可以直接乘起来

记 \(cnt_i\) 表示时间 \(i\) 有 \(cnt_i\) 个不拥挤地点

答案就是 \(\prod_{i=S}^T cnt_i\)

可是值域很大，开不起数组

但操作却不算太多（起码能开下）

所以可以类比离散化的思想，将每一次的操作的时间记录下来，然后对每一次的操作，使用数据结构维护区间修改，最后单点查询每一段的值，用 \(n\) 减掉即为本段时间的不拥挤地点数 \(cnt_i\)

\(T3\)

正解

区间\(dp\)

考虑答案只会在一个查询经过一个点 \(k\) 并和区间 \(\left[l,r\right]\) 有交集但不包含是时如果在此处断开就会使答案增加

所以便可以 \(dp\)，转移时，枚举断点，考虑转移时的代价 \(cost(l,r,k)\) 就是符合使答案增加的询问数

因为 \(k\) 在区间内，所以只需要考虑包含关系，可以使用二维前缀和的思想，最后用过 \(k\) 区间数减掉包含 \(\left[l,r\right]\)的区间数即可

\(T4\)

正解

设 \(p_i\) 为 \(i\) 号箱子有猫的概率，\(b_i\) 为 \(i\) 链接的隧道通向的点

为方便用 \(x\) 代替 \(p_i\), \(y\) 代替 \(p_{b_i}\)

考虑一条链的情况，因为两个箱子之间相互独立，故直接转移，\(x=x\times y, y=1-(1-x)(1-y)\)

但本题会出现环，而环两端的点并不相互独立，所以要另寻他发

可以枚举两个端点的状态，用出现此种情况的概率乘上转移出来的 \(p_n\) 再加起来即可

细节:只需求出包含 \(n\) 的基环树中的点即可

偶然想起来可以写写日记(绝不是因为以前懒)
以前的以后再补，咕咕咕