北京信息科技大学第十一届程序设计竞赛（重现赛）解题报告
A kotori和糖果
将一个堆二分，递归求该堆合并的最小代价，用map判重。
B kotori和气球
dp递推，在第i个位置放颜色为x的球的方案数为在i-1处放除x以外的球的方案数之和
状态转移方程：s[i][x]=sum{s[i-1][y]，y!=x}
状态转移方程：s[i][x]=sum{s[i-1][y]，y!=x}
C kotori和出道
先递推求出每一轮报数是奇数位还是偶数位出局直到只剩一个人，然后将该过程逆推即可求得获胜者编号
D kotori和迷宫
直接BFS求解即可
E kotori和素因子
打表筛出每个数的质因子，然后深搜求解最小值
F kotori和n皇后
用map存行列对角线上是否有皇后存在，对角线压成与x的两个截距，然后记录最早符合条件的i
G kotori和抽卡（二）
DP，在i次抽到j张R的概率为在i-1次抽到j张R的概率乘这次没中的概率+在i-1次抽到j-1张R的概率乘这次中的概率
状态转移方程：a[i][j]=a[i-1][j-1]*0.8+a[i-1][j]*0.2;
状态转移方程：a[i][j]=a[i-1][j-1]*0.8+a[i-1][j]*0.2;
H andy和购物
贪心，最优惠的折扣对应最大的价格，排序后相乘累加
I andy种树
差分裸题（不会差分就百度），最后求一次前缀和顺带输出即可
J andy的树被砍了
我们可以做一个假设：每颗树都是第一天种的，在第i天还剩下a[i]高，那么每棵树的初始高度即为a[i]+s[i-1] (s是b的前缀和),那么只要对前缀和二分每颗树在第一天种下，在第几天会被砍光即可
开发本科够了，早准备早投递
投递牛客等公司10个岗位 >
