分类:题解

题意有 $n(\le 1000)$ 个人,每个人有分数 $s[i]$ 。有 $S$ 组限制 $(A,B)$ ,要求 $s[A] > s[B]\times k$ 或 $s[A] > s[B]\times \frac{1}{k}$ ,如果不满足则 $A$ 需要女装。已知 $t$ 个人的初始分数。求最大的 $T$ ,使得限制变为 $s[A] > s[B]\times (k-T)$...
题解 图论-最短/最长路 图论-负环 图论-差分约束
省选/NOI-
题意略(太复杂了不想写)题解令 $f[i]$ 为不大于 $x$ 的最大斐波那契数,那么 $x$ 的父亲节点就是 $x-f[i]$ 。斐波那契数列的第 $58$ 项刚好小于 $10^{12}$ ,所以预处理前 $58$ 个就行了。求两个节点的 $\text{LCA}$ 可以用一种类似树剖的方法,不断地取 $u$ 和 $v$ 中的较大值跳到父节点,直到 $u$ 和 $v$ 相等。层数最多只有 $...
题解 图论-LCA
普及+/提高
题意给出一个 $n(\le 2\times 10^5)$ 点的树。从 $C$ 出发,先到 $A$ 和 $B$ 中较近的点,然后到另一个点。求可能的路径最大值。题解$A\rightarrow B$ 这段路径是肯定要走的,然后还有一段 $\max_c (\min (AC,BC))$ 。显然 $AB$ 是直径,然后从 $A,B$ 出发分别 $\text{dfs}$ 一次求出距离即可。#includ...
题解 图论-树的直径
提高+/省选-
题意给出一棵 $n(\le 10^5)$ 个点的树,要求选连续的 $k$ 个点,使得其它城市到这些点距离的最大值最小。题解可以发现树的中心一定要选,然后中心的周围再选 $k-1$ 个点。先求出直径,然后找到中心。再以中心为根,找到所有节点到叶节点的距离 $res[i]$ 并从大到小排序,然后选前 $k$ 个节点即可。可以证明这些节点一定是连续的。#include<bits/stdc++...
题解 图论-树的直径
普及+/提高
双倍经验:洛谷2195 HXY造公园题意给出一个有 $n(\le 3\times 10^5)$ 个点 $m(\le 3\times 10^5)$ 条边的森林。要求支持两种操作:求 $x$ 所在树的直径将 $x,y$ 所在的树合并,要求合并后树的直径最小题解合并可以用并查集来实现,用 $ans[x]$ 表示 $x$ 子树中的直径长度。对于操作 $1$ ,直接输出 $ans[x]$ 。对于操作 ...
题解 数据结构-并查集 图论-树的直径
省选/NOI-
题意对于一棵二叉树,如果它所有节点的左右子树交换后和原树一样,那么称它为对称二叉树。给出一棵 $n(\le 10^6)$ 个节点的二叉树,求它所有对称子树中节点个数的最大值。题解可以发现,如果一个节点 $x$ 的左子树的 左->中->右 遍历和右子树的 右->中->左 遍历相同,那么以 $x$ 为根的子树就是棵对称二叉树。所以对于一个点,维护以它为根的子树的两种遍历方...
题解 算法-哈希
普及+/提高
题意略题解$\because a,b\geq 0 \ , \ \therefore y\geq x$ ,不妨设 $y=x+k(k\geq 0)$ ,原式化为:$$k^2+2kx=ax+b\tag{1}$$当 $a=2k,b=k^2$ ,即 $a^2=4b$ 时有无数组解,输出 inf 。否则 $(1)$ 式可以化为:$$(a-2k)x=k^2-b$$$$x=\dfrac{k^2-b}{a-2...
题解 数学
尚无评定
在与机房大佬们的合作下,rk89,rating+=140。题解代码中省略的程序头:#include<bits/stdc++.h> #define fi first #define se second #define ll long long #define mp make_pair #define ha 1000000007 #define ui unsigned int #de...
题解 比赛-Codeforces
题意给出黑点白点各 $n(\le 100)$ 个,要求一个黑点连接一个白点,并且所有线段都不相交。题解所有线段不相交 $\rightarrow$ 两两连最近的点 。那么把距离变成负数就是KM算法裸题了,但这道题有个神奇的坑点:如果在 find() 里更新顶标的偏移值 d ,就会T;而改在外面更新就A了。我也不知道为什么,看来以后得改下KM算法的写法了。#include<bits/std...
题解 算法-KM算法
省选/NOI-
Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ,求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数,那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序,这样...
题解 动态规划 算法-差分
NOI/NOI+/CTSC
A.Keanu Reeves题意题解显然答案最多为 $2$ 。如果本来就不一样多,答案就是 $1$ ;否则把第一个数划出去即可,答案为 $2$ 。#include<bits/stdc++.h> using namespace std; inline int read() { char ch=getchar(); int f=1,x=0; while (ch&l...
题解 比赛-Codeforces
赛前,ljq:不得了,6个人开黑,上紫稳了啊。10+min过去,大家都A了2道,ljq:这场怕不是要AK。最后辣鸡C题,毁我青春。不过还是得怪做题策略有问题,如果直接跳过C去做DE应该都能A掉,这次就算是用rating买教训了。A.Pens and Pencils过水已略B.Rooms and Staircases题意我相信过不了多久洛谷上就会有翻译了题解可以发现答案一定是从某一端出发,到达...
题解 比赛-Codeforces
题意有 $n(\le 50)$ 个人用 $m(\le 50)$ 张卡牌玩游戏。第一局由玩家 $1$ 坐庄抽卡,如果卡上的数字是 $x$ ,那么从他的位置数第 $x$ 的人就被处决。第二局就由被处决的人的后一个人坐庄,以此类推,最后剩下的玩家获得胜利。求每个玩家的胜率。题解概率DP,用 $f[i][j]$ 表示还剩 $i$ 个人,从坐庄的人往后数第 $j$ 个人的胜率。如果只剩 $1$ 个人,...
题解 动态规划
提高+/省选-
题意要求构造一个长度为 $n(\le 10^{15})$ 的 $0/1$ 环形序列,满足任意连续 $m(2\le m \le 5)$ 个数的和不超过 $k$ 。求方案数。题解$m$ 比较小,可以状压。可以发现答案其实就是把一个状态往后推 $n$ 次,最后回到自己的方案数。两个状态之间的转移关系 $s[i][j]$ 可以提前预处理出来,然后把 $s$ 看成一个矩阵,合法状态 $i$ 对答案的贡...
题解 算法-搜索 算法-状态压缩 数学-快速幂 数学-矩阵
省选/NOI-
题意一棵 $n(\le 50000)$ 个点的树,有 $m(\le 50000)$ 支军队驻守在一些节点。要求根节点到每个叶子节点之间的路径上都有军队驻守,军队可以同时移动,每小时移动 $1$ 单位长度。问至少要多久才能满足条件,无解输出 -1(没有)。题解答案显然满足单调性,所以可以二分答案 $mid$ 。接下来只需要判断在 $mid$ 时间内能否满足条件。(1)如果军队 $i$ 在根节点...
题解 算法-二分/三分 算法-贪心 算法-倍增
省选/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