BUPT新生暑假个人排位赛03 Solution

继续补欠帐。。这是北邮新生排位赛第三场。

A. 学姐的数码管

一道有点蛋疼的模拟题。。。当时格式错误PE好多发。。。。

同样是一道简单的模拟题，只需要判断旋转的角度%360对应的是0、90、180还是270，并分别输出就可以了。

当时被这题坑惨了。。。其实就是一道简单的字符串判重问题，只不过当时想尝试写一写Trie树，结果被卡空间卡到死。。。这题用hash或直接开map即可水过。

题目大意是求长为n的仅由a、b、c、d构成的序列中含有奇数个a和偶数个b的序列的个数。

这是一道简单的数学题。首先，长为n的序列总数为4^n 。其中a的个数不是奇数就是偶数，b的情况也相同。因此同时含有奇数个a和偶数个b的序列的个数为( 4^n )/4，即4^(n-1) 。使用快速幂即可。

定义一颗平衡二叉树满足条件：对于任意节点，其左子树的权值之和等于右子树权值之和。如图：

我们用序列表示上图平衡二叉树，即4 1 1 2 4 4。现在给定一个序列，求其能最长的能构成平衡二叉树的子序列。子序列元素为原序列的子集，且元素间保持原顺序。

这道题可以通过区间dp来做，设f[i][j][t]表示在区间[i,j]中和为2^t 的序列的最长长度，则可写出状态转移方程：

1	f[i][j][t] = max( max(f[i][k][t-1] + f[k+1][j][t-1]), f[i+1][j][t], f[i][j-1][t] )

目标函数为max(f[1][n][i])