A fresh start.

当时比赛的时候没做出来这题,做了 洛谷3586 才知道这题的做法。题意有 $N(\le 3\times 10^5)$ 张卡,卡上有数字 $A_i(\le n)$ 。$\forall k$ ,问:每次取 $k$ 张数字互不相同的卡,能取多少次。题解记录每个数字出现的次数为 $s_i$ ,问题就转化为:每次选 $k$ 个正数 $-1$ ,最多操作多少次。然后就可以直接用 洛谷3586 的结论了(...
题意给出一个长度为 $n(\le 10^6)$ 的全 $0$ 序列,要求支持以下操作:单点修改给出 $(c,s)$ ,每次取 $c$ 个正数 $-1$ ,问能否操作 $s$ 次。题解先考虑操作 $2$ 。设 $\geq s$ 的数有 $x$ 个,这些数每次都可以取,此外还需要 $(c-x)$ 个数。设 $< s$ 的数的和为 $sum$ ,如果 $sum < (c-s)\time...
题解 数据结构-树状数组
省选/NOI-
题意有 $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
Day -inf[数据删除]Day 0上午和wzx打前一天晚上的CF,结果我B题就不会(我看标签里有个 combinatorics 就不停的推排列组合式子,结果就一傻逼题),rp++;然后3min猜到C题结论5min切了,rp--。后来又因为初始化问题调了1h的D,rp++。下午被徐妈逼迫复习初赛,到头来还不是没考。我就装模做样的看了一下,还发现个资料上的锅,剩下的时间全在颓废。晚上回去参加...
游记
题意给出黑点白点各 $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
标签
其它-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