梦.:如此短暂

SGU 193 解题手记
　　求出最大的k，使得(n,k)=1，那么每个人都可以接到球了。于是问题转化为求最大的k，1

#include
……
阅读全文——共625字

SGU190 解题手记
　　先把棋盘像国际象棋那样染成黑白相间，然后把需要挖掉的格子挖掉。将每个格子看作顶点，相邻的格子连一条边，这样就构成一个二分图了。在二分图上做匹配，复杂度O(N^4)，有点悬。
　　Submit 1: AC。事实证明，我的程序还是比较快的，排第13名(2008-2-21)。

……
阅读全文——共1079字

SGU188 解题手记
　　对于任意两个巡逻方向不同的人，都能很容易地求出他们在T时间以内碰面多少次。
　　首先算出这两个人在T之间之内一共能跑多远，然后求出两人最初位置的距离（在和速度的方向上），如果两人T之间之内跑得路程大于最初位置的距离，那么至少相遇一次，用两人T之间之内跑得路程除以1000求得总共相遇几次。
　　Submit 1: WA on 7。当两人恰好在T时刻第1次相遇时，算错了。
……
阅读全文——共376字

SGU186 解题手记
　　这个破题实在是看不明白。
----------From SGU Forum------------
Author: Rafail
……
阅读全文——共1326字

SGU180 解题手记
　　求一个序列中的逆序对个数。把序列从中间分开，先统计左右两边的子序列中各自的逆序对个数，然后把左右两边排序，这样就可以统计出左边和右边之间的逆序对的个数。以上过程其实就是MergeSort。
　　Submit 1: WA on 12。仔细检查了程序发现没有逻辑错误。看SGU的forum发现需要注意两点：1.需要用long long；2.输出long long应该用%I64d。
……
阅读全文——共407字

SGU178 解题手记
　　为了让拆的次数最少，必须让每一段尽可能的大。每拆一次，就会得到一段长度为1的，以及被拆的link左边和右边的两段。假设需要拆x次，那么就会得到x段长度为1的，其他的段就应该排成(x+1),(x+1)*2,(x+1)*4,(x+1)*8,...
　　其实就是求一个不等式：
　　x+(x+1)+(x+1)*2+...+(x+1)*2^x>=N
……
阅读全文——共916字

SGU177 解题手记
　　这题跟USACO的Shaping Regions有相似之处，我曾写过一篇解题报告：http://www.studentblog.net/m/bslgh/archives/2006/usaco211.html。
　　采用倒序染色+封闭然过色的格子的办法。对每一行开一个链表，染色时将白色部分记入总和，染色过后将这个格子删去。由于每个格子只被染色一次，所以总复杂度能控制在O(n^2)级别。
……
阅读全文——共691字

SGU174 解题手记
　　用并查集维护所有线段的端点，最初所有的端点都以自己为根，加入一条线段时，若两个端点在同一个集合中，则说明出现“封闭区域”，否则将一个端点的根设置为另外一个。并查集要有路径压缩。
　　实现上，用map作为并查集的容器。
　　Submit 1: WA on 2。合并操作写错了。“将一个端点的根设置为另外一个”是不准确的，应该是“将两个端点所在集合合并”。
……
阅读全文——共960字