2022/8/14

2022/8/14

暴力的建出循环mmm次的飞行器图，长度n×m≤5e6n \times m \leq 5e6n×m≤5e6， 之后考虑每个点iii处能一次跳到的位置共有121212个，即筛子数为j∈[1,6]j \in [1, 6]j∈[1,6]直接走到i+ji + ji+j 处后选择不走，或者 走到i+ji + ji+j处后继续选择走ai+ja_{i + j}ai+j​步，即一步内共121212种走法:j∈[1,6], i+jj \in [1, 6], ~i + jj∈[1,6], i+j 和  i+j+ai+j~i + j + a_{i + j} i+j+ai+j​，...

将期望表达式按定义写出后提取公因子，具体步骤： 为了书写方便，令pi=1/pip_i = 1 / p_ipi​=1/pi​，qi=∏j=1i(1−pj) q_i = \prod_{j=1}^i{(1 - p_j)}qi​=∏j=1i​(1−pj​)，特别的令q0=1q_0 = 1q0​=1， Ex=p1×1+q1p2×2+...+qn−1pn×nE_x = p_1 \times 1 + q_1 p_2 \times 2 + ... + q_{n - 1} p_n \times nEx​=p1​×1+q1​p2​×2+...+qn−1​pn​×n ​ +qn p1×(n+1)+qn...

若出现证明错误请指明，个人思路。 图中nnn个点构成共n×(n−1)n×(n - 1)n×(n−1)条无向边的完全图，从原点开始沿着一个严格递减的路径最远可以走到多少点。 很明显的想法就是从原点开始dfs所有可行路径，但是会出现环路走到之前经过的点导致复杂度过高，但可以发现搜索进行过程中一个事实：考虑任意一个环上的起点，从该点选择一条距离dis1dis_1dis1​的出边后经过一系列移动再到该点时只会选择严格小于dis1dis_1dis1​的出边。 所以可以把每个点的n−1n-1n−1条出边按权值排序，每次向下搜索时先递归搜索小的边并同时维护fff数组（f[i][j]f[i][j]f[i][j...

成绩：CB组国一 试题 A: 2022 // 不会 试题 B: 钟表 #include<bits/stdc++.h> using namespace std; int main() { for(int i = 0;i < 6;i ++) for(int j = 0;j < 60;j ++) for(int k = 0;k < 60;k ++) { int s1 = i * 3600 + j * 60 + k; int s2 ...

卢本伟NB

第十三届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组 wls题解 新手，乱写的，有错误和改进下面评论就行。。 先放个代码，吃完饭回来写具体的题解。 A 九进制转十进制 1478 B 顺子日期 题目有歧义，我个人偏向于14 14 (4) C 刷题统计 我是Sb，没看数据范围，典型0分答案↓。 #include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; signed main() { ios::sync_with_stdio(false); int...

新年快乐，卢本伟NB！

不会树旋(比赛时候看着gif图模拟，现学现卖)，不会Splay 依然可通过本题 将被打乱的树和初始树都计算每个结点的深度(定义根节点深度为111)，然后按初始树的广度优先搜索顺序枚举所有结点，如果结点当前深度大于其位于初始树上的深度就一直旋转到深度相同位置（每次旋转都会使当前结点深度−1-1−1），这样贪心的由顶至下将所有结点都恢复到原来的深度即可恢复如初。 至于为什么这么做是对的，比赛期间并没有具体证明，第一感觉就是打乱的树是由初始树一步步旋转而来，左旋右旋互为逆操作，所以可以感性的想象深度相同时位置也会恢复如初。 这样每个结点最多旋转nnn次，总旋转次数≤n(n+1)/2\leq n(n ...

官方题解地址 https://codeforces.com/blog/entry/99067 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEm. A. Not Shading 分四种情况讨论： 若第rrr行第ccc列的元素 (以下简称Ai,jA_{i,j}Ai,j​) 初始就是黑色，则需要操作000次。 若第rrr行或第ccc列存在至少一个黑色格子，则需要操作111次。 若n×mn × mn×m的格子中存在至少一个黑色格子，则需要操作222次即可将n×mn × mn×m的所有格子变成黑色。 若n×mn × mn×m的格子中不存在黑色格子，则无解。 //木の葉舞...

今年最可惜的一场ACM 本来这篇想发到自己的写的博客网页上，写完网页才知道我没有服务器，阿里云海外服务器都卖没了，只能回来发到牛客上了，虽然本来就没人看...。 开局看出B是签到题但是漏读了b数组严格单调递增的条件导致样例都过不去，看了眼榜发现此时J已经过了几十个队就去读了下题发现是个简单模拟题就成功签了个到。 然后继续去想B题，由于A数组的数据范围特别小，所以暴力枚举所有和的可能只有不到200种，每次贪心的去取总时间复杂度大概2e7左右，已知需要的和的大小（sum）时贪心方法为从左到右枚举每一个数(a[i])，判断在其之前最后出现的(我使用的map，这里数据范围只有1-200用数组标记也...