Test
2017-10-27 13:47:52    200    0    0    二分 贪心   
H国有n个城市,这n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都,也是树中的根节点。 
H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。 
现在,在H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。 
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
2017-10-27 13:45:00    187    0    0    二分 差分 线段树   

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份订单,每份订单用三个正整数描述,分别为dj,sj,tj,表示某租借者需要从第sj天到第tj天租借教室(包括第sj天和第tj天),每天需要租借dj个教室。 
我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改订单。

2017-10-27 13:34:34    190    0    0    扩展欧几里得   
求关于x的同余方程ax ≡ 1 (mod b)的最小正整数解。
2017-10-27 13:30:24    176    0    0    set 倍增   

小A和小B决定利用假期外出旅行,他们将想去的城市从1到N编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市i 的海拔高度为Hi,城市i 和城市j 之间的距离d[i,j]恰好是这两个城市海拔高度之差的绝对值,即d[i,j] = |Hi - Hj|。

旅行过程中,小A和小B轮流开车,第一天小A开车,之后每天轮换一次。他们计划选择一个城市S作为起点,一直向东行驶,并且最多行驶X公里就结束旅行。小A和小B的驾驶风格不同,小B总是沿着前进方向选择一个最近的城市作为目的地,而小A总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出X公里,他们就会结束旅行。 
在启程之前,小A想知道两个问题: 
1.对于一个给定的X=X0,从哪一个城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值最小(如果小B的行驶路程为0,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小A开车行驶的路程总数与小B行驶的路程总数的比值都最小,则输出海拔最高的那个城市。 
2. 对任意给定的X=Xi 和出发城市Si,小A开车行驶的路程总数以及小B行驶的路程总数。

2017-10-27 13:11:29    190    0    0    tarjan 割点   
n个点m条边的无向连通图,无重边无自环.
求对于所有i,去掉第i个点后有多少对有序点不连通. 
2017-10-25 20:40:09    207    0    0    博弈论   

我我我不会博弈论吧...

2017-10-25 21:02:55    188    0    0    博弈论 枚举 高斯消元法 贪心   

我不打游戏的啊...

2017-10-23 19:06:31    128    0    0    贪心 高精度   

恰逢H国国庆,国王邀请n位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这n位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

2017-07-14 00:22:25    42    0    0    日常 数学   

几道简单代数题.

2017-06-28 21:22:55    244    0    0    学习笔记 递推   

"假装自己还是普及组的年龄"