分类:OI

45 篇文章

暴力数据结构 : 珂朵莉树 (ODT)
前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构,因那道题题面(CF896C)关于珂朵莉而得名。 珂朵莉树适用于以下的情况:维护一个序列,有区间赋值操作,数据随机。下面是珂朵莉树板子题: 维护一个序列,需要支持以下操作1. 将 $[l,r]$ 区间所有数加上 $x$2. …
[NOI Online 3 提高组] 魔法值 题解
前言 好题,考的时候用循环节做法水了部分分。看上去是图论实际上是矩阵乘(yi)法(huo)。 题面 H 国的交通由 $n$ 座城市与 $m$ 条道路构成,城市与道路都从 $1$ 开始编号,其中 $1$ 号城市是 H 国的首都。H 国中一条道路将把两个不同城市直接相连,且…
BZOJ #4070 [Apio2015]雅加达的摩天楼
Description 印尼首都雅加达市有 $N$ 座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 $0$ 到 $N−1$。除了这 $N$ 座摩天楼外,雅加达市没有其他摩天楼。 有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 $0$ 到 $M−1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$…
BZOJ #2700 聚会 & #4269 再见 Xor & #4247 挂饰 & #4576 [Usaco2016 Open]262144 & #2460 [BeiJing2011]元素 & #3039 玉蟾宫 & #4543 [POI2014]Hotel 加强版 & #2396 神奇的矩阵 & #1213 [HNOI2004]高精度开根
#2700 聚会 Description Alice 正在组织一次有 $M$ 位同学参加的同学聚会。Alice 有 $N$ 种不同的茶,每种茶有各自的单价和类别(红茶或绿茶)。每隔一单位时间,聚会上都有一个同学离开。Alice 希望安排一种泡茶的方案,每单位时间都给所有剩下的同学们泡同一种之前没有泡过的茶,花费就是此茶的单价乘以剩余的同学数。同时,…
BZOJ #1999 [Noip2007]Core 树网的核 & #2936 [Poi1999]降 水 & #1907 树的路径覆盖 & #1270 [BeijingWc2008]雷涛的小猫
BZOJ #1999 [Noip2007]Core 树网的核 Description 设 $T=(V, E, W)$ 是一个无圈且连通的无向图(也称为无根树),每条边带有正整数的权,我们称 $T$ 为树网(treenetwork),其中 $V, E$ 分别表示结点与边的集合,$W$ 表示各边长度的集合,并设 $T$  有 $n$ 个结点。 路径:树…
[ZJOI2010]网络扩容
题面 给定一张有向图,每条边都有一个容量 $C$ 和一个扩容费用 $W$。这里扩容费用是指将容量扩大 $1$ 所需的费用。 求: 1、 在不扩容的情况下,$1$ 到 $N$ 的最大流; 2、 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。 题目链接 思路 第一问是一个裸的最大流。 对于第二问,考虑在每条边旁边加一条边,对于边 $…
[SDOI2009]晨跑
题目描述 题目大意:给出一张点数为 $n$,边数为 $m$ 的有向图,除了点 $1$ 和点 $n$ 外每个点和每条边只能走一次,求从点 $1$ 到点 $n$ 的最小费用最大流。 题目链接 思路 这道题主要是题面难理解。 由于一个点只能经过一次,我们一个点拆分为两个点,中间连一条流量为 $1$,费用为 $0$ 的边。 注意点 $1$ 和 点 $n$ …
网络流 24 题 – 分配问题
题面 题目传送 题目描述 有 $ n $ 件工作要分配给 $ n $ 个人做。第 $ i $ 个人做第 $ j $ 件工作产生的效益为 $ c_{ij} $。试设计一个将 $ n $ 件工作分配给 $ n $ 个人做的分配方案,使产生的总效益最大。 输入格式 第 $ 1 $ 行有 $ 1 $ 个正整数 $ n $,表示有 $ n $ 件工作要分配给…
网络流 24 题 – 负载平衡问题
题面 题目传送 题目描述 $G$ 公司有 $n$ 个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使 $n$ 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。 输入格式 第 $1$ 行中有 $1$个正整数 $n$,表示有 $n$ 个仓库。 第 $2$ 行中有 $n$ 个正整数,表示 $n$ 个仓库的库存量。…
P2774 方格取数问题
题面 洛谷 P2774 题目描述 在一个有 $m*n$ 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 $2$ 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。 输入格式 第 1 行有 2 个正整数 $m$ 和 $n$,分别表示棋盘的行数和列数。接下…