Doraemon's Blog

2021.12.04下午4点，第46届ACM/ICPC南京站圆满结束，同时这也寓意着我的ACM生涯到此也正式画上了句号。 生涯战绩 2020-河南省CCPC-银牌 2020-天梯赛-国三 2021-蓝桥杯-国二 2021-河南省ICPC-银牌 2021-天梯赛-国二 2021-河南省CCPC-银牌 2021-ICPC南京站-铜牌 相遇  我与ACM的接触纯属偶然，甚至对于计算机专业的选择我也并不自信，19年高考失利，伴随着不再复读的决心进入了我的分数可以达到的最好专业，刚入学时，因为对新事物的好奇，我奔走于各个社团之间，希望能丰富自己的大学生活。十月份学校举行百团大战活动，我在许多社团都填了报名表，但不幸的是，没有一个社团愿意收我咱也不知道他们收人的标准是什么咱也不敢问，当时我一直在参与微控科创协会的C语言培训，一周大概有3次，每次2个小时左右，当时我真的是一个纯小白，但经过了一段时间的C语言学习，我慢慢地爱上了这门语言，还记得当时在控制台打印出杨辉三角时，我内心不可言喻的欣喜。   某天晚上，班群里发来了算法协会的一个招新公告，我当时对 ...

通过Beautiful定位标签，获取图片链接，仅限于图片直接内嵌于网页源代码中，有的网站图片链接藏在js文件，无法爬取 1234567891011121314151617181920212223242526#爬取umei.cc中的图片import requestsfrom bs4 import BeautifulSoupdomain = "https://umei.cc/katongdongman/dongmantupian/" #网站地址headers = { "User-Agent": "Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/96.0.4664.45 Safari/537.36"}res = requests.get(domain, headers=headers)res.encoding = 'utf-8' #防止中文乱码conten ...

使用了request、re(正则)、csv模块 123456789101112131415161718192021222324252627282930#爬取豆瓣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) Chrome/96.0.4664.45 Safari/537.36"}obj = re.compile(r'<li>.*?<span class="title">(?P<name>.*?)</span>.*?&# ...

期望: 结果乘以结果出现的概率 $E(X+Y)=E(X)+E(Y)$ $E(XY)=E(X)E(Y)——(X和Y相互独立)$ 问题一描述投硬币，连续出现K次正面的投掷次数期望值。 解法假设已经连续抛出$n-1$次正面，需要$T{n−1}$次。想得到$n$次正面，则再进行一次投掷$Tn=T{n−1}+1+?$ 若硬币为正面则游戏结束，还需要抛0次$Tn=T_{n−1}+1+0.5∗0+?$） 如果硬币为反面，则游戏重来，还需要投掷$0.5∗Tn$次，递推公式如下所示： $Tn=T_{n−1}+1+0.5∗0+0.5∗Tn$ 求出通项公式: $Tn=2^{n+1}+2$ 问题二题目链接 设dp[i]表示i个座位最后坐满人的情况，那么对于n个座位而言，第一个人上车就有n个选择，坐在第一个位置，剩下的就是dp[n-2]，坐在第二个位置，剩下的就是$dp[0]+dp[n-3]$，坐在第三个位置，剩下的就是$dp[1]+dp[n-4]$，以此类推… 求个和，就是$2*sum[n-2]$，sum[n-2]表示前n-2项的前缀和(dp[0]=0) 还要把第一个人加上，因为有n个选择，所以加n，每 ...

POJ2420三分和二分输出答案是l还是r就看中间的判断条件，不满足条件更新的那个值就是要输出的值 12345678910111213141516171819202122232425262728293031323334353637383940#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 a[N],b[N];double getdis(double x,double y){ double res=0; for(int i=1;i<=n;i++) res+=sqrt(pow(x-a[i],2)+pow(y-b[i],2)); return res;}double ...

Primality Test根据题意可知，求连续两个质数相加除以2向下取整后是否还是质数，因为是连续的两个质数，所以取中位数后一定不会是质数，1除外 123456789101112131415#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) printf("YES\n"); else printf("NO\n"); } return 0;} Nun Heh Heh Aaaaaaaaaaa给定一个字符串，求这个字符串有多少个子序列满足由前缀nunhehheh和k个a(k>0)组成。 例如nunhehhehaaaa ...

L Euler Function 题目大意： 给定n个数字，每一个数字不超过100，m次询问 把一个区间的所有数字乘以w(w<=100) 求一个区间所有数的欧拉函数和(mod 998244353) 首先明白一个性质： $phi(n)=n/(p1p2p3…)(p1-1)(p2-1)*(p3-1)…$ 而n也可以表示为$p1p2p3…$ 所以$phi(n)=(p1-1)(p2-1)(p3-1)…$ 那么$phi(w*n)$的值怎么求？ 把w质因子分解，可以发现如果n和w有同一个质因子c，那么$phi(cn)=phi(n)c$，如果存在一个质因子w有，n没有，那么$phi(cn)=phi(n)(c-1)$，发现w的质因子在要乘的区间中都有，那么这道题就变成了简单的区间乘法，区间询问，但是区间中不一定包含w的所有质因子，所以就要去找到那些不包含w的某个质因子的位置，把这些位置单独拿出来乘以(c-1)，如何找到这些位置呢？ 可以考虑开一个vis数组，vis[x]标记一个区间是否都存在质因子x，那么每次做区间乘法时，就可以把w质因子分解，对于每一个质因子c，都去线段树中找，如果一个区间 ...

> 用途：用来缩点（实际是用来缩强连通分量） 强连通分量：在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。 算法流程首先需要引入几个数组： dfn[i]: 表示刚遍历到i号节点的时间戳 low[i]: 设以i为根的子树为Subtree(i)，low[i]定义为以下节点的dfn最小值：subtree(i)中的节点、从Subtree中连出一条不指向子树的边 idx[i]: 缩完强连通分量后i号节点后所在的缩点编号 siz[i]: 缩点的子树大小 那么代码就可以写了 1234567891011121314151617181920212223242526void targan(int x){ dfn[x]=low[x]=++tim; stk.push(x); instk[x]=1; for(int i=h[x];~i;i=e[i].next){ int v=e[i].to; if(!dfn[ ...

A*算法在求一个点到目标点的最短距离时，可以加快速度，如果使用dijstla是nlogn的时复，但是A*更快，当节点足够多，边足够大时，可能不能求起点到所有点的最短距离，空间不够或者时复顶不住，这个时候A*或许能做，A使用了一个启发式函数f()，其含义是节点到终点的估计距离，这个距离可以是曼哈顿距离，可以是实际到终点的最短距离等等，只要满足*估计距离小于等于实际距离即可，只要满足了这个，那么用f(u)+dis(u)当作优先队列的排序规则，每次取出最小值，这个点的最短距离就确定了，证明我找不到，画个图可以想一下是有道理的 ACWing.178.第K短路 我看到这道题，不会A之前，我只能想到Knlogn的时复，跑K次dijstla…太菜了，其实更好的是使用BFS，给每一个状态加上一个距离，使用优先队列，每次取出距离最小的点，其实就是dijstla，只不过少了dis数组，这样子做如果不加优化空间和时间都顶不住，所以开一个cnt[]数组记录每一个点被更新了几次，如果一个点已经被更新K次了，之后这个点就没必要再入队了，加上这个优化后，时复和空间复杂度最坏就是Knlogn，但是这道题还是过不去 ...

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