北京信息科技大学第十一届程序设计竞赛(重现赛)解题报告
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的前缀和),那么只要对前缀和二分每颗树在第一天种下,在第几天会被砍光即可