Title:Farey Sequence
time:1s
memory:64m
Author: Mathematica
筛法＋dp＋欧拉函数
///////////////////////////////
Title:Maximum sum
time:1s
memory:64m
Author: Mathematica
简单的dp
///////////////////////////////////////
Title:Longge's problem
time:1s
memory:64m
Author: Mathematica
方法一
1)求出所有因子
2)DP+容斥
方法二
利用欧拉函数
答案是 sima( Euler(n/pi)*pi ) pi, i=1...m
Euler是欧拉函数
pi是n的因子
////////////////////////////////////////////////
Title:Cows
time:3s
memory:64m
Author: Mathematica
利用树状数组做统计,处理好相同的情况。
/////////////////////////////////////////////////////////////
Title: Stars in Your Window
time:1s
memory:64m
Author: kinfkong
本题的模型是: 给定平面上的n个点，每个点赋有一个值，用一个固定
大小的矩形(矩形只可以平移，不能旋转)使它套得的总值最大. 考虑
到这么一个事实，如果以点p1为中心的矩形能覆盖到点p2, 则以点p2
为中心的矩形必可覆盖到点p1. 因而问题可以转换成, 以原来的每个
点为中心作一个矩形， 每个矩形有一个值，找出平面上被这些矩形覆
盖的总值最大的区域.
于是，我们可以用线段树来解决这个问题. 像求矩形并面积那样，先
对Y坐标离散化，建立线段树，然后从左往右扫描，遇到矩形的左边就
进入插入操作，遇到右边就删除. 线段树中的每个结点有两个需要更
新和维护的数据域: max和cover, 分别表示这个区间中最大的分值及
完全覆盖这区间的总分值. 于是,
本结点的max = MAX{左儿子的max,右儿子的max} + 本结点的cover.
每次插入操作后，检查根结点的max值. 找出最大的就是答案.
/////////////////////////////////////////////////////////////
Title: Greatest Common Subtree
time:1s
memory:64m
Author: kinfkong
假如现在要求以A为根及以B为根的两棵树的Greatest Common Subtree,
即GCS(A,B). 如果A的儿子为u_1,u_2,...,u_t, B的儿子为v_1,v_2,...
,v_s, 则我们可以建立一个二部图进行加权匹配: u_i和v_j边一条边,
权值的大小为GCS(u_i,v_j). 则
GCS(A,B) = 最大加权匹配的值 + 1.
为了得到二部图的边的权值，我们得先解决一个子问题 GCS(u_i,v_j).
因此要一边递归一边加权匹配. 递归出口是当GCS(x,y)中的x或y是叶子
结点时就返回1.
/////////////////////////////////////////////////////////////
Title: A Funny Game
time:1s
memory:64m
Author: Mathematica
可以证明, 当n(n>=1) 个硬币排成一排的时，先手必胜. 这是因为，先
手可以拿掉中间的一个或两个，从而留下个数相同的两排，形成一个败
局.
所以，当n个币排成一圈时，如果n=1,2，先手胜. 否则，先手败.
/////////////////////////////////////////////////////////////
Title:Highways
time:1s
memory:64m
Author: Mathematica
最小生成树
Apple Tree
author:magicpig
解法
树形dp
数组二维go，bk
go[t][i]代表节点t的所有子树上走i步不返回,取得的最大苹果数
bk[t][i]代表节点t的所有子树上走i步并返回,取得的最大苹果数
求节点为x，实行不断合并子树求最优值
当前合并到了q棵子树：
go[x][i]就是这q棵子树上走i步不返回的最优值
bk[x][i]就是这q棵子树上走i步并返回的最优值
合并第q+1棵子树(不妨设第q+1棵子树的根为y)的时候，有
go[x][i] = max( bk[x][j]+go[y][i-j], bk[y][j],go[x][i-j] ), j=0.....i
bk[x][i] = max( bk[x][j]+bk[y][i-j] ) j=0,.....i;
边dfs边处理这两个数组就可以了
|