杂题

以你之姓@ 2023-10-10 10:23 38阅读 0赞

# ** 聪明的质监员** #

先胡乱打了个二分，1~w二分直接和上一个ans 比较如果小的话往左跑，大的话往右跑。

然后总感觉不对，发现这么搞是错的因为和s相比要得最优解就需使值尽量接近所以求出来的turnans假如大于s往左反之往右。

然后超时显然挨个枚举的时间复杂度太高为log2n\*m\*l所以想到删去一个循环而m的循环显然不可删所以想到了sort直接合并在一个循环中干发现并不对。

想了半天最后看题解将l不一定要删去而是利用求区间以及数的特点想到前缀和将m\*l变为n+m;先跑一遍n预处理出sumw和sumv的前缀和到时直接枚举m算即可避免了枚举m区间中的元素。

前缀和......

# **栅栏** #

暴力搜索tle然后剪枝，去掉冗杂的情况，用一个mark数组if(mark\[i\]\[turn\[i\]\]这种情况有过不再访问)，但需住意m和1~mid的循环顺序，eg1.xu:4 2 6,ti：4 2 6假如先搜到在6的木板上砍出4和2剩下6就无法弄出而mark\[3\]\[0\]==1,下次搜到在6上砍6就无法继续了

所以得出在木板相同情况下尽量处理需求长度大的木板所以对1—n(需要)sort,从mid搜到1.

然后wa了样例91，发现还有类似eg.xu:25 15 11,ti:25 26,

正解：在26上砍15和11在25上砍15.所以对于一块有需求的木板尽量用小的木板来砍出所以sort1-m循环1-m顺序就调对了但内存稍大。

另解：前缀和卡去无用mid

# **覆盖问题** #

一开始看到有点懵朦胧中开始打维护了很多，后来把大块分成了左上左下右上右下，然后又对每个mid跑4遍n依次卡去左上。。。。。。如果有一个符合即可。。。疯狂WA0,然后发现l看成了s，wa20以为细节实际思路是错的eg，一条线上分不开

所以搜索和回溯，对于一个大块找出左右4个顶点依次枚举删去每一块对剩下的块每卡一块记录快个数并删点卡4块能删完即可

# **靶形数独** #

暴力搜索45分发现对每个点都把所有点搜了一遍然后从1，1开始填每一个点t80,把pos,mul.i,j从时刻求改为预处理没有什么大用，二进制优化卡去无用bool型判断，用01串表示填过的数eg111111101表示2已用对每行每列每块都保留状态相与得能填的数。T90改变搜索顺序从左下到右上ac.

暴搜关键：全局bool 型judge 判断符合条件与否.

预处理技巧：先找中间return然后即可一大块的继续判断抛去了中心的不同也可数组初始化打\{6,6,6,6.。。。。。\}；

# ** 传染病控制** #

记录深度按照深度搜索记录每个深度的所有节点枚举卡去num\[i\]预处理出一个点的儿子节点加上它的个数初始cnt=n,枚举并减去num\[v\]即可，但需要标记子节点所以用dfs序记录order指向的点即可，对于每个子节点o(1)标记o(1)查询，然后发现内层循环j打错成i将深度x和点v搞混，然后wa80,读题感觉当不可能有健康人被感染时，疾病就中止传播

有点不对所以造了组数据发现提前把人卡完及对下个深度所有点都标记就无法到count=0;

所以特批return即可。

# **聪聪和可可** #

预处理出最短路然后利用最短路预处理猫在i,鼠在j时猫走一步走到了哪；

