2015 UESTC Winter Training #8
The 2011 Rocky Mountain Regional Contest
Regionals 2011 >> North America - Rocky Mountain
开始时貌似是UVAlive挂了，无论交什么都WA，后来转战HDU
这次水题比较多，其中B题据说有更加高级的方法。
G题WA了两发，才发现竟然没有输出Case!!!
未完成：D F H I J
A - Iterated Difference
水题，模拟迭代即可。
在UVALIVE用的bits/stdc++.h头文件，粘到HDU上，结果直接CE了一发。
B - Shape Number
给出一串数描述一个封闭的图形，比如上边的22234446466001207560（最长300,000位），因为同一个图形旋转或者变换 起始位置会得到不同的数串，所以要进行标准化，标准化后第i位为原数串中第i+1位与第i位的差。最后一位是原串第一位与最后一位的差。然后求最小字典序环。
比赛时是用简单的模拟水过去的（能水过去也太水了），据说有模板或者可以用后缀数组，一会儿去学习一下。
C - Stock Prices
水题，多关键字排序后再对结果排下序即可。
E - Pills
看到1、2、5、14、42这个序列就应该想到是卡特兰数
F - Robot Navigation
给一个机器人，一个只有火山和通路的地图n*m（均小于等于1000），火山不可以走，还给了起点，终点，和起始的朝向，现在机器人1s只能前进一步或者向左向右转90度，问到达目的地有几种路径，并且时间均最小。
比赛时调了1个多小时最后还是TLE，之后再调试一下。
G - User Names
相当水的模拟
I - Wealthy Family
给一棵n个结点构成的树（n<=150,000），给出每个节点的父亲节点，以及权值。现在要从中取K个结点（1<=k<=300）。使得K个结点中任意两个结点都不是父子关系，问K个结点权值和最大是多少。
这道题还没有写，但是有思路。
能想到的就是树形DP，设dp[i][j][k]为以节点i为根的子树中取出j个结点，且取出的结点不存在父子关系。k=0表示取出根结点，k=1表示不取出根结点。
dp[i][j][0]=∑max{ dp[child][j][0] , dp[child][j][1] }
dp[i][j][1]=∑dp[child][j-1][0]
但是显然数组无法开到dp[150000][300][2]，可能会用到记忆化搜索。