2011年省赛选拔组队系列赛1解题报告

随便写写,主要是E题。-by fatest

A:Treasure

模拟题目啊这是,我居然打了啊这是=。=

B:Driving Range

C:Frosh Week

逆序数,别人给了个模板我居然还sb的re+wa了9次,后来自己打了个归并排序求逆序反而一次A了。???逵猩瘛?

D:Fair Division

排序吧,我给每个人另外加了一个表示开始位置的项,然后,主按大小副按位置排序,从小到大减一下,再按位置排序,输出,ok。

E:Free Goodies

题目大意是有两个人,分N个物品,每个物品分别对两个人有不同的价值。两个人每次轮流从未被拿走的物品中拿走一个物品。规则是第一个人每次是拿剩下物品中对他而言价值最高的那个,如果有相同的就会拿那个对另外一个人价值最低的物品。另一个人是每次拿那个能保证他最后能拿到价值最大的物品,当然如果有多种选项的话也会优先选择那个对另外一个人价值最低的物品。现在告诉你物品和谁先拿,问最后两人分别能拿到多少?

显然第一个人的选择是很容易处理的,只要对物品进行一次排序,就可以保证第一个人是从头开始往后面取第一个没有被取走的物品。

第二个人就麻烦点了,因为物品是轮流取的,而他又不是必须按照一定的顺序来取,按照顺序一步一步的去判断每次取哪一个并不可取。所以我是直接贪心出他最后要取那些物品。以1表示他取这个位置的物品,0 表示不取,初始化为10101010....(或01010101....看谁先取)。然后注意到所有的1都可以和右边的0交换位置,并且保证交换后第二个人必定有方法可以取到所选择的物品(因为一开始的状态已经是极限的了)。我在这边就直接暴力N^2,枚举每个0位置,判断能否和它左边最小的满足条件的1交换,可以就交换,不可以就枚举下一个。完成后再统计一下两个人分别取的物品的价值之和。

F:Non-Decreasing Digits

DP+高精度,会java的无视,


G:CD

单纯的用归并比较一遍吧。

H:Celebrity Split



为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright © 2008-2025 (浙ICP备2022001332号), TZOJ. All Rights Reserved.
2017-2025 台州市非普软件技术有限公司,浙江省台州市君悦大厦B幢1603室