然后打dfs暴力，t掉。（之前wa50是因为if(pct\*(cnt+1)<0.001）return是不对的因为一点一点的递增也可以达到同样效果。

T和ac代码的不同在于用f数组可以记忆化搜索直接乘上概率就行，到时搜到直接return，但dfs暴搜就有很多的重复。

Ac代码还需注意if(f\[i\]\[j\]) return,不然不仅重复搜索而且用f\[i\]\[j\]+=...的形式会重复加错误。

# **Easy**  #

1.  用概率\*得分相加，概率及得分增加的概率，=（g\[i-1\]+1）\*(g\[i-1\]+1)-(g\[i-1\]\*g\[i-1\])=2\*g\[i-1\]+1;概率分别为0,1,0.5；
2.  如果a\[i\]=’o’,f\[i\]=(g\[i\]\*g\[i\])+ago\[f\[i\]\]（考虑有断带的情况加上以往的期望得分），

网站解释：2、当*s*\[*i*\]==*o*，则*f*\[*i*\]=*f*\[*i*−1\]+2∗*g*\[*i*−1\]+1,*g*\[*i*\]=*g*\[*i*−1\]+1（*f*\[*i*\]=*f*\[*i*−1\]+2∗*g*\[*i*−1\]+1是因为*f*\[*i*\]=(*g*\[*i*−1\]+1)2=*g*\[*i*−1\]2+2∗*g*\[*i*−1\]+1,*g*\[*i*−1\]2=*f*\[*i*−1\]）;

不能将其中的g\[i-1\]^2认为是g\[i-1\]\*g\[i-1\],期望平方不等于平方的期望。

错误理解：这里其实是错的因为g\[i-1\]+1默认为他连续，

所以应为

*f*\[*i*\]=(*g*\[*i*−1\]+1)2+ago\[f\[i\]\]=*g*\[*i*−1\]2+2∗*g*\[*i*−1\]+1+ago\[f\[i\]\],*g*\[*i*−1\]2=*f*\[*i*−1\]-ago\[f\[i\]\]）; 前后消去了但ago\[i\],在解释式子中不应砍去

# **OSU!**  #

关键：期望的平方不等于平方的期望，这么看来上面EASY题解网页上是对的，

F\[i\]=f\[i-1\]+((leng\[i-1\]+1)^3-leng\[i-1\]^3)\*a\[i\];

(leng\[i-1\]+1)^3-leng\[i-1\]^3=1+3\*leng\[i-1\]^2+leng\[i-1\],

不能直接这么用是因为leng\[i-1\]^2!=leng\[i-1\]\*leng\[i-1\],这里代表的是平方的期望而不是期望的平方一个是长度平方乘概率一个是长度平方乘概率平方。

E（(X+1)^2）=E(x^2+1+2x)=E(x^2)+1+2E（x）,e(x)及leng\[x\],所以提外处理e\[x^2\];

# **抵制克苏恩** #

这题其实用记忆华搜索和聪聪和可可是一样的思路。注意的是dp数组+搜索将问题简单化原来可能会search很多遍一点一点加转为dp\[k\]\[ka\]\[kb\]\[kc\]=f\[ka\]\[kb\]\[kc\](1/a+b+c+1);return时直接乘上这种情况发生的概率即可。当然也和dp差不多for循环倒叙x先求出k。。。其实和search一样。将末端的期望伤害固定。

# **概率充电器** #

树上期望dp这题恶心的地方就是双向边而且每个点都有自己点亮自己的概率。所以分开考虑；

法一：概率加法和概率减法：

对于两个相互独立的事件A、B，P(A+B)=P(A)+P(B)-P(A)\*P(B)，P(A)=(P(A+B)-P(B))/(1-P(B))。（！！）

我们可以用两次dfs求出f1、f2的值。

①对于f1，由于树中叶子节点不存在孩子，f1\[叶子结点\]=q\[叶子结点\]，而对于非叶子节点，f1\[i\]=q\[i\]+∑f1\[son\]\*p（注意这里的加法运算指代的是上述提到的

概率加法）

②对于只由父亲贡献充电，我们考虑两个父子元件。对于父亲本身来说，给儿子充电的概率=总概率-儿子给自己充电的概率，pfa=f2\[fa\]-f1\[now\]\*p(同样这里的减法用上面的概率加法)

f2\[now\]=f1\[now\]+pfa\*p（同理这里的加法用的是上述的概率加法）

解释： f\[fa\]+=f\[son\]\*line\[i\].w-f\[fa\]\*f\[son\]\*line\[i\].w;//(不能直接加得减去father通电的情况下son又传给了father的概率,这种状况下并不是儿子使他亮的)；

Pfa是先算出了f\[x\]除去儿子对它的贡献后亮的概率so,pfa\*p就是father对son的贡献概率再次使用概率加法；。。。概率加法减法需是严格的概率。

法二：既然直接算f\[处于充电状态\]这么麻烦考虑f\[处于充电状态\]=1-f\[不处于充电状态\]；

F\[不\]初始就=1-p\[i\];然后再求儿子对它贡献时直接乘上概率即可。

F\[x\]\*=1-(1-f\[v\])\*line\[i\].w;其中式子的后部分并没有f\[x\]，所以计算fa贡献时可以直接除去就可以求出除了v对它贡献外的概率再让f\[v\]\*=即可

（法一中的f\[x\]+=...后部分中有f\[x\],第二遍dfs就不能直接减了）；

所以就将恶心的概率加减法变成乘法直接乘除。

最终ans+=1-f\[i\];即可思路简单了很多。

# **走迷宫** #

有强连通分量考虑对每个强连通分量高斯消元。

F\[x\]=f\[x\]+sigma(f\[v\]+1)/out\[x\];

先进行trajan缩点（最好对缩完点后的图重建一个图用vector记录SCC中的小点方便高斯）。拓扑排序进行倒退，f\[t\]=1,x->v,f\[v\]+=(f\[x\]+1)/out\[v\],其中out\[v\]是初始图。（因为算的是期望所以对于f\[v\]到达f\[t\]的可能得/out\[v\]而不是out\[x\]）.拓扑原因：对于正在消的点其出边指向的点（及能更新f\[正在消的点\]）已bfs过所以是对的。

对于每个SCC直接高斯然后在ans更新f\[x\]的函数中直接对belong\[v\]!=belong\[x\]的点消出度更新f值；

错误两次：1.还未进行高斯就对SCC指向的点更新了；

2.高斯消元w未memset.

# **The Prices**  #

看了半天才知道想当于背包是啥意思：f\[i\]\[j\]=f\[i-1\]\[k\]+c\[1\]+c\[2\]+...(相差的总额)+d\[i\];这是一个类似于背包的式子（k=j-x）;所以用已知推未知把背包反着来f\[i\]\[j+k\]推以后的j 对于每一个i来说先来f\[i\]\[j\]的基础一部分基础是正确的用正确的推出再正确(0是正确的)最后用背包不断更新i相关j最后再比较确定正确

for(int j=0;j<(1<<m);j++)  f\[i\]\[j\]=f\[i-1\]\[j\]+d\[i\];  //为了以后不用实时加上d\[i\]; （i-1,0是正确的用这个为基础推），这个也是其中一钟状态正好比较

for(int j=0;j<(1<<m);j++) f\[i\]\[j\]=min(f\[i\]\[j\],f\[i-1\]\[j\]);//这是啥都不买的情况

# **班服** #

一开始思路是错的用01串表示了每个样式在哪个队中方便查找（其实用boolmark就行）而且f\[i\]\[j\]表示到i选j的方案数，发现不对因为其中很复杂不能直接加减。

所以可以将目光转向样式因为样式有重叠就不行所以这样想会简单些，而i<=10,很容易想到状压（j表示所有队依次的状态（选没选）），

f\[i\]\[j\]=sigmaf\[i-1\]\[j^(1<<（k-1）)\]+f\[i-1\]\[j\],k是包含i样式的班级

因为对于j状态来说可能得到它的上一个状态就是......f\[i\]\[j\]表示考虑到样式i的贡献时状态为j的方案数

# **字符串的距离** #

设字符串A和B的字串A\[1...i\]和B\[1...j\]的扩展距离是val(i, j)；

用dp把问题小化

依题意，字符串A和B有三种可能的情况：

1）A串最后一个字符是空格，B串最后一个字符是字母，则val(i, j) = val(i-1, j) + k；