vol3.htm

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

　　DP，并用斜率优化法优化到O(n)。有关斜率优化法的原理请参看<a href=vol2.htm#1171>1171</a>，在此只对本题进行数学推导。<p>
　　逆推。用T[i]表示第i项工作以后的工作所需的总时间，F[i]表示第i项工作以后的工作的总处理成本因素。设<b>从0时间开始</b>做第i项工作以后的工作所需的总成本为cost[i]，则有状态转移方程：<br>
　　cost[n]=0<br>
　　cost[i]=min{(S+T[i]-T[j])*F[i]+cost[j]}(i&ltj<=n)<br>
　　cost[0]为所求。<p>
　　决策a比决策b优(a>b)的充要条件是：<br>
　　　　(S+T[i]-T[a])*F[i]+cost[a]<(S+T[i]-T[b])*F[i]+cost[b]<br>
　　<=> cost[a]-cost[b]<(T[a]-T[b])*F[i]<br>
　　<=> (cost[a]-cost[b])/(T[a]-T[b])>F[i] (∵T[a]&ltT[b])<p>
　　定义(cost[a]-cost[b])/(T[a]-T[b])为决策a、b间的<b>斜率</b>。维护一个决策队列，使它满足相邻元素间的斜率递增。当阶段为i时，先将决策i+1加入队尾，通过不断删除队列倒数第二个元素来维护它斜率的单调性。然后若队首两元素间的斜率小于F[i]，则说明队首决策现在不是、将来也不会是最优决策，故将其删除。当队首两元素间斜率大于等于F[i]时，队首元素就是当前的最优决策了。
<script>detail 1266,"最小生成树"</script>
　　下文中，把输入的图称作G，选定的生成树称作S，S中的边叫做<b>树边</b>，其余的边叫做<b>非树边</b>。<br>
　　为什么要修改某些边的权值呢？这是因为，把一条非树边Y加入S后，S中会出现一个环，而这个环上的某一条树边X的权值(w[X])可能比Y的权值(w[Y])大。为了使S成为最小生成树，就必须减小X的权值，增大Y的权值，以使w[X]<=W[Y]。如果把w[X]的变化量（当然是减小量）记作d[X]，把w[Y]的变化量（当然是增加量）记作d[Y]，那么我们可以列出不等式：w[X]-d[X]<=w[Y]+d[Y]，即d[X]+d[Y]>=w[X]+w[Y]。<br>
　　对于什么样的边对(X,Y)，需要列这样的不等式呢？这样的边需要满足的条件是：把Y加入S后，X在形成的环上。也就是说，X在S中Y的两个顶点间的路径上。对于任一条非树边Y，为了找出需要与它列不等式的所有树边X，我们需要把S看成一棵有根树，求出Y的两个端点u、v的最近公共祖先a。分别从u和v向上走到a，对路上满足w[X]>w[Y]的边X都列出一个不等式。这一步求最近公共祖先，由于数据规模很小，朴素算法就可以，当然也可以用效率更高的Tarjan算法，详见<a href=vol1.htm#1068>1068</a>题。<br>
　　现在我们得到了一个不等式组，我们需要求出使所有变化量之和最小的一组解。观察这组不等式，发现它们与求<b>二分图最大权匹配</b>（参见<a href=vol2.htm#1148>1148</a>题）时顶标所满足的条件形式完全相同。而求出最大权匹配后，顶标之和确实达到了最小。因此我们建立一个二分图B，把每条树边看成一个X顶点，每条非树边看成一个Y点。如果一个X点与一个Y点之间列了不等式，那么B中它们之间的边权就是不等式的右边，即它们在G中的权值之差；如果没有列，那么B中它们之间的边权为0。如果X点数与Y点数不相等，则补齐，并让它与所有异种点之间的边权全为0。然后用KM算法求出B的最大权匹配，这时匹配边的总权值（也就是所有顶点的顶标和）就是最小代价。同时，我们还求出了一种修改权值的方案：每个点的顶标就是它对应的G中的边的权值的变化量。<br>
　　其实，上面“补齐”的顶点若是X顶点（一般情况下非树边比树边多得多），则它们根本不必考虑，因为它们即使匹配上了，对权和的贡献也只是0。因此，匹配完原有的X顶点就可以停止了。<p>
　　长郡中学的王俊提出了一种更简单的算法。他把求最大权匹配的问题转化为求最大匹配。他的思路是：题目中只要求求出最小代价，并没有要求求出修改方案，因此把边上的权值转移到点上。他建立了一个新的二分图B'，以所有的树边为X顶点，所有边（包括树边与非树边）为Y顶点。X顶点及边均无权值，Y顶点的权值为G中的边权。B'中的边是这样连的：B中每一条权不为0的边在B'中都有对应的边，另外每个代表树边的Y顶点都与代表同一树边的X顶点之间连一条边。这样做以后，B的完备匹配与B'的最大匹配之间就建立了一一对应的关系，且对应的两个匹配的权和之和为原图中所有树边的权值之和：
  <ul><li>如果B的匹配中与某个X顶点相连的边权为0，那么B'中这个X顶点就匹配与自己代表同一树边的Y顶点。B中这条边的权值为0，B'中这条边的权值为这个顶点代表的树边本身的权值，其和为树边本身的权值。
  <li>如果B的匹配中与某个X顶点相连的边权不为0，那么B'中这个X顶点仍匹配B中X匹配的Y顶点。B中这条边的权值为w[X]-w[Y]，B'中这条边的权值为w[Y]，和仍为w[X]，即树边的权值。</ul>
