望千鱼`Blog

为什么选择Hexo？    Hexo 是一个基于 Node.js 的静态博客生成工具，它提供了简洁的命令行界面和易于理解的配置文件。     Hexo 拥有活跃的社区，提供了大量的主题和插件，可以轻松实现各种功能和样式定制。     Hexo 生成的是静态网页文件，不需要依赖数据库和服务器端代码，因此具有较高的安全性。 为什么选择Butterfly？  我选择了Butterfly主题，Butterfly是一个自定义性非常高的主题，并且有大量的用户使用，生态非常完善。选取原因如下： 美观现代化     时尚、美观和现代化的设计风格，吸引人的界面和布局，能够给读者留下深刻的印象。 响应式设计     采用响应式设计，可以在各种设备和屏幕尺寸上提供良好的用户体验。可以在桌面、平板电脑和手机等设备上自适应地显示，读者可以随时随地访问你的博客。 可定制性  &en ...

五一上海之旅我❤️上海～时间仓促！可惜没去上海的大学看看😭特别是华师大 【关于交通】🔹杭州东站出发上海虹桥站～🔹市内交通：可以坐公交🚌、地铁🚇、出租，地铁特别不人性化（指示灯非常难看，外地人太不友好啦 【必打卡景点】🔸外滩：在外滩可以感受到大上海的繁华，南京路的高楼足以让我们停驻于此，还有和平饭店，在外滩看东方明珠真的美，真的繁华🌸 🔸田子坊：像北京798，田子坊有很多的设计室、画家工作室等其实一般，比较商业化。 🔸上海博物馆：去一座城市一定要去趟博物馆，去感受这座城市的历史与风貌，上海博物馆还是值得去看 🔸黄浦江夜游：比较推荐，提前预定的，江风吹拂，两岸繁华的景象，太美了🌉 【关于美食】▪️蟹黄面、蟹黄饭：强烈推荐，超好吃，配上熏鱼，可以炫几碗🍜 ▪️上海生煎：外皮金黄，有芝麻，很香，肉馅很嫩，味道还可以 ▪️蝴蝶酥！ 【关于住宿】🏠住在了延安路附近，如果是背包客也可以选择南京路附近的青旅，上海交通很方便. 我爱上海～

A 回文大师 哈希二分/kmp 【补】题目链接 题意：翻译过来就是求每一个前缀串 在原串的反串中有多少个相同的子串 题解：可以构造一个反串枚举反串开始的位置 再二分去找最长的和原前缀匹配（哈希O1判断）的在原串的位置，这个位置之前的所有前缀 的ans都+1，最后答案用差分维护#include <bits/stdc++.h>#define int unsigned long longusing namespace std;const int N=1e6+5;const int M=1e9+7;const int qwq=23333;int p[N];int a[N];int ans[N];int haa[N],hbb[N];int get(int a,int b) { return hbb[b]-hbb[a-1]*p[b-a+1];}signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n; cin>>n; ...

A 疫苗小孩 二分题目链接 题意：题解：#include<bits/stdc++.h>#define int long longusing namespace std;const int N=1e6+5;int pos[N];signed main() { int n; cin>>n; string s; cin>>s;s='.'+s; int cnt=0; for(int i=1; i<=n; i++) { if(s[i]=='0') pos[++cnt]=i; } int k, w, q; cin>>k>>w>>q; int ans=0; for(int i=1; i<=cnt; i++) { int p1=lower_bound(pos+1, pos+1+cnt, pos[i]+k)-pos; ...

A R 模拟题目链接 题意：给一个包含只包含大写字母的字符串，找有多少个子串包含 k 个 R 字符且不包含 P 字符 题解：不包括 P 就分段来计算至少包含 k 个 R贡献就等于这个位置 第前 k 个 R 位置 #include<bits/stdc++.h>#define int long longusing namespace std;const int N=2e5+5;int a[N], p[N];signed main() { int n, k; cin>>n>>k; string s; cin>>s; s=s+"P"; int cnt=0; a[0]=-1; for (int i=0; i<=n; i++) { if(s[i]=='P') a[++cnt]=i; } int ans=0; for(int j=1; j<=cnt; j++) { int cntt=0; p ...

B 智乃买瓜 dp题目链接 题意：有 $ n $ 个物品重量为 $ai$ ，可以买一整个或买一半或不买，问重量和为$1，2…m$的方案数。$ (0<=n<=1e3，1<=m<=1e3, 2<ai<=2*1e3) $ 题解：$dp[i]$ 表示重量和为 $i$ 的方案数转移方程为$if(j>=a[i]) dp[j]+=dp[j-a[i]]$ $dp[j]$从 $dp[j-a[i]]$的状态转移过来$if(j>=a[i]/2) dp[j]+=dp[j-a[i]/2]$ #include <bits/stdc++.h>#define int long longusing namespace std;const int N=2e5+5;const int M=1e9+7;int a[N];int dp[N];signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cout.tie(0); int n, m; cin>>n>> ...

A 九小时九个人九扇门 dp题目链接 题意：一个数字的数字根是指：将该数字各数位上的数字相加得到一个新的数，直到得到的数字小于 $10$ 为止.。设置小于 $10$ 的数字，其数字根就为其本身。$k$ 个人能够打开门上数字为d的一扇数字门，当且仅当这 $k$ 个人的腕表数字之和的数字根恰好为 $d$。$(1<=n<=1e5,1<ai<=1e9)$ 题解：状态$dp[i][j]$ 表示考虑了前 $i$ 个数，选择了一些数字使得数字根为 $j$ 的方案数 转移方程 不加当前位使得数字根为 $j$ 的方案数为上一位继承来$dp[i][j] += dp[i - 1][j];$加上当前位使得数字根为 $f(a[i]10+j)$ 的方案数为上一位继承来$dp[i][f(a[i]10+j)] += dp[i - 1][j];$当前位的方案数+1$dp[i][f(a[i])]++;$ #include<bits/stdc++.h>using namespace std;#define int long longconst int N=1e6+100; const ...

题意：输入一个点 P 和一条圆弧（圆周的一部分），你的任务是计算 P 到圆弧的最短距离。换句话说，你需要在圆弧上找一个点，到 P 点的距离最小。 题解：呃先找圆心显然假如点跟圆心的连线在那段扇形的圆弧范围内，点到圆弧的最短距离为点到圆心的距离减去半径然后取绝对值；不然，点到圆弧的最短的距离为到这段圆弧的两个端点的最小值。 那怎么判断是不是在圆弧范围内呢？ 本来想找PB和OA,OC是否有交点但是wa了好像不是精度问题 两个点是不是在一条线的两端可以用叉积判断 判断 C,D 点是否在 AB 线段两边 向量 AB 和向量 AC 是顺时针，所以他们的叉积 >0 向量 AB 和向量 AD 是逆时针，所以他们的叉积 <0只要 Cross(AB,AC)*Cross(AB,AD)<0 时，就是在不在同一侧所以这样看， B 就在射线 AC 和 AD 中间~就可以判断 P 是否在圆环范围内对于这题就可以用来判断 P 是否在 OC,OA 之间 但是上面只适用劣弧的情况 还要考虑平角和优弧的情况 反正还是用这个叉积判qaq 代码：#include & ...

题目链接：最小的指数题意：牛妹手里捧着 T 个数，对于每个数x，将其分解质因数，并输出它的质因子指数的最小值。形式化地，对于数x = p1^a1 * p2^a2 … pk^ak，输出min{a1,a2…ak}。1<=T<=100000 , 1<=n<=1018 题解：首先想到素数的话min=1 米勒罗宾素数检测（Miller-Rabin）然后min<=64然后指数<=sqrt(1e18)然后假设min==6就可以小范围素数筛搞搞T=1e5所以把1e4内的质数筛出来, 每次先把 $n$, 变成 $1$ 或者 $>1e4$ 的数对于剩下的数大于 $1e4$ 的剩下的答案无非是 1,2,3,4 #include <bits/stdc++.h>using namespace std;#define int long longconst int N=2e5+5;bool vis[N];int prime[N];int tot=0;void prim() { vis[1]=1; for(int i=2; i<=100 ...

相关概念割点：无向连通图，删除这个点和这个点关联的边，图不连通 点双连通图：无向连通图，没有割点出现 桥：无向连通图，删除某条边，图不连通 边双连通图：无向连通图，没有桥 时间戳：对一个图做深度优先搜索的时候，第一次访问某个点的时间 强连通分量：有向图任意两点都可互相到达 ​ 求割点和点连通分量int times = 0;int dfn[maxn], low[maxn]; // dfn记录时间戳// low(u)来表示 u 以及其后代 **最多经过** 一条反向边能回到的最早的点的时间戳int bcc_cnt = 0; // 点双连通分量数量bool iscut[maxn]; // 标记是否是割点bool vis[maxn<<1]; // 记录这条边是不是访问过了处理重编set<int> bcc[maxn]; // 记录每个点双连通分量里面的点stack<edge> S; // 记录连通分量的点集void dfs (int u, int fa) { dfn[u] = low[u] = ++times; in ...