在前期市场调查和站址勘测之后,公司得到了一共 个可以作为通讯信号中转站的地址,建立第 个通讯中转站需要的成本为 ()。另外公司调查得出了所有期望中的用户群,一共 个。关于第 个用户群的信息概括为 , 和 :这些用户会使用中转站 和中转站 进行通讯,公司可以获益 。(,,)公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?
「SCOI2007」修车 - 费用流
同一时刻有 位车主带着他们的爱车来到了汽车维修中心。维修中心共有 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。
顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
「SCOI2010」游戏 - 二分图匹配
在游戏里,他拥有很多的装备,每种装备都有两个属性,这些属性的值用 之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。终极 BOSS 很奇怪,攻击他的装备所使用的属性值必须从 开始连续递增地攻击,才能对 BOSS 产生伤害。也就是说一开始的时候,只能使用某个属性值为 的装备攻击 BOSS,然后只能使用某个属性值为 的装备攻击 BOSS,然后只能使用某个属性值为 的装备攻击 BOSS …… 以此类推。他最多能连续攻击 BOSS 多少次?
OS X 与虚拟机中 Linux 无缝整合
OS X 中有很多与 GNU/Linux 相似的地方,但也有很大的差异,很多时候 GNU/Linux 系统比 OS X 好用一些,而 OS X 的图形界面比 GNU/Linux 不知要高到哪里去了 …… 二者兼得的方法,就是使用虚拟机。
下面以最好用的虚拟机软件 VirtualBox
为例,演示配置 Archlinux 虚拟机与 OS X 主机无缝整合的步骤。
「NOI2003」文本编辑器 - Splay
操作名称 | 输入文件中的格式 | 功能 |
---|---|---|
Move k |
将光标移动到第 个字符之后,如果 ,将光标移到文本第一个字符之前 | |
Insert n S |
在光标后插入长度为 的字符串 ,光标位置不变, | |
Delete n |
删除光标后的 个字符,光标位置不变, | |
Get n |
输出光标后的 个字符,光标位置不变, | |
Prev |
光标前移一个字符 | |
Next |
光标后移一个字符 |
「SCOI2011」糖果 - 强连通分量 + 拓扑排序
幼儿园里有 个小朋友,老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。在分配糖果的时候,需要满足小朋友们的 个要求。幼儿园的糖果总是有限的,想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
「HAOI2006」受欢迎的牛 - 强连通分量
每一头牛的愿望就是变成一头最受欢迎的牛。现在有 头牛,给你 对整数 ,表示牛 认为牛 受欢迎。这种关系是具有传递性的,如果 认为 受欢迎, 认为 受欢迎,那么牛 也认为牛 受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
「CodeVS 2822」爱在心中 - 强连通分量
在爱的国度里有 N 个人,在他们的心中都有着一个爱的名单,上面记载着他所爱的人(不会出现自爱的情况)。爱是具有传递性的,即如果 A 爱 B,B 爱 C,则 A 也爱 C。
如果有这样一部分人,他们彼此都相爱,则他们就超越了一切的限制,用集体的爱化身成为一个爱心天使。现在,我们想知道在这个爱的国度里会出现多少爱心天使。而且,如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的,否则输出 -1。
Tarjan 强连通分量学习笔记
在一个有向图中,如果某两点间都有互相到达的路径,那么称中两个点强连通,如果任意两点都强连通,那么称这个图为强连通图;一个有向图的极大强连通子图称为强连通分量。
Tarjan 算法可以在 的时间内求出一个图的所有强连通分量。