2019-Sp046-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(1.png,700px)]]

[[Image(2.png,700px)]]


[wiki:2019-team2 返回Runespoor]


[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001482 contest]

== 流水账 ==


== 总结 ==

'''zqq: ''' 今天开场我们很崩溃。我的D题最简单的地方写错了，调了很久（因为那种数据只会在G满的时候出错，没有机时没有测这样的数据）。Heltion写B的构造也调了非常久。

            I题是我的锅，中途我都想到了容斥，但是没有仔细去想，认为是错的。其实我想I题的时间挺少的，一开始调D就给lyk想，后来写完E就直接写I了，就中途出去买咖啡想了一下。

            E题的方向一开始想对了，但是没有仔细往下想，后来思路就有点奇怪。

            I题最后竟然卡过去了。用32位机没有long long会变快。

            A，C都是可做的题，但是没有时间了。

            建议一开场调不出来题多和队友交流，我的D题是因为只有我会轮廓线dp所以只能自己调，建议Heltion再遇到类似的情况和lyk交流一下，或者直接让他来写，这样开场的节奏好很多。

            复杂度错误的东西虽然偶尔可以卡一卡，但是还是应该想更加正确的算法。

'''Heltion: ''' 看完B发现是个简单数逻题,然后很快在纸上画出了正解,数好了点数和边数,但不知道为什么加边的时候总是加漏边, 加了好多次终于加完了,

                然后发现式子推错了, 又加了一些点和边. 然后发现题目符号看反了,过了样例交了一发wa, 然后发现输入顺序看反了,终于过了.

                然后口胡了一个E的多一个O(kn^4^/64)的做法. 然后一起卡卡卡卡卡I.

                这两天都是开场看到能做的题懒得解释就自己直接上了, 然后过了很久下来发现已经凉了.

== 题解 ==

* A ：圆方树 + DP。 环上概率要两个方向分开算。超级好写。40min就写完了，除了没有判断无解几乎1A。但是今天没有时间写了

* B : 一个点入边权全是1000就是或门,一个点入边权全是-1000就是或非门,然后搞一搞,最后构造几个点使得1变成1,1/2变成0即可.

      zqq：主要难以想到的是构造一个常数（其实第一步我一个人也挺难想到，就是每个点有效输入只有0,1/2,1,但是还没有看题队友就告诉我了）。抓住 inf : 1 , 0 : 1 / 2 , -inf : 0的性质，把一个输入连两层inf就是常数1。之后就可以用这个1来构造或门和反相器（有常数就可以区分0和1/2,1和1/2）。写的时候要把所有东西都在草稿纸上画清楚，包括每一层怎么构造。然后把或和reverse封装成函数，减少可能犯的错误。

          然后要敢于交，要手画一个样例太麻烦了。所以我就直接交了。然而这道题真的很坑，他变量右边是1，左边是n，还好heltion WA 8了，所以我补的时候很顺利，总共30几分钟就过了。

* C : 观察样例可以发现轨迹有一些规律，大致就是从左到右，再从右到左。写一个dfs，从左到右和从右到左时，8个方向分别有各自的优先级（参照样例），进行dfs。打印出dfs到结果时，dfs树每一层选择的是第几个儿子，可以发现大部分时候就是选择的第一个儿子。找出这一串东西的规律即可。n较小时需要暴力。

* I ： '''三维偏序可以容斥！'''。直接统计二维偏序，每对三维偏序会被计算三次，二维偏序只会计算一次。复杂度一个log

 [wiki:2017-Sp263-team2 legilimens]

 * [https://icpc.camp/deep-dark-fantasy/20170501 DeepDarkFantasy]

 * [https://icpc.camp/wood-cube/Petrozavodsk%20Summer-2016%20Pavel%20Khaustov%202 WoodCube]

 * [https://icpc.camp/new-meta/2017/2/28%20Pavel%20Khaustov%20Contest%202 NewMeta]

== 补题 ==

* A ：zqq

* C : lyk

* G :

* H :

返回Runespoor

contest

流水账

总结

zqq: 今天开场我们很崩溃。我的D题最简单的地方写错了，调了很久（因为那种数据只会在G满的时候出错，没有机时没有测这样的数据）。Heltion写B的构造也调了非常久。

I题是我的锅，中途我都想到了容斥，但是没有仔细去想，认为是错的。其实我想I题的时间挺少的，一开始调D就给lyk想，后来写完E就直接写I了，就中途出去买咖啡想了一下。

E题的方向一开始想对了，但是没有仔细往下想，后来思路就有点奇怪。

I题最后竟然卡过去了。用32位机没有long long会变快。

A，C都是可做的题，但是没有时间了。

建议一开场调不出来题多和队友交流，我的D题是因为只有我会轮廓线dp所以只能自己调，建议Heltion再遇到类似的情况和lyk交流一下，或者直接让他来写，这样开场的节奏好很多。

复杂度错误的东西虽然偶尔可以卡一卡，但是还是应该想更加正确的算法。

Heltion: 看完B发现是个简单数逻题,然后很快在纸上画出了正解,数好了点数和边数,但不知道为什么加边的时候总是加漏边, 加了好多次终于加完了,

然后发现式子推错了, 又加了一些点和边. 然后发现题目符号看反了,过了样例交了一发wa, 然后发现输入顺序看反了,终于过了.

然后口胡了一个E的多一个O(kn4/64)的做法. 然后一起卡卡卡卡卡I.

这两天都是开场看到能做的题懒得解释就自己直接上了, 然后过了很久下来发现已经凉了.

题解

  • A ：圆方树 + DP。 环上概率要两个方向分开算。超级好写。40min就写完了，除了没有判断无解几乎1A。但是今天没有时间写了
  • B : 一个点入边权全是1000就是或门,一个点入边权全是-1000就是或非门,然后搞一搞,最后构造几个点使得1变成1,1/2变成0即可.

zqq：主要难以想到的是构造一个常数（其实第一步我一个人也挺难想到，就是每个点有效输入只有0,1/2,1,但是还没有看题队友就告诉我了）。抓住 inf : 1 , 0 : 1 / 2 , -inf : 0的性质，把一个输入连两层inf就是常数1。之后就可以用这个1来构造或门和反相器（有常数就可以区分0和1/2,1和1/2）。写的时候要把所有东西都在草稿纸上画清楚，包括每一层怎么构造。然后把或和reverse封装成函数，减少可能犯的错误。

然后要敢于交，要手画一个样例太麻烦了。所以我就直接交了。然而这道题真的很坑，他变量右边是1，左边是n，还好heltion WA 8了，所以我补的时候很顺利，总共30几分钟就过了。

  • C : 观察样例可以发现轨迹有一些规律，大致就是从左到右，再从右到左。写一个dfs，从左到右和从右到左时，8个方向分别有各自的优先级（参照样例），进行dfs。打印出dfs到结果时，dfs树每一层选择的是第几个儿子，可以发现大部分时候就是选择的第一个儿子。找出这一串东西的规律即可。n较小时需要暴力。
  • I ： 三维偏序可以容斥！。直接统计二维偏序，每对三维偏序会被计算三次，二维偏序只会计算一次。复杂度一个log

legilimens

补题

  • A ：zqq
  • C : lyk
  • G :
  • H :
附加文件