2016-2017 CT S03E05: Codeforces Trainings Season 3 Episode 5 (2016 Stanford Local Programming Contest, Extended)

感觉如果不把训练时的套题补一补,就会继续成为傻逼,所以开坑记录一下还不会做的题目,以及做的题目。

这套题比赛的时候,我们队出了7个题目,一共13个题目。不少队伍都AK了,所以表现的有点差。

当前进度:

5/13

Problem C: Card Collecting

题意:一共有种牌,每次有两种选择:1.选择张牌作为交换来得到张牌。可视为不花费时间。2.花费一小时时间,有的概率获得机会得到一个有张牌的卡包,的含义是当前你有种卡牌你就有的概率获胜。这个卡包里的牌的种类之间是相互独立的,也就是每张牌出现在这个卡包内的概率都可以视为。那么,问得到种牌最少的期望时间。

考虑期望dp,那么考虑设代表当前有种牌,有张多余的牌到集齐种牌的最小期望时间。那么根据题意,转移方式有两种,第一种是如果有大于等于张多余的牌的时候我们可以通过换牌得到一种新的牌。第二种就是我们可以花费一小时开卡包得到张牌。但是这样的话我们不能明确知道这张牌中到底有多少张已经拥有,或是新的卡牌。所以考虑给dp加一维,变成代表当前有种牌,有张多余的牌而且卡包剩余卡牌数目为的情况下到集齐种牌的最小期望时间。假如现在卡包里还有牌,也就是大于。那么我们肯定是要等这些卡的情况全部出现完,才会决定是否需要换牌策略。所以我们考虑只在的情况下才考虑换牌。那么dp转移方程就很简单了。

换牌:

抽卡(当卡包里还有牌的时候):。分成卡包里的第k张牌是否为新牌讨论。

抽卡(需要开一个新包的时候):是一个卡包的容量,此时等于

那么就可以做了。。。行吧,貌似大家都是暴搜的啊。。。。因为小于等于小于等于,所以最多张多余的牌就一定可以凑齐张卡牌。所以第二维最多。时间复杂度:。实际上这是最坏的情况。

 

Problem E: Election of Evil

题意:给出一个集合里面的人,这些人是可以被控制的。然后给出一个集合里面的人,以及个关系,告诉你可以控制,问集合中可以被控制的人,注意要按照字典序输出。

bfs一下。

 

Problem H: Hunter’s Apprentice

题意:给出个点组成的一个简单边形,简单多边形的定义是:两个相邻边都只有一个交点,没有重点。问这些点的顺序是否是按照顺时针还是逆时针的顺序给出的。

题意不清,不知道顺逆时针是针对什么而言的。。。。如果是针对多边形内一点,我们可以做叉积求面积和看最终是否大于0即可。总之题意不清,有点傻逼。。。

Problem I: Ingenious Lottery Tickets

题意:略。

傻逼模拟题。按照题意随便做做。

Problem J: Jurisdiction Disenchantment

题意:给出个点的坐标,现在需要你找一个最小的矩形框住大于一半的点。保证是一个奇数,,坐标都在之内。

其实就是要找一个矩形恰好框住个点,那么我们先按照x坐标排序,然后枚举矩形的左右端点,然后把这个矩形左右端点之间的所有点加入一个新数组,按照y排序,然后枚举最高点,在这个过程中维护最小的面积。

时间复杂度:

 

2016-2017 CT S03E05: Codeforces Trainings Season 3 Episode 5 (2016 Stanford Local Programming Contest, Extended)》上有2条评论

  1. Hannah

    大佬好强,请问可以带带我吗
    还有,可以要一下你们队伍过的A,D,F,G的题解吗?
    我真的好菜啊/哭

    回复
    1. kugwzk 文章作者

      抱歉我已经退役很久了…可能这套题当时的代码都找不到了,如果没有写在博客里就是可能当时我队友过的了。所以可能帮不到你了。

      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注