北京林业大学第一届程序设计竞赛题解

北京林业大学第一届程序设计竞赛题解

A：

直接模拟即可，循环一遍看有多少个数大于等于60.

B：

该题可用公式求解。

可以发现，第n个金字塔所用的积木数S_n=1²+3²+5²+···+(2n-1)²;

是从1开始的n个奇数的平方和，由自然数的平方和公式可得出最终公式：

(4n3-n)/3;

还需注意，本题数据范围是1~10^6，需要用int64。

直接循环也是可以的

C：

直接模拟。小写字母里只有a b d e g o p q有圈圈，其中g算两个，数字里只有4 6 8 9 0有圈圈，其中8算两个。统计一下即可。

D：

思路：考虑先取扑克K（13），可以分别取0-4张，再考虑取Q（12）……

依次递归，最后考虑取扑克A（1）

对于f(n,c)， n代表数字总和， c代表当前考虑的牌，初始为13

f(n,c-1)：      所取牌中无c，

f(n-c,c-1)*4 :   所取牌中有1张c,4种花色共4种取法；

f(n-2*c,c-1)*6 : 所取牌中有2张c,4种花色6种取法；

f(n-3*c,c-1)*4 : 所取牌中有3张c,4种花色共4种取法；

f(n-4*c,c-1) :   所取牌中有4张c,4种花色共1种取法；

递归函数为上述相加。

递归边界

1.n<0 或则 当前总和n大于1到c中的牌各取4张之和   则取法为0种；

2.n==0或则 当前总和n等于1到c中的牌各取4张之和   则取法为1种（不取或全取）

E：

本题需要使用数据结构线段树+Lazy Tag标记法，每个节点记录对应区间的余票数量，对于放票操作，可以直接对线段树进行更新，对于购票操作需要先查询可购数量，再进行更新。每次更新和询问时都需要使用lazy tag对区间票数进行向下和向上的迭代。每次更新或者询问结束后，所有的余票信息都存储在其可能存在的最浅的节点中。

F：

仓鼠能从高的格子向与其相同高度或低的格子滚动，且高度差不超过100；

从开始的格子起对于四个方向符合要求的格子使用DFS或者BFS把所有能走的路径都走完，每次计数加一，最后得到的值就是结果。

G：

抽象题目

这题实际上可以抽象成两部分，第一部分是选择分组方案，第二部分是根据分的组数x计算预测成本，并使之最小，不难发现预测成本和x是成正比的，所以我们首先求出最小的X,再根据这个x求最小预测成本就好

求小X：

我们相当于要一次性分最少的组找出Wa，由于要一次性，所以不能二分，但是我们可以把所有的细胞数二进制编码，得到一个长为log(n)的二进制串，然后我们把第一位为1的作为一组，第二位为1作为1组，以此类推。最后看结果时，第一组若有Wa细胞，则Wa细胞的第一位一定为1，同理第二位第三位……

最后就能得到Wa细胞的编号，所以得到最小的x就是n的二进制串长度为logn，但是要注意这里我们只需要确定n-1个就好，最后一个可以根据前面的结果得到，所以最小x是 log(n-1)

求预测成本：

这个就是根据算出来的 x 和 给的阈值m求预测成本，相当于求长为x的二进制串（YN可以看做1和0）中，所有子序列中Y与N的个数差最大不超过m的串有多少个。

这是一道明显的DP 

我们用dp[i][x][y]记录状态，x表示到i长度时最多的Y比N多的数目，y表示最多的N比Y多的数目 

则状态转移方程如下： 

dp[i][x][y]=dp[i-1][x+1][y-1]+dp[i-1][x-1][y+1]

H：

           题目大意描述了一个简版的Pagerank算法。有n个网站，m对关系，输入的m对关系都为A B 的形式，意思的是从域名A有一个超链接指向域名B，B的rate此时加1，注意前提条件是A,B不能相同，做法我们可以用map来对每一个域名记录其rate，接着将map导入到一个含有pair的vector里面，然后按照rate大小对vector排序，注意如果rate相同，则按照字典序大小排，最后将每个域名及其rate值按从大到小输出即可。

I：

题意：给出n根高度为1,2,3,一直到n的杆子，从左边能看到l根，右边能够看到r根，问有多少种可能

假设已经安排好了高度为2到i的杆子，

那么高度为1的杆子的放置方法有三种情况

1.放在最左边:从左边看得见，右边看不见

2.放在最右边：从右边看得见，左边看不见

3.放在中间，有i-2个空位可以插，左右都看不见

故：

d[i][j][k]表示让高度为1~i的杆子排成一行，从左边看能看到j个，从右边看能看到k个 的方案

状态转移：

case 1：插到左边，则左边看得见右边看不见；d(i-1,j-1,k);

case 2： 插到右边，……；d(i-1,j,k-1);

case 3：插到中间，两边都看不到；d(i-1,j,k)*(i-2);

状态转移方程为：ans=dp(i-1,j-1,k)+dp(i-1,j,k-1)+dp(i-1,j,k)*(i-2);  

J：

本题是求给定的一些点，以及这些点的M临近点到椭圆最短距离的和。首先利用kdtree对点进行维护，这样可以快速的求出每个红宝石的M个邻近点。因为这些邻近点可能有重复的，比如同一个蓝宝石是两个红宝石的M邻近点。所以求出来的所有邻近点进行去重。将求出来的坐标绕着椭圆圆心，顺时针旋转sita，并减去椭圆圆心坐标，得到新的点坐标。此时求点到椭圆的距离相当于求旋转平移之后的点到圆心在原点，长轴在x轴上的标准椭圆的距离。判断该点所在的象限，该点与椭圆在该象限内的曲线的距离是凹函数，可以利用三分法求解。（对于求最小距离也可以用牛顿法进行求解）同理可以求出各个点距离，最后求和即可。

K：

编译原理题。因加入了自定义的错误检查，故无法使用网上现成的解析器，需自行构造。测试数据量小，对性能要求不高，采用递归下降算法即可。

题目给出的6种错误都容易判断：

④⑤两项在词法分析阶段即可检查。

出现①错误只有两种情况，要么文本非{或[开头，要么按对象进行解析或按有序表进行解析后还有剩余字符(非空)。

⑥只要在构建对象的名值对列表时，将新值与原有值比较即可。

判断②错误需考虑“}”的Follow集，“}”之后只可能跟着“}”、“]”、“,”或文件结束。如果跟着的是文件结束或“]”，很容易判断；若是跟着“}”，则等同于连续的一串“}”中少了最后一个；若是跟着“,”，且其后跟着非“"”，也很容易判断错误；若是跟着“,”且其后字符能正常解析成“名值对”，则错误相当于第一种情况。

③错误的判断最为复杂，但排除其它错误后还不能正常解析的话，即可判断为③错误。