CSP-38th

目录

1.正态分布

2.走马

3.信息传输

4.字符串可能性个数

5.最多访问节点个数

---

1.正态分布

本来是很简单的一道模拟题，根据 (n-u) /a 的整数位、十分位确定是在第几行，根据百分位确定是在第几列，但是我直接将 (n-u)/a 乘以100后进行 // 和 % ，忽略了题目中说了 “a是100的因数” ，那么如果我不在第一时间 (n-u)* 100/a 的话会导致小数上的差异。

这个问题我检查了很久才发现，影响了做题节奏，所以还是要先看清楚题目意思，注意题目细节

2.走马

在棋盘上，一棋子从起点按照马的走法，走k步，请问能到的所有可能方块数

太久没做题了，我第一时间竟然发昏地用DFS，注意：这道题是有k步这个条件的，有些节点虽然在前面路径中了，已经add在vis里面，导致提前扼杀了这个点，但是有可能这个点在其他路径里面是较新点，如果你直接杀死他的话会导致他后面的可能性被忽略

虽然可以取消vis的剪纸，坚持add不会影响最后 len(vis) 的个数，但是这样的时间复杂度就过高了

所以像这种k步的想都不用想直接BFS即可

3.信息传输

这道题目就题面长度都有个五六页，真的看都不想看了

4.字符串可能性个数

确定了字符串长度n，中间参杂了m个 # 号，要求至少有一个 cff 字符串在另一个具体什么字符串我忘记了反正长为6

题目解析：# 号将这个长为 n 的空间分割为 m+1 段空间，要求其中要符合上面的要求，其他的随便26字符即可

那么先开个 l 数组，记录 m+1 段空间的长度，再根据长度 3 、6 、9(3+6) 进行挂标记 flag1、flag2、flag3

到时候我们需要实现的要求就是 至少有一个cff在长为6的字符串2左边，这个要求可以用 f2 存储，那么它需要的前置条件就是前面出现过 cff，这个用 f1 存

那么我们的 dfs 搜索树就是从字符串空间的左边到右边的，逐步实现 f1、f2

def dfs(step,now,f1,f2):
#step:当前所在字符串区间
#now:当前搜索路径上的字符串可能数
#f1:前面是否有字符串1
#f2:前面是否有字符串2if step==m+1:#总共m+1段if f2:ans=(ans+now)%MODreturnzong=26**l[step]#总共可能数：每个位置都是26个字符if step in flag1:#从长度更长开始，因为长度越长可能性越多if f2:dfs(step+1,now*zong,1,1)else:if f1:#当前面有f1时可以凑f2now1=(l[step]-6+1)*26**(l[step]-6)dfs(step+1,now1,1,1)now2=zong-now1#也可以不凑，那么就是总可能减去上一个分支dfs(step+1,now2,1,0)else:'''后面的类似，主要是维护 f1 和 f2'''

5.最多访问节点个数

这个问题是一个图论，主要的大意如下：

有很多个浏览节点目标集，对于每个浏览节点目标集：

        在所有节点中有一个节点会被损坏，现在对所有可能性进行求和，也就是 西格玛f(x) ，这里的x就是被损坏的节点

                而且我们的起点也是不固定的，所以要求的是最佳起点，使得上面的 f(x)和最大，也就是 f(x)=max{ f(x,y) } 其中x是断点，y是假设起点

#输入是双向路，到时候我们用链表结构串起来即可def dfs(i,now):#i是断点for new in d[now]:if new==i:continueif new not in vis:vis.add(new)dfs(i,new)for l in c:#目标节点集su=0for i in range(1,n+1):#需要求maxma=0for j in range(1,n+1):#需要求每个 y 时的值vis=set()if j!=i:vis.add(j)#执行bfs获取vis#然后判断vis中有多少在目标集中for li in l:if li in vis:cnt+=1su+=cntprint(su)