2020-team0x06-017

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team0x06 返回]

[[Image(Standings.png, 1000px)]][[BR]][[Image(Submissions.png, 600px)]]

== 概述 ==

2017 - ICPC - Shenyang

== 流水账 ==

开场跟榜，czyh'''I1Y5'''(FB)，lmh'''K2Y16'''。lmh写C写了一半发现不太会做，听了czyh的dp思路也不太靠谱，于是换czyh上机对F打表，'''F2Y54'''，fx'''L1Y59'''。czyh给M打表，lmh和fx讨论G，机上的czyh听着听着觉得他会做G了，lmh觉得靠谱。czyh把表打出来，两人找到了前一半规律，于是czyh先写G，lmh继续找后一半规律，'''G2Y113'''。lmh看着表一头雾水，完全找不到规律，于是和fx讨论起A，两人做了前一半，后一半不会做。czyh写完G，又找到了M的另一半规律，但还差一个问题没解决。两人均不会，求助fx，同样不会，czyh重新读了题，发现这个问题实际不存在，于是'''M1Y142'''(FB)。

期间fx和lmh讨论B，两人一步步把整个做法推出来了。此时无题可做，lmh打算捡起C，fx给他提供了一个贪心做法，lmh觉得靠谱于是上机去写。期间czyh和fx讨论了H，觉得可以写。lmh写完WA了，换czyh上机，lmh陆续改了几个小错误，但还是WA。

第4h，fx在纸上写B的分类讨论，lmh找fx修了C的做法，一直找不到问题，czyh在机上艰难地写写调调。封榜后czyh终于调过了样例，获得WA，改了改精度无果。lmh找到了cornercase，叉掉了fx的贪心，觉得应该沿着czyh的dp思路继续思考。lmh看了看czyh的debug过程，感觉这个保留6位小数没有spj，于是czyh修了-0.0就过了，'''H4Y261'''。

fx上机拿着写好的2张纸写B，lmh和czyh讨论C，czyh提了个n^5^的dp，明显过不了，lmh提了个n^4^的dp，觉得还可以。最后10min，fx自觉写不完，lmh写了写C，没过。

== 总结 ==

=== ntwbvdbl_oe ===

 * 《论如何给czyh喂题》

=== Orange_User ===

=== functionendless ===
似乎贡献莫名得少? 就想了个L,胡了个G,推了个B(还没时间写),搞了A但无用,C还是假的23333
不过没有大占机时开心..

== 题解 ==

A: 将16^n^乘到公式里，快速幂%(16*(8k+t))再/(8k+t)即可算出分数第n位，求出n到n+6位且维护进位即可

B: 1. fx的暴力做法: 成极大环则不为割边,两极大环中间部分全为割边. set维护竖线位置(pos),极大环起点位置(st),终点位置(en),BIT维护前缀横边(hor),竖边(ver)前缀和,注意下标的规定. 对着操作转移即可
  2.暴力的机智做法: 线段树维护某区间最左和最右的竖线, set维护上下两条都联通的极大区间,对询问维护即可(其实代码量差不多?)

C: 先按yx排序，枚举多边形底边上的点，将其下的点删去，将其余点极角排序，dp[k][j]表示最后一段折线为k-j的最大面积，有dp[k][j]=max{dp[l][k]+sijk}，'''注意共线情况'''

D: 

E:

F: 打表OEIS

G: 打表发现概率只和度数有关

H: 三国杀模拟（不取模真是**）

I: 签到

J: 

K: 签到

L: 可以很容易证明,对于某条边,只要它左子树size>=k且右子树size>=k,则这条边可计入答案

M: 先写个暴力，容易发现每个点的概率只和该点度数有关

[/wiki/2020-team0x06 返回]


概述

2017 - ICPC - Shenyang

流水账

开场跟榜，czyhI1Y5(FB)，lmhK2Y16。lmh写C写了一半发现不太会做，听了czyh的dp思路也不太靠谱，于是换czyh上机对F打表，F2Y54，fxL1Y59。czyh给M打表，lmh和fx讨论G，机上的czyh听着听着觉得他会做G了，lmh觉得靠谱。czyh把表打出来，两人找到了前一半规律，于是czyh先写G，lmh继续找后一半规律，G2Y113。lmh看着表一头雾水，完全找不到规律，于是和fx讨论起A，两人做了前一半，后一半不会做。czyh写完G，又找到了M的另一半规律，但还差一个问题没解决。两人均不会，求助fx，同样不会，czyh重新读了题，发现这个问题实际不存在，于是M1Y142(FB)。

期间fx和lmh讨论B，两人一步步把整个做法推出来了。此时无题可做，lmh打算捡起C，fx给他提供了一个贪心做法，lmh觉得靠谱于是上机去写。期间czyh和fx讨论了H，觉得可以写。lmh写完WA了，换czyh上机，lmh陆续改了几个小错误，但还是WA。

第4h，fx在纸上写B的分类讨论，lmh找fx修了C的做法，一直找不到问题，czyh在机上艰难地写写调调。封榜后czyh终于调过了样例，获得WA，改了改精度无果。lmh找到了cornercase，叉掉了fx的贪心，觉得应该沿着czyh的dp思路继续思考。lmh看了看czyh的debug过程，感觉这个保留6位小数没有spj，于是czyh修了-0.0就过了，H4Y261。

fx上机拿着写好的2张纸写B，lmh和czyh讨论C，czyh提了个n5的dp，明显过不了，lmh提了个n4的dp，觉得还可以。最后10min，fx自觉写不完，lmh写了写C，没过。

总结

ntwbvdbl_oe

  • 《论如何给czyh喂题》

Orange_User

functionendless

似乎贡献莫名得少? 就想了个L,胡了个G,推了个B(还没时间写),搞了A但无用,C还是假的23333

不过没有大占机时开心..

题解

A: 将16n乘到公式里，快速幂%(16*(8k+t))再/(8k+t)即可算出分数第n位，求出n到n+6位且维护进位即可

B: 1. fx的暴力做法: 成极大环则不为割边,两极大环中间部分全为割边. set维护竖线位置(pos),极大环起点位置(st),终点位置(en),BIT维护前缀横边(hor),竖边(ver)前缀和,注意下标的规定. 对着操作转移即可

2.暴力的机智做法: 线段树维护某区间最左和最右的竖线, set维护上下两条都联通的极大区间,对询问维护即可(其实代码量差不多?)

C: 先按yx排序，枚举多边形底边上的点，将其下的点删去，将其余点极角排序，dp[k][j]表示最后一段折线为k-j的最大面积，有dp[k][j]=max{dp[l][k]+sijk}，注意共线情况

D:

E:

F: 打表OEIS

G: 打表发现概率只和度数有关

H: 三国杀模拟（不取模真是**）

I: 签到

J:

K: 签到

L: 可以很容易证明,对于某条边,只要它左子树size>=k且右子树size>=k,则这条边可计入答案

M: 先写个暴力，容易发现每个点的概率只和该点度数有关

附加文件