2019年6月

题意令 $C_{s,t}$ 表示从 $s$ 到 $t$ 的不同的最短路的数目,$C_{s,t}(v)$ 表示经过 $v$ 从 $s$ 到 $t$ 的最短路的数目;则定义:$$ I(v)=\sum_{s \ne v,t\ne v} \frac{C_{s,t}(v)}{C_{s,t}}$$其中点数 $n\le 100$ ,边数 $m\le 4500$ 。题解$n\le 100$ ,又要统计所有节...
题解 图论-最短/最长路
提高+/省选-
题意给出一个 $N$ 点有向图,从 $1$ 到 $N$ ,要求恰好 $T$ 时刻到达。其中 $N\le 10$ ,边权 $\in[1,9]$ 。边权为 $0$ 代表没有边。题解考虑边权只可能为 $1$ 的情况。用 $f[i][j]$ 代表 $i\rightarrow j$ 恰好 $T$ 时刻到达的方案数,那么$$f_T[i][j]=\sum_{k=1}^{N} f_{T-1}[i][k]\t...
题解 数学-矩阵
省选/NOI-
题意求不包含子串 $A$ 的长度为 $N$ 的数字 $X$ 的个数。答案对 $K$ 取模。其中 $A$ 的长度 $M\le 20$,$N\le 10^9$,$K\le 1000$ 。题解矩阵乘法优化dp。用 $\text{f[i][j]}$ 表示在 $X$ 中做到第 $i$ 位,匹配到 $A$ 中第 $j$ 位的方案个数。最终的答案即为:$$\sum_{i=0}^{M-1} \text{f[...
题解 字符串 数学 数学-矩阵 字符串-kmp
省选/NOI-
题意给出一张无向连通图,求 $S$ 到 $E$ 经过 $N$ 条边的最短路。其中边数 $T\le 100$ ,点的编号 $\le 1000$ ,$N\le 10^6$ 。题解因为是连通图,所以点最多有 $T+1\le 101$ 个。显然 $O(T^3)$ 的 $\text{Floyd}$ 是可以接受的。考虑 $\text{Floyd}$ 的过程:$$\text{dis[i][j]}=\min...
题解 图论-最短/最长路 思维题 数学-矩阵
提高+/省选-
题意在 $R\times C$ 的含障碍的图上把箱子从起点推到终点,人一开始在另一个起点,求人的最短路径。多组数据。$R,C\le 20$题解显然箱子是连续移动的,但人有时需要绕一圈去箱子的背面,所以先对箱子做 $\text{bfs1}$ 。保存一个五元组 $(b_x,b_y,m_x,m_y,now)$ ,表示当前箱子在 $(b_x,b_y)$ ,人在 $(m_x,m_y)$ ,操作序列为 ...
题解 算法-搜索
省选/NOI-
题意给出一个 $n$ 点 $m$ 边的有向图,从 $1$ 出发再回到 $1$ ,途中要逆行一次,问途中最多经过多少个点。$n,m\le 10^{5}$ 。题解显然要缩点,缩点后点权即为连通分量中点的个数 $\text{siz[]}$ 。然后对强连通分量重新建边,正边为 $\text{edge2}$ ,反边为 $\text{edge3}$ 。对正边跑最长路得到以 $1$ 为起点的最长路 $\t...
题解 图论-最短/最长路 图论-Tarjan
省选/NOI-
该合集为乱序版,强度和顺序无关。1ljq:zyt你个龟儿子(几秒后)ljq:我的儿子zyt2wzx:(因当事人墙裂要求删除背景)这凉了啊ljq:没凉,(两秒后),不是很凉,还是有那么一点凉的。3ljq:尔喔(自行脑补发音)4wzx:这是国家发改委指定番目(指《目隐都市的演绎者》)5wzx:ljq中考假期把《方法》和《问题》看完了,而我看完了《目录》(指《路人女主的养成方法》、《我的青春恋爱物...
瞎扯
题意解同余方程组:$$x\times ATK_i\equiv A_i\pmod {P_i}\tag{1}$$$ATK$ 还需要平衡树或者multiset推出来。其中方程个数 $N\le 10^{5}$ ,$A_i\le 10^{12}$ 。题解将原式化简:$$ATK_i\times x+P_i\times y=A_i$$可以用 $\text{exgcd}$ 求出 $x$ 的最小整数解 $S_...
题解 数学 数学-扩展中国剩余定理
省选/NOI-
LOJ最优解达成!题意求满足下列要求的长度为 $2n$ 的序列 $S$ 的个数,对 $p$ 取模:是 $2n$ 的全排列奇数项、偶数项分别递增$\forall i\in [1,n] \ , \ S_{2i-1} < S_{2i}$题解对于性质 $2$ ,可以考虑将 $1...2n$ 的数字按照从小到大的顺序依次放入序列。每个数字可以放在最前的奇数或偶数位。分析性质 $3$ ,显然偶数位...
题解 数学 数学-扩展卢卡斯定理 数学-卡特兰数
省选/NOI-
标签
其它-Firefox1 其它-pbds1 其它-pjax1 其它-Ubuntu1 其它-VSCode1 其它-网易云音乐1 动态规划52 动态规划-区间DP9 动态规划-单调队列优化DP5 动态规划-图上DP1 动态规划-斜率优化DP5 动态规划-树形DP16 动态规划-状压DP16 动态规划-线性DP10 动态规划-背包DP3 图论4 图论-LCA4 图论-Tarjan11 图论-二分图1 图论-割点3 图论-基环树1 图论-差分约束4 图论-强连通分量2 图论-最小环1 图论-最小生成树6 图论-最短/最长路19 图论-树上差分2 图论-树的直径4 图论-桥1 图论-缩点5 图论-负环4 字符串3 字符串-kmp2 思维题3 数学26 数学-bsgs2 数学-exgcd4 数学-gcd2 数学-中国剩余定理2 数学-卡特兰数1 数学-卢卡斯定理4 数学-快速幂4 数学-扩展中国剩余定理1 数学-扩展卢卡斯定理3 数学-矩阵5 数学-约数1 数学-组合数3 数学-质数1 数据结构-动态开点线段树1 数据结构-单调栈1 数据结构-单调队列2 数据结构-可持久化字典树2 数据结构-堆4 数据结构-字典树2 数据结构-并查集2 数据结构-栈1 数据结构-树状数组6 数据结构-树链剖分10 数据结构-线段树5 数据结构-队列1 比赛-Codeforces21 比赛-JX Round1 比赛-NOIp/CSP5 算法-KM算法1 算法-二分/三分12 算法-位运算1 算法-倍增4 算法-分块2 算法-分治3 算法-哈希2 算法-多叉树转二叉树2 算法-差分4 算法-悬线法1 算法-拓扑排序2 算法-排序3 算法-搜索21 算法-模拟5 算法-状态压缩4 算法-贪心10 算法-高精度3 问题-逆序对2 题目-一本通5 题目-网络流24题2