acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 题解

    题意: * 有 333 道题,每题按过题人数决定分值(500,1000,…,3000500,1000,\dots,3000500,1000,…,3000)。 * 你可以 hack 某些人:每 hack 一次加 100100100 分。 * 每个人某题得分形如: scorei=xi(250−ti)250score_i=\frac{x_i(250-t_i)}{250} scorei =250xi (250−ti ) 求最终排名的最小可能值。 思路要点: * 总分最大 900090009000,因此 hack 次数最多 909090; * 能被 hack 的人数量也至多 909090。 * 先枚举每道题的分值(等价于确定每题可 hack 人数),复杂度 O(73)O(7^3)O(73); * 确定后“hack 越多越好”,你的分数可直接计算; * 再用 dpi,j,kdp_{i,j,k}dpi,j,k 统计每题 hack 次数固定时,你能达到的最小排名,时间复杂度约为: O(303⋅90)O(30^3\cdot 90) O(303⋅90) 总体复杂度: O(73⋅303⋅90)O(7^3\cdot 30^3\cdot 90) O(73⋅303⋅90)

    userId_undefined
    pangz
    39阅读
    0回复
    4点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页