Tongji Online Judge Solutions
Welcome to T ongji O nline J udge S olutionsV olume 1
放心大胆地做吧，不会TLE:)
第一问即经典的最长不上升子序列问题，可以用一般的DP算法，也可以用高效算法，但这个题的数据规模好像不需要。2 )。注意：
...2*5=...10（舍）或...60，最后一位非零数为6。而恰好2*8=16，末位为6。
用数组模拟链表即可。
每一个保留的数字都从可取的范围中取最小的一位即可。用a[i]表示第i个保留的数字在原数中的位置，设a[0]=0，则a[i]的范围为a[i-1]+1~n-m+i。
借用化学术语说，“一个2跟一个5反应生成一个0，因为2过量，所以照5算”。n!末尾零的个数就是1~n这n个数中因数5的个数，即n div 5+n div 52 +n div 53 ...直到某项减少至0为止。
用实数乘，超过100就除以10，最后取个位即可。
开一个最小下标为0，最大下标为最大总质量的一半(maxw)的布尔数组b，初始时仅b[0]为true。依次读入每一个石子的质量。设当前石子的质量为m，则对于原来的任一个值为true的b[i](0<=i<=maxw-m)，令b[i+m]为true。处理完每个石子后，设值为true的b值中最大下标为x，则x就是把石子按质量尽可能平均地分为两堆后较轻的那一堆的质量。
垃圾题。不要按照一般的乘法竖式输出，而要观察样例程序的输出，然后照葫芦画瓢……SPOJ上有一道Simple Arithmetics，比这个题好得多，推荐做一下。
说是麻将游戏，其实就是连连看嘛。好像有不少人看不懂题意，可以Google一个连连看玩一下。Maigo的原始算法： 循环 ，循环中经过的位置个数叫做循环的长度 。如N=4时，有两个循环：1-2-4-8-7-5-1，长度为6；3-6-3，长度为2。答案就是所有循环长度的最小公倍数。显然算法时空复杂度均为O(n)（因为需要记录一个数是否已被某个循环经过）。Wasltone的高效算法： Ahyangyi给出的证明： p mod (2*n+1)。假设1经过p步回了家，那么可得1*2p mod (2*n+1)=1。由此可得对任一数字x，均有x*2p mod (2*n+1)=x，即1回家时任一数字都回了家。
对于非叶子结点 ：当前待确定分母的最小值就是max{上一个分母加1，当前剩余分数的倒数的整数部分加1}。第2项之所以加1，是因为当前分母必须小于以后的分母。它的最大值则是min{当前剩余分数除以尚未确定的分数个数的商的倒数的整数部分，当前最优解的最后一个分母减1}。前一项可以这样理解：如果当前待确定分母大于这一项，那么以后的分母都会大于这一项，当前待确定的及以后的分数加起来肯定小于当前剩余分数。后一项则是显然的：如果当前分母都大于等于当前最优解的最大分母了，那么当前结点一定不会扩展出更优解。
对于叶子结点 ：这里就无需讨论什么范围了。若当前剩余分数的分子恰好为1，且分母大于上一个分数的分母，且分母小于最优解的最大分母，则更新解，否则退出。
注： 本题的题目描述不甚清楚。在多解的情况下，题目只说要分数个数最少，分数个数相同的情况下最大的分母最小。但是，若最大的分母还相同怎么办呢？比如8/27，是分解成1/4+1/36+1/54，还是分解成1/6+1/9+1/54？对此，我的程序输出的是找到的第一个解4 36 54，亦即认为在最大的分母还相同的情况下，取字典顺序最小的一个。这可能不是出题者的原意，但用这种标准，我AC了。
假设我们要求kensta的序号，那么我们只要求出以a开头的、以e开头的、以ka开头的……字符串各有多少，累加就行了。剩下的任务就是已知一些字符，求它们可以组成多少个不同的字符串。这是一个重排列问题。假设共有n种字符，其中字符ci 有ai 个，那么求这些字符可以组成的不同字符串数的公式为2 =160000。
先用预处理算出符号的所有填法对应的结果，然后问哪个输出哪个就行。
此题的确定算法，不是TLE就是MLE。这时，随机算法就大显神通了。
把上面j个盘子移到某一工作柱上。这一步可以用四个柱子，所需移动次数为g[j]。 把下面i-j个盘子移到目的柱上。因为上一步占用的工作柱在此步中不能使用，因此此步所需移动次数为f[i-j]。 再把工作柱上的j个盘子移到目的柱上，所需移动次数为g[j]。 g[1]=1
然而仅仅利用这个式子，算法复杂度是O(n2 )的，对于n<=50000的数据范围，显然无法承受。因此，我们列出i值较小时的f[i]和g[i]，以期发现某种规律。
i 1 2 3 4 5 6 7 8 9 10 11
f[i] 1 3 7 15 31 63 127 255 511 1023 2047
g[i] 1 3 5 9 13 17 25 33 41 49 65
观察这个表，我们可以大胆地猜想g[i]的规律：从1开始，加2次2，再加3次4，再加4次8，再加5次16…… 这个猜想的证明过程过于琐碎，详细、严谨的步骤反而会妨碍理解，我只说一下大概思路：显然g[2]是用g[1]和f[1]算出来的。假设g[i]=g[j]*2+f[i-j]，那么g[i+1]=min{g[j+1]*2+f[i-j],g[j]*2+f[i-j+1]}，即把f或g的下标增加1。为什么呢？因为f和g两个数列都是增长的，而且增长得越来越快。如果在最优解的基础上让f的下标变大、g的下标变小，或是相反，结果不是不变就是变大。亲手模拟一下g的计算过程，就会发现，g数列加2k 的次数等于g数列加2k-1 的次数与f数列加2k 的次数之和。 由此可以得出上面的猜想。k ，其中k从1开始取整数值。
搜索、判重。判重时若保存整个图象比较每个格子则嫌慢，其实有一点小技巧：把每个图象看作一串二进制数，用一个数来存储这个图象每个格子的信息，再加上一个宽度就可以唯一地表示一个图象了。由于一个图象经翻转、旋转可得到8种形态，我们需要按某种规则只存储一个（如宽度取较长边，宽度一定时使二进制数最小）。这样既节省了时间，又节省了空间。
用一个队列q来存储序列，初始时设q[0]=1。设三个头指针f1,f2,f3，分别对应于三个质数p1,p2,p3（假设p1<p2<p3）。头指针的初值均为0。每次取q[f1]*p1,q[f2]*p2,q[f3]*p3中的最小值，如果当前队列为空或它与当前队尾元素不同，则将其放进队列。无论是否放进队列，都将产生最小值的头指针加1。当队列达到所需的长度时，输出队尾元素。
赤裸裸的最小生成树模型。
思路极清晰：列多元一次方程组，用高斯消元法解。所谓高斯消元法，就是用一个含xi 的方程（记为Ei ）与其它所有方程加减，消去其它方程中的xi ，待解出x1 至xi-1 后，代入Ei 求xi 。但编程极麻烦，具体来说，有下面几点提示或注意事项：
跟1117 一样，列方程时最好在整个反应式最左边加个'+'，倒着进行。
消元时若待消的未知数已不存在，则No solution。
消元时若未知数比方程多两个或两个以上，即方程过少，则No solution。
消到只剩一个未知数时，方程应当一个也不剩，否则，剩下的方程中均只含最后一个未知数，它只能等于0，这是不合题意的。简言之，方程过多时也是No solution。
两个方程加减后不要忘了及时约掉各系数的最大公约数，以免过程中系数过大。
消元结束后，令x1 =1，利用各Ei 依次推出各xi 。若碰到某个xi 为分数，则将x1 至xi-1 均乘以xi 的分母。若碰到某个xi <=0，则No solution。 树型DP 贪心 二分图最小覆盖 Cocoran 大牛是怎么想出来的。i 表示a1 至ai 的和，S'i 表示b1 至bi 的和。下面研究三种操作对各Si 的影响：
对ai-1 、ai 、ai+1 (1<i<n)进行操作，相当于交换了Si-1 和Si 。
对an 、a1 、a2 进行操作，相当于把所有的Si 都减去a1 ，再交换S1 与Sn 。
对an-1 、an 、a1 进行操作，相当于把所有的Si 都加上an ，再交换Sn-1 与Sn 。 i 都加上或减去了某一数值，然后进行了若干次交换。于是把a1 至an 、b1 至bn 分别排序，若所有的Si -S'i 均相等，则YES，否则NO。
简单深搜。只是面对某一个棋局时，若轮到的一方无处下子，要妥善处理pass的情况。
把x+y+z的为奇数的格子染成黑色，x+y+z为偶数的格子染成白色。若n为奇数，则Yes的充要条件是起点与终点均为黑色；若n为偶数，则Yes的充要条件是起点与终点异色。
每次取数列的后四项，让两头两项为正，中间两项为负（当然反过来也行），这样这四项的和就是0了，将这四项删去。这样做到最后最多只剩3项。若剩3项或一项也不剩（即n mod 4=3或0），则答案为0，否则答案为1（因为添加负号不改变和的奇偶性，而这时所有数的和为奇数，故答案无法达到0）。
用best[t]表示在时间t以前Tom得到的最大加工费。按时间递增的顺序计算best数组。对每个best[t]，首先令其为上一个时间的best值，然后对于每一个在时间t结束的工作（设其开始时间为s，加工费为m），比较best[s]+m与best[t]的值，取大者。1017 石子归并 问题。本题的大数据规模版本就是1166 背包问题 。
把每个时间段看成一条线段，用扫描线法找到被n条线段同时覆盖的区间，输出。当然要注意输入输出的细节。
老老实实地按题目说的顺序判断，即先判断所有砖中是否有交叉，再判断所有砖中是否有越界情况，最后判断地板是否全被覆盖。切不可看到第一块砖越界了就下结论，因为第二块和第三块可能交叉。两块砖(x1,y1)-(x2,y2)与(x3,y3)-(x4,y4)交叉的充要条件是(x1<x4) and (x3<x2) and (y1<y4) and (y3<y2)。第三步判断砖是否盖满地板时，可以累加所有砖的面积，若这个和与地板的面积相等，则盖满。
用f[n]表示最后一个数是n时，可以构造出的数的总数。规定f[0]=1，则显然有f[n]=f[0]+f[1]+...+f[n div 2]。Σ Ki*MPi <=maxlongint5 >maxlongint，所以P不会超过4。3 =3375000，这个复杂度是完全可以承受的。我们可以枚举左边，用一个表将所有可能的结果及其出现次数存储起来，然后枚举右边，在表中查找右边结果的相反数，累加表中存储的出现次数即得到答案。现在的问题是：用什么表来存储结果呢？哈希表 。哈希函数很好找：设x为结果，那么hash(x)=abs(x) mod bigprime，其中bigprime为一个取定的大质数。这样，存储和查找就几乎都是线性的了。这样处理以后，算法的时间复杂度为O(M3 )，带一个适中的常数系数。不要用指针，而用数组来模拟，因为指针本身就耗内存，而且分配、回收操作也浪费不少时间。至于处理冲突的问题，可以建立公共溢出区，即把冲突的元素统统放到公共溢出区中。
哈希表中无需存储原始的元素。假设原始元素为x，那么在hash表中只需存储x div bigprime+ord(x>0)。之所以要加入ord(x>0)一项，是因为如果不加，-1和1就会变成同一个数0。经过这一变换，x的范围就由原来的longint变为integer（我的bigprime取的是999983），又省了大量内存。 space值的计算 ：如果一个B结点(i)的space值为无穷大，而它的两个孩子（a、b）的space值都已算出，且有一个小于j（不妨设space[a]<j），那么令space[i]为j。这是因为可先利用大小为j的堆栈空间计算以b为根的子树，1个单位的堆栈空间被用来存储结果，而剩下的j-1个单位的堆栈空间足以计算以a为根的子树。
swap值的计算 ：对于.结点，swap[j,i]显然为0。对于B结点(i，左右孩子分别为a、b)，则swap[j,i]=min{swap[j-1,i],swap[j,a]+swap[j-1,b],swap[j,b]+swap[j-1,a]+1}。注意最后一个元素，若先计算右子树，后计算左子树，则最后需交换两个结果，因此要加1。
感谢Faint.Wisdom讲解求最近公共祖先(LCA)的Tarjan算法！ 计算当前结点的层号lv[x]，并在并查集中建立仅包含x结点的集合，即root[x]:=x。
依次处理与该结点关联的询问。
递归处理x的所有孩子。
root[x]:=root[father[x]]（对于根结点来说，它的父结点可以任选一个，反正这是最后一步操作了）。 版本2 。
本题数据范围很小（这是当然的），所以可以用分层图BFS解决。2 =2010 表示这个状态。于是，我们首先需要求出在每一层中，有哪些位置是不可到达的。这一过程很简单：在确定每个镜子的方向后，从每个发射器出发，把不可到达的位置依次做上标记即可。2 层，旋转了第2个镜子，那么就来到了第101002 xor 000102 =101102 层。如果搜到了任一层的终点，则成功。
A simple prob isn't usually an easy prob.自由段 ）。若自由段开头某一段的和<=0，那么这一段就可以删去了。因此可另开一个累加器s0，每次把i后移一个位置，在s上加上第i个数，在s0上加上第j个数。若某时刻s0<=0，则p:=j;dec(s,s0);s0:=0。若队列中只有一段，那么这一段就是自由段开头的一段，因为它的和<=0，故把它删去即可。
若队列中不只这一段，那么可以把这一段与上一段合并：inc(a[r-1],a[r]);b[r-1]:=b[r];dec(r)，因为反正这一段的和<=0，若删掉最后这一段之前的所有段，不如把这一段一起删掉。重复合并直至队列中只剩一段或a[r]>0为止。 版本1 中所述。
P.S.楼天城大牛有不用数组的算法，程序运行的时间也只有我的1/3——25ms左右。他是怎样做的我就不知道了(-_-b)
一种更简单的O(n)算法：
一个猫老大数分解质因数后的形式为n=p*q(p<q)，那么一定有p在2至sqrt(n)的范围内，而q在此范围外；
若n不是猫老大数，则：
n可能等于1，这时n在2至sqrt(n)范围内无质因数；
n可能本身就是质数，这时n在2至sqrt(n)范围内亦无质因数；
n有多于2个（不是2种）质因数，这时n在2至sqrt(n)范围内的质因数必然多于1个（不是1种）。这点可由反证法证明：假设n在2至sqrt(n)范围内的质因数只有1个，那么其余的2个或2个以上质因数就都大于sqrt(n)，其积必大于n，而是这不可能的。 对踵点 ”的定义：如果过凸包上的两个点可以画一对平行直线，使凸包上的所有点都夹在两条平行线之间或落在平行线上，那么这两个点叫做一对对踵点。下面将证明最远距离点对一定是一对对踵点。Waterfish 指出我贪心算法的错误。其实这个题的正宗解法还是搜索。1 k1 *p2 k2 *...*pn kn ，则a的约数个数为(k1 +1)*(k2 +1)...*(kn +1)。显然，在约数个数相同的情况下，要使a最小，应有k1 >=k2 >=...>=kn 。因此，我们可以搜索每个质因数的指数，把上面的不等式当作剪枝条件。质因数只需用前trunc(log2 100000)=16个即可。9 ，可以这样：29 =(24 )2 *2，其中24 =(22 )2 ，而22 =(21 )2 ，21 为已知。如果在第i个数字处开始不是最后一个数，那么next[i]表示下一个数开始的位置； 如果在第i个数字处开始的数是最后一个数，则next[i]=l+1； 如果自第i个数字起的序列无法划分，则next[i]=0。 next[next[i]]>0，即从next[i]开始的序列可以划分； s[i..next[i]-1]表示的数小于s[next[i]..next[next[i]]-1]表示的数，即严格递增； next[i]尽可能大。 吃掉第i个垃圾 ，即update(l[i,j],l[i-1,j]+g[i].life)；用第i个垃圾来垫高 。令t=j+g[i].height，即把第i个垃圾用来垫高后卡门爬上的总高度。如果t>=d，则卡门于g[i].time时爬了出来，否则update(l[i,t],l[i-1,j])。顶点 。依次统计顶点为(x,y)(1<=y<=x<=n)的三角形。假若某一条斜的被删边正好处于从(x,y)出发的两条斜直线上，那么顶点的对边在这条被删边以上（如果它在(x,y)的上方）或以下（如果它在(x,y)的下方）的三角形都不复存在了。因此，使用斜的被删边来缩小u~d的范围。
现在，u~x-1和x+1~d的每一个值都对应着一个以(x,y)为顶点的三角形。下面就检查一下这些三角形是否被水平的被删边破坏掉。最后剩下的三角形就是图中存在的三角形，累计即可。
再用一遍1014 中的化学术语：“一个2跟一个5反应生成一个0，因为2过量，所以照5算”。也就是说，因数5应是我们关注的对象。计算1至n的不是5的倍数的数之积的末位数可以const，因为n的末位数与积的末位数之间存在对应关系。当然，n=0和n=1的情况例外。
因为乘以5之前和之后的末位数都是偶数，所以乘以5的效果与乘以8相同，即：2*5->6，4*5->2，6*5->8，8*5->4。
显然这道题需要用高精度。不要图省事而用字符串，因为字符串与数组相比，delete(s,1,1)这个操作太费时间。而且，我的经验表明，用字符串会莫名其妙地WA掉。
a[1,1] and b[1] xor a[1,2] and b[2] xor ... xor a[1,m] and b[m] = false
其中b[i]是未知数。本题的答案，就是上述方程组的解的组数减1（空集不符合题意）。注意到所有方程的右边均为false，因此这个方程组不会无解。自由变量 ，也就是说，它是取true还是取false都可以，同时它已经不存在了，不必消去；否则找一个b[i]的系数不为false的方程，用它与其它每一个方程进行异或运算，再把这个方程本身删除，这样就消去了b[i]。因为当自由变量取特定值时，每个非自由变量都可由自由变量根据消去这个非自由变量时与其它方程异或的方程算出，所以方程组的解的组数就是2^自由变量个数。
。
宽搜即可，因为总状态数只有(10*10*4)2=160000。
先用预处理算出符号的所有填法对应的结果，然后问哪个输出哪个就行。
此题的确定算法，不是TLE就是MLE。这时，随机算法就大显神通了。
项比前一项大2k，其中k从1开始取整数值。
搜索、判重。判重时若保存整个图象比较每个格子则嫌慢，其实有一点小技巧：把每个图象看作一串二进制数，用一个数来存储这个图象每个格子的信息，再加上一个宽度就可以唯一地表示一个图象了。由于一个图象经翻转、旋转可得到8种形态，我们需要按某种规则只存储一个（如宽度取较长边，宽度一定时使二进制数最小）。这样既节省了时间，又节省了空间。
用一个队列q来存储序列，初始时设q[0]=1。设三个头指针f1,f2,f3，分别对应于三个质数p1,p2,p3（假设p1<p2<p3）。头指针的初值均为0。每次取q[f1]*p1,q[f2]*p2,q[f3]*p3中的最小值，如果当前队列为空或它与当前队尾元素不同，则将其放进队列。无论是否放进队列，都将产生最小值的头指针加1。当队列达到所需的长度时，输出队尾元素。
赤裸裸的最小生成树模型。
思路极清晰：列多元一次方程组，用高斯消元法解。所谓高斯消元法，就是用一个含xi的方程（记为Ei）与其它所有方程加减，消去其它方程中的xi，待解出x1至xi-1后，代入Ei求xi。但编程极麻烦，具体来说，有下面几点提示或注意事项：
(n>=m)
(n>m)，两式相减得f[n]-f[n-1]=f[n-1]-f[n-m-1] (n>m)。于是可以化简最后一个方程：
。之所以化成第二种形式是为了方便计算，是因为第二种形式中和式的每一项的计算过程中只用了乘除法，可以用对数计算，而结果不超过1，可以直接相加。另外，不必每个组合数都重新计算，计算一个组合数时，在上一个的基础上乘以一个数再除以一个数即可。这样设计出的算法是线性的，虽然每次运算慢了点。
典型的博弈问题，寻找猫的必败态。显然，0是必败态。观察每次可以拿的黄金的块数，发现它们都不能被3整除，因此，3的倍数都是必败态。因此，如果开始时黄金块数是3的倍数，则王胜，否则猫胜，第一次拿走黄金块数除以3的余数即可。因为10 mod 3=1，所以求一个数除以3的余数只要把所有数位相加，这个和除以3的余数就是原数除以3的余数。
枚举左右两边（不要忘了整块布的左右边界），然后在左右两边确定的竖条中用扫描线法找能切出的高度最大的手绢。可在预处理中把所有的上下边排一下序，做扫描线时直接利用。
先用预处理求出sqrt(maxlongint)以内的质数表。对一个给定的数n，若n正好是某个质数的平方，那么它是一个猫老大数。以下讨论n不是某质数平方的情况：
观察图1，设∠1+∠2≤180°，∠3+∠4≤180°。那么如果∠1≥∠4，则由于∠1+∠2≤180°，一定可过B、E作两条平行线使边AB落在其中一条上；反之，则可过B、E作两条平行线使DE落在其中一条上。也就是说，当一条线段截凸包所成的两组“同旁内角”之和均不超过180°时，这条线段的两个端点是一对对踵点。因此，若一条线段的两个端点不是对踵点，则必有一组同旁内角之和大于180°。
再观察图2。因为有一组同旁内角之和大于180°，所以这两个角中必有一个角大于90°（不妨设∠ABE>90°）。这种情况下显然有AE>BE，因此BE不是最远距离点对。也就是说，不是对踵点的点对一定不是最远距离点对，所以最远距离点对一定是对踵点。
，其中i表示第一棵子树中结点的数目。
首先看到题目中顶点的编号方式不利于解题，故将其转换为坐标表示法，如原来的顶点8转换为第4行第2列，即(4,2)。转换方法如下：设顶点x的上方有t行，则t是方程t*(t+1)/2=x-1的正数解的整数部分（体会一下方程右边-1的巧妙性）。于是，顶点x便转换为(t+1,x-t*(t+1) div 2)。