[Codeforces 19D] Points

题目地址

描述

在二维平面上内进行$n (1 \leq n \leq 2 \cdot 10^{5})$次操作,一共有三种种类的操作:

  1. $add$ $x,y$ 将点$(x,y)$加入二维平面坐标系内。
  2. $remove$ $x,y$ 将点$(x,y)$从二维平面坐标系内删除。
  3. $find$ $x,y$ 找到点$(x,y)$右上角的点集$(x_{i} > x, y_{i} > y)$。如果有多个输出$x$最小的,若还是存在多个输出$y$最小的。

每次操作满足$x,y$均为非负数,且操作合法。

자세히 보기

Partager

[CTSC 1999]补丁VS错误

题目地址

描述

题面比较长而且有些晦涩,这里就不贴了。
简要的描述一下:你现在有一个包含$n$种$bug$、$m$个补丁的软件,每一个补丁有五个参数,补丁的运行时间$t$,此补丁能够运行当且仅当补丁所在的软件包含$B_{i}+$中的所有$bug$而不包含$B_{i}-$中的任何$bug$,应用此补丁之后软件将修复$F_{i}-$个$bug$同时产生$F_{i}+$个新$bug$。
每一个补丁可以安装多次,求修复完所有$bug$的最短的时间;如果问题有解,输出总耗时,否则输出$0$。
$1 \leq n \leq 15, 1 \leq m \leq 100$

자세히 보기

Partager

[IOI1999]花店橱窗布置

描述

某花店现有$F$束花,每一束花的品种都不一样,同时至少有同样数量的花瓶,被按顺序摆成一行,花瓶的位置是固定的,从左到右按$1$到$V$顺序编号,$V$是花瓶的数目。花束可以移动,并且每束花用$1$到$F$的整数标识。如$i < j$,则花束$i$必须放在花束$j$左边的花瓶中。例如,假设杜鹃花的标识数为$1$,秋海棠的标识数为$2$,康乃馨的标识数为$3$,所有花束在放入花瓶时必须保持其标识数的顺序,即杜鹃花必须放在秋海棠左边的花瓶中,秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目,则多余的花瓶必须空,即每个花瓶只能放一束花。

자세히 보기

Partager

[IOI 1994]北京2008的挂钟

题目地址

描述

此处输入图片的描述
在$2008$北京奥运会雄伟的主会场的墙上,挂着如上图所示的$3 \times 3$的九个挂钟(一开始指针即时针指向的位置请根据输入数据调整)。然而此次奥运会给与了大家一个机会,去用最少的移动操作改变上面的挂钟的时间全部为$12$点正(我们只考虑时针)。然而每一次操作并不是任意的,我们必须按照下面给出的列表对于挂钟进行改变。每一次操作我们给而且必须给指定的操作挂钟进行,每一个挂钟顺时针转动$90$度。

자세히 보기

Partager

BZOJ 1233 [Usaco2009Open]干草堆tower

题目地址

描述

奶牛们讨厌黑暗。 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有$N$大包的干草$(1 \leq N \leq 100000)$(从$1$到$N$编号)依靠传送带连续的传输进牛棚来。第$i$包干草有一个 宽度$W_{i}(1 \leq w_{i} \leq 10000)$。所有的干草包的厚度和高度都为$1$。

자세히 보기

Partager

BZOJ 1001: [BeiJing2006]狼抓兔子

题目地址

描述

现在小朋友们最喜欢的“喜羊羊与灰太狼”,话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:
不想画图了,盗链QAQ
左上角点为$(1,1)$,右下角点为$(N,M)$(上图中$N=3,M=4$),有以下三种类型的道路:

  • $(x,y) \Leftrightarrow (x+1,y)$
  • $(x,y) \Leftrightarrow (x,y+1)$
  • $(x,y) \Leftrightarrow (x+1,y+1)$

자세히 보기

Partager

「雅礼集训 2017 Day2」C

一如既往没有题目地址0w0

描述

有一棵$n$个结点的树,对于点 $i(i > 1)$,它的父亲结点编号为 $\left \lfloor \frac{i}{2} \right \rfloor$。
现在有 $m$ 只鸟,每只鸟有初始位置 $p_{i}$。树上每个结点有最大容量 $c_{i}$,表示这个结点最多能容纳的鸟的数量。定义移动一只鸟的代价为树上的距离。
现在询问,对于 $k$ 从 $1 \sim m$,将前 $k$ 只鸟移动位置使得满足每个结点上的鸟的个数不大于最大容纳量的最小代价。

자세히 보기

Partager

「雅礼集训 2017 Day2」B

当然还是没有题目地址呀 QAQ
我太弱了,表示这道题目想了很久才想明白题解中的方法呀,真的很巧妙呀!
在 chrt 学姐的帮助下终于明白了,大概这次写的有点多,中间可能有描述不恰当和错误的地方,欢迎捉虫 QAQ

描述

考虑一个 $n \times n$ 的 $01$ 矩阵,计算出所有满足每一行和每一列 $1$ 的个数都是 $2$ 的矩阵个数。
设对于 $n$ 的答案为 $f_{n}$,你需要输出 $\sum_{i = 1}^{n}f_{i}$,答案对 $998244353$ 取模。

자세히 보기

Partager

常系数线性齐次递推关系学习笔记

初中的班主任好像生病了,本来准备和同学一起去看望老师,但是好像去不了QAQ
真的很想见一见初中的同学,好想他们呀

阅读这篇文章你所需要的前置技能大概有:基础的线性代数,以及看懂渣叙述的深厚语文功底 =w=
可能有表述不清或者错误的地方,欢迎指正!

자세히 보기

Partager

BZOJ 1575: [Usaco2009 Jan]气象牛Baric

题目地址

描述

为了研究农场的气候,Betsy帮助农夫John做了$N(1 \leq N \leq 100)$次气压测量并按顺序记录了结果$M_{1} \cdots M_{N}(1 \leq M_{i} \leq 1,000,000)$,Betsy想找出一部分测量结果来总结整天的气压分布,她想用$K(1 \leq K \leq N)$个数$s_{j} (1 \leq s_{1} < s_{2} < \cdots < s_{K} \leq N)$来概括所有测量结果。
她想限制如下的误差: 对于任何测量结果子集,每一个非此子集中的结果都会产生误差,总误差是所有测量结果的误差之和。更明确第说,对于每一个和所有$s_{j}$都不同的$i$:

  • 如果 $i$ 小于 $s_{1}$, 误差是: $2 \times | M_{i} - M_{s_{1}} |$
  • 如果$i$在$s_{j}$和$s_{j+1}$之间,误差是: $| 2 \times M_{i} - Sum(s_{j}, s_{j+1}) |$ $\cdots$ $Sum(x, y) = M_{x} + M_{y}$;$(M_{x} 和 M_{y} 之和)$
  • 如果$i$大于$s_{K}$,误差为: $2 \times | M_{i} - M_{s_{K}} |$

Besty给了最大允许的误差$E (1 \leq E \leq 1,000,000)$,找出最小的一部分结果使得误差最多为$E$。

자세히 보기

Partager