- 博客(69)
- 收藏
- 关注
RSS订阅原创 Yjmstr的算法竞赛模板（updating）
YJMSTR的算法竞赛模板目录文章目录YJMSTR的算法竞赛模板目录图论一、最短路1.spfa与负环1.1 bfs-spfa找负环：1.2 dfs-spfa找负环2.dijkstra模板（set模拟二叉堆堆优化)3.Floyd求多源最短路/传递闭包/倍增floyd3.1&&3.2最短路代码略3.3 倍增floyd4.差分约束二、生成树总结图论最短路（spfa，dijkstra，floyd， 负环，差分约束）、最小生成树（最小直径生成树、度限制最小生成树）。一、最短路
2023-07-12 19:02:48
810
原创 codeforces 1139E Maximize Mex
前言我是傻逼正文题意：有nnn个学生和mmm个社团，第iii个学生能力值为pip_ipi，属于社团cic_ici。在ddd天内 每天从每个社团里选出一个人组成一队SSS该队的能力值为mex(S)mex(S)mex(S)第iii天时第kik_iki个学生会离开社团（在该天组队之前）求每天能选出的队伍能力值最大是多少1≤m≤n≤50001\le m \le n \le 50001≤m≤n≤50000≤pi<50000 \le p_i < 50000≤pi<5000
2021-02-12 13:30:39
141
原创 洛谷P3227 [HNOI2013]切糕
前言我是傻逼正文妙妙建图把每个(x,y)位置上的纵轴看成一条链如果没有DDD的限制，直接求出每一纵轴上的最小值之和就行相当于有一个源点向所有纵轴连容量inf\infinf的边，所有纵轴各自连一条长为RRR的链到汇点，求最大流\最小割考虑把DDD的限制加进网络流如果一个相邻的纵轴选了高度iii那么当前纵轴低于i−Di-Di−D和高于i+Di+Di+D的位置都不能选直接从相邻纵轴的位置iii向当前纵轴的位置i−Di-Di−D连边即可高于i+Di+Di+D的情况也被从当前纵轴连向相邻纵
2021-02-04 22:21:19
107
原创 AT2167 [AGC006F] Blackout
前言我是傻逼正文神仙题嗷把原图看成邻接矩阵，(x,y)是黑色的看成从x向y连一条有向边，问题转为求最终有向边的边数。如果存在边x->y，边y->z, 且边z->x不存在，那么会自动生成边z->x最终的图是若干个有向三角形和端点不依次相接的边考虑将各个连通分量三染色，记三种颜色分别为0 1 2如果一个连通块可以被染成三种颜色，那么所有0和1之间将连边，所有1和2之间将连边，所有2和0之间将连边对答案的贡献是cnt0∗cnt1+cnt1∗cnt2+cnt2∗cnt0cn
2021-02-04 15:39:09
107
原创 codeforces 786E ALT最小割 树剖+线段树优化建图
前言我是傻逼正文题意：给出一颗树和若干条路径，可以花费代价1使路径合法，或者使某条边变“好”。当一条路径经过的每条边都为“好”，那么这条边也合法求最小代价使所有给出的路径合法，并输出方案。1≤n,m≤200001\le n,m \le 200001≤n,m≤20000这是一个"二选一"求最小开销的最小割模型。把原图中的边转化成点，把每个人和他路径上的所有边连边，容量为infinfinf,人和源点连边，代价为111,边和汇点连边，代价也为111 求最小割就是答案了。但这样建图复杂度太高，得写
2021-02-03 17:12:04
114
原创 codeforces 342E Xenia and Tree 点分树
题意：给定一棵nnn个节点的树，初始时111号节点为红色，其余为蓝色。要求支持如下操作：将一个节点变为红色。询问节点uuu到最近红色节点的距离。共qqq次操作。1≤n,q≤1051 \le n, q \le 10 ^51≤n,q≤105点分树：将点分治时的重心按分治的层级连成一颗树，根据重心的性质树高不会超过log nlog \ nlog n于是暴力就变成log的了对某个结点进行修改的话，影响的是他到根的一段log长的路径回到这题先建出点分树，...
2021-01-31 10:31:44
186
原创 洛谷P3806 点分治1
树上的路径可以分为两类，一类是经过当前子树的根结点的，另一类是在当前子树内的。这两种路径里找加起来长度为k的就行了。第一类路径可以直接算（当前子树的根为lca）， 第二类路径每次递归到重心处理下去，就可以转化为第一种路径#include<bits/stdc++.h>using namespace std;const int maxn = 1e4 + 7, maxm = 1e7, inf = 1e9+7;struct edge { int v, w, nxt;}e[maxn
2021-01-30 18:54:11
75
原创 Gym102538 300iq Contest 3 部分补题记录 || 杨氏矩阵学习笔记
目录文章目录目录前言D.Disjoint Lis前置知识：杨氏矩阵杨表和排列的对应关系：前言我是傻逼D.Disjoint Lis题意：定义一个排列是“好”的，如果在这个排列中能找到两个不相交的最长上升子序列。给定nnn，求长为nnn的"好"排列个数对998244353取模的结果。n<=75n<=75n<=75前置知识：杨氏矩阵参考链接杨氏矩阵又叫杨表 满足：若(i,j)为空，则它右边和下边的位置也一定为空若(i,j)有元素w,则它右边和下边要么为空，要么有比w大的
2021-01-22 16:35:59
450
原创 矩阵树定理||高斯消元求行列式
参考链接-博客园 参考链接-oiwiki定理部分并没有什么原创内容，全是阅读上面两篇文章做的笔记。矩阵树定理KirchhoffKirchhoffKirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。矩阵树定理有很多形式，以下内容是一些声明。应用矩阵树定理的图允许重边，但是不允许自环。以下内容是照抄oiwiki的无向图情况：设GGG是一个有nnn个顶点的无向图。定义度数矩阵D(G)D(G)D(G)为：Dii(G)=deg(i),Dij(G)=0,i≠jD_{ii
2021-01-21 21:49:58
551
原创 HDU 2481 Toy
是上一题FJOI轮状病毒的加强版，前置知识：BurnsideBurnsideBurnside引理：所有等价类的数目为其所有置换的不动点数目的平均值。具体见《算法竞赛入门经典——训练指南》无旋情况下的递推式是F[n]=3∗F[n−1]−F[n−2]+2F[n] = 3*F[n-1]-F[n-2]+2F[n]=3∗F[n−1]−F[n−2]+2用dp来推：先考虑链的情况设f[i]f[i]f[i]表示第iii个点还没和中心连通 前i−1i-1i−1个点已经和中心或者第iii个点连通g[i]g[i]
2021-01-21 21:48:48
87
原创 洛谷P2144 [FJOI2007]轮状病毒
矩阵树定理的第二题把nnn轮状病毒的图建出来套用矩阵树定理就行了这辈子不可能写高精度召唤python不能直接把度数标出来 会wa1 得直接模拟建图过程maxn = 107deg = [[0 for i in range(maxn)] for j in range(maxn)]D = [[0 for i in range(maxn)] for j in range(maxn)]G = [[0 for i in range(maxn)] for j in range(maxn)]L = [
2021-01-21 18:57:47
111
原创 洛谷P4111[HEOI2015]小z的房间
矩阵树定理的第一题用高斯消元法算行列式#include<bits/stdc++.h>using namespace std;#define ll long longconst int maxn = 83, md = 1e9;int n, m, L[maxn][maxn], a[10][10], A[maxn][maxn];int D[maxn][maxn], tot, id[maxn][maxn];char str[maxn];int nx[4] = {-1, 0, 1, 0}
2021-01-21 16:50:03
136
3
原创 Codeforces Good Bye 2020 补题记录
系列文章目录文章目录系列文章目录前言G. Song of the Sirens前言我是傻逼G. Song of the Sirens给定n和q，字符串s0和t，t的长度为nsis_isi满足si+1=si+ti+sis_{i+1} =s_i+t_i+s_isi+1=si+ti+si,加号表示字符串相接q次询问，每次询问给出一个字符串www，求www作为子串在sis_isi中的出现次数...
2021-01-20 23:14:29
158
原创 Educational Codeforces Round 102 (Rated for Div. 2)
Educational Codeforces Round 102 (Rated for Div. 2)文章目录Educational Codeforces Round 102 (Rated for Div. 2)前言A.Replacing ElementsB.String LCMC.No More InversionsD.前言我是傻逼A.Replacing Elements先判一下a中最大元素是否<=d 如果否 再判一下最小的两个元素之和是否<=d就行了#include<bit
2021-01-17 14:11:29
85
原创 Codeforces Round #694 (Div. 2)
Codeforces Round #694 (Div. 2)比赛链接文章目录Codeforces Round #694 (Div. 2)A.Strange PartitionB.Strange ListC.Strange Birthday PartyD.Strange DefinitionA.Strange Partition向上取整，有余数的数越多越好合并不会让有余数的数变多，只会变少或不变所以求max就一个个算，求min就全部合并为一个数#include<bits/stdc++.h&
2021-01-14 15:11:44
112
原创 Codeforces Round #695 (Div. 2)
Codeforces Round #695 (Div. 2)比赛链接目录Codeforces Round #695 (Div. 2)A. Wizard of OrzB. Hills And ValleysC. Three BagsA. Wizard of Orz构造98901234567…形式的就是最大的了一开始写了个错的98987654321… 添了几发罚时如果是正式赛就gg了#include<bits/stdc++.h>using namespace std;int t,
2021-01-14 13:50:25
121
原创 洛谷P4308 CTSC2011幸福路径 倍增floyd
给每个点加上边权为0的自环设f[i][j][t]f[i][j][t]f[i][j][t]表示从点i到点j走2^t步的最长路径长度那么有f[i][j][t]=max{f[i][j][t−1],f[i][k][t−1]+f[k][j][t−1]∗ρ2t}f[i][j][t] = max\{f[i][j][t-1], f[i][k][t-1]+f[k][j][t-1]*\rho^{2^t}\}f[i][j][t]=max{f[i][j][t−1],f[i][k][t−1]+f[k][j][t−1]∗ρ2t}
2020-12-20 15:44:58
117
1
原创 洛谷P1841 JSOI2007重要的城市 Floyd
每个合法点对(i,j)最多只会贡献一个重要的城市那么我们跑一遍floyd在floyd的时候求出每个点对最后一个用来松弛的中间点如果存在多个中间点 说明这个点对不会贡献重要的城市最后答案还要离散化一下 因为不同点对贡献的重要的城市可能相同#include<bits/stdc++.h>using namespace std;const int maxn = 207;int f[maxn][maxn], ans[maxn][maxn];int stk[20007], tot, top
2020-12-20 11:04:59
139
1
原创 Gym102870 2020-2021 “Orz Panda” Cup Programming Contest 补题记录
D. Data Structure Master and Orz Pandas树上期望dp列个式子跑一遍树形dp就做完了场上剩半小时才开这题 没写出来亏死#include<bits/stdc++.h>using namespace std;const int maxn = 1e5 + 7, md = 998244353;#define ll long longll ksm(ll a, ll b) { a %= md; ll res = 1; while (
2020-12-15 13:34:28
281
原创 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019) 补题记录
A.max or minCF上ac了洛谷wa1？好神啊不会做去膜了下官方题解 并跟着写了一发线段树 结果写挂了没调出来后来换珂朵莉树T爆了bzy：set维护线段不是很常见的操作吗 你怎么写到100行的我：。。。。。做法如下注意到有意义的只是当前数字与目标数字的大小关系我们可以令小于当前数字的数全部变成-1 大于则为1 等于为0考虑以下情况如果序列是0 1 1 1 或者0 -1 -1 -1 要让他们变成0只要进行（n-（0的个数））次操作即可如果是0 -1 1 -1 这样的交替序列 如
2020-12-10 01:03:52
367
原创 图的绝对中心&最小直径生成树 GYM102391 I -Minimum Diameter Spanning Tree
题面参考：窝们要枚举绝对中心在哪一条边上假设绝对中心S在边<u,v>上 离u的距离是x根据定义 他到其他点的最短路的最大值最小 且这个最大值会出现两次把他写成函数的形式：d(i,x)=min(d[u][i]+x,d[v][i]+w−x)d(i,x) = min(d[u][i]+x,d[v][i]+w-x)d(i,x)=min(d[u][i]+x,d[v][i]+w−x),其中x是S到u的距离，www是边<u,v><u,v><u,v>的边权而窝们要
2020-11-10 11:37:33
229
原创 NOIP2013货车运输 计蒜客习题 蒜头君运送宝藏
手画样例容易发现每次询问所求答案为路径上的最小边而最大生成树的最小边一定是所有生成树中最大的 且原图的连通性不变指定每个连通块中的任意一个结点为根建树 可以发现每次询问的货车路径经过他们的LCA可以在求LCA的同时维护最小边的信息 同样用一个倍增数组 而判断连通可以用并查集半个周日都献给这题了丂点击打开链接#include<bits/stdc++.h>using namespace...
2020-04-18 11:49:10
297
1
原创 计蒜客习题-打鸟 二分图匹配 最大流
经典模型 题意求最小操作次数其实是求有点的每行最多选一个 每列最多选一个能选几个 把行划成一个集合 列划成一个集合 然后连边跑二分图匹配 最大匹配就是答案 鸟那么可爱为什么要打鸟（i,j)有鸟 就连i->j 网络流版本要加n防重复
2020-04-18 11:48:52
218
原创 计蒜客习题 蒜头君倒水
推出转移矩阵 (1−xxy1−y)\begin{pmatrix}1-x&y \\x&1-y\end{pmatrix} 之后的就很显然了 倒了几次就是求转移矩阵的几次幂 然后乘上原矩阵(ab)\begin{pmatrix}a\\b\end{pmatrix}即可 传送门 注意矩阵乘法不满足交换律#include<bits/stdc++.h>using namespace std
2020-04-18 11:48:42
257
原创 计蒜客习题-城市规划 最小边覆盖集
不用管独立的居民区，统计点数的时候加进来就行了 由于是无向图 要插双向边//最小边覆盖集==最大点独立集==顶点数-最大匹配//把地图交替染色 构建二分图#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;#define p1 (i-1)*m+j-1#defin
2020-04-18 11:48:19
99
原创 计蒜客习题-棋盘上的马 最大点独立集
看见棋盘直接黑白染色，发现马只会跳到属于二分图另一侧的点上给每个点按坐标编号 只连接编号为奇数的点到编号为偶数的点的边 最后点数（n*n-m）减去最大匹配数 就是最大点独立集的点数如图 每个奇数位置的点可以贡献8条有向边 所以总边数应该是点数*8/2 并不会炸 暴力连边建图即可#include#include#include#includeusing
2020-04-18 11:46:56
142
原创 计蒜客习题-俄罗斯套娃 最小路径覆盖
套娃和矩形嵌套一样是典型的DAG把嵌套关系用有向边表示可以得到一个DAG可以把DAG上的点i拆成两个点 i 和 i' 分别放在两个集合中 如果原图i-j有边 二分图里就连一条i-j'的边 跑匈牙利求解最小路径覆盖数==DAG的点数n（拆点前）-最大匹配数（拆点后的新图） 即答案//拆点保证不重复#include#include#include#includeusing
2020-04-18 11:46:46
123
原创 BZOJ1433 ZJOI2009假期的宿舍 计蒜课习题-座谈会的椅子分配 二分图
用dinic解决最大匹配 拆点分别表示椅子和人1433: [ZJOI2009]假期的宿舍Time Limit:10 SecMemory Limit:162 MBSubmit:3612Solved:1540[Submit][Status][Discuss]Description学校放假了······有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都...
2020-04-18 11:46:35
202
原创 计蒜客习题 消除字符串
用二进制表示字符串中每个字母的选取状态 然后dpisp(i)函数判断传入的选取方式i对应子序列是否回文点击打开链接#include<bits/stdc++.h>using namespace std;int n;#define maxs (1<<n)const int inf=0x3f3f3f3f;string s;int dp[1<<16];in...
2020-04-18 11:46:24
172
原创 计蒜客习题-蒜头君的积木
状压dp 预处理状态然后枚举子集点击打开链接#include<bits/stdc++.h>using namespace std;//const int maxn=17;const int m=(1<<16)+1;int n,W;int cnt=0,dp[m],s[17],w[17];inline int count(int x){//计算该状态下的w ...
2020-04-18 11:46:11
198
原创 NOI2001 炮兵阵地 计蒜客习题 灌溉机器人
状压dp入门题 昨天调好久了结果zz把判断行内相交的函数写错没调出来 位运算优先级搞错了）点击打开链接#include<iostream>#include<cstdio>#include<cctype>#include<cmath>//状态：dp[i][j][k]表示当前在第i行 i行状态编号为j i-1行状态编号为k的最大格子数//答案...
2020-04-18 11:45:58
146
原创 BZOJ1562 计蒜客习题-距离序列 洛谷P1963 NOI2009 变换序列
Sample Input 51 1 2 2 1Sample Output 1 2 4 0 3HINT 30%的数据中N≤50； 60%的数据中N≤500； 100%的数据中N≤10000。如果原序列中的x位置的数可以放在新序列的y位置上 就连一条x到y的边 跑一遍二分图 如果hungary()==n 则有解 由于要字典序最小 要反着跑匈牙利算法 因为匈牙利算法会让之后拓展到的结点挤掉之
2020-04-17 17:21:28
174
原创 计蒜客习题-道路阻拦 求最小割的边数
UPD：原来是因为参数传递是用栈控制的 按照如下方式传参会变成addedge(d,c,v,u)addedge(d,c,v,u)addedge(d,c,v,u) 就……可以防hack？快读玄学错误浪费我一个晚上+早上 发现如果不直接在addedge()函数里用read做参数 比如addedge(read(),read(),read(),read())addedge(read(),read(...
2020-04-17 17:21:17
137
1
原创 计蒜客习题-班长竞选 最小割 “二选一 方案不同有额外开销”模型
设源点S，汇点T对于所有赞成的人 从S连一条边到他们对应的点上 容量设为1对于所有反对的人 从他们对应的点上连一条边到T 容量为1对于所有有朋友 关系的a和b 在他们之间连一条无向边 容量为1 最小割可以用dinic跑出来 即所求答案 只要记好朋友之间的冲突总数就好了#include<iostream>#include<cstdio>#in...
2020-04-17 17:21:05
180
原创 计蒜客习题-最优标号 最小割 按位拆点
胡伯涛：最小割模型在信息学竞赛中的应用 福一学长太神了%%% 这篇论文里有提到spoj839的做法 就是计蒜客这题的原题 观察异或的性质 如果要让异或和最小 就要让每一个二进制位上的冲突最小 就像之前班长竞选那题一样 转成最小割模型求解 之前的想法是把每一个点拆成31个点 当处理第j个二进制位的时候 点i的第j位拆出来的点编号为i+n*j 但是这种做法空间开销太大 不好处理 发现可以对每...
2020-04-17 17:20:53
175
原创 计蒜客习题-蒜头君的蜡笔
一开始has_no_edge函数里用vector 爆炸了 第四个点被卡 换成手写栈 第五个点还是被卡 调调调 讨了一份代码发现自己没离线做） 这个故事告诉我们要先预处理 要模2322322^{32} 直接让int自然溢出即可#include<bits/stdc++.h>using namespace std;const int maxn=20;#define ll l...
2020-04-17 17:20:42
197
原创 计蒜客习题-蒜头君的多项式
会炸int 要求多项式(px+qy)k(px+qy)k(px+qy)^k的 xaybxaybx^{a}y^{b}这一项的系数，需要忽略x,yx,yx,y 直接令它们为1即可 这样我们得到了一个新的多项式(p+q)k(p+q)k(p+q)^k题目所求的xaybxaybx^{a}y^{b}这一项的系数 等价于求新多项式的第b+1b+1b+1项的值 根据牛顿二项式定理 (x+y)n=∑&n...
2020-04-17 17:20:29
239
原创 计蒜客习题-蒜头君的建设方案
直接dfs算size#include#include#include#include#includeusing namespace std;const int maxn=1000007;struct edge{ int v,nxt,w;}e[maxn<<1];int p[maxn],eid=0,size[maxn],n;/*其实只要求出num_a(i) 就能算另一
2020-04-17 17:20:16
146
原创 NOI2006 最大获利 最大权合闭图 计蒜客习题-课程开发计划
UPD：点开计蒜客的第二题 这™不是这题原题？？ctrl+c ctrl+v AC我还能说啥——————————————————————胡伯涛《最小割模型在信息学竞赛中的应用》这篇论文超神了以下是一般的O(Maxflow(n+m,n+m))解法把用户群视为正权点 权值为收益 和S连 容量为点权中转站设为负权点 权值为开销 和T连 容量为点权的相反数原图的无向边容量设为inf然后求出最小割和所选用户...
2020-04-17 17:19:11
80
原创 计蒜客习题-最优订单方案 最大权闭合图
UPD:其实不需要getans函数 直接把所有正权点的点权加起来就是ans了_______________________________________________________________和NOI2006 最大获利相似的做法 但是这题要多dfs一遍求出选点的方案从S出发dfs 如果e[i].c>0 就沿着这条链往下走 经过的点就是所选的点算答案的时候是e[i^1].c>0...
2020-04-17 17:18:36
108
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人