Doraemon's Blog

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

AC自动机以trie为基础，结合了kmp的next数组思想而创造出来的一种数据结构，用来解决多模式串匹配问题 问题背景P3808 【模板】AC自动机（简单版） 给定n个模式串（$n<=1e6$），一个主串s（$s<=1e6$），问主串中包含多少个这些之中的模式串？ AC自动机传统做法，利用KMP，O(n)遍历每一个模式串，O(n)匹配是否包含此模式串，复杂度O(n2) 利用AC自动机，先把所有的模式串插入到trie中，接下来预处理一个fail数组，fail[i]表示i节点失配后该去找哪个节点（类似next数组），fail数组的真正含义是当前正在匹配的模式串的后缀和其他所有模式串的前缀可以匹配最大长度的那个模式串，有点绕。 这张图中的6号节点的fail指针指向7号节点，因为6号节点的后缀s和7号节点的前缀s相同，且匹配长度最大，所以fail[6]=7。 1234567891011121314151617181920queue<int> q;void build(){ //这里把根节点的儿子节点入队，因为如果只把根节点入队的话会导致根节点失配指 ...

Bellman-ford 用途： 判负环 计算含有负权边的最短路径 重边不会影响答案，因为Bellman-ford会遍历所有的边 算法流程先存边，Bellman-ford的存边十分随意，什么储存方式都可以，只有一个要求，就是每次都要遍历到所有的边！ 既然如此就用一个结构体去存，一个for循环就可以遍历到所有的边了。 123struct node{ int u,v,w}e[MAXN]; 算法十分简单，每次只要让所有的边进行一次更新即可，如果不存在负环，那么一个点最多被n-1个点更新(除了自己)，所以外层循环遍历n-1次，内层循环遍历每一条边 123456for(int i=1;i<n;i++){ for(int j=1;j<=m;j++){ int u=e[j].u,v=e[j].v,w=e[j].w; dis[v]=min(dis[v],dis[u]+w); }} 如果存在负环，那么经过上面的松弛操作后，一定还有点还可以被松弛，负环可以把环上点能到的所有点的权值都松弛到无限小，遍历所有点，检查 ...

数位DP 解决的是求一段区间中满足一定条件的数的数量，形式固定 数位DP模板123456789101112131415161718192021int 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(...) sum+=dfs(pos-1,...,limit && (i==up)); } if(!limit) dp[pos][...]=sum; return sum;}//ps 如果有前导0就可以加一个 lead,一开始传1，然后后面就传lead&&(i==0)就可以了int work(int x) { int len=0; while( ...

半平面交用于求几个凸包围成的面积 一条直线可以将平面分为两部分，我们取左半部分，右半部分舍弃，那么所有的直线围成的左半部分的面积的交集就是半平面交。 算法流程首先把所有线首先按照角度从小到大排序，角度相同就按照线从左到右排序，排序后用一个双端队列来维护，每次新进来一条边，判断这条边是否在队列的队尾两条边的交点左边，如果是，就把队尾元素pop出去，如此往复，队头也是如此，所有边遍历完后还要用队头去维护队尾，用队尾去维护队头 线点123456struct point{ double x,y;}pt[MAXN];struct line{ point a,b;}L[MAXN]; 函数思想很简单，但是实现很复杂，一点点错误满盘皆输，这8个函数非常有用 1234567891011121314151617181920212223242526272829point operator-(point a,point b){ //重载运算符 return {a.x-b.x,a.y-b.y};}double cross(po ...

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