A.jsy与他的物理实验 f[i][j]表示做了i次实验得到j分的概率。 初始f[0][8] = 1.0 成功做了第i个实验: f[i][j] += f[i - 1][j - k[i]] * p[i] / 100.0 ($8 \leq j - k[i] < 35$) 未做成第i个实验 : f[i][j] = f[i - 1][j] * (100 - p[i]) / 100.0 ($8 \leq j < 35$) 最后算出期望后除以所有大于等于35分的概率和即为在能修够35分的情况下还需做实验次数的期望。 如果所有实验得分和加起来再加8仍小于35分则输出-1 B.flappy bird 我们只需算出到达每个管道所需耗费的最小体力。 我们可以知道bird的飞行路...

A.face the truth 签到题，只需判断m+m是否大于n即可。 B.flame of despair 这道题标程运用了一些略高级的数据结构，现在看不明白不要紧。 将输入的m个数字当做字符串建立AC自动机，建立好fail指针后建成Trie图。 设三维状态f[i][j][mask]为当前的数字modn为i，并且当前在自动机的j号节点上，当前数字中已经出现过mask这个集合中的串了。 显然初态就是f[0][0][0]，终态是f[0][x][全集]。 所以我们需要找一条从初态到终态的路径，使得走过的路径构成的数字串尽可能小。数字最小首先要位数最小，然后字典序最小。所以只需要从初态开始宽度优先搜索，按字典序的顺序扩展状态，第一个访问到的终态的路径就是答案。 注意数字串是不能有前...

题目链接 嗯……这场是我们出的，好像的确是难了吧。 但这些题在自己看来还是很棒的啊尤其是03，被诟病也都无所谓了。 1001 Chessboard 首先，若$n \lt k$，则棋盘连一个$1×k$的矩形都放不下，输出$0$。 我们只需要考虑$n≥k$的情况。将棋盘类似于黑白染色，按$(i+j)$模$k$划分等价类，给每个格子标一个号。 标号之后，会注意到每条从左下到右上的斜线数字都是相同的，那么对于$s×s$的格子，其内部数字有且恰好有$2s-1$种，所以当$s<={k\over2}$的时候，内部数字有$floor({k\over2})*2-1\lt k$种，所以不能有更佳的方案。 从而证明最优的方案一定是仅剩下一个$s×s$的正方形区域没有被覆盖到，其中$s≤{k\ove...

题目链接 一棵树，点上有权，每次询问以u节点为中心，半径r以内的节点中，权值最大的节点的编号是多少。如果有多个节点，返回编号最小的。 同样用树点分治解决，每次在子树内找到重心后，用vector记录该子树内所有点到中心的距离，排序后记录对应前缀的节点权值最大值。 对于每个询问只需要在每个包含该节点的分治重心内的vector二分查找即可。 特别的，即使在某个分治重心内，询问的点与某个点在一个子树内部。这时这两个节点的距离会被认为是两个节点到重心的距离之和。其实也无所谓，因为这个子树以后也是会被询问到的，那时就可以得到正确的距离，两个节点到重心的距离之和一定不小于正确的距离。 时间复杂度为$O(nlog^2n)$ Written with StackEdit.

题目链接 治愈身心的大模拟题。 推荐大家闲的没事干的时候去写写，绝对比想象的要有趣的多。 真·完全没坑 Written with StackEdit.

题目链接 首先先把题意读明白。 建立出对应Trie的AC自动机，发现题目给出的两个操作都可以对应在Fail树上。 Fail树即把每个节点的fail指针反向构成的树。 我们先研究一下仅修改/查询一个点的情况。 修改一个点，即将这个点在Fail树中的子树节点点权全部+1 查询一个点，即查询Fail树从根到该节点经过节点的权值和 显然修改/查询多个点就是把修改/查询单个点构成的集合并起来。 将Fail树树链剖分，同时得到了树的dfs序列，子树对应一个区间，根到点的路径对应多条重链的并。 修改很简单，只需求出需要修改的区间的并，再对并修改。 查询的话则需要稍微思考一下，询问的是多条从根到各个节点的并的节点权值和。可以发现其实对于每条重链，被询问的部分对应的都是一个...