梦.:如此短暂

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

SGU171 解题手记
　　贪心。将所有的学生按weight从大到小排序，然后按顺序让每个人去刚好能去的zone（即没邀请满人的zone中level刚好小于这个学生的），如果没地方可去，就暂时记为“无处可去”。最后，把所有“无处可去”的学生随意分配到没满的zone。
　　Submit 1: AC。

……
阅读全文——共297字

SGU 148 解题手记
　　最朴素的，用c[k,v]表示淹掉第k层，且能够给第k+1层灌进v重量的水要花的钱：c[k,v]=min{ P(k)|(if W(k)>=v) , c[k-1,max{v,L(k)+1}-W(k)] }。最后所求是c[N,0]。但这样做空间尚且可以解决，无奈时间复杂度太大了。
　　但暂时想不到好办法，拿这个试一试吧。
　　不行，没办法记录决策。
……
阅读全文——共427字

SGU103 解题手记
　　给的图是一个动态的图，边权非负且在发生周期性的变化。要求两点之间的最短路。
　　考虑Dijstra还能不能用。Dijstra的过程是不断将距离源点最近的点加入集合S，直到目标点也被加入S。Dijstra要求随着路径上节点数目的增加，路径长度也相应增加，即不能出现负权边。他的贪心基于这样的考虑：若能尽早到达某个点，就尽早到达，尽早到达这个点时扩展出的经过这个点的路径，比较晚达到这个点时扩展出的经过这个点的路径短。这个题中，边权的变化是有规律的，我发现尽早到达的想法仍然正确。所以Dijstra可以用。
……
阅读全文——共1760字

SGU172 解题手记
　　这个题看起来是noi的食物链的化简版，同样用并查集，也直接套用“建立环并想办法摞在一起”。参见北极天南星的解题报告。
　　被一个学生选过的两门课互称为opposite。接到一个学生的选课单后：
　　如果两门课的根（根就是并查集中的根）相同，那就no answer了；
……
阅读全文——共1756字

SGU170 解题手记
　　把二进制数10换成01可以让10异或11，一个二进制数中相邻的两位如果不同，可以对应的异或0……0110……0，就可以把这两位换个位置。异或是个很好的运算，满足交换律和结合律，而且若有a xor b=c，则有a xor c=b,b xor c=a。
　　把输入的字符串转化成二进制串，源串和目标串异或就得到转化所需的0……0110……0操作序列的异或结果，把这个结果拆成操作序列就行了。由于操作序列的顺序不影响异或结果，所以从高位往低位拆就行了。拆不出来的，就是无解。
……
阅读全文——共808字

　　SGU600+的前10个题（114-163之间）。
　　虽然已经是600+，但这10个题仍然以水题为主，总的来说，1AC率有所上升（1000+的16个题只有2个1AC的），但有的题目上犯的错误远远超过1000+的16个题。
　　所犯严重错误：124看错题意，133两次看错题意。
　　编码速度仍然有待提高，昨天看到一个说他2分钟写过了一个水题，实在汗颜，我现在2分钟内连输入输出都写不完。但速度应该以质量为基础，所以仍然要以提高编码质量为主。
……
阅读全文——共281字

SGU116 解题手记
　　题目大意：如果一个数是质数，而且他在质数序列里的序号也是质数，那么他就是超级质数。要求将输入的数字n表示成超级质数的和的形式，而且所用超级质数数目最小。
　　求超级质数的方法很直白，按题目叙述的做就可以了。然后做一个多重背包。n就是包，超级质数序列是物品。
　　Submit 1: RTE on 2。数组下标越界，不仅是RTE，而且是WA。
……
阅读全文——共456字