2019-team666-0029

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2019-team666 返回]

== 概述 ==

solved:7/11 985 dirt:58%

rank:41/106

[http://10.71.10.90/pia/trac/wiki/2017-C07-team2 Legilimens]

[http://10.71.10.90/pia/trac/wiki/2017-C07-team1 Reconquista]

[[Image(Standings.jpg,800px)]]

[[Image(Submissions.jpg,800px)]]

== 流水账 ==

出门yyc签了A,'''A1y3''',然后跟榜，队友签了C、D，'''D1y30,C1y44'''。这时hyw和yyc讨论G题，遇到瓶颈，喊tjc来看，tjc给出了一种可行解，于是hyw写G，挂了一发以后tjc帮忙查出一个细节写的有问题，'''G2y75'''。这时yyc冲上去写I，顺便看到榜上B和H都过了一片，hyw和tjc讨论H，得到了一个很不好写的做法，于是先放着。这时yyc的I题wa了两次，hyw去看J，yyc和tjc讨论出了B题，tjc写B，'''B1y131'''。hyw有一个J的三分做法但感觉不一定对，而且很难写，于是也扔了。这时yyc看F，tjc和yyc接着讨论I，yyc冲上去写I又挂了两次。这时机位空了，也没有题可写，hyw给tjc讲了一下F的题意tjc，tjc想了一下不会做就去看K，hyw和yyc继续研究I，hyw想出了一个关于gcd的做法，机位空了20分钟以后hyw决定去打个I的表，发现gcd大的时候可能不好做。卡了半个小时I以后hyw因为开不出别的题继续想I，yyc去开E还是F，这时tjc想出了K，写了一会儿过了，'''K2y237'''。hyw把I的做法跟tjc讲了一下，tjc立刻想出了一个fix的方法，于是hyw上机重构I，中间因为细节一直过不了自己造的样例，后来又因为输出顺序原因wa了一发，最后'''I7y262'''。这时yyc上机写F，hyw重读了一遍E发现之前读的E假了，而且给出了做法，但是来不及写了。最后F没有写完。

== 总结 == 

=== yyc ===

呜呜呜我菜坏了...I题证明时思路不清晰，F赛后看题解有个小细节不对以外大致应该对了...

=== tjc  ===

难受啊。。I题没想出来啊。。

=== hyw  ===

这场后期比较崩的原因主要是H一直没有想到简单的做法，I题卡了好久，这两个题还是水平不够。间接导致E、F两个题开的太晚了，不过决策上也没大失误，主要还是菜，想出做法的时间太晚了。

吹一波神仙队友tjc搞出了神仙博弈题K，托队友的福小小踩了刚组队时的leg一题hhh

然后就是最近感觉经常遇到那种代码量极大的题？这种题我总是本能的会很害怕，可能还是要多写？

ps1.好像I这种整点相关的构造题都和gcd有关？今天算是碰巧想到才做出来，还是naive啊。

ps2.E的表达式求值对每种类型的元素写个parser orz fengsuiyan 


=== 题解 ===

A,B,C,D：签到

E：

F：

G：tjc给的方法很妙，复杂度可以均摊。题意就是一堆2的-k次方加和，超过1就把加数扔掉。考虑二进制，加数就暴力加，维护最左边开始连续1的个数（递增的，暴力扫，可以均摊），顺便维护二进制中1的个数，加数1的位置等于左边连续1的个数要特判，如果二进制1的个数=左边连续1的个数就说明这个和是0.11111000000....这样（用于特判和是否恰好为1）。其他情况如果加数的1的位置<左边连续1的个数那么肯定和超过1了。

H：

I:设题中给的数是x0,y0，题中限制条件即|x0*y-y0*x|<=50000。gcd(x0,y0)<=50000时，取(0,0)(x0,y0)和(x,y)，确定(x,y)的方法是解|(x0/gcd)*y-y0/(gcd)*x|=1，扩欧即可。gcd>50000时，取凹四边形(0,0)(x0,y0-1)(x0/gcd,y0/gcd)(x0-1,yy)。

J：

K：surreal number与非平等博弈。

定义：游戏状态x={L|R}=一个数，L为玩家A可以达到的所有状态构成的集合，R为玩家B可以到达的所有状态构成的集合。保留左集合中最大数和右集合中最小数。0={|}，x+1={x|}，x+1/2={x|x+1}，x+1/4={x|x+1/2}，依此类推（具体参见Conway的"On numbers and games"）

游戏局面之和等于对应数之和，公平等价于游戏局面的值为0。按定义计算出所有游戏的值后进行状压dp+meet in the middle计算答案即可。

本题只是非平等博弈中很小的一个部分。。。（太可怕了）

[/wiki/2019-team666 返回]

概述

solved:7/11 985 dirt:58%

rank:41/106

Legilimens

Reconquista

流水账

出门yyc签了A,A1y3,然后跟榜，队友签了C、D，D1y30,C1y44。这时hyw和yyc讨论G题，遇到瓶颈，喊tjc来看，tjc给出了一种可行解，于是hyw写G，挂了一发以后tjc帮忙查出一个细节写的有问题，G2y75。这时yyc冲上去写I，顺便看到榜上B和H都过了一片，hyw和tjc讨论H，得到了一个很不好写的做法，于是先放着。这时yyc的I题wa了两次，hyw去看J，yyc和tjc讨论出了B题，tjc写B，B1y131。hyw有一个J的三分做法但感觉不一定对，而且很难写，于是也扔了。这时yyc看F，tjc和yyc接着讨论I，yyc冲上去写I又挂了两次。这时机位空了，也没有题可写，hyw给tjc讲了一下F的题意tjc，tjc想了一下不会做就去看K，hyw和yyc继续研究I，hyw想出了一个关于gcd的做法，机位空了20分钟以后hyw决定去打个I的表，发现gcd大的时候可能不好做。卡了半个小时I以后hyw因为开不出别的题继续想I，yyc去开E还是F，这时tjc想出了K，写了一会儿过了，K2y237。hyw把I的做法跟tjc讲了一下，tjc立刻想出了一个fix的方法，于是hyw上机重构I，中间因为细节一直过不了自己造的样例，后来又因为输出顺序原因wa了一发，最后I7y262。这时yyc上机写F，hyw重读了一遍E发现之前读的E假了，而且给出了做法，但是来不及写了。最后F没有写完。

总结

yyc

呜呜呜我菜坏了...I题证明时思路不清晰，F赛后看题解有个小细节不对以外大致应该对了...

tjc

难受啊。。I题没想出来啊。。

hyw

这场后期比较崩的原因主要是H一直没有想到简单的做法，I题卡了好久，这两个题还是水平不够。间接导致E、F两个题开的太晚了，不过决策上也没大失误，主要还是菜，想出做法的时间太晚了。

吹一波神仙队友tjc搞出了神仙博弈题K，托队友的福小小踩了刚组队时的leg一题hhh

然后就是最近感觉经常遇到那种代码量极大的题？这种题我总是本能的会很害怕，可能还是要多写？

ps1.好像I这种整点相关的构造题都和gcd有关？今天算是碰巧想到才做出来，还是naive啊。

ps2.E的表达式求值对每种类型的元素写个parser orz fengsuiyan

题解

A,B,C,D：签到

E：

F：

G：tjc给的方法很妙，复杂度可以均摊。题意就是一堆2的-k次方加和，超过1就把加数扔掉。考虑二进制，加数就暴力加，维护最左边开始连续1的个数（递增的，暴力扫，可以均摊），顺便维护二进制中1的个数，加数1的位置等于左边连续1的个数要特判，如果二进制1的个数=左边连续1的个数就说明这个和是0.11111000000....这样（用于特判和是否恰好为1）。其他情况如果加数的1的位置<左边连续1的个数那么肯定和超过1了。

H：

I:设题中给的数是x0,y0，题中限制条件即|x0*y-y0*x|<=50000。gcd(x0,y0)<=50000时，取(0,0)(x0,y0)和(x,y)，确定(x,y)的方法是解|(x0/gcd)*y-y0/(gcd)*x|=1，扩欧即可。gcd>50000时，取凹四边形(0,0)(x0,y0-1)(x0/gcd,y0/gcd)(x0-1,yy)。

J：

K：surreal number与非平等博弈。

定义：游戏状态x={L|R}=一个数，L为玩家A可以达到的所有状态构成的集合，R为玩家B可以到达的所有状态构成的集合。保留左集合中最大数和右集合中最小数。0={|}，x+1={x|}，x+1/2={x|x+1}，x+1/4={x|x+1/2}，依此类推（具体参见Conway的"On numbers and games"）

游戏局面之和等于对应数之和，公平等价于游戏局面的值为0。按定义计算出所有游戏的值后进行状压dp+meet in the middle计算答案即可。

本题只是非平等博弈中很小的一个部分。。。（太可怕了）

附加文件