分类:题解

题意求 $N$ 点无向图的最小生成树,满足 $1$ 号节点度数 $\le s$ 。$N\le 30$ 。题解思想考虑构造一个以 $1$ 号节点为根的树,则 $1$ 号节点必须与子树中所有连通块相连。记录去掉 $1$ 号节点后的连通块个数,即 $1$ 号节点的最小度数,为 $tcnt$ 。(题目保证有解即 $tcnt\le s$)对每个连通块分别求出最小生成树,这样就得到了除 $1$ 号节点外...
题解 图论-最小生成树
省选/NOI-
题意$n\times n$ 的格点中站了 $n$ 个人,要让他们站在一排,求最少的移动次数。$n\le 100000$ 。题解选择第几排显然是取所有人 $y$ 坐标的中位数最优。移动到相应位置显然,按照 $x$ 的坐标顺序安排这一排内的顺序是最优的,所以先对 $x_i$ 进行第一次排序。但这样还是需要移动到不同位置,于是处理 $x_i-i$ ,这样就相当于移动到同一位置了,取中位数即可。代码...
题解 算法-排序
题意给出两组点,求两组点间的最近点对。每个组中点数 $N\le 1000$ ,坐标 $x,y\le 10^9$ 。题解按 $x$ 坐标分治,并且对分别属于左右块的点对单独处理。注意数组需要开两倍。#include<bits/stdc++.h> #define ll long long using namespace std; inline ll read() { c...
题解 算法-分治
题意在 $[0,m]$ 中选一个数,使得它经过给定的 $n$ 个 &、|、^ 操作后得到的数最大。$2\le m\le 10^{9} \ , \ 2\le n\le 10^{5}$ 。题解所有数都 $\le 2^{30}$ ,而且修改都只涉及二进制的修改,所以对每一位进行贪心。用 $s_0$ 代表最初全为 $0$ 的数在操作后每一位的值;用 $s_1$ 代表最初全为 $1$ 的数在操...
题解 算法-贪心
提高+/省选-
题意给出 $n$ 个数,求逆序对个数。其中 $n\le 500000$ ,每个数 $\le 999,999,999$ 。题解数的范围很大,所以直接用树状数组肯定不行。但事实上我们只关心数之间的顺序,所以排序后用 $\text{ord[]}$ 记录顺序即可。#include<bits/stdc++.h> #define ll long long using namespace s...
题解 问题-逆序对 数据结构-树状数组
提高+/省选-
题意从 $m$ 部电影中选出 $1$ 部给 $n$ 个人看。每部电影的配音和字幕都使用的不同的语言,每个人只掌握一种语言,用 $1\le id\le 10^{9}$ 的数表示不同语言。对于选出来的电影,如果某人能听懂配音,他会非常高兴;如果能看懂字幕,他会比较高兴。问:选择哪部电影,使得非常高兴的人最多;如果一样多,应使比较高兴的人最多。$n,m\le 200000$ 。题解显然可以对每部电...
题解 算法-排序
普及+/提高
题意给出一个 $5\times 5$ 的 $0/1$ 矩阵,每次点击某一个点会改变自身及上下左右的状态。求把矩阵全部变为 $1$ 的最少步数。多组数据,组数 $N\le 500$ 。题解考虑逐行递推,如果上一行 $(i,j)$ 是 $0$ ,那么就需要点击当前行的 $(i+1,j)$ 。最后校验最后一行是否全为 $1$ 即可。但第 $1$ 行没有上一行,所以我们需要枚举第 $0$ 行的状态,...
题解 算法-状态压缩
题意定义图的连通数是每个点可以到达的点数之和,求一个有向图的联通数。其中点数 $N\le 2000$ 。题解显然直接用 $\text{Floyd}$ 传递闭包是不现实的,于是我直接照题解用了bitset。用 bitset $\text{s[i]}$ 表示 $i$ 与 $N$ 个点的连通情况。直接双重循环枚举用 | 合并起来即可。需要注意自己和自己也要算,但给出的矩阵是不算的,所以需要写在后面...
题解
省选/NOI-
题意给出一个无向图,有下列操作:$(1,a,b)$ ,查询 $a\rightarrow b$ 路径上桥的数量$(0,a,b)$ ,删除边 $(a,b)$ 。保证无论航线如何被破坏,任意时刻任意两点都能够相互到达。其中点数 $N\le 30000$ ,边数 $M\le 100000$ ,操作数 $Q\le 40000$ 。题解显然,桥的数量就是缩完点后两点间的树上距离,动态询问树上距离显然就是...
题解 数据结构-树链剖分 图论-桥
省选/NOI-
题意给出一个有向图,有边权 $w_i$ 和点权 $s_i$ 。要求找一个环,使 $\dfrac{\sum s_i}{\sum w_i}$ 最大。其中点数 $N\le 1000$ ,边数 $M\le 5000$ 。题解$0/1$ 分数规划。设当前二分值为 $mid$ ,题目即为$$\dfrac{\sum s_i}{\sum w_i} > mid$$$$\sum (s_i-mid\time...
题解 图论-负环
提高+/省选-
题意令 $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-
标签
其它-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