路终会有尽头，但视野总能看到更远的地方。

题目大意

    Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为$n$的一个正整数数组。
    Peter求出了这个数组的所有子段和，并将这$n(n+1)/2$个数降序排序，他想知道前$k$个数是什么。

题目大意

    一张$n$个点$m$条有向边的图上，有$q$个配送需求，需求的描述形式为$(s_i,t_i,l_i,r_i)$,即需要从点$s_i$送到$t_i$，在时刻$l_i$之后（包括$l_i$）可以在$s_i$领取货物，需要在时刻$r_i$之前（包括$r_i$）送达$t_i$，每个任务只需完成一次。
    图上的每一条边均有边权，权值代表通过这条边消耗的时间。在时刻$0$有一个工作人员在点$1$上，求他最多能完成多少个配送任务。
    在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。当然在一个点逗留也是允许的。

题目大意

    游乐园被描述成一张$n$个点，$m$条边的无向图（无重边，无自环）。每个点代表一个娱乐项目，第$i$个娱乐项目需要耗费$c_i$分钟的时间，会让小y和妹子的开心度分别增加$h1_i$,$h2_i$，他们俩初始的开心度都是$0$。每条边代表一条路，第$i$条边连接编号为$x_i$,$y_i$的两个娱乐项目，从$x_i$走到$y_i$或者从$y_i$走到$x_i$耗费的时间都是$t_i$分钟。小y和妹子预计在游乐园里玩$k$分钟。最开始的时候，小y和妹子会等概率的随机选择一个娱乐项目开始玩，每玩完一个项目后，小y和妹子会等概率的随机选择一个可以从当前项目直达的且来得及玩的项目作为下一个项目。如果玩完一个项目后周围没有可以直达的且来得及玩的项目，小y和妹子就会提前结束游玩。请你分别计算小y和妹子在游玩结束后开心度的期望。

题目大意

    有一个树状的城市网络（即$n$个城市由$n-1$条道路连接的连通图），首都为$1$号城市，每个城市售卖价值为$a_i$的珠宝。
    你是一个珠宝商，现在安排有$q$次行程，每次行程为从$u$号城市前往$v$号城市（走最短路径），保证$v$在$u$前往首都的最短路径上。
    在每次行程开始时，你手上有价值为$c$的珠宝（每次行程可能不同），并且每经过一个城市时（包括$u$和$v$），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
    现在你想要对每一次行程，求出会进行多少次购买事件。

题目大意

题目大意

    小C学习了二分图匹配，二分图是一种特殊的图，其中的点可以分到两个集合中，使得相同的集合中的点两两没有连边。
    图的“匹配”是指这个图的一个边集，里面的边两两不存在公共端点。
    匹配的大小是指该匹配有多少条边。
    二分图匹配我们可以通过匈牙利算法得以在O(VE)时间复杂度内解决。
    小C觉得单纯的二分图匹配算法毫无难度，因此提出新的问题：
    现在给你一个$N$个点$N-1$条边的连通图，希望你能够求出这个图的最大匹配以及最大匹配的数量。
    两个匹配不同当且仅当存在一条边在第一个匹配中存在而在第二个匹配中不存在。

题目大意

    给定$n$个数$a_1,a_2,\ldots,a_n$，求这$n$个数两两的差值（共$n*(n-1)/2$个）的中位数。

题目大意

    因为SJY干的奇怪事情过多，SJY收到了休假的通知，于是他准备在都市间来回旅游。SJY有一辆车子，一开始行驶性能为$0$，每过$1$时间行驶性能就会提升$1$点。每个城市的道路都有性能要求。SJY一共有$t$时间休息，一开始他位于$1$号城市（保证$1$号城市道路要求为$0$），他希望在$n$号城市结束旅程。每次穿过一条城市间的路会花费$1$时间，当然他也可以停留在一个城市不动而花费$1$时间。当且仅当车子的行驶性能大于等于一个城市，我们才能到达那里。SJY希望知道，旅游的方案模$10086$后的答案。（只要在某一时刻通过的道路存在一条不相同，就算不同的方案）

题目大意

    下课了，Polo来到球场，但他到了之后才发现…被放了飞机…
    无事可做的他决心找点乐子，比方说……跳台阶……
    球场边有N个台阶拍成一行，第$i$个台阶的高度是$H_i(0\lt H_i\le10^9)$，第$0$个台阶，也就是地面的高度为$0$。Polo打算把这$N$个台阶分成两个集合$S_a,S_b$（可以为空），对于一个台阶集合$S=\lbrace P_1,P_2,…P_{|S|}\rbrace$，其中$P_1\lt P_2\lt\ldots\lt P_{|S|}$，他需要花费$\sum_{i=1}^{|S|}|H_{p_i}-H_{p_{i-1}}|$的体力值来完成。
    现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？

题目大意

    在遥远的S星系中一共有$N$个星球，编号为$1\ldots N$。其中的一些星球决定组成联盟，以方便相互间的交流。
    但是，组成联盟的首要条件就是交通条件。初始时，在这$N$个星球间有$M$条太空隧道。每条太空隧道连接两个星球，使得它们能够相互到达。若两个星球属于同一个联盟，则必须存在一条环形线路经过这两个星球，即两个星球间存在两条没有公共隧道的路径。
    为了壮大联盟的队伍，这些星球将建设$P$条新的太空隧道。这$P$条新隧道将按顺序依次建成。一条新轨道建成后，可能会使一些星球属于同一个联盟。你的任务是计算出，在一条新隧道建设完毕后，判断这条新轨道连接的两个星球是否属于同一个联盟，如果属于同一个联盟就计算出这个联盟中有多少个星球。