纪中2016.12.10比赛总结

100+100+20+0=220
250分也好呀！！！
今天看见比赛标题就有点虚虚的。“提高C”呵呵，赶紧看题。
T1：分发糖果。
一道一看就是规律的题，怒打数据库（还错了）。后来用一个判断质数的方法，后来一个高明的草稿本推算，发现不通。推了个20以内的东东，出现了：1、2、4、8、16可行。果断打正解：
判断是不是2的次方。OK。为什么正在思考。
T2：下棋。
推了推每个人与别人对弈的价值差，发现正解，果断打。后来检查时发现漏打两个东东，差点100分飞走。
正解：算出每个人与别人对弈的价值差。用一个快排，输出前k个即可。
T3：X-因子链。
刚开始看不懂题目，把中间高能的X0=1，X1，X2，。。。，Xm=X給理解炸了。最后30分钟怒打，找质因数的方法。没有考虑到未知的质因数数量众多，于是全排列就时间炸了。
正解：有很多解法。
我从徐某某的裤兜里掏出了一样神器——动态规划。
先求出n的所有因数（是因数不是质因数）。
设f[i]表示当前走到第i个的最长。
r[i]表示当前走到第i个方案数。
伪代码：
i:=1 to l{n因数有多少} do
j:=1 to i-1 do
if a[i] mod a[j]=0 then//判断可不可以分。
begin
if f[i]=f[j]+1 then//长度相等，更新方案数
begin
r[i]:=r[i]+r[j];
end
else
if f[i]<f[j]+1 then//f[i]长度小于f[j]+1，更新f[i]和r[i]
begin
f[i]:=f[j]+1;
r[i]:=r[j];
end;
end;
ans:=max(f[1...n]),max(r[1..n]).
T4：二叉树
剩下3分钟，打了个random（据说RP好有30分），结果文件输入输出错了。呵呵。
蒟蒻方法：输出2。30分。（比random好用很多！！！）
正解：本人用扬哥的方法：
把后序遍历的翻转，得到顺序为“根右左”。可以看出，两个序列的第一个（根）是相同的。序列一的第二个字母是左子树的根，序列二的第二个字母是右子树的根。如果左右子树的根不同，就分开两个子树，分别求方案数，乘起来；如果左右子树的根相同，就把这个子树的方案数乘2。
感谢扬哥！
AK。