卢俊达

这里是个人技术小站,用于学习与记录,欢迎各位光临。

前言


首先恭喜自己,终于写出了能在POJ上排第一名的代码。其次为自己惋惜下,判重时少了个“j!=x”的条件,找了n久才发现这个小bug,这要是在赛场上,肯定悔死了。首先用spfa做,怎么都找不出错误,甚至以为自己模板写错了,再用dijkstra做,发现依然wa,才觉得不是模板问题。

题目大意


哥伦布要从野人手里买20种货物。用以下四种种方法可以买到货物:

  • 按货物的价格(以金币为单位)付足金币。
  • 对于每个货物,可以用一个玻璃珠代替一个金币。
  • 用等价的其他种类货物交换。
  • 用价格更低的货物加上金币来交换。

问每种物品至少需要花多少金币才能买到。

Read More…

题目大意


教室里有 N*M 个座位,每个座位有一个“舒适值”。上课之前,有K个学生进入教室来占座。每个学生进入教室的时间都不同,且进入教室后会立马占座(忽略占座时间),每个学生都会按下述规则占座。

  • 每个学生会占T个座位,其中一个座位是自己的,其他是朋友的。
  • 学生会优先选择同一行相邻的T个座位占座,并且他会坐在最左边。
  • 如果有多个方案,那么他将选择能使自己“舒适值”最高的方案。
  • 如果没办法帮朋友占座,就只给自己占,并选择“舒适值”最高的座位。

根据所给条件,输出每个人自己占据的座位的坐标。

Read More…

题目大意


小镇有n场婚礼在一天之内矩形,第i场婚礼的开始时间为Si,结束时间为Ti。在每一场婚礼中,有一个重要仪式,即牧师给予两位新人传达主的祝福。对于第i场婚礼,祝福仪式可以在[Si,Ti]中任何时候举行,但是必须超过总时间的一半以上。

小镇只有一位牧师,所有的祝福仪式都必须要他在场。同时,牧师必须在整数时刻开始或者结束祝福仪式,不过他可以在结束一场之后立刻开始另一场。

现在给你所有婚礼的信息,请问是否能够安排好一个祝福仪式的顺序,使得牧师能够给所有新人带去祝福。

Read More…

题目大意:

给出一个元素个数为n的序列num[],元素值两两不同,问序列中满足 num[i]<num[j]<num[k] 或 num[i]>num[j]>num[k] (i<j<k) 的三元子序列的个数是多少。

Read More…

题目大意:

给出两个整数n、m表示屏幕的长宽。屏幕上有一些窗口,每个窗口都是矩形的,窗口的边框用同一个大写字母来表示,不同的窗口的大写字母必定不同。

由于窗口的重叠,有些窗口的有些部分被其他窗口覆盖。但是,肯定有一些窗口在最顶端,不被其他任何窗口覆盖。我们称这些窗口为“顶端窗口”。你的任务就是找出所有的顶端窗口。

Read More…

题目大意:

给出一个图,要求在图中选取一些节点和边构成一个“边权和/点权和”最小的树。

Read More…

题目大意:

给出一个无向图,求解至少删去多少个点,才能使网络不连通。

Read More…

描述:

一个新学期来临了,学生们烦恼与选课。学生们在网络课程系统上面选课。那里有n门课,第i门课准许在时间间隔(Ai,Bi)内选择。那意味着,如果你想选第i门课,你必须在时间Ai之后和Bi之前选择它。Ai和Bi全部用分钟表示。一个学生只能每5分钟选一次课,但是他可以选择在任意时间开始选课,还有可以尝试任意多次。例如,如果你尝试在5分21秒时选课,那么你可以在10分21秒,15分21秒,20分21秒…时继续尝试。一个学生不能在同一时间选择多于一门的课。可能会发生有一个学生在尝试选课时却发现已经无课可选的情况。

请你来计算下一个学生至多能选多少门课。

Read More…