文章列表
爬取豆瓣Top250电影信息
使用了 request、re (正则)、csv 模块 #爬取豆瓣 Top250 的电影名称,评分,导演与演员import requestsimport reimport csvurl = "https://movie.douban.com/top250" #豆瓣链接headers = { # headers,伪装浏览器访问 "User-Agent":": Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko)...
more...数学期望
期望:结果乘以结果出现的概率 E(X+Y)=E(X)+E(Y)E(X+Y)=E(X)+E(Y)E(X+Y)=E(X)+E(Y) E(XY)=E(X)E(Y)——(X和Y相互独立)E(XY)=E(X)E(Y)——(X和Y相互独立)E(XY)=E(X)E(Y)——(X和Y相互独立) # 问题一 # 描述 投硬币,连续出现 K 次正面的投掷次数期望值。 # 解法 假设已经连续抛出n−1n-1n−1 次正面,需要Tn−1T_{n−1}Tn−1 次。想得到nnn 次正面,则再进行一次投掷Tn=Tn−1+1+?Tn=T_{n−1}+1+?Tn=Tn−1+1+? 若硬币为正面则游戏结束,还需要抛 0...
more...CCPC2021网络赛复赛
# Primality Test 根据题意可知,求连续两个质数相加除以 2 向下取整后是否还是质数,因为是连续的两个质数,所以取中位数后一定不会是质数,1 除外 #include <bits/stdc++.h>using namespace std;typedef long long LL;LL t , n;int main(){ scanf("%lld" , &t); while (t --) { scanf("%lld" , &n); if (n == 1)...
more...ICPC2021网络赛2
# # L Euler Function 题目大意: 给定 n 个数字,每一个数字不超过 100,m 次询问 把一个区间的所有数字乘以 w (w<=100) 求一个区间所有数的欧拉函数和 (mod 998244353) 首先明白一个性质: phi(n)=n/(p1∗p2∗p3...)∗(p1−1)∗(p2−1)∗(p3−1)...phi(n)=n/(p1*p2*p3...)*(p1-1)*(p2-1)*(p3-1)...phi(n)=n/(p1∗p2∗p3...)∗(p1−1)∗(p2−1)∗(p3−1)... 而 n...
more...targan缩点
用途:用来缩点(实际是用来缩强连通分量) 强连通分量:在有向图 G 中,如果两个顶点 u,v间有一条从u到v的有向路径,同时还有一条从v到u的有向路径,则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通,称 G 是一个强连通图。有向非强连通图的极大强连通子图,称为强连通分量。 # 算法流程 首先需要引入几个数组: dfn [i]: 表示刚遍历到 i 号节点的时间戳 low [i]: 设以 i 为根的子树为 Subtree (i),low [i] 定义为以下节点的 dfn 最小值:subtree (i) 中的节点、从 Subtree 中连出一条不指向子树的边 idx [i]:...
more...A*算法
A * 算法在求一个点到目标点的最短距离时,可以加快速度,如果使用 dijstla 是 nlogn 的时复,但是 A * 更快,当节点足够多,边足够大时,可能不能求起点到所有点的最短距离,空间不够或者时复顶不住,这个时候 A* 或许能做,A * 使用了一个启发式函数 f (),其含义是节点到终点的估计距离,这个距离可以是曼哈顿距离,可以是实际到终点的最短距离等等,只要满足估计距离小于等于实际距离即可,只要满足了这个,那么用 f (u)+dis (u) 当作优先队列的排序规则,每次取出最小值,这个点的最短距离就确定了,证明我找不到, 画个图可以想一下是有道理的 # ACWing.178. 第...
more...Leetcode-1915-最美字符串数量
# 最美子字符串的数目 美丽的字符串定义为该字符串至多一个字母出现奇数次,给定一个字符串求该字符串包含多少个美丽的子串。(该字符串由前十个小写英文字母组成) 由于只会由前 10 个字母组成,所以可以把所有的字符当作一个二进制位,0 表示该字符出现了偶数次,1 代表字符出现了奇数次,那么现在好的状态就变成了 0 和 2i,我们从前往后遍历字符串,求一个前缀异或状态,两个前缀异或起来即可得到一段区间的状态,那么问题就转化为了所有的位置前面有多少个状态和当前状态异或后是一个好的状态,如此我们就可以开一个数组 cnt [i] 记录从起始位置到当前位置 i 状态出现的次数,ans+=cnt...
more...Bellman-ford
# Bellman-ford 用途: 判负环 计算含有负权边的最短路径 重边不会影响答案,因为 Bellman-ford 会遍历所有的边 # 算法流程 先存边,Bellman-ford 的存边十分随意,什么储存方式都可以,只有一个要求,就是每次都要遍历到所有的边! 既然如此就用一个结构体去存,一个 for 循环就可以遍历到所有的边了。 struct node{ int u,v,w}e[MAXN];算法十分简单,每次只要让所有的边进行一次更新即可,如果不存在负环,那么一个点最多被 n-1 个点更新 (除了自己),所以外层循环遍历 n-1...
more...判断是否存在一条线经过所有线段
# ACWING 如果一条直线经过了所有线段,那么把这条直线旋转之后,边界就是卡在两个线段的端点处 那么就可以遍历每两个端点,判断这两个端点组成的直线是否穿过了所有的线段,如果是,则存在,不是继续找,找不到就不存在 如何判断一条直线是否经过了所有点呢?挨个判断这条线是否穿过线段 #include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optimize(3,"Ofast","inline")#define debug...
more...