　　因此，B和B'中对应匹配的权和之和为原图中所有树边的权值之和。欲求B的最大权匹配，只需求B'的最小权最大匹配。而G'的权值都在Y顶点上，因此把所有Y顶点按权值递增的顺序排序，依次匹配即可。<br>
　　（注：我的程序用的是王俊的算法，但X顶点和Y顶点被交换了过来。）
<script>detail 1267,"小店购物"</script>
　　首先要突破一个思维定势：同一种商品如果要买多个，其实不必同时购买。这样我们就可以得出一种购买策略：先把需要买的东西各买一件，然后用最低的优惠价购买剩下的商品。后一步显然很简单，所以，题目转化为如何用最少的钱购买每种所需商品各一件。为叙述方便，下文中所说的“商品”都是指需要购买的商品，设这些商品共n种。<br>
　　我们建立一个有向图G，图中有0至n共n+1个顶点。1至n号顶点各代表一种商品。从0向每个顶点引一条边，边权为这种商品的原价。另外，如果商品A可以优惠商品B，就从A到B引一条边，边权为优惠价。理想的情况是每种商品都以最低价购买，因此我们把通往1至n号每个顶点的权最小的边挑出来组成G的子图H。子图H具有这样一个性质：<b>每个顶点的入度均为1。</b>如果H可以进行拓扑排序，那么我们就可以根据这个拓扑序来以最低价购买每种商品了，总费用就是H中所有边的权和。<br>
　　那么现在的问题就是H中有圈怎么办。如果H中有圈，那么圈上的物品是不可能均以最低价购买的，必然有一个最低价要被放弃。那么放弃哪一个呢？我们通过把缩圈来确定。缩圈的方法如下：
  <ul><li>首先把圈上所有边的权值都累加到总费用中。
  <li>然后把起点A在圈外，终点B在圈内的边的权值减少一个值，这个值等于圈内指向B的权值。
  <li>最后把圈缩成一点C。现在C的入度变成了0，为使H的性质依然成立，我们需要找出G中指向C的权最小的边，并把这条边加入H中。</ul>
　　我们决定不以最低优惠价购买的商品，就是新加入的边在缩圈以前指向的顶点所代表的商品，因为这样做增加的总费用（缩圈后新加边的权值）最小。不断缩圈直至H中无圈，问题便得到了解决。
<script>detail 1268,"树的序号"</script>
　　设有n个结点的二叉树共有c[n]棵，则c[n]可以通过公式<img align=absmiddle src=img_vol3/1268_1.gif>计算（i为左子树的结点数）。<br>
　　有了c数组，便很容易求出输入的序号表示的二叉树有几个结点，在有这么多结点的树中它的序号（从0开始）是多少。然后枚举左子树的结点数，又很容易求出它的左右子树各有几个结点，在相同结点数的子树中它们的序号各是多少。递归下去即可求出整个树了。
<script>detail 1269,"亮底牌"</script>
　　只存第一个人的牌可以节省内存（如果这也算技巧的话）。
<script>detail 1270,"杂务"</script>
　　每个杂务的完成时间等于它的所有先行杂务的完成时间的最大值加上它本身需要的时间。答案就是所有杂务完成时间的最大值。
<script>detail 1271,"括号序列"</script>
　　首先运用一点技巧：把输入序列中相邻且配对的括号全都去掉，一直去到不能再去为止。这一步可以减小一般数据的规模。<br>
　　然后进行DP。设f[i,j]为简化后字符串中第i个字符至第j个字符构成的子串需要添加的括号数。
  <ul><li>当i>j时我们规定f[i,j]=0。
  <li>当i=j时显然有f[i,j]=1。
  <li>当i&ltj时，我们可以把这个字符串分为两段分别处理，因此f[i,j]为所有f[i,k]+f[k+1,j]中的最小值，这里i<=k&ltj。另外，如果第i个字符和第j个字符恰好配对，那么可以就让它们配对，即f[i,j]还可以等于f[i+1,j-1]。</ul>
