文档章节

Codechef March Challenge 2020 Division 1 BREAK

o
 osc_t4kk3au7
发布于 07/01 14:41
字数 996
阅读 11
收藏 0

精选30+云产品,助力企业轻松上云!>>>

其他题看兔队的博客,我懒得更了(


Subtask 1 每一次丢最小的肯定不劣,证明似乎挺显然的来着。


Subtask 2.

先把 \(n \leq 2\) 的情况判掉,只需简单枚举若干情况。

对于 \(n \geq 3\),结论是存在方案的充要条件是以下条件无一成立:

  1. 不存在一个数出现大于等于 \(n+1\) 次;
  2. 先手手上的牌是最大的 \(n\) 张而且它们数字一样;
  3. 后手手上的牌是最小的 \(n\) 张而且它们数字一样。

首先这些条件有一成立则不存在方案是显然的。接下来考虑上述条件不成立时构造一组方案。

首先接下来构造的方案在一轮中双方只会各甩一张牌用于进入下一轮,所以最后一轮谁是先手是确定的。最后一轮的先手方显然更想要点数小的牌,所以我们认为最后一轮先手方倾向小点数、后手方倾向大点数。

在每一轮,如果这一轮先手的牌数不为 \(1\) 则如下操作:选择两个数 \(A<B\) 满足先手手上有至少一张 \(A\),双方手上至少有一张 \(B\),且去掉这两个数之后不存在数出现次数超过一半。后手手上有 \(B\) 的方案优先级更高,也就是尽可能选择 \(B\) 使得后手手上有 \(B\)。因为有上面条件的限制所以这总是可以做到的。接着双方把一张 \(A,B\) 暂时拿出,将先手剩余的牌中先手倾向性最大的牌和 \(A\) 留在手上,其余手牌送给后手,最后先手出一张 \(A\)、后手出一张 \(B\) 结束这个回合。


煮个栗子:第一轮先手和后手分别写在上下两行:

6 5 4
3 2 1

第一轮先手选择 \(A=4,B=6\),然后先手把 \(6\) 丢过去,然后先手丢 \(4\)、后手丢 \(6\) 结束当前回合;

第二轮先手选择 \(A=3,B=5\),然后先手把 \(1\) 丢过去(因为他倾向于更大的,也就是会倾向于 \(2\))丢过去,然后先手丢 \(3\)、后手丢 \(5\) 结束当前回合;

最后先手手上是 \(1\)、后手手上是 \(2\),直接丢完,达成平局。

注意到如果第二轮先手选择 \(A=1,B=2\) 也是合法的,但是这会导致最后一轮先手手上为 \(5\),就不合法了。


接下来解释其正确性。

注意到在第 \(1\) 轮之后第 \(1\) 轮先手手上只有 \(1\) 张牌。我们分两种情况进行讨论:

  • 如果第 \(1\) 轮先手手上的数是当前最大的数,那么接下来 \(B\) 一定等于他手上的数,那么在第 \(2\) 轮结束后,第 \(2\) 轮先手一定可以把剩余的牌中他最想要的牌拿在手上;
  • 如果第 \(1\) 轮先手手上的数不是当前最大的数,那么第 \(1\) 轮的 \(B\) 一定来自第 \(2\) 轮先手,那么在当前所有数中第 \(2\) 轮先手最想要的数一定在他手上,因为第 \(2\) 轮先手最想要的数是第 \(1\) 轮先手最不想要的。而按照上面的策略在第 \(2\) 轮结束后,第 \(2\) 轮先手一定可以把剩余的牌中他最想要的牌拿在手上。

注意到第 \(2\) 轮先手可以把他想要的牌拿在手上,而这张牌是第 \(1\) 轮先手最不想要的牌,故此时第 \(1\) 轮先手手上的牌中一定有他最想要的牌。那么仍然进行上面的操作,可以时刻保证双方最想要的牌均在他们的手上,这样在最后一个回合的时候,这个回合的先手方手上的数就一定比后手方小了。

o
粉丝 0
博文 53
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Codechef March Challenge 2020 Division 1 BREAK

其他题看兔队的博客,我懒得更了( Subtask 1 每一次丢最小的肯定不劣,证明似乎挺显然的来着。 Subtask 2. 先把 $n leq 2$ 的情况判掉,只需简单枚举若干情况。 对于 $n geq 3$,结论是存在...

osc_unnbi4yg
03/18
1
0
Codechef March Challenge 2020 Division 1 BREAK

其他题看兔队的博客,我懒得更了( Subtask 1 每一次丢最小的肯定不劣,证明似乎挺显然的来着。 Subtask 2. 先把 (n leq 2) 的情况判掉,只需简单枚举若干情况。 对于 (n geq 3),结论是存在...

cjoier_Itst
03/18
0
0
[科技] 假装是ETT的ETT

[科技] 假装是ETT的ETT [科技] 假装是ETT的ETT Codechef 的 April Challenge 2019 Division 1 的 Sonya and Queries 这题的$45$分部分分,似乎是一个出栈入栈序$ETT$,看着似乎还挺好的,就写...

osc_chydd7b8
2019/04/13
2
0
CodeChef---- February Challenge 2018----Points Inside A Polygon

链接:https://www.codechef.com/FEB18/problems/POINPOLY Points Inside A Polygon Problem Code: POINPOLY You are given a convex polygon with N vertices. You have to find any ⌊N/1......

osc_y4jbxqkl
2018/02/08
2
0
11个在线编码大赛,与全球程序员PK

 英文原文:10 Online Coding Contests For Programmers!   如果你拥有出色的编码技能,或者虽然你只是名初学者,但你愿意去锻炼自己的编码能力,愿意去和顶尖的编码者进行 PK,那么这篇文...

crystaltiger
2013/09/05
54
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka如何在千万级别时优化JVM GC问题?

大家都知道Kafka是一个高吞吐的消息队列,是大数据场景首选的消息队列,这种场景就意味着发送单位时间消息的量会特别的大,那既然如此巨大的数据量,kafka是如何支撑起如此庞大的数据量的分发...

hummerstudio
06/18
0
0
我打赌!90%程序员都破解不了这个粽子,不信你试!

放假了 各位读者朋友们,马上就是端午小长假啦,开心激动有木有? 新的故事文章还在创作中,写了初稿感觉不太满意又推倒重来。其实写故事还是挺难的,读者可能第一次第二次有新鲜感,写多了就...

轩辕之风
06/24
0
0
如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

前言 “删库跑路”是程序员经常谈起的话题,今天,我就要教大家如何删!库!跑!路! 开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解...

后端技术漫谈
01/14
0
0
PHP设计模式之代理模式

PHP设计模式之代理模式 代理人这个职业在中国有另外一个称呼,房产经济人、保险经济人,其实这个职业在国外都是叫做房产代理或者保险代理。顾名思义,就是由他们来帮我们处理这些对我们大部分...

硬核项目经理
2019/09/23
0
0
Redis的复制模式

Redis的复制功能分为同步(sync)和命令传播(command propagate)两个操作。 同步 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。 1. 旧版本的执行步骤 从服务器...

osc_s9cni3go
3分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部