PocketCat blog

2021.12.04 下午 4 点，第 46 届 ACM/ICPC 南京站圆满结束，同时这也寓意着我的 ACM 生涯到此也正式画上了句号。 # 生涯战绩 2020 - 河南省 CCPC - 银牌 2020 - 天梯赛 - 国三 2021 - 蓝桥杯 - 国二 2021 - 河南省 ICPC - 银牌 2021 - 天梯赛 - 国二 2021 - 河南省 CCPC - 银牌 2021-ICPC 南京站 - 铜牌 # 相遇   我与 ACM 的接触纯属偶然，甚至对于计算机专业的选择我也并不自信，19...

通过 Beautiful 定位标签，获取图片链接，仅限于图片直接内嵌于网页源代码中，有的网站图片链接藏在 js 文件，无法爬取 #爬取 umei.cc 中的图片import requestsfrom bs4 import BeautifulSoupdomain = "https://umei.cc/katongdongman/dongmantupian/" #网站地址headers = { "User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64)...

使用了 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)...

期望：结果乘以结果出现的概率 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...

# POJ2420 三分和二分输出答案是 l 还是 r 就看中间的判断条件，不满足条件更新的那个值就是要输出的值 #include <iostream>#include <cmath>#include <iomanip>#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)#define endl '\n'using namespace std;const int N=1e3+100;const double eps=1e-5;int n;int...

# 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)...

# # 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...

用途：用来缩点（实际是用来缩强连通分量） 强连通分量：在有向图 G 中，如果两个顶点 u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。 # 算法流程 首先需要引入几个数组： dfn [i]: 表示刚遍历到 i 号节点的时间戳 low [i]: 设以 i 为根的子树为 Subtree (i)，low [i] 定义为以下节点的 dfn 最小值：subtree (i) 中的节点、从 Subtree 中连出一条不指向子树的边 idx [i]:...

A * 算法在求一个点到目标点的最短距离时，可以加快速度，如果使用 dijstla 是 nlogn 的时复，但是 A * 更快，当节点足够多，边足够大时，可能不能求起点到所有点的最短距离，空间不够或者时复顶不住，这个时候 A* 或许能做，A * 使用了一个启发式函数 f ()，其含义是节点到终点的估计距离，这个距离可以是曼哈顿距离，可以是实际到终点的最短距离等等，只要满足估计距离小于等于实际距离即可，只要满足了这个，那么用 f (u)+dis (u) 当作优先队列的排序规则，每次取出最小值，这个点的最短距离就确定了，证明我找不到， 画个图可以想一下是有道理的 # ACWing.178. 第...

# 最美子字符串的数目 美丽的字符串定义为该字符串至多一个字母出现奇数次，给定一个字符串求该字符串包含多少个美丽的子串。（该字符串由前十个小写英文字母组成） 由于只会由前 10 个字母组成，所以可以把所有的字符当作一个二进制位，0 表示该字符出现了偶数次，1 代表字符出现了奇数次，那么现在好的状态就变成了 0 和 2i，我们从前往后遍历字符串，求一个前缀异或状态，两个前缀异或起来即可得到一段区间的状态，那么问题就转化为了所有的位置前面有多少个状态和当前状态异或后是一个好的状态，如此我们就可以开一个数组 cnt [i] 记录从起始位置到当前位置 i 状态出现的次数，ans+=cnt...

AC 自动机以 trie 为基础，结合了 kmp 的 next 数组思想而创造出来的一种数据结构，用来解决多模式串匹配问题 # 问题背景 P3808 【模板】AC 自动机（简单版） 给定 n 个模式串（n<=1e6n<=1e6n<=1e6），一个主串 s（s<=1e6s<=1e6s<=1e6），问主串中包含多少个这些之中的模式串？ # AC 自动机 传统做法，利用 KMP，O (n) 遍历每一个模式串，O (n) 匹配是否包含此模式串，复杂度 O (n2) 利用 AC 自动机，先把所有的模式串插入到 trie...

# Bellman-ford 用途： 判负环 计算含有负权边的最短路径 重边不会影响答案，因为 Bellman-ford 会遍历所有的边 # 算法流程 先存边，Bellman-ford 的存边十分随意，什么储存方式都可以，只有一个要求，就是每次都要遍历到所有的边！ 既然如此就用一个结构体去存，一个 for 循环就可以遍历到所有的边了。 struct node{ int u,v,w}e[MAXN];算法十分简单，每次只要让所有的边进行一次更新即可，如果不存在负环，那么一个点最多被 n-1 个点更新 (除了自己)，所以外层循环遍历 n-1...

数位 DP 解决的是求一段区间中满足一定条件的数的数量，形式固定 # 数位 DP 模板 int num[100],dp[100][...];int dfs(int pos,int ...,bool limit) { if(pos==0) return ; if(!limit && dp[pos][...]!=-1) return dp[pos][...]; int up=limit?num[pos]:9; int sum=0; for(int i=0; i<=up; i++) { if(...)...

半平面交用于求几个凸包围成的面积 一条直线可以将平面分为两部分，我们取左半部分，右半部分舍弃，那么所有的直线围成的左半部分的面积的交集就是半平面交。 # 算法流程 首先把所有线首先按照角度从小到大排序，角度相同就按照线从左到右排序，排序后用一个双端队列来维护，每次新进来一条边，判断这条边是否在队列的队尾两条边的交点左边，如果是，就把队尾元素 pop 出去，如此往复，队头也是如此，所有边遍历完后还要用队头去维护队尾，用队尾去维护队头 # 线点 struct point{ double x,y;}pt[MAXN];struct...

# ACWING 如果一条直线经过了所有线段，那么把这条直线旋转之后，边界就是卡在两个线段的端点处 那么就可以遍历每两个端点，判断这两个端点组成的直线是否穿过了所有的线段，如果是，则存在，不是继续找，找不到就不存在 如何判断一条直线是否经过了所有点呢？挨个判断这条线是否穿过线段 #include <bits/stdc++.h>//#pragma G++ optimize(2)//#pragma G++ optimize(3,"Ofast","inline")#define debug...