Codeforces Round #408 (Div. 2)

说好的22:35开始推迟到0:35......

共6题, 比赛时完成A-C. C题搞复杂啦, Editorial比较喵......

题解: 4/6.

2017-04-10

NOI

[NOI 2009] 植物大战僵尸

在n行m列的地图上进行植物大战僵尸游戏. 每个格子上都有植物. 僵尸从右边进入地图, 只能直走, 只能依次吃植物. 每株植物有一个整数, 表示僵尸吃掉它的收益. 每株植物有一个攻击位置集合, 攻击力无穷 (一击致命), 零冷却时间; 保证植物不能攻击自己所在位置. 求僵尸的最大收益 (可以选择不进行任何攻击). (1≤n≤20, 1≤m≤30, -10000≤Score≤10000)

2017-04-10

bzoj

[bzoj 1458] 士兵占领

M*M的棋盘, 一个格子至多放一个士兵, 某K个有障碍的格子不能放. 要求第i行至少放Li个, 第j列至少放Cj个, 求最少士兵数目, 或报告无解. (M,N≤100, 0≤K≤M*N)

2017-04-09

bzoj

[bzoj 1095] [ZJOI2007]Hide 捉迷藏

n个结点的不带权的无根树, 每个结点或黑或白, 初始全黑. q个操作: - 切换结点i的颜色 - 查询黑点之间的最远距离

只有一个黑点输出0, 没有黑点输出-1. (n≤10^5, m≤5*10^5)

2017-04-09

WC

[bzoj 1758] [Wc2010]重建计划

一棵n个结点, 边带权的无根树, 求包含[L,U]条边的简单路径的最大平均权值 (权值和/边数), 保留3位小数. (n≤10^5, 1≤L≤U≤n-1, 边权≤10^6)

虽然AC花费了比想象中更多的功夫, 但我认为数据加强后这是一道不错的题.

2017-04-06

NOI

[NOI 2014] 购票

一棵以1为根的n个结点的树, 边带权 (视为距离). 从某点u到达树根的方式: 支付一定代价跳到距离不超过l[u]的祖先v, 再支付一定代价跳到v的某个距离不超过l[v]的祖先w......设一次跳跃的起点为s, 起点终点之间的距离为d, 则这次跳跃的代价为(p[s]d+q[s]), p, q是给定的参数. 求每个点到达树根的最小代价. (0≤p≤10^6, 0≤q≤10^12, 1≤fa[v]<v, 0<v与父亲的距离≤l[v]≤2*10^11, n≤2*10^5)

2017-04-06

NOI

[bzoj 1492] [NOI2007]货币兑换Cash

有A, B两种金券和人民币. 每天A, B券有价值a, b (元/单位金券) 和一个比例r. 支持两种操作, 每天操作种类和次数不限: - 卖出金券: 将o%的A券和o%的B券以当天的价值兑换为人民币. o是顾客提供的[0,100]内的实数. - 买入金券: 支付i元人民币, 兑换当天总价值为i的金券, 其中A, B之比为当天的参数r.

已知天数N, 初始钱数S, 未来N天每天的参数a, b和r, 求N天后最多能获得多少元人民币, 保留3位小数. (测试数据保证精度误差不会超过10^-7; N≤10^5, 0<a,b≤10, 0<r≤100, 答案≤10^9, a, b, r是实数)

题面上的提示: 采用快速的读入方式; 必然存在一种最优方案满足: 每次买进使用完所有人民币, 每次卖出所有金券.