信息学国家集训队作业1070rep

1、环城汽车赛的解题【问题描述】一个有向环有 n（不超过 100000）个点。每条弧和每个点上都值。你要找出这样的点：以这个点为起点沿该环“走”一圈，初始计数为 0，每到达一个点就得到相应的权值，每经过一条弧就扣去相应的权值，给定的权值保证满足到达终点的时候计数依然为 0，即点权和等于边权和，要保证任何时刻的计数都不小于 0。【分析与算法】首先，先来分析一下样例。发现从点 112（即权值为 1 的点）和点 3（即权值为 5 的点）无法完成任务，因为从它们出发根本就到不了下一个点！。而从点 2 和点 4 出发就可以完成，因为当它们到达点 1或点 3 时有 1 点的“储备”，所以就不会被扣成负数了。6

2、7362这给一个启示，就是点权和边权都不是最重要的，所关心的并不是它们而是它们的差。它们的差反5映了移动到下一个点所导致的计数值的变化。第 i 个点的点权减去它连接到下一个点的弧上的权值，所得的差为 Di。设容易发现，第一个点满足条件当且仅当同时满足 D10，D1+D20，D1+D2+D30，D1+D2+Dn=00。同理，容易得出，第二个点满足条件当且仅当同时满足 D20，D2+D30，D2+D3+D40，D2+D3+Dn+D10。那么，这两个条件之间把第二个点的条件两端都加上关系呢？D1，就会得到 D1+D2D1，D1+D2+D3D1，D1+D2+D3+D4D1，D1+D2+D3+Dn+D1

3、= D1D1。发现不等式左端又变成了 D1，D1+D2，D1+D2+D3，D1+D2+Dn。因此，使用。在判断第一个点时计算出来的不等式左边的值可以保留到以后但是，由于仍然要判断 N2 个等式是否成立，算法的时间复杂度仍然是O(n2)，那么，如何利用这个特性来降低算法的时间复杂度呢？由于每一个不等式组中所有的不等式的右边都是相等的，设某个不等式组中所有不等式的右边值为 q，立刻min(D1,D1+D2,D1+D2+D3,D1+D2+Dn)q。由于 min(D1,D1+D2,D1+D2+D3,D1+D2+Dn)是固定的，不等式组立刻被简化为不等式。最后一步，又发现这些简化以后得到的不等式的右边同

4、样可以被写成D1+D2+Dk，1kn 的形式。最后，1、2、3、得到一个异常简单的算法：求出 D。令 S0=0，Si=Si-1+Di，求出 S，并求出 S 的最小值。求出 S 中有多少个数等于最小值。每个等于最小值的数就对应了一个符合条件的节点。【小结】这道题目难度并不大，但是题目的数学味道比较浓，解法也比较简洁而巧妙。对于这类题目，可以通过去掉冗余信息简化题目，利用已经求出的值来减少计算量，最终找到一个令人满意的算法。【附原题】（来源：TongJi Online Judge 1070）环城汽车赛XYZ 城要举行一场汽车赛，因为 XYZ 城的巿长是个怪人，所以这次汽车赛有特殊的规则。在这次比赛

5、的环形赛道上设有 N 个汽车。选手可以选择任意一个作为起点。比赛开始时每辆汽车油箱里都没有油。在到达第 i 个时了，汽车可以有那加 Oi 升的油。(设一升油可以开一 km，并和速度无关)。所以的油加起来正好可以开完全程。最快开完全程(逆时针)的选手将获得第一名。当然，所有的选手都想夺冠，所以他们都想先知道从哪些开始可以跑完全程。这个任务就交给你了！Input第一行为一整数 T，表示有 T 组测试数据。每组测试数据二行。每组测试数据的第一行是一个数字 N(4=N100000)第二行是用空格分开的 2N 个整数，第一个数是第一个可以提供的油 O1升，第二个数是第一站到第二站距离 D1km(N 个站是逆时针排列的)，最后一个是第 N 站个第一站的距离 DNkm。(Oi,Di=100000)Output对于每一组测试数据你输出一行两个数第一个数是一共有多少站可以那开始完成全程，第二个数是最小的可以完成全程的的(如果第一个数是