LuoguP4593 [TJOI2018]教科书般的亵渎
Description 题目链接 小豆喜欢玩游戏,现在他在玩一个游戏遇到这样的场面,每个怪的血量为 $a_i$,且每个怪物血量均不相同,小豆手里有无限张“亵渎”。亵渎的效果是对所有的怪造成 $1$ 点伤害,如果有怪死亡,则再次施放该法术。我们认为血量为 $0$ 怪物死亡。 小豆使用一张 “亵渎”会获得一定的分数,分数计算如下,在使用一张“亵渎”之后…
bzoj3217 ALOEXT
Description 给定一个序列,有以下 $4$ 种操作: I x y 插入 $y$ 到第 $x$ 个之前。D x 删除第 $x$ 个元素。C x y 修改第 $x$ 个元素为 $y$。F l r 询问区间 $[l,r]$ 的次大值与区间一个数的异或最大值。 强制在线,$1\leq N,M \leq 10^5$。 Solution 这道题显然可…
LuoguP2839 [国家集训队]middle
Description 题目链接 一个长度为 $n$ 的序列 $a$,设其升序排序之后为 $b$,那么序列 $a$ 的中位数定义为 $b_{\lfloor\frac{n}{2}\rfloor}$,其中 $a,b$ 从 $0$ 开始标号,除法取下整。 给你一个长度为 $n$ 的序列 $s$。回答 $Q$ 个这样的询问:$s$ 的左端点在 $[a,b]…
浅谈莫队
简介 莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前,莫队算法已经在 Codeforces 的高手圈里小范围流传,但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时,只分析了普通莫队算法,但是经过 OIer 和 ACMer 的集体智慧改造,莫队有了多种扩展版本。莫队算法可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩…
LuoguP3209 [HNOI2010] 平面图判定
Description 判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要判定的是一类特殊的图是否是平面图,图中存在一个包含所有顶点的环,即存在哈密顿回路。 对于一个无向图 $G=(V,E)$,如果能够做到把它画在同一个平面上,使得 $\forall (a,b)(c,d)$,$a,b,c,d$ 两两不等的情况下,边 $(a,b)$ 和…
LuoguP3007 [USACO11JAN] The Continental Cowngress G
Description 给出 $n$ 个法案,$m$ 头牛的意见, 每头牛会表决两次。每次表决格式为 i Y 表示“支持 $i$ 号法案”或 i N 表示“反对 $i$ 号法案”。最终,每头牛至少要有一个表决被满足。不可能成立的话输出 IMPOSSIBLE,否则输出方案。 $1\leq N \leq 1,000,1\leq M \leq 4,000…
浅谈 Manacher
基本概念 回文子串:字符串中反转后与反转前相同的子串。 最长回文子串:字符串中长度最大的回文子串。 第 $i$ 位回文半径:以字符串第 $i$ 位为中心的回文子串的最大长度的一半。 在处理回文子串的问题时,一般需要求出字符串每一位的回文半径。 为了避免奇偶讨论和边界问题,我们可以在每一位字符两侧添加同一个特殊字符,在字符串的首尾各添加一个不同的特殊…
YbtOJ 维护集合 题解
Description 你需要维护一个可重集,初始集合为空,支持 $4$ 种操作: I k 向集合内插入元素 $k$。A k 将集合内所有元素加上 $k$。S k 将集合内所有元素减去 $k$。F k 查询集合内第 $k$ 大。 你需要进行 $n$ 次操作。 一开始给出一个下界 $Minv$,表示集合内的所有元素都必须大于等于 $Minv$,在任何…
CF724G Xor-matic Number of the Graph 题解
Description 题目链接 给你一个无向图,有 $n$ 个顶点和 $m$ 条边,每条边上都有一个非负权值。 我们称一个三元组 $(u,v,s)$ 是有趣的,当且仅当对于 $u,v\in [1,n]$,有一条从 $u$ 到 $v$ 的路径(可以经过相同的点和边多次),其路径上的权值异或和为 $s$。对于一条路径,如果一条边经过了多次,则计算异或…
浅谈线性基
简述 线性基是竞赛中常用来解决子集异或一类题目的算法。基:在线性代数中,基(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。同样的,线性基是一种特殊的基,它…
UVA1104 芯片难题 Chips Challenge 题解
Description 题目链接 有一个 $N \times N$ 的棋盘,可以在上面放棋子。 有些格子不能放棋子,有些格子必须放棋子,剩下的格子随意。 要求放好棋子之后满足如下两条要求: 第 $i$ 行和第 $i$ 列的棋子数目必须一样多。$(1\leq i \leq N)$第 …
LuoguP2223 [HNOI2001]软件开发 题解
Description 某软件公司正在规划一项n天的软件开发计划,根据开发计划第i天需要ni个软件开发人员,为了提高软件开发人员的效率,公司给软件人员提供了很多的服务,其中一项服务就是要为每个开发人员每天提供一块消毒毛巾,这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种,A种方式的消毒需要a天时间,B种方式的消毒需要b天(b>a),…
LuoguP2605 [ZJOI2010]基站选址 题解
Description 题目链接 有 $N$ 个村庄坐落在一条直线上,第 $i(i>1)$ 个村庄距离第 $1$ 个村庄的距离为 $D_i$。需要在这些村庄中建立不超过 $K$ 个通讯基站,在第 $i$ 个村庄建立基站的费用为 $C_i$。如果在距离第 $i$ 个村庄不超过 $S_i$ 的范围内建立了一个通讯基站,那么村庄就被通讯信号覆盖。如果第 …
密码保护:无题随笔
这篇文章受密码保护,输入密码才能阅读
LuoguP3104 [USACO14MAR]Counting Friends G 题解
Description 题目链接 $n(1\leq n\leq 500)$ 头奶牛都有一个或一个以上的朋友。$FJ$ 记录每头牛的朋友数,但他傻不小心混入了一个错的数字,请找出。 Solution 不得不说O2大法好( 所以我们要多吸氧(bushi 然而为啥我是跑得最慢的呀( 首先我们可以考虑一下暴力怎么打。 直接枚举哪一个点是多余的,然后暴力判断…
LuoguP4893 GodFly的求导工具 题解
Description 题目链接 给定一个 $n$ 次整系数函数 $f(x)$,问 $f(x)$ 的 $k$ 阶导在 $x_i$ 处的导数。 $1\leq n \leq 100,k\leq n,m\leq 10,a_i\leq 10^5,x_i\leq 10^5$ Solution 很好奇这题是怎么评紫的(? 咳咳,对于这道题,你先要有亿点简单高等…
[持续缓慢更新中]计算几何 学习笔记
Part 0 基本部分 const double eps=1e-8;//精度问题 const double PI=acos(-1);//圆周率 I int Cmp(double x){return fabs(x)<eps?0:(x<0?-1:1);}//比较浮点数 I double sqr(double x){return x*x;}/…
POJ1019 Number Sequence 题解
Description 题目链接 给定一串有规律的数:11212312341234512345612345671234567812345678912345678910123456789101112345678910,问从左往右数第 $i$ 个数字是多少? $1\leq i \leq 2147483647$ Solution 直接把这串数字分组:$1…
POJ1850 Code 题解
Description 题目链接 将由小写字母组成的字符串按照以下条件排序: 长度按升序排序相同长度按字典序排序 我们将这些字符串标上序号,问一字符串对应的序号是多少? $1\leq len \leq 10$ Solution 很明显,这题也可以分两类组合起来。 字符串长度为 $[1,len-1]$,这时可以通过组合数公式易知其数量。字符串长度为 …
POJ3252 Round Numbers 题解
Description 题目链接 定义 Round Numbers 为在二进制下,0 的个数大于等于 1 的个数的数。 求范围内 Round Numbers 的个数。 $1 ≤ Start < Finish ≤ 2,000,000,000 $ Solution 显然问题可以转化成求 $[1,N]$ 的 …