梦.:如此短暂

SGU160 解题手记
　　记前k个数字能凑出来的分数的集合为S[k]，将S[k]中每个分数 * 第k+1个数字 Mod M加入S[k+1]，再把S[k]中的分数并入S[k+1]，这时S[k+1]就是前k+1个数字能凑出来的分数了。
　　Submit 1: AC。

……
阅读全文——共295字

　　虽然题目描述的比较乱，但依稀看的出来，大意是给出一棵树，对每个节点求与它距离最远的点到它的距离。
　　对每个节点保存三个距离——向上扩展的最大距离（就是节点的深度）、向下扩展的最大距离（以及经过的第一个子节点）、向下扩展的次大距离（以及经过的第一个子节点），下面分别用dis[i,0],dis[i,1],dis[i,2]表示（经过的节点用point[i,1],point[i,2]表示），节点i,j之间的距离用g[i,j]表示。
……
阅读全文——共1842字

　　给出的是一棵树，要求这棵树的权值最大的连通子图的权值。
　　树型DP可以：f(T)=sum{f(t)|f(t)>0,t是T的子树}。
　　存图用邻接表。
　　这样DP的话，树根肯定要被选入连通子图，所以还要枚举树根。复杂度是，承受不了。
……
阅读全文——共816字

本文为转载，不遵循GFDL。
一位高手对我的建议：

一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的
……
阅读全文——共779字

　　这题有人归为树型DP，我看不像，至少没有决策枚举的过程，完全是个“树型递推”。稀疏图用邻接表存，然后DFS一下就变成树了。
　　Submit 1: WA on 1。实在没找到什么地方错了。
　　（重装系统时不小心把这题的解题手记和程序弄丢了，只好重写，以上内容是根据回忆写的，不保证准确）
　　Submit 2: RTE on 13。重写程序后，第一个点直接过了，因没有以前的程序，查不出为什么那个程序WA on 1了。但RTE也够奇怪的，查了一遍程序，没有发现有数组越界或者指针指向非法地址的问题。生成大数据测试。发现在n>15000时出现了RTE，而且是指针指向非法地址！一句一句的查发现，如下写法：(main()中) vertex vertexes[16000]; 数组的有些成员没有初始化！怀疑根本没有调用构造函数。
……
阅读全文——共1218字

　　最小分成的块数当然就是k+1，分割方法一共只有两种吧？如下图：

　　Submit 1: WA on 2。很可惜，分割方法不只有两种。
　　应该画一条弦，则圆被分成两部分，两部分可以各自看成点数比较少的圆，用两部分分割方法数相乘。以一点为这条弦的一端，枚举另一端求和。
……
阅读全文——共490字

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

　　本文是我的一篇笔记，其中提到的解决方案并未经过严格测试。在未能深刻理解每个步骤或命令的情况下，请勿直接模仿。另欢迎指正我的错误。
　　本文中的内容截止到2007年3月10日仍然有效，3月10日之后因为我换用Ubuntu，不再对此文的内容进行测试。
　　总结一下FC6下常用软件的安装配置。

……
阅读全文——共4543字