　　按j-i递增的顺序计算f数组，答案就是f[1,l]（l为简化后的字符串的长度）。<br>
　　另外注意：<b>输入中可能有空串，因此程序结尾处的until seekeof一定要改为until eof，否则空串就会被忽略掉。</b><p>
　　P.S.如果谁有O(n<sup>2</sup>)或者更优的算法，请告诉我。
<script>detail 1272,"生产计划"</script>
　　先解释一下题意：工厂每天都有一定的产品需求量，这些产品可以当天生产，也可以调用以前的库存。第n天的产品如果当前生产，那么生产每吨产品的花费就是cost[n]；如果在第m天生产后存储到第n天，那么每吨产品的总花费就是cost[m]+s*(n-m)。<br>
　　算法是很简单的。设第n天每吨产品的最小花费为best[n]，则best[n]=min{cost[i]+s*(n-i)}(1<=i<=n)。显然best的递推式为best[1]=cost[1],best[n]=min{cost[n],best[n-1]+s}(n>1)。
<script>detail 1273,"逆序统计"</script>
　　下面的叙述中省略取模运算。<br>
　　用DP进行预处理。设f[n,k]为有k个逆序对的n个数的排列的数目。当k<0或k>n*(n-1)/2时，规定f[n,k]=0。计算非0的f[n,k]时，考察数n的位置。如果它是最后一个数，那么它与其它数构成了0个逆序对；如果它是倒数第二个数，则它构成了1个逆序对……如果它是第1个数，则它构成了n-1个逆序对。故有<img align=absmiddle src=img_vol3/1273_1.gif>。<br>
　　为计算方便，我们设s[n,k]为f[n,0]至f[n,k]的累加和（k<0时s[n,k]=0），这样状态转移方程便化为s[n,k]=s[n-1,k]-s[n-1,k-n]。我们不必计算f数组而可以直接计算s数组，当提问f[n,k]时，输出s[n,k]-s[n,k-1]。<br>
　　注意到当a+b=n*(n-1)/2时，f[n,a]=f[n,b]。因此，数组的第二维下标的最大值不必设为maxn*(maxn-1)/2，而只需设为此值的一半。这样会节省一半的空间和一定的时间。你可以看一下本题的状态，我是第一个用少于1M的内存解决问题的:)
<script>detail 1274,"二进制问题"</script>
　　设输入的数的二进制表示中最右边的一组连续的1有n个，则把这组1前面的那一个0改成1，这一组1本身改为0，并把整个数的最后n-1位改为1。
<script>detail 1275,"补丁VS错误"</script>
　　用二进制数表示每个错误存在与否的状态，以及每个补丁的使用条件和使用效果，可以用位运算简便地求出每个状态可以使用哪些补丁及使用后的新状态编号。于是问题转化为求一个有向图中某两点间最短路的问题。可采用用堆优化的Dijkstra算法，复杂度为O(nlogn+nm)（n为状态总数，m为补丁数）。
<script>detail 1276,"倒水问题"</script>
　　宽搜求最短路。由于每个任一时刻至少有一个杯子是空的或满的，所以状态可以用一个二元组表示：(0,x)表示第1个杯子空，(1,x)表示第1个杯子满，(2,x)表示第2个杯子空，(3,x)表示第2个杯子满；四种情况的x均表示另一个杯子中的水量。两杯都空的特殊状态用(0,0)或(2,0)表示均可，两杯都满的情况类似。
<script>detail 1277,"独木舟上的旅行"</script>
　　把体重超过独木舟最大载重量一半的人叫做<b>胖子</b>，其余的人叫做<b>瘦子</b>。首先把所有的人按体重排序（当然用桶排，因为人可能很多，而体重的可能值却很少）。按体重递减的顺序处理每一个胖子，如果有瘦子可以跟他同乘一条船，则把他们安排到同一条船上，否则只好让胖子独坐一条船了。当胖子处理完后，剩下的瘦子就可以一对一对地上船了。
<script>detail 1278,"午餐"</script>
　　首先，同一队中的人必须满足一个条件：吃饭越慢的越排在前面。简单证明一下：假设两个人打饭的时间分别为a、b，吃饭的时间分别为c、d，其中c&ltd。假设第一个人排在前面，则第一个人吃完饭的时刻为a+c，第二个人吃完饭的时刻为a+b+d，这两个时刻的较大值为a+b+d（因为c&ltd）。如果把他们的位置对换，则两个时刻分别为b+d和b+a+c。显然这两个都小于a+b+d。因此我们先把所有人按吃饭时间降序排列。<br>
　　然后使用DP算法。用buy[i]和eat[i]分别表示第i个人打饭和吃饭所需时间，sum[i]表示前i个人打饭所需的时间之和。设time[i,j]表示前i个人排队，第一队的总打饭时间为j时，最后一个人吃完饭的最早时刻。如果(i,j)是一种不可能的状态，则time值为无穷大。初始时只有time[0,0]为0，其余皆为无穷大。求time[i,j]时，对第i个人所排的队分情况讨论：
  <ul><li>当j>=buy[i]且time[i-1,j-buy[i]]不等于无穷大时，第i个人可以排第一队。这时最后一个吃完饭的人可能就是第i个人，也可能不是。如果是，则他吃完饭的时刻就是j+eat[i]；如果不是，则其余i-1个人吃完饭的时刻就是time[i-1,j-buy[i]]（很巧妙的）。这两个时刻的较大值就是所有i个人吃完饭的时刻，记作t1（如果第i个人不可以排第一队，则t1为无穷大）。
  <li>当time[i-1,j]不等于无穷大时，第i个人可以排第二队。如果最后一个吃完饭的人就是第i个人，则他吃完饭的时刻就是sum[i]-j+eat[i]，否则其余i-1个人吃完饭的时刻就是time[i-1,j]。这两个时间的较大值就是所有i个人吃完饭的时刻，记作t2（如果第i个人不可以排第二队，则t2为无穷大）。</ul>
