临近年末,给大家整理了一些常用模板。
其中动态规划,搜索这类题我认为它没有固定的模板(正规竞赛很少考裸的背包这种吧),所以没写。
模板大多来自于各大知名OJ的题解,也有部分来自别人的博客,少数是博主自己写的。
#define ll long long
ll read(){ll f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(ll X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0');
}
struct myqueue{int data[N];int head, rear;bool init(){ //初始化head = rear = 0; return true;}int size(){ return (rear - head + N) % N;} //返回队列长度 bool empty(){ //判断队列是否为空if(size()==0) return true;else return false;}bool push(int e){ //队尾插入新元素。if((rear + 1) % N == head ) return false; //队列满data[rear] = e;rear = (rear + 1) % N;return true;}bool pop(int &e){ //删除队头元素,并返回它if(head == rear) return false; //队列空e = data[head];head = (head + 1) % N;return true;}int front(){ return data[head]; } //返回队首,但是不删除
}Q;
struct mystack{int a[N]; //存放栈元素int t = 0; //栈顶位置void push(int x){ a[++t] = x; } //送入栈int top() { return a[t]; } //返回栈顶元素void pop() { t--; } //弹出栈顶int empty() { return t==0?1:0;} //返回1表示空
}st;
const int N = 1e6 + 5;
int heap[N], len=0; //len记录当前二叉树的长度
void push(int x) { //上浮,插入新元素heap[++len] = x;int i = len;while (i > 1 && heap[i] < heap[i/2]){ swap(heap[i], heap[i/2]); i = i/2; }
}
void pop() { //下沉,删除堆头,调整堆heap[1] = heap[len--]; //根结点替换为最后一个结点,然后结点数量减1int i = 1;while ( 2*i <= len) { //至少有左儿子int son = 2*i; //左儿子if (son < len && heap[son + 1] < heap[son]) son++; //son //与小的儿子交换swap(heap[son], heap[i]); i = son; //下沉到儿子处}else break; //如果不比儿子小,就停止下沉}
}
const int N = 1050;
int s[N];
void init_set(){ //初始化for(int i = 1; i <= N; i++) s[i] = i;
}
int find_set(int x){ //查找return x==s[x]? x:find_set(s[x]);
}
void merge_set(int x, int y){ //合并x = find_set(x); y = find_set(y);if(x != y) s[x] = s[y]; //把x合并到y上,y的根成为x的根
}
const int N = 1000;
#define lowbit(x) ((x) & - (x))
int tree[N]={0};
void update(int x, int d) { //单点修改:修改元素a[x], a[x] = a[x] + dwhile(x <= N) {tree[x] += d;x += lowbit(x);}
}
int sum(int x) { //查询前缀和:返回前缀和sum = a[1] + a[2] +... + a[x]int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans;
}
区间求和,区间修改
const int N = 1e5 + 10;
ll a[N]; //记录数列的元素,从a[1]开始
ll tree[N<<2]; //tree[i]:第i个结点的值,表示一个线段区间的值,例如最值、区间和
ll tag[N<<2]; //tag[i]:第i个结点的lazy-tag,统一记录这个区间的修改
ll ls(ll p){ return p<<1; } //定位左儿子:p*2
ll rs(ll p){ return p<<1|1;} //定位右儿子:p*2 + 1
void push_up(ll p){ //从下往上传递区间值tree[p] = tree[ls(p)] + tree[rs(p)];
}
void build(ll p,ll pl,ll pr){ //建树。p是结点编号,它指向区间[pl, pr]tag[p] = 0; //lazy-tag标记if(pl==pr){tree[p]=a[pl]; return;} //最底层的叶子,赋值 ll mid = (pl+pr) >> 1; //分治:折半build(ls(p),pl,mid); //左儿子build(rs(p),mid+1,pr); //右儿子push_up(p); //从下往上传递区间值
}
void addtag(ll p,ll pl,ll pr,ll d){ //给结点p打tag标记,并更新treetag[p] += d; //打上tag标记tree[p] += d*(pr-pl+1); //计算新的tree
}
void push_down(ll p,ll pl,ll pr){ //不能覆盖时,把tag传给子树if(tag[p]){ //有tag标记,这是以前做区间修改时留下的ll mid = (pl+pr)>>1; addtag(ls(p),pl,mid,tag[p]); //把tag标记传给左子树addtag(rs(p),mid+1,pr,tag[p]); //把tag标记传给右子树tag[p]=0; //p自己的tag被传走了,归0}
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改:把[L, R]内每个元素加上dif(L<=pl && pr<=R){ //完全覆盖,直接返回这个结点,它的子树不用再深入了 addtag(p, pl, pr,d); //给结点p打tag标记,下一次区间修改到p时会用到return; }push_down(p,pl,pr); //如果不能覆盖,把tag传给子树ll mid=(pl+pr)>>1;if(L<=mid) update(L,R,ls(p),pl,mid,d); //递归左子树if(R>mid) update(L,R,rs(p),mid+1,pr,d); //递归右子树push_up(p); //更新
}
ll query(ll L,ll R,ll p,ll pl,ll pr){//查询区间[L,R];p是当前结点(线段)的编号,[pl,pr]是结点p表示的线段区间if(pl>=L && R >= pr) return tree[p]; //完全覆盖,直接返回push_down(p,pl,pr); //不能覆盖,递归子树ll res=0;ll mid = (pl+pr)>>1;if(L<=mid) res+=query(L,R,ls(p),pl,mid); //左子结点有重叠if(R>mid) res+=query(L,R,rs(p),mid+1,pr); //右子结点有重叠return res;
}
int ls(int p){ return p<<1; }
int rs(int p){ return p<<1|1;}
int n=1000, s[1005][4005]; //s[i][j]:身高区间i,活泼区间j的最大缘分
void subBuild(int xp, int p, int pl, int pr) { //建立第二维线段树:活泼度线段树s[xp][p] = -1;if(pl == pr) return;int mid=(pl+pr)>>1;subBuild(xp, ls(p), pl, mid);subBuild(xp, rs(p), mid + 1, pr);
}
void build(int p,int pl, int pr) { //建立第一维线段树:身高线段树subBuild(p, 1, 0, n);if(pl == pr) return;int mid=(pl+pr)>>1;build(ls(p),pl, mid);build(rs(p),mid + 1, pr);
}
void subUpdate(int xp, int y, int c, int p, int pl, int pr) {//更新第二维线段树if(pl == pr && pl == y) s[xp][p] = max(s[xp][p], c);else {int mid=(pl+pr)>>1;if(y <= mid) subUpdate(xp, y, c, ls(p), pl, mid);else subUpdate(xp, y, c, rs(p), mid + 1, pr);s[xp][p] = max(s[xp][ls(p)], s[xp][rs(p)]);}
}
void update(int x, int y, int c, int p, int pl, int pr){ //更新第一维线段树:身高xsubUpdate(p, y, c, 1, 0, n); //更新第二维线段树:活泼度yif(pl != pr) {int mid=(pl+pr)>>1;if(x <= mid) update(x, y, c, ls(p), pl, mid);else update(x, y, c, rs(p), mid + 1, pr);}
}
int subQuery(int xp, int yL, int yR, int p, int pl, int pr) { //查询第二维线段树if(yL <= pl && pr <= yR) return s[xp][p];else {int mid=(pl+pr)>>1;int res = -1;if(yL <= mid) res = subQuery(xp, yL, yR, ls(p), pl, mid);if(yR > mid) res = max(res, subQuery(xp, yL, yR, rs(p), mid + 1, pr));return res;}
}
int query(int xL, int xR, int yL, int yR, int p, int pl, int pr) {//查询第一维线段树if(xL <= pl && pr <= xR) return subQuery(p, yL, yR, 1, 0, n); //满足身高区间时,查询活泼度区间else { //当前结点不满足身高区间int mid = (pl+pr)>>1;int res = -1;if(xL <= mid) res = query(xL, xR, yL, yR, ls(p), pl, mid);if(xR > mid) res = max(res, query(xL, xR, yL, yR, rs(p), mid + 1, pr));return res;}
}
const int N = 200010;
int cnt = 0; //用cnt标记可以使用的新结点
int a[N], b[N], root[N]; //a[]是原数组,b[]是排序后数组,root[i]记录第i棵线段树的根结点编号
struct{ //定义结点
int L, R, sum; //L左儿子, R右儿子,sum[i]是结点i的权值(即图中圆圈内的数字)
}tree[N<<5]; // <<4是乘16倍,不够用;<<5差不多够用
int build(int pl, int pr){ //初始化一棵空树,实际上无必要int rt = ++ cnt; //cnt为当前结点编号tree[rt].sum = 0;int mid=(pl+pr)>>1;if (pl < pr){tree[rt].L = build(pl, mid);tree[rt].R = build(mid+1, pr);}return rt; //返回当前结点的编号
}
int update(int pre, int pl, int pr, int x){ //建一棵只有logn个结点的新线段树int rt = ++cnt; //新的结点,下面动态开点tree[rt].L = tree[pre].L; //该结点的左右儿子初始化为前一棵树相同位置结点的左右儿子tree[rt].R = tree[pre].R; tree[rt].sum = tree[pre].sum + 1; //插了1个数,在前一棵树的相同结点加1int mid = (pl+pr)>>1;if (pl < pr){ //从根结点往下建logn个结点if (x <= mid) //x出现在左子树,修改左子树 tree[rt].L = update(tree[pre].L, pl, mid, x);else //x出现在右子树,修改右子树tree[rt].R = update(tree[pre].R, mid+1, pr, x);}return rt; //返回当前分配使用的新结点的编号
}
int query(int u, int v, int pl, int pr, int k){ //查询区间[u,v]第k小if (pl == pr) return pl; //到达叶子结点,找到第k小,pl是结点编号,答案是b[pl] int x = tree[tree[v].L].sum - tree[tree[u].L].sum; //线段树相减int mid = (pl+pr)>>1;if (x >= k) //左儿子数字大于等于k时,说明第k小的数字在左子树return query(tree[u].L, tree[v].L, pl, mid, k);else //否则在右子树找第k-x小的数字 return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}
基础莫队
struct node{ //离线记录查询操作int L, R, k; //k:查询操作的原始顺序
}q[N];
int pos[N];
int ans[N];
int cnt[N]; //cnt[i]: 统计数字i出现了多少次
int a[N];
bool cmp(node a, node b){if(pos[a.L] != pos[b.L]) //按L所在的块排序,如果块相等,再按R排序return pos[a.L] < pos[b.L];if(pos[a.L] & 1) return a.R > b.R; //奇偶性优化,如果删除这一句,性能差一点return a.R < b.R; if(a.L==b.L) return a.R < b.R;return a.L < b.L; */
}
int ANS = 0;
void add(int x){ //扩大区间时(L左移或R右移),增加数x出现的次数cnt[a[x]]++;if(cnt[a[x]]==1) ANS++; //这个元素第1次出现
}
void del(int x){ //缩小区间时(L右移或R左移),减少数x出现的次数cnt[a[x]]--;if(cnt[a[x]]==0) ANS--; //这个元素消失了
}
倍增
//洛谷P3379 的倍增代码
#include
using namespace std;
const int N=500005;
struct Edge{int to, next;}edge[2*N]; //链式前向星
int head[2*N], cnt;
void init(){ //链式前向星:初始化for(int i=0;i<2*N;++i){ edge[i].next = -1; head[i] = -1; }cnt = 0;
}
void addedge(int u,int v){ //链式前向星:加边edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
} //以上是链式前向星
int fa[N][20], deep[N];
void dfs(int x,int father){ //求x的深度deep[x]和fa[x][]。father是x的父结点。deep[x] = deep[father]+1; //深度:比父结点深度多1fa[x][0] = father; //记录父结点for(int i=1; (1<if(deep[x]=0;i--) //x最多跳19次:2^19 > 500005if(deep[x]-(1<=deep[y]) //如果x跳过头了就换个小的i重跳x = fa[x][i]; //如果x还没跳到y的层,就更新x继续跳if(x==y) return x; //y就是x的祖先//(2)x和y同步往上跳,找到LCAfor(int i=19;i>=0;i--) //如果祖先相等,说明跳过头了,换个小的i重跳if(fa[x][i]!=fa[y][i]){ //如果祖先不等,就更新x、y继续跳x = fa[x][i]; y = fa[y][i];}return fa[x][0]; //最后x位于LCA的下一层,父结点fa[x][0]就是LCA
}
int main(){ init(); //初始化链式前向星int n,m,root; scanf("%d%d%d",&n,&m,&root); for(int i=1;i //读一棵树,用链式前向星存储int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u);}dfs(root,0); //计算每个结点的深度并预处理fa[][]数组while(m--){int a,b; scanf("%d%d",&a,&b); printf("%d\n", LCA(a,b));}return 0;
}
Tarjan求LCA
#include
using namespace std;
const int MAXN = 5e5+ 10;
int fa[MAXN], head[MAXN], head_ask[MAXN], cnt, cnt_ask, ans[MAXN];
bool vis[MAXN];
int n, m, s;
struct Edge{int to, dis, next;int num;
}edge[MAXN << 1], ask[MAXN << 1];
void add_edge(int u, int v, int dis) {edge[++cnt].to = v;edge[cnt].next = head[u];head[u] = cnt;
}
void add_ask(int x, int y, int num) { //num 第几个查询ask[++cnt_ask].to = y;ask[cnt_ask].num = num; //第几个查询 ask[cnt_ask].next = head_ask[x];head_ask[x] = cnt_ask;
}
int find(int x) { //并查集 return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void init() {cnt = 1;cnt_ask = 1;memset(vis, 0, sizeof(vis));fa[n] = n;
}
void Tarjan(int x) {vis[x] = true;for(int i = head[x]; i ; i = edge[i].next) {int to = edge[i].to;if( !vis[to] ) {Tarjan(to);fa[to] = x;}}for(int i = head_ask[x]; i; i = ask[i].next) {int to = ask[i].to;if( vis[to] ){ ans[ask[i].num] = find(to);}}
}
int main () {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m >> s;int x, y;init();for(int i = 1; i < n; ++i) {fa[i] = i;cin >> x >> y;add_edge(x, y, 0);add_edge(y, x, 0);}for(int i = 1; i <= m; ++i) {cin >> x >> y;add_ask(x, y, i);add_ask(y, x, i);} Tarjan(s); for(int i = 1; i <= m; ++i) {cout << ans[i] << endl;}
}
const int N = 1e6+10;
const double alpha = 0.75; //不平衡率。一般用alpha来表示
struct Node{int ls,rs; //左右儿子int val; //结点存的数字int tot; //当前子树占用的空间数量,包括实际存储的结点和被标记删去的点int size; //子树上实际存储数字的数量int del; //=1表示这个结点存有数字,=0表示这个点存的数字被删了
}t[N];
int order[N],cnt; //order[]记录拍扁后的结果,即那些存有数字的结点。cnt是数量
int tree_stack[N],top = 0; //用一个栈来回收和分配可用的结点
int root = 0; //根结点,注意重建过程中根结点会变化
void inorder(int u){ //中序遍历,“拍平”摧毁这棵子树if(!u) return; //已经到达叶子,退出inorder(t[u].ls); //先遍历左子树if(t[u].del) order[++cnt] = u; //如果该结点存有数字,读取它else tree_stack[++top] = u; //回收该结点,等待重新分配使用inorder(t[u].rs); //再遍历右子树
}
void Initnode(int u){ //重置结点的参数t[u].ls = t[u].rs = 0;t[u].size = t[u].tot = t[u].del = 1;
}
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}
//int rebuild_num=0; //测试:统计重建次数
void build(int l,int r,int &u){ //把拍扁的子树拎起来,重建
// rebuild_num++; //测试:统计重建次数int mid = (l + r) >> 1; //新的根设为中点,使重构出的树尽量平衡u = order[mid];if(l == r){Initnode(u); return;} //如果是叶子,重置后返回if(l < mid) build(l,mid - 1,t[u].ls);//重构左子树if(l == mid) t[u].ls = 0; //注意这里,不要漏了build(mid + 1,r,t[u].rs); //重构右子树Update(u); //更新
}
void rebuild(int &u){ //重建。注意是&ucnt = 0;inorder(u); //先拍平摧毁if(cnt) build(1,cnt,u); //再拎起,重建树else u = 0; //特判该子树为空的情况
}
bool notbalance(int u){ //判断子树u是否平衡if((double)t[u].size*alpha <=(double)max(t[t[u].ls].size,t[t[u].rs].size))return true; //不平衡了return false; //还是平衡的
}
void Insert(int &u,int x){ //插入数字x。注意是&u,传回了新的uif(!u){ //如果结点u为空,直接将x插到这里u = tree_stack[top--]; //从栈顶拿出可用的空结点t[u].val = x; //结点赋值Initnode(u); //其他参数初始化return;}t[u].size++;t[u].tot++;if(t[u].val >= x) Insert(t[u].ls,x); //插到右子树else Insert(t[u].rs,x); //插到左子树if(notbalance(u)) rebuild(u); //如果不平衡了,重建这棵子树
}
int Rank(int u,int x){ //排名,x是第几名if(u==0) return 0;if(x>t[u].val) return t[t[u].ls].size+ t[u].del + Rank(t[u].rs, x);return Rank(t[u].ls,x);
}
int kth(int k){ //第k大数是几?int u = root;while(u){if(t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;else if(t[t[u].ls].size >= k) u = t[u].ls;else{k -= t[t[u].ls].size + t[u].del;u = t[u].rs;}}return t[u].val;
}
void Del_k(int &u,int k){ //删除排名为k的数t[u].size--; //要删除的数肯定在这棵子树中,size减1if(t[u].del && t[t[u].ls].size + 1 == k){t[u].del = 0; //del=0表示这个点u被删除了,但是还保留位置return;}if(t[t[u].ls].size + t[u].del >= k) Del_k(t[u].ls,k); //在左子树上else Del_k(t[u].rs,k - t[t[u].ls].size - t[u].del); //在右子树上
}
void Del(int x){ //删除值为k的数Del_k(root,Rank(root,x)+1); //先找x的排名,然后用Del_k()删除if(t[root].tot * alpha >= t[root].size)rebuild(root); //如果子树上被删除的结点太多,就重构
}
const int N = 50005;
const int INF = 0x7fffffff;
struct Node{char s[100]; int ls,rs,fa,pri;friend bool operator<(const Node& a,const Node& b){return strcmp(a.s,b.s)<0;}
}t[N];
void buildtree(int n){ //不用栈,直接查最右链for(int i=1;i<=n;i++){int pos = i-1; //从前一个结点开始比较,前一个结点在最右链的末端while(t[pos].pri < t[i].pri) pos = t[pos].fa; //沿着最右链一直找,直到pos的优先级比i大t[i].ls = t[pos].rs; //图(4):i是19,pos是24, 15调整为19的左儿子t[t[i].ls].fa = i; //图(4):15的父亲是19t[pos].rs = i; //图(4):24的右儿子是19t[i].fa = pos; //图(4):19的父亲是24}
}
void buildtree2(int n){ //用栈来辅助建树stack ST; ST.push(0); //t[0]进栈,它一直在栈底for(int i=1;i<=n;i++){int pos = ST.top();while(!ST.empty() && t[pos].pri < t[i].pri){pos = t[ST.top()].fa;ST.pop(); //把比i优先级小的弹出栈}t[i].ls = t[pos].rs;t[t[i].ls].fa = i;t[pos].rs = i;t[i].fa = pos;ST.push(i); //每个结点都一定要进栈}
}
void inorder(int x){ //中序遍历打印if(x==0) return;printf("(");inorder(t[x].ls); printf("%s/%d",t[x].s,t[x].pri); inorder(t[x].rs); printf(")");
}
const int M = 2e6+10;
int cnt, root;
struct Node{int fa,ls,rs,size; char val;}t[M]; //tree[]存树;
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;} //用于排名
char str[M]={0}; //一次输入的字符串
int build(int L,int R,int f){ //把字符串str[]建成平衡树if(L>R) return 0;int mid = (L+R)>>1;int cur = ++cnt;t[cur].fa = f;t[cur].val= str[mid];t[cur].ls = build(L,mid-1,cur);t[cur].rs = build(mid+1,R,cur);Update(cur);return cur; //返回新树的根
}
int get(int x){return t[t[x].fa].rs == x;} //如果u是右儿子,返回1;左儿子返回0
void rotate(int x){ //单旋一次int f=t[x].fa, g=t[f].fa, son=get(x); //f:父亲;g:祖父if(son==1) { //x是右儿子,左旋zagt[f].rs = t[x].ls; //图“单旋”中的结点bif(t[f].rs) t[t[f].rs].fa = f;}else { //x是左儿子,右旋zigt[f].ls = t[x].rs;if(t[f].ls) t[t[f].ls].fa = f;}t[f].fa=x; //x旋为f的父结点if(son == 1) t[x].ls=f; //左旋,f变为x的左儿子else t[x].rs=f; //右旋,f变为x的右儿子t[x].fa = g; //x现在是祖父的儿子if(g){ //更新祖父的儿子if(t[g].rs==f) t[g].rs = x;else t[g].ls = x;}Update(f); Update(x);
}
void splay(int x,int goal){ //goal=0,新的根是x;goal!=0,把x旋为goal的儿子if(goal == 0) root=x;while(1){int f = t[x].fa, g=t[f].fa; //一次处理x,f,g三个点if(f == goal) break;if(g != goal) { //有祖父,分一字旋和之字旋两种情况if(get(x)==get(f)) rotate(f); //一字旋,先旋f、gelse rotate(x);} //之字旋,直接旋xrotate(x);}Update(x);
}
int kth(int k,int u){ //第k大数的位置if( k == t[t[u].ls].size + 1) return u;if( k <= t[t[u].ls].size ) return kth(k,t[u].ls);if( k >= t[t[u].ls].size + 1) return kth(k-t[t[u].ls].size-1,t[u].rs);
}
void Insert(int L,int len){ //插入一段区间int x = kth(L,root), y = kth(L+1,root); //x:第L个数的位置,y:第L+1个数的位置splay(x,0); splay(y,x); //分裂//先把x旋到根,然后把y旋到x的儿子,此时y是x的右儿子,且y的左儿子为空t[y].ls = build(1,len,y); //合并:建一棵树,挂到y的左儿子上Update(y); Update(x);
}
void del(int L,int R){ //删除区间[L+1,R]int x=kth(L,root), y=kth(R+1,root);splay(x,0); splay(y,x); //y是x的右儿子,y的左儿子是待删除的区间t[y].ls=0; //剪断左子树,等于直接删除。这里为了简单,没有释放空间Update(y); Update(x);
}
void inorder(int u){ //中序遍历if(u==0) return;inorder(t[u].ls);cout<
bool isprime(int x){if(x <= 1) return 0;for(int i=2;i*i<=x;i++)if(x%i == 0) return 0;return 1;
}
一般筛法
int n,cnt=0;//cnt是素数个数
int prime[10001];//存素数
cin >> n;//n表示范围
memset(prime,1,sizeof(prime);//先全定为素数
prime[0] = 0;
prime[1] = 0;//特判
for(int i=2;i//如果没被修改过就一定是素数prime[++cnt]=i;//前面的已经遍历过了,可以节约无用空间来存素数for(int k=i*i; k
欧拉筛法
int n,cnt=0;
int prime[10001];//存素数
bool vis[10001];//保证不做素数的倍数
cin >> n;
memset(prime,0,sizeof(prime);
memset(vis,0,sizeof(vis);
for(int i=2;i<=n;i++){if(!vis[i])//不是目前找到的素数的倍数prime[cnt++] = i;//找到素数for(int j=0;jvis[i*prime[j]] = true;//找到素数的倍数不访问if(i % prime[j] == 0) break;}
}
#define ll long long
ll gcd(ll a,ll b){if(b == 0) return a;return gcd(b,a%b);
}
ll mul(ll a,ll b,ll m){ //乘法取模:a*b mod ma = a%m; //先取模,非常重要,能在一定程度上防止第10行a+a溢出b = b%m;ll res = 0;while(b>0){ //递归思想if(b&1) res=(res+a)% m; //用b&1判断b的奇偶a=(a+a)% m; //需要保证a+a=2a不能溢出,否则答案错误b>>=1;}return res;
}
typedef long long ll;
ll fastPow(ll a, ll n, ll mod){ll ans = 1;a %= mod; 止下面的a*a越界while(n) {if(n & 1) ans = (ans*a) % mod; //取模 a = (a*a) % mod; //取模n >>= 1;}return ans;
}
struct matrix{ int m[N][N]; }; //定义矩阵,常数N是矩阵的行数和列数
matrix operator * (const matrix& a, const matrix& b){ //重载*为矩阵乘法。注意constmatrix c; memset(c.m, 0, sizeof(c.m)); //清零for(int i=0; i //矩阵快速幂,代码和普通快速幂几乎一样matrix ans; memset(ans.m,0,sizeof(ans.m));for(int i=0;iif(n&1) ans = ans * a; //不能简写为ans *= a,这里的*重载了a = a * a;n>>=1;}return ans;
}
#include
using namespace std;
double a[105][105];
double eps = 1e-7;
int main(){int n; scanf("%d",&n);for(int i=1;i<=n;++i)for(int j=1;j<=n+1;++j) scanf("%lf",&a[i][j]);for(int i=1;i<=n;++i){ //枚举列int max=i;for(int j=i+1;j<=n;++j) //选出该列最大系数,真实目的是选一个非0系数if(fabs(a[j][i])>fabs(a[max][i])) max=j;for(int j=1;j<=n+1;++j) swap(a[i][j],a[max][j]); //移到前面if(fabs(a[i][i]) < eps){ //对角线上的主元系数等于0,说明没有唯一解puts("No Solution");return 0;}for(int j=n+1;j>=1;j--) a[i][j]= a[i][j]/a[i][i]; //把这一行的主元系数变为1for(int j=1;j<=n;++j){ //消去主元所在列的其他行的主元if(j!=i) {double temp=a[j][i]/a[i][i];for(int k=1;k<=n+1;++k) a[j][k] -= a[i][k]*temp;}}}for(int i=1;i<=n;++i) printf("%.2f\n",a[i][n+1]); //最后得到简化阶梯矩阵return 0;
}
#define ll long long
ll extend_gcd(ll a,ll b,ll &x,ll &y){if(b == 0){ x=1; y=0; return a;}ll d = extend_gcd(b,a%b,y,x);y -= a/b * x;return d;
}
#include
#define ll long long
using namespace std;
const int MAX = 12;
ll n,ans;
ll read(){ll f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(ll X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0');
}void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,x,y);ll z=x;x=y;y=z-(a/b)*y;
}
ll a[MAX],b[MAX],M[MAX],t[MAX],s=1,y;
int main(){n = read();for(int i=1;i<=n;i++){a[i] = read();b[i] = read();s *= a[i];}for(int i=1;i<=n;i++) M[i]=s/a[i];for(int i=1;i<=n;i++){exgcd(M[i],a[i],t[i],y);t[i] = (t[i]%a[i]+a[i])%a[i];}for(int i=1;i<=n;i++) ans+=b[i]*M[i]*t[i]%s;write(ans%s);return 0;
}
#include
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll ai[N], mi[N];
ll mul(ll a,ll b,ll m){ //乘法取模:a*b % mll res=0;while(b>0){if(b&1) res=(res+a) % m;a=(a+a) % m;b>>=1;}return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){ //扩展欧几里得if(b == 0){ x=1; y=0; return a;}ll d = extend_gcd(b,a%b,y,x);y -= a/b * x;return d;
}
ll excrt(){ //求解同余方程组,返回最小正整数解ll x,y;ll m1 = mi[1], a1 = ai[1]; //第1个等式ll ans = 0;for(int i=2;i<=n;i++){ //合并每2个等式 ll a2 = ai[i], m2 = mi[i]; // 第2个等式 //合并为:aX + bY = c ll a = m1, b = m2, c = (a2 - a1%m2 + m2) % m2;//下面求解 aX + bY = cll d = extend_gcd(a,b,x,y); //用扩展欧几里得求x0if(c%d != 0) return -1; //无解x = mul(x,c/d,b/d); //aX + bY = c 的特解t,最小值 ans = a1 + x* m1; //代回原第1个等式,求得特解x'm1 = m2/d*m1; //先除再乘,避免越界。合并后的新m1ans = (ans%m1 + m1) % m1; //最小正整数解a1 = ans; //合并后的新a1}return ans;
}
int main(){scanf("%d", &n);for(int i=1;i<=n;++i) scanf("%lld%lld",&mi[i],&ai[i]);printf("%lld",excrt());return 0;
}
inline LL quick_mul(LL a,LL b,LL m) //快速乘
{ll ans = 0;a %= m;b %= m;while (b) {if (b & 1) {ans = (ans + a) % m;}a = (a + a) % m;b >>= 1;}return ans;
}LL quick_pow(LL a,LL b,LL m) //快速幂
{LL res=1;a%=m;while(b){if(b&1) res=quick_mul(res,a,m);a=quick_mul(a,a,m);b>>=1;}return res;
}
bool Miller_rabin(LL n,int num)
{
//先将特殊情况判断一下if(n==2||n==3) return true;if(n%2==0||n==1) return false;srand((unsigned)time(NULL)); //为接下来a的随机取值用 LL d=n-1;int s=0;while(!(d&1)) s++,d>>=1;//若d的二进制的最后一位不是1,则说明d还是偶数 for(int i=0;iLL a=rand()%(n-2)+2;//2~n-1;LL x=quick_pow(a,d,n), y=0;for(int j=0;jy=quick_mul(x,x,n);//先平方 if(y==1&&x!=1&&x!=(n-1)) return false;//验证二次探测原理 x=y;}if(y!=1) return false;//不满足费马小定理,那就肯定不是质数}return true;
}
#include
#define ll long long
using namespace std;
ll p;
long long read(){long long f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(long long X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0');
}
inline ll power(ll x,ll mod){ll ans = 1;for(;mod;mod>>=1){//快速幂 if(mod & 1)ans = x*ans%p;x = x*x%p;}return ans;
}
inline ll inv(ll x){return power(x,p-2);//费马小定理求逆元
}
inline ll C(ll n,ll m){ll ans = 1;for(int i=n;i>=n-m+1;i--)ans = ans*i%p;ll s = 1;for(int i=2;i<=m;i++)s = s*i%p;return ans*inv(s)%p;
}
inline ll lucas(ll n,ll m){return C(n%p,m%p)*C(n/p,m/p)%p;
}
int main(){int T = read();while(T--){ll n = read(); ll m = read(); p = read();write(lucas(n+m,n)); putchar('\n');}return 0;
}
#include
#include
using namespace std;
long long n,m,p,cnt/*个数*/,pr[1010]/*质数*/,al[1010]/*指数*/;
void exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法
{if (!b) return (void)(x=1,y=0);exgcd(b,a%b,x,y);long long tmp=x;x=y;y=tmp-a/b*y;
}
long long ny(long long a,long long p)//逆元
{long long x,y;exgcd(a,p,x,y);return (x+p)%p;
}
long long POW(long long a,long long b,long long p)//快速幂
{long long t=1;a%=p;for(;b;b>>=1){if(b&1) t=t*a%p;a=a*a%p;}return t;
}
long long fac(long long n,long long p,long long ppa)//计算n!
{if (n==0) return 1;long long cir=1/*循环节*/,rem=1/*余数*/;for (long long i=1;i<=ppa;i++) if(i%p) cir=cir*i%ppa;cir=POW(cir,n/ppa,ppa);for(long long i=ppa*(n/ppa);i<=n;i++) if(i%p) rem=rem*(i%ppa)%ppa;return fac(n/p,p,ppa)*cir%ppa*rem%ppa;
}
long long sum_fac(long long n,long long p)//n!中p的个数
{return nlong long fz=fac(n,p,ppa),fm1=ny(fac(m,p,ppa),ppa),fm2=ny(fac(n-m,p,ppa),ppa);long long mi=POW(p,sum_fac(n,p)-sum_fac(m,p)-sum_fac(n-m,p),ppa);return fz*fm1%ppa*fm2%ppa*mi%ppa;
}
void pfd(long long n,long long m)//分解p
{long long P=p;for(long long i=2;i*i<=p;i++){if(!(P%i)){long long ppa=1;while(!(P%i)) ppa*=i,P/=i;pr[++cnt]=ppa;al[cnt]=C(n,m,i,ppa);}}if(P!=1) pr[++cnt]=P,al[cnt]=C(n,m,P,P);
}
long long crt()//中国剩余定理
{long long ans=0;for(long long i=1;i<=cnt;i++){long long M=p/pr[i],T=ny(M,pr[i]);ans=(ans+al[i]*M%p*T%p)%p;}return ans;
}
long long exlucas(long long n,long long m)//扩展卢卡斯
{pfd(n,m);return crt();
}
int main()
{cin>>n>>m>>p;cout<
#include
#define ll long long
using namespace std;
const int MAX = 3e6+10;
ll n,p;
ll inv[MAX];
int main(){ios::sync_with_stdio(false);cin >> n >> p;inv[1] = 1;for(int i=2;i<=n;i++)inv[i] = (p-p/i)*inv[p%i]%p;for(int i=1;i<=n;i++)cout << inv[i] << "\n";return 0;
}
inline ll power(ll x,ll mod){ll ans = 1;for(;mod;mod>>=1){//快速幂 if(mod & 1)ans = x*ans%p;x = x*x%p;}return ans;
}
inline ll inv(ll x){return power(x,p-2);//费马小定理求逆元
}
void exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法
{if (!b) return (void)(x=1,y=0);exgcd(b,a%b,x,y);long long tmp=x;x=y;y=tmp-a/b*y;
}
long long ny(long long a,long long p)//逆元
{long long x,y;exgcd(a,p,x,y);return (x+p)%p;
}
int prime[N]; //记录质数
int vis[N]; //记录最小质因子
int euler_sieve(int n){ int cnt=0;memset(vis,0,sizeof(vis));memset(prime,0,sizeof(prime));for(int i=2;i<=n;i++){ if(!vis[i]){ vis[i]=i; prime[cnt++]=i;} //vis[]记录最小质因子for(int j=0; j if(i*prime[j] >n) break; vis[i*prime[j]] = prime[j]; //vis[]记录最小质因子if(i%prime[j]==0) break; }}return cnt;
}
int euler(int n){int ans = n;for(int p = 2; p*p <= n; ++ p){ //试除法:检查从2到sqrt(n)的每个数if(n%p == 0){ //能整除,p是一个因子,而且是质因子,请思考ans = ans/p*(p-1); //求欧拉函数的通式while(n%p == 0) //去掉这个因子的幂,并使得下一个p是质因子n /= p; //减小了n}}if(n != 1) ans = ans/n*(n-1); //情况(1):n是一个质数,没有执行上面的分解 return ans;
}
bool vis[N];
int prime[N];
int Mob[N];
void Mobius_sieve(){int cnt = 0;vis[1] = 1;Mob[1] = 1;for(int i = 2; i <= N; i++){if(!vis[i]) prime[cnt++] = i, Mob[i] = - 1;for(int j = 0; j < cnt && 1LL * prime[j] * i <= N; j++){vis[prime[j] * i] = 1;Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);if(i % prime[j] == 0) break;}}
}
#include
using namespace std;
typedef long long ll;
const int N = 5e6+7; //超过n^(2/3),够大了
int prime[N]; //记录质数
bool vis[N]; //记录是否被筛;
int mu[N]; //莫比乌斯函数值
ll phi[N]; //欧拉函数值
unordered_map summu; //莫比乌斯函数前缀和
unordered_map sumphi; //欧拉函数前缀和
void init(){ //线性筛预计算一部分答案int cnt = 0;vis[0] = vis[1] = 1;mu[1] = phi[1] = 1;for(int i=2;iif(!vis[i]){ prime[cnt++] = i;mu[i] = -1;phi[i] = i-1;}for(int j=0;jvis[i*prime[j]] = 1; if(i%prime[j]){ mu[i*prime[j]] = -mu[i];phi[i*prime[j]] = phi[i]*phi[prime[j]];} else{mu[i*prime[j]] = 0;phi[i*prime[j]] = phi[i]*prime[j]; break;}}}for(int i=1;i //最后,mu[]和phi[]改为记录1~N的前缀和。mu[i] += mu[i-1];phi[i] += phi[i-1];}
}
int gsum(int x){ // g(i)的前缀和return x;
}
ll getsmu(int x){if(x < N) return mu[x]; //预计算if(summu[x]) return summu[x]; //记忆化 ll ans = 1; //杜教筛公式中的 1for(ll l=2,r;l<=x;l=r+1){ //用整除分块计算杜教筛公式r = x/(x/l); ans -= (gsum(r)-gsum(l-1))*getsmu(x/l);}return summu[x] = ans/gsum(1);
}
ll getsphi(int x){if(x < N) return phi[x];if(sumphi[x]) return sumphi[x]; //记忆化,每个sumphi[x]只用算一次ll ans = x*((ll)x+1)/2; //杜教筛公式中的 n(n+1)/2for(ll l=2,r;l<=x;l=r+1){ //用整除分块计算杜教筛公式,这里算 sqrt(x)次r = x/(x/l);ans -= (gsum(r)-gsum(l-1))*getsphi(x/l);} return sumphi[x] = ans/gsum(1);
}
int main(){ init(); //用线性筛预计算一部分int t; scanf("%d",&t);while(t--){ int n; scanf("%d",&n);printf("%lld %lld\n",getsphi(n),getsmu(n));}return 0;
}
#include
using namespace std;
const int N=11000002;
int n,P[N<<1]; //P[i]: 以s[i]为中心的回文半径
char a[N],s[N<<1];
void change(){ //变换n = strlen(a);int k = 0; s[k++]='$'; s[k++]='#';for(int i=0;is[k++]=a[i]; s[k++]='#';} //在每个字符后面插一个#s[k++]='&'; //首尾不一样,保证第18行的while循环不越界n = k;
}
void manacher(){int R = 0, C;for(int i=1;iif(i < R) P[i] = min(P[(C<<1)-i],P[C]+C-i); //合并处理两种情况else P[i] = 1;while(s[i+P[i]] == s[i-P[i]]) P[i]++; //暴力:中心扩展法 if(P[i]+i > R){R = P[i]+i; //更新最大RC = i;}}
}
int main(){scanf("%s",a); change();manacher();int ans=1;for(int i=0;i
#include
using namespace std;
const int N = 800000;
struct node{bool repeat; //这个前缀是否重复int son[26]; //26个字母int num; //这个前缀出现的次数
}t[N]; //trie
int cnt = 1; //当前新分配的存储位置。把cnt=0留给根结点
void Insert(char *s){int now = 0;for(int i=0;s[i];i++){int ch=s[i]-'a';if(t[now].son[ch]==0) //如果这个字符还没有存过t[now].son[ch] = cnt++; //把cnt位置分配给这个字符now = t[now].son[ch]; //沿着字典树往下走t[now].num++; //统计这个前缀出现过多少次}
}
int Find(char *s){int now = 0;for(int i=0;s[i];i++){int ch = s[i]-'a';if(t[now].son[ch]==0) return 3; //第一个字符就找不到now = t[now].son[ch];}if(t[now].num == 0) return 3; //这个前缀没有出现过if(t[now].repeat == false){ //第一次被点名t[now].repeat = true;return 1;}return 2;// return t[p].num; //若有需要,返回以s为前缀的单词的数量
}
#include
#define ll long long
using namespace std;
const int N = 1e6+10;
int kmp[N];
int main(){string a,b;cin >> a >> b;a = " "+a; b = " " + b;int la = a.size()-1,lb = b.size()-1;for(int i=2,j=0;i<=lb;i++){while(j&&b[i]!=b[j+1]) j = kmp[j];if(b[i] == b[j+1]) j++;kmp[i] = j;} for(int i=1,j=0;i<=la;i++){while(j&&a[i]!=b[j+1]) j = kmp[j];if(a[i] == b[j+1]) j++;if(j == lb){cout << i-j+1 << "\n";j = kmp[j];}}for(int i=1;i<=lb;i++)cout << kmp[i] << " ";return 0;
}
struct Tree//字典树
{int fail;//失配指针int vis[26];//子节点的位置int end;//标记有几个单词以这个节点结尾
}AC[1000000];//Trie树
int cnt=0;//Trie的指针
inline void Build(string s)
{int l=s.length();int now=0;//字典树的当前指针 for(int i=0;iif(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点AC[now].vis[s[i]-'a']=++cnt;//构造出来now=AC[now].vis[s[i]-'a'];//向下构造 }AC[now].end+=1;//标记单词结尾
}
void Get_fail()//构造fail指针
{queue Q;//队列 for(int i=0;i<26;++i)//第二层的fail指针提前处理一下{if(AC[0].vis[i]!=0){AC[AC[0].vis[i]].fail=0;//指向根节点Q.push(AC[0].vis[i]);//压入队列 }}while(!Q.empty())//BFS求fail指针 {int u=Q.front();Q.pop();for(int i=0;i<26;++i)//枚举所有子节点{if(AC[u].vis[i]!=0)//存在这个子节点{AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];//子节点的fail指针指向当前节点的//fail指针所指向的节点的相同子节点 Q.push(AC[u].vis[i]);//压入队列 }else//不存在这个子节点 AC[u].vis[i]=AC[AC[u].fail].vis[i];//当前节点的这个子节点指向当//前节点fail指针的这个子节点 }}
}
int AC_Query(string s)//AC自动机匹配
{int l=s.length();int now=0,ans=0;for(int i=0;inow=AC[now].vis[s[i]-'a'];//向下一层for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)//循环求解{ans+=AC[t].end;AC[t].end=-1;} }return ans;
}
const int MAXN = 2e6 + 5;struct Node{Node *ch[26], *fail;int len, sum;
}tr[MAXN];int n;
char s[MAXN];
int ncnt = 2;
Node *last;Node *New(int len) {tr[ncnt].len = len;tr[ncnt].fail = &tr[0];for (int i = 0; i < 26; i++) tr[ncnt].ch[i] = &tr[0];return &tr[ncnt++];
}Node *GetFail(Node *x, int pos) {while (s[pos - x->len - 1] != s[pos]) x = x->fail;return x;
}void Init() {tr[0].len = 0; tr[1].len = -1;tr[0].fail = &tr[1]; tr[1].fail = &tr[0];for (int i = 0; i < 26; i++) tr[0].ch[i] = tr[1].ch[i] = &tr[0];last = &tr[0];
}void Insert(int pos) {Node *cur = GetFail(last, pos);if (cur->ch[s[pos] - 'a'] == &tr[0]) {Node *now = New(cur->len + 2);now->fail = GetFail(cur->fail, pos)->ch[s[pos] - 'a'];now->sum = now->fail->sum + 1;cur->ch[s[pos] - 'a'] = now;}last = cur->ch[s[pos] - 'a'];
}
const int N = 1e6+5, M = 2e6+5; //1百万个点,2百万个边
int cnt=0,head[N]; //cnt等于其他值也行,根据题目要求赋值
struct {int to, next, w;} edge[M];
void addedge(int u,int v,int w) {cnt++;edge[cnt].to = v; edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt;
}
int n,a[25],dir[30][30]; //dir[i][j]=1表示i、j是先后关系
int topo[25],vis[30],indegree[30]; //topo[]记录拓扑排序,indegree记录度,vis标记是否访问
void dfs(int z,int cnt){int i;topo[cnt]=z; //记录拓扑排序if(cnt==n-1) { //所有点取完了,输出一个拓扑排序for(i=0;iif(!vis[a[i]] && dir[z][a[i]] )indegree[a[i]] --; //把所有下属的度数减一}for(i=0;iif(!vis[a[i]] && dir[z][a[i]] )indegree[a[i]] ++;}vis[z]=0; //恢复
}
封闭传包
for(int k=1; k<=n; k++) //floyd的3重循环for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) if(dp[i][k] && dp[k][j];)dp[i][j] = 1;
#include
#define ll long long
using namespace std;const int N = 1e5+5,M = 2e5+5;
int n,m,s;
struct EDGE{int u,v,w,nxt;
}edge[M]; int tot,head[N];
void add(int u,int v,int w){edge[++tot].u = u; edge[tot].v = v;edge[tot].w = w; edge[tot].nxt = head[u];head[u] = tot;
}
int d[N]; bool vis[N];
priority_queue >q;
void dijkstra(){memset(d,0x3f,sizeof(d)); d[s] = 0;q.push(make_pair(0,s));while(!q.empty()){int x = q.top().second; q.pop();if(vis[x]) continue;for(int i=head[x];i;i=edge[i].nxt){int y = edge[i].v , z = edge[i].w;if(d[x]+z < d[y]){d[y] = d[x]+z;q.push(make_pair(-d[y],y));}}vis[x] = true;}
}
int main(){ios::sync_with_stdio(false);cin >> n >> m >> s;for(int i=1;i<=m;i++){int u,v,w;cin >> u >> v >> w;add(u,v,w);}dijkstra();for(int i=1;i<=n;i++)cout << d[i] << " ";return 0;
}
const int INF = 1e6;
const int N = 105;
struct Edge { int u, v, w; } e[10005]; //边:起点u,终点v,权值w
int n, m, cnt;
int pre[N]; //记录前驱结点,用于打印路径。pre[x]=y:在最短路径上,结点x的前一个结点是y
void print_path(int s, int t) { //打印从s到t的最短路if(s==t){ printf("%d ", s); return; } //打印起点print_path(s, pre[t]); //先打印前一个点printf("%d ", t); //后打印当前点。最后打印的是终点t
}
void bellman(){int s=1; //定义起点int d[N]; //d[i]记录第i个结点到起点s的最短距离for (int i=1; i<=n; i++) d[i]=INF; //初始化为无穷大d[s]=0;for (int k=1; k<=n; k++) //一共有n轮操作for (int i=0; i < cnt; i++){ //检查每条边int x = e[i].u, y = e[i].v;if (d[x] > d[y] + e[i].w){ // x通过y到达起点s:如果距离更短,更新d[x] = d[y] + e[i].w;pre[x] = y; //如果有需要,记录路径}}printf("%d\n", d[n]);// print_path(s,n); //如果有需要,打印路径
}
const int N = 1e6+5, M = 2e6+5; //1百万个点,2百万个边
int n, m;
int pre[N]; //记录前驱结点,用于打印路径
void print_path(int s, int t) { //打印从s到t的最短路if(s==t){ printf("%d ", s); return; } //打印起点print_path(s, pre[t]); //先打印前一个点printf("%d ", t); //后打印当前点。最后打印的是终点t
}
int head[N],cnt; //链式前向星
struct {int to, next, w;}edge[M]; //存边
void init(){ //链式前向星初始化for(int i = 0; i < N; ++i) head[i] = -1; //点初始化for(int i = 0; i < M; ++i) edge[i].next = -1; //边初始化cnt = 0;
}
void addedge(int u, int v, int w){ //前向星存边edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;
}
int dis[N]; //dis[i],从起点到点i的距离
bool inq[N]; //inq[i] = true 表示点i在队列中
int Neg[N]; //判断负环(Negative loop)
int spfa(int s) { //返回1表示出现负环memset(Neg, 0, sizeof(Neg));Neg[s] = 1;for(int i=1; i<=n; i++) {dis[i]=INF; inq[i]=false; } //初始化dis[s] = 0; //起点到自己的距离是0queue Q; Q.push(s); //从s开始,s进队列inq[s] = true; //起点在队列中while(!Q.empty()) {int u = Q.front(); Q.pop(); //队头出队inq[u] = false; //u已经不在队列中for(int i=head[u]; ~i; i = edge[i].next) { //~i也可以写成 i!=-1int v = edge[i].to, w = edge[i].w; //v是u的第i个邻居if (dis[u]+w < dis[v]) { //u的第i个邻居v,它借道u,到s更近dis[v] = dis[u]+w; //更新邻居v到s的距离pre[v] = u; //如果有需要,记录路径if(!inq[v]) { //邻居v更新状态了,但v不在队列中,放进队列inq[v] = true;Q.push(v);Neg[v]++; //点v进入队列的次数if(Neg[v] > n) return 1; //出现负环}}}}return 0;
}
#include
using namespace std;
const int N = 5005,M = 2e5+1;
struct Edge{int u,v,w;}edge[M]; //用最简单且最省空间的结构体数组存边
bool cmp(Edge a, Edge b){ return a.w < b.w;} //从小到大排序
int s[N]; //并查集
int find_set(int x){ //查询并查集,返回x的根if(x != s[x])s[x] = find_set(s[x]); //路径压缩return s[x];
}
int n,m; // n个点,m条边
void kruskal(){sort(edge+1, edge+m+1, cmp); //对边做排序for(int i=1; i<=n; i++) s[i]=i; //并查集初始化int ans = 0, cnt=0; //cnt: 已经加入MST的边数for(int i=1; i<=m; i++){ //贪心:逐一加入每条边if(cnt == n-1) break; //小优化:不要也行int e1 = find_set(edge[i].u); //边的前端点u属于哪个集?int e2 = find_set(edge[i].v); //边的后端点v属于哪个集?if(e1 == e2) continue; //属于同一个集:产生了圈,丢弃else{ //不属于同一个集ans += edge[i].w; //计算MSTs[e1]= e2; //合并cnt++; //统计MST中的边数}}if(cnt == n-1) cout << ans; //n-1条边else cout << "orz"; //图不是连通的
}
int main(){cin >> n >> m;for(int i=1; i<=m; i++) cin >> edge[i].u >> edge[i].v >> edge[i].w;kruskal();return 0;
}
#include
using namespace std;
const int N=5005,M = 2e5+1;
struct edge{ //记录边
int to, w;
edge(int a,int b){ to = a, w = b;} //赋值
};
vector G[M];
struct node {int id, dis; //id:点;dis:边node(int a, int b){ id = a, dis = b;} //赋值bool operator < (const node &u) const { return dis > u.dis; }
};
int n, m;
bool done[N]; //done[i]=ture: 表示点i已经在MST中
void prim() { //对比dijkstra: 求s到其他所有点的最短路int s = 1; //从任意点开始,例如从1开始for(int i =1;i<=N;i++) done[i]=false; //初始化priority_queue q;q.push(node(s, 0)); //从s点开始处理队列int ans=0,cnt=0;while (!q.empty()) {node u = q.top(); q.pop(); //pop出距集合U最近的点uif (done[u.id]) continue; //丢弃已经在MST中的点,有判圈的作用done[u.id] = true; //标记ans += u.dis;cnt++; //统计点数for (int i = 0; i< G[u.id].size(); i++) { //检查点u的所有邻居edge y = G[u.id][i]; //一个邻居yif (done[y.to]) continue; //丢弃已经在MST中的点q.push(node(y.to, y.w)); //扩展新的邻居,放进优先队列}}if(cnt == n) cout << ans; //cnt=n个点。注意在kruskal代码中cnt是边数
else cout << "orz";
}
int main() {cin>>n>>m;for(int i=1; i<=m; i++) {int a,b,w; cin>>a>>b>>w;G[a].push_back(edge(b,w)); G[b].push_back(edge(a,w)); //双向边}prim();return 0;
}
#include
using namespace std;
const int N = 55;
int degree[N]; //记录度
int G[N][N]; //存图
void euler(int u){ //从u开始DFSfor(int v = 1; v <= 50; v++) { //v是u的邻居if(G[u][v]) {G[u][v]--;G[v][u]--;euler(v);cout << v << " " << u << endl; //在euler()后打印,即回溯时打印}}
}
int main(){int t; cin >> t;int cnt = 0;while (t--) {cnt++;if(cnt != 1) cout << endl;cout << "Case #" << cnt << endl;memset(degree, 0, sizeof(degree));memset(G, 0, sizeof(G));int n; cin >> n;int color;for(int i = 0; i < n; i++) { //输入n条边int u, v; cin>>u>>v;color = u; //记录一种颜色。测试的时候可能只出现某些颜色degree[u]++;degree[v]++; //记录点的度G[u][v]++;G[v][u]++; //存图:=0不连接,=1连接,>1有重边}int ok = 1;for(int i = 1; i <= 50; i++)if(degree[i] % 2) { //存在奇点,无欧拉路cout<<"some beads may be lost"<
#include
#define ll long long
using namespace std;ll read(){ll X = 0 ; int f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){ch = getchar();f = -1;}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 2e4+10 , M = 2e5+10;
int n,m; int to[M] , nxt[M] , head[N] , tot;
inline void add(int x,int y){to[++tot] = y;nxt[tot] = head[x];head[x] = tot;
}int dfn[N] , low[N] , Num; bool cut[N];
void tarjan(int x,int rt){dfn[x] = low[x] = ++Num;int flag = 0;for(int i=head[x];i;i=nxt[i]){int y = to[i];if(!dfn[y]){tarjan(y,rt);low[x] = min(low[x],low[y]);if(dfn[x] <= low[y])flag++;}else low[x] = min(low[x],dfn[y]);}if(flag > 1) cut[x] = true;else if(flag && rt != x) cut[x] = true;
}int main(){n = read(); m = read();for(int i=1;i<=m;i++){int x = read() , y = read();add(x,y); add(y,x);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);int cnt = 0;for(int i=1;i<=n;i++)if(cut[i]) cnt++;printf("%d\n",cnt);for(int i=1;i<=n;i++)if(cut[i]) printf("%d ",i);return 0;
}
#include
#include
#include
using namespace std;
const int N = 1005;
int n, m, low[N], dfn;
vector G[N]; //存图
void dfs(int u,int fa){ //计算每个点的low值low[u]= ++dfn;for(int i=0;iint v = G[u][i];if(v == fa) continue;if(!low[v]) dfs(v,u);low[u] = min(low[u], low[v]);}
}
int tarjan(){int degree[N]; //计算每个缩点的度数memset(degree,0,sizeof(degree));for(int i=1; i<=n; i++) //把有相同low值的点看成一个缩点for(int j=0; jwhile(~scanf("%d%d", &n, &m)){memset(low, 0, sizeof(low));for(int i=0; i<=n; i++) G[i].clear();for(int i=1; i<=m; i++){int a, b; scanf("%d%d", &a, &b);G[a].push_back(b); G[b].push_back(a);}dfn = 0;dfs(1,-1);int ans = tarjan();printf("%d\n",(ans+1)/2);}return 0;
}
https://www.luogu.com.cn/problem/P3387
#include
#define ll long long
using namespace std;ll read(){ll X = 0 ; int f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){ch = getchar();f = -1;}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 1e4+10 , M = 1e5+10;
int n,m;
int a[N];class Graph{private:int tot;public:int head[N],ver[M],nxt[M];inline void add(int u,int v){ver[++tot] = v;nxt[tot] = head[u];head[u] = tot;}
}c1,c2;int dfn[N],low[N],Num,fa[N],val[N],Sum;
int stk[N],top;bool ins[N];
void tarjan(int x){dfn[x] = low[x] = ++Num;stk[++top] = x; ins[x] = true;for(int i=c1.head[x];i;i=c1.nxt[i]){int y = c1.ver[i];if(!dfn[y]){tarjan(y);low[x] = min(low[x],low[y]);}else if(ins[y])low[x] = min(low[x],dfn[y]);}if(low[x] == dfn[x]){Sum++;do{val[Sum] += a[stk[top]];ins[stk[top]] = false;fa[stk[top]] = Sum;}while(stk[top--] != x);}
}int main(){n = read(); m = read();for(int i=1;i<=n;i++)a[i] = read();for(int i=1;i<=m;i++){int u,v;u = read(); v = read();c1.add(u,v);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int u=1;u<=n;u++)//缩点 for(int j=c1.head[u];j;j=c1.nxt[j]){int v = c1.ver[j];if(fa[u] == fa[v]) continue;c2.add(fa[u],fa[v]); in[fa[v]]++;}/*...*/return 0;
}
#include
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
vector G[N];
int father[N],val[N],mark;
bool vis[N];
ll dp[N][2];
void addedge(int from,int to){G[from].push_back(to); //用邻接表建树father[to] = from; //父子关系
}
void dfs(int u){ //和洛谷P1352 几乎一样dp[u][0] = 0; //赋初值:不参加dp[u][1] = val[u]; //赋初值:参加vis[u] = true;for(int v : G[u]){ //遍历u的邻居vif(v == mark) continue; dfs(v);dp[u][1] += dp[v][0]; //父结点选择,子结点不选dp[u][0] += max(dp[v][0],dp[v][1]); //父结点不选,子结点可选可不选}
}
int check_c(ll u){ //在基环树中找环上一个点vis[u] = true;int f = father[u];if(vis[f]) return f; //第2次访问到,是环上一个点else check_c(f); //继续向父结点方向找
}
ll solve(int u){ //检查一棵基环树ll res = 0;mark = check_c(u); //mark是基环树的环上一个点 dfs(mark); //做一次dfsres = max(res,dp[mark][0]); //mark不参加mark = father[mark];dfs(mark); //mark的父结点不参加,再做一次dfsres = max(res,dp[mark][0]);return res;
}
int main(){int n; scanf("%d",&n);for(int i = 1;i <= n;i++){int d; scanf("%d%d",&val[i],&d); addedge(d,i);}ll ans = 0;for(int i = 1;i <= n;i++)if(!vis[i]) ans += solve(i); //逐个检查每棵基环树printf("%lld\n",ans);return 0;
}
#include
#include
#include
#define MAXN 10//定义最大节点数
using namespace std;
vector G[MAXN];//用邻接表作为图的存储结构
int color[MAXN];//保存每个节点的颜色
int V,E;
void read(){for(int i = 0;i < E;i ++){int s,t;cin >> s >> t;G[s].push_back(t);G[t].push_back(s);}
}
bool dfs(int v,int c){color[v] = c;//给节点 v 染色为 c//依次对 v 相邻的点进行处理for(int i = 0;i < G[v].size();i ++){//如果相邻的点和自己颜色相同则则无法达成目标if(color[G[v][i]] == c) return false;//如果相邻的点没有染色,且对这个点染不同的颜色后,对之相邻顶点的搜索出现矛盾则无法达成目标if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;}return true;//如果对所有相邻的点都染色成功则返回 true
}
void solve(){//对邻接表中的顶点依次进行搜索染色for(int i = 0;i < V;i ++){if(color[i] == 0){if(!dfs(i,1)){cout << "NO" << endl;return ;}}}cout << "YES" << endl;
}
int main(void)
{cin >> V >> E;read();solve();return 0;
}
#include
#define ll long long
using namespace std;
ll read(){ll X = 0 , f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){f = -1;ch = getchar();}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 510;
const int M = 5e4+10;
int n,m,e;
int ver[M],nxt[M],head[N],tot;
inline void add(int x,int y){ver[++tot] = y;nxt[tot] = head[x];head[x] = tot;
}
bool vis[N];
int match[N];
bool dfs(int x){for(int i=head[x];i;i=nxt[i]){int y = ver[i];if(vis[y]) continue;vis[y] = true;if(!match[y] || dfs(match[y])){match[y] = x;return true;}}return false;
}int main(){n = read(); m = read(); e = read();for(int i=1;i<=e;i++){int u,v;u = read(); v = read();add(u,v);}int ans = 0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans += dfs(i);}cout << ans;return 0;
}
#include
using namespace std;
const int INF = 1e9;
const int N = 250;
#define ll long long
int n, m;
ll graph[N][N], pre[N]; //graph[][]不仅记录图,还是残留网络
ll flow[N];
ll bfs(int s,int t){ //一次bfs找一条增广路memset(pre,-1,sizeof pre);flow[s] = INF; pre[s] = 0; //初始化起点queue Q; Q.push(s); //起点入栈,开始bfswhile(!Q.empty()){int u = Q.front(); Q.pop();if(u==t) break; //搜到一个路径,这次bfs结束for(int i=1; i<=n; i++){ //bfs所有的点if(i!=s && graph[u][i]>0 && pre[i]==-1){pre[i] = u; //记录路径Q.push(i);flow[i] = min(flow[u], graph[u][i]); //更新结点流量}}}if(pre[t]==-1) return -1; //没有找到新的增广路return flow[t]; //返回这个增广路的流量
}
ll maxflow(int s, int t){ll Maxflow = 0;while(1){ll flow = bfs(s,t); //执行一次bfs,找到一条路径,返回路径的流量if(flow == -1) break; //没有找到新的增广路,结束int cur = t; //更新路径上的残留网络while(cur!=s){ //一直沿路径回溯到起点int father = pre[cur]; //pre[]记录路径上的前一个点graph[father][cur] -= flow; //更新残留网络:正向边减graph[cur][father] += flow; //更新残留网络:反向边加cur = father;}Maxflow += flow;}return Maxflow;
}
int main(){int s,t; scanf("%d%d%d%d",&n,&m,&s,&t);memset(graph,0,sizeof graph);for(int i=0; iint u,v,w; scanf("%d%d%d",&u,&v,&w);graph[u][v] += w; //可能有重边}printf("%ld\n",maxflow(s,t));return 0;
}
#include
using namespace std;
#define ll long long
const ll INF=1e9;
int n,m,s,t;
const int N=250, M=11000; //M定义为边的两倍:双向边
int cnt=1,head[N]; //8-16行:链式前向星。cnt初值不能是0,可以是1、3、5
struct {int to, nex, w;} e[M];
void add(int u,int v,int w) {cnt++; //cnt初值是1,cnt++后第一个存储位置是cnt=2,是偶数位置e[cnt].to = v;e[cnt].w = w;e[cnt].nex = head[u];head[u] = cnt;
}
int now[N],dep[N]; //dep[]记录点所在的层次(深度)
int bfs() { //在残留网络中构造分层图for(int i=1;i<=n;i++) dep[i]=INF;dep[s] = 0; //从起点s开始分层now[s] = head[s]; //当前弧优化。now是head的拷贝queueQ; Q.push(s);while(!Q.empty()) {int u = Q.front(); Q.pop();for(int i=head[u]; i>0;i=e[i].nex) { //搜点u的所有邻居,邻居是下一层int v = e[i].to;if(e[i].w>0 && dep[v]==INF) { // e[i].w>0表示还有容量Q.push(v);now[v] = head[v];dep[v] = dep[u]+1; //分层:u的邻居v是u的下一层if(v==t) return 1; //搜到了终点,返回1}}}return 0; //如果通过有剩余容量的边无法到达终点t,即t不在残留网络中,返回0
}
int dfs(int u,ll sum) { //sum是这条增广路对最大流的贡献if(u==t) return sum;ll k,flow=0; //k是当前最小的剩余容量for(int i=now[u]; i>0 && sum>0; i=e[i].nex) {now[u]=i; //当前弧优化int v=e[i].to;if(e[i].w>0 && (dep[v]==dep[u]+1)){ //分层:用dep限制只能访问下一层k = dfs(v,min(sum,(ll)e[i].w));if(k==0) dep[v] = INF; //剪枝,去掉增广完毕的点。其实把INF写成0也行e[i].w -= k; //更新残留网络:正向减e[i^1].w += k; //更新残留网络:反向加。小技巧:奇偶边flow += k; //flow表示经过该点的所有流量和sum -= k; //sum表示经过该点的剩余流量}}return flow;
}
int main() {scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++) {int u,v,w; scanf("%d%d%lld",&u,&v,&w);add(u,v,w); add(v,u,0); //双向边,反向边的容量是0}ll ans=0;while(bfs()) ans += dfs(s,INF); //先后做BFS和DFS。当t不在残留网络中时退出printf("%lld",ans);return 0;
}
#include
using namespace std;
#define ll long long
const ll INF=1e9;
int n,m,s,t ;
const int N=250, M=11000; //M定义为边的两倍:双向边
int cnt=1,head[N]; //链式前向星
struct{int from, to, nex, w;} e[M];
void add(int u, int v, int w){cnt++; e[cnt].from = u;e[cnt].to = v;e[cnt].w = w;e[cnt].nex = head[u];head[u] = cnt;
}
int now[M], pre[M]; //pre[]用于记录路径,pre[i]是路径上点i(的存储位置)的前一个点(的存储位置)
int dep[M], gap[M]; //dep[i]: 点i的高度;gap[i]:高度为i的点的数量
void bfs(){ //用BFS确定各顶点到汇点的距离memset(gap,0,sizeof(gap)); //初始化间隙数组memset(dep,0,sizeof (dep)); //所有点的高度初始为0dep[t] = 1; //汇点t的高度是1,其他点的高度都大于1queue Q; Q.push(t); while(!Q.empty()){int u = Q.front(); Q.pop();gap[dep[u]]++; //间隙数组:计算高度为dep[u]的结点个数for(int i=head[u]; i>0; i=e[i].nex){ int v = e[i].to; //v是u的邻居点if(e[i^1].w && dep[v]==0){ //反向边不用处理;高度不等于0的已经处理过了dep[v] = dep[u]+1; Q.push(v);}}}
}
ll Augment(){ //沿着增广路径更新残留网络ll v = t, flow = INF;while(v != s){ //找这个路径的流量int u = pre[v]; //u是v向源点s方向回退的上一个点,相当于DFS的回溯 if(e[u].w < flow) flow = e[u].w; //路径上的最小容量就是这个路径的流量v = e[u].from; //更新v,继续回退}v = t;while(v != s){ //更新残留网络int u=pre[v]; //向源点s方向回退e[u].w -= flow; //正向边e[u^1].w += flow; //反向边。用到了奇偶边的技巧v = e[u].from; //更新v,继续回退}return flow; //返回这个路径的流量
}
void ISAP(){ bfs(); //用bfs()求每个点到汇点的距离(高度)ll flow = 0; //计算最大流 int u = s; //从源点s开始找增广路径memcpy(now, head, sizeof (head)); //当前弧优化。now是head的拷贝while(dep[s] <= n){ //最大距离(高度)是n if(u == t){ //找到了一条增广路径flow += Augment(); //更新残留网络,更新流量u = s; //回到s,重新开始找一条增广路径}bool ok = 0; //用于判断是否能顺利往下走for(int i=now[u]; i; i=e[i].nex){ //在u的邻居中确定路径的下一个点int v = e[i].to; //v是u的邻居点if(e[i].w && dep[v]+1==dep[u]){ //沿着高度递减的方向找下一个点ok = 1; //顺利找到了路径的下一个点pre[v] = i; //记录路径now[u] = i; //记录当前弧,下一次跳过它u = v; //u更新为路径的下一个点vbreak; //退出for,回到while循环,继续找路径的下一个点}}if(!ok){ //路径走不下去了,需要更新u的高度重新走if(!--gap[dep[u]]) break; //u的下一个深度的点没有了,断层了,退出whileint mindep = n+10; //mindep用于计算u的邻居点的最小高度。初值比n大就行for(int i=head[u]; i; i=e[i].nex){ //在u的邻居中找最小的高度int v = e[i].to;if(dep[v]
scanf("%d%d%d%d", &n,&m,&s,&t);
for(int i=1; i<=m; ++i){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,0); //反向边的初始容量是0}ISAP();return 0;
}
#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int dis[N], pre[N], preve[N]; //dis[i]记录起点到i的最短距离。pre和 preve见下面注释
int n, m;
struct edge{int to, cost, capacity, rev; //rev用于记录前驱点edge(int to_,int cost_,int c,int rev_){to=to_; cost=cost_; capacity=c; rev=rev_;}
};
vector e[N]; //e[i]:存第i个结点连接的所有的边
void addedge(int from,int to,int cost,int capacity){//把1个有向边再分为2个e[from].push_back(edge(to, cost, capacity, e[to].size()));e[to].push_back(edge(from, -cost, 0, e[from].size()-1));
}
bool spfa(int s, int t, int cnt){ //套SPFA模板bool inq[N];memset(pre, -1, sizeof(pre));for(int i = 1; i <= cnt; ++i) {dis[i]=INF; inq[i]=false; }dis[s] = 0;queue Q;Q.push(s);inq[s] = true;while(!Q.empty()){int u = Q.front();Q.pop();inq[u] = false;for(int i=0; i < e[u].size(); i++)if(e[u][i].capacity > 0){int v = e[u][i].to, cost = e[u][i].cost;if(dis[u]+cost < dis[v]){dis[v] = dis[u]+cost;pre[v] = u; //v的前驱点是upreve[v] = i; // u的第i个边连接v点if(!inq[v]){inq[v] = true;Q.push(v);}}}}return dis[t] != INF; //s到t的最短距离(或者最小费用)是dis[t]
}
int mincost(int s,int t,int cnt){ //基本上是套最大流模板int cost = 0;while(spfa(s,t,cnt)){int v = t, flow = INF; //每次增加的流量while(pre[v] != -1){ //回溯整个路径,计算路径的流int u = pre[v], i = preve[v]; //u是v的前驱点,u的第i个边连接vflow = min(flow, e[u][i].capacity); //所有边的最小容量就是这条路的流v = u; //回溯,直到源点}v = t;while(pre[v] != -1){ //更新残留网络int u = pre[v], i = preve[v];e[u][i].capacity -= flow; //正向减e[v][e[u][i].rev].capacity += flow; //反向加,注意rev的作用v = u; //回溯,直到源点}cost += dis[t]*flow; //费用累加。如果程序需要输出最大流,在这里累加flow}return cost; //返回总费用
}
int main(){while(~scanf("%d%d", &n, &m)){for(int i=0;iint u,v,w; scanf("%d%d%d",&u,&v,&w);addedge(u,v,w,1); addedge(v,u,w,1); //把1个无向边分为2个有向边 }int s = n+1, t = n+2;addedge(s,1,0,2); //添加源点addedge(n,t,0,2); //添加汇点printf("%d\n", mincost(s,t,n+2));}return 0;
}
博主正在参与2022博客之星的评选,希望各位的五星支持