Wicky Roam's Blog

三道水题，就差不多可以保铜奖了

嗯，借用一下HIT某大牛的简略解释，

A : 一个球体组成的金字塔，每层都是三角形。第一层1个，第二层1+2个，第三层1+2+3个，第n层1+2+3+….+n个。从第一层开始
往下按顺序给每个小球编号，每层的三角形也是从上到下遍。现在给定一个编号，求它的位置，也就是层数、层内的列数和列内的
第几个。
二分+二分，推的时候可能有点儿麻烦，不是我写的

B : 一个数有K个约数（算自己）就叫K维数。求第n大的K维数。n <= 10000, K <= 100且K为质数或完全平方数。
数论+高精，题中最重要的部分就是数据范围。。。要注意K是完全平方数时有两种情况不能漏

C : 100个点的带权无向图，每个点连着一个港口。有n艘船，船数和图顶点数相等。每艘船有一个初始位置，是图中的一个顶点。
每个港口只能停一艘船，问怎么调度能让所有船都停到港口里，总路程的和最小。
Floyd+完全二分匹配（或最大流最小费用流），反正应该有0边或负边，最好用后者，前者由于队友模板不强，没过…

D : AX = b的线性方程组求解，A是n*n的方阵，维数最多到100。要精确解，用分数输出。
Java题，叫Java题一点也不过分，因为Java有高精库，用C++模板实在太麻烦了，所以说，多学一门语言多有好处啊！

E : 算法不太难，但是5个小时内几乎不可做。题目描述很繁杂，最后单独写。
应该是个模拟+DP+网络流的繁琐题目，的确几乎不可做

F : 给定一个数i，对i, i+1, i+2求和。要求求和过程中任何一位都不能产生进位，十进制数。给定一个数n < 10^10，问小于等于
n的数中有多少满足条件。
排列组合简单题

G : 一个有向无环图，10000个点，每个点都有一个权。满足只有一个点在拓扑序最顶端。这个点是起点。有一艘船从这个点出发，
有两个玩家分别操纵，第一个玩家走第一步，第二个玩家走第二步，第一个玩家再走第三步，类推。必须顺着有向边走。直到不能
走为止，最后的得分是路径上所有点权的和。如果该权>=某常数F则玩家1赢，否则2赢。问1是否能必胜。
博弈，算法还没想，不难，现场很多人也做了

H : 一片海域，最大20*20。里面有障碍，漩涡，出发地和目的地。有一艘船要到达目标，它能做两个操作，普通走和加速走。普通
走一次走一格，加速走一次走d <= 5格。加速走必须要路径上的d格不能有障碍，否则不允许加速。漩涡必须加速走才能穿过，普通
走不能穿过。加速有次数限制，在输入数据中给出。穿越一个漩涡减少1点HP。要满足在减少HP最少的前提下用最短的步数到达目标，
问这个最短的步数。
当时没太读懂题意，反正挺诡异

I : 一个简单无向图（无自环无平行边），最多1000个点。给1000个数，是这1000个点的度。文是否有一个图和满足给定的度条件。
简单题，没看题直接敲的，学图论的第一个算法。。。

J : 题目具体没搞懂，也记不请了，当是也没细想。直觉像计算几何 + 动态规划一类的东西。
是n个监测站为顶点划分成n-2个三角形，每个三角形内有岛屿，对三角形赋权，使n-2个最大权-最小权最小
当时没想，应该就是CG+DP