　　t1和t2的较小值就是time[i,j]。答案就是所有time[n,j]的最小值，其中j的取值范围为0~sum[n]。
<script>detail 1279,"金字塔"</script>
  <table cellpadding=9><tr>
    <td><img src=img_vol3/1279_1.gif>
    <td><img src=img_vol3/1279_2.gif>
    <td>　　如图，把四面体放到坐标系中，使B点与原点重合，C点落在x轴正半轴上，D点位于xOy平面且y坐标为正，A点z坐标为正。B、C坐标很容易写出。利用两点间距离公式及BD、CD的长度，可以解出D点坐标。再利用两点间距离公式及AB、AC、AD的长度，可以解出A点坐标。四面体的体积就是dnz/6。
  </table>
<script>detail 1280,"九数码问题-版本2"</script>
　　双向广搜，即分别以初始状态和目标状态为根建两棵搜索树，这边搜一层，那边搜一层……。状态编号与<a href=#1258>版本1</a>相同。经试验，双向广搜在最坏的情况下的搜索量也只有4~5万个状态（总状态数有9!=362880个之多），效率很高。
<script>detail 1281,"星际大战"</script>
　　显然，分出的每项应尽量接近，否则，让大数减1，小数加1将使积更大。而且，分出的每个数不可以超过4，因为超过4的数总可以再分成两半，这两半的积比原数大。又显然不可以分出1，故分出的数只能是2,3,4。<br>
　　因为2*2=4，所以2和4的效果是一样的。那么问题就是尽量多分2还是多分3的问题。由于2^3<3^2，所以尽量多分3是正确的选择。如果人数是3的倍数，那么就全分成3人组；如果人数除以3余2，那么就把剩下2人分为一组；如果余1，那么就拿出4人分成一组。