2020-team12-W2021-T0(Solo)
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[/wiki/2020-team12 返回]
== Ranklist ==
[[Image(cf1.png,800px)]]
[[Image(cf2.png,800px)]]
== 概述 ==
题解和反思：
A.
B.
C.
D.
E.
F.思路：想到要一位一位填并且每填一位算一下当前的前缀后面还有多少种方案、进行相减。
当时的思路：通过容斥推出了错排的结果f(5)=（5！-C(5,2)*f(2)-C(5,3)*f(3)...)，发现在题目这种会爆longlong的情况下无法做大数；又发现位置也很重要，会有些数不能被置为“pi=i”然后GG
实际上一位一位肯定没错，关键是要找到一种可以一块块加而非容斥的算式即可；并且还要至少先想到全貌而不是一个简单的错排。
f(n,m,k)表示n个位置，填出m个数，有k个数可以填出pi=i。 先发现f(n,m,k) = f(n-m,0,k-m) *C(k,m)，然后只需要考虑g(n,m)=f(n,0,m)
考虑取一个可以填成pi=i的位置p用除了会使得pi=i以外的n-1个数填，则k-1个可以pi=i的数填入一个会让状态变为g(n-1,m-2),n-k个不可的填入一个则会变为g(n-1,m-1)
得到通式g(n,m) = (m-1)*g(n-1,m-2)+(n-m)*g(n-1,m-1)
边界情况:m=1时g(n,m) = (n-m)*g(n-1,m-1); g(1,1)=0, g(0,0)=g(0,1)=1; 还有最重要的C(0，0）=1。 后面就是两重循环一位位填入。
G.
H.
I.
J.一个恒星提供两个函数，从角度a[i]开始向两边递减，因为地图是圆的关系，我们在经过0或2π时断裂，然后每个函数只要在开头记录s[i]结尾记录-s[i]用两个点保存，排序后，暴力算出0位置的答案，然后开始扫，用tots存当前的总系数，因为整个函数是由若干段一次函数组成，答案肯定在端点上，每次计算向下一个端点转移，保留最大值即可，注意2π不需要再算一次。
K.
L.
M.题目直接转化为求几个封闭的联通块，对于一个最小的菱形可以直接n^2^暴力求，稍大的联通块至少包含一个"."，观察发现规律"."与"."之间显然4联通，又因为在奇位上的符号只能是'\'或'/'，偶位反之那么当'.'四联通上是'\'该位置还与左上角和右下角联通,是'/'时，与右上角和左下角联通。直接bfs即可。注意有些直接与外界联通的联通块不需要统计进答案。[/wiki/2020-team12 返回]
Ranklist
/cf1.png)
/cf2.png)
概述
题解和反思：
A.
B.
C.
D.
E.
F.思路：想到要一位一位填并且每填一位算一下当前的前缀后面还有多少种方案、进行相减。
当时的思路：通过容斥推出了错排的结果f(5)=（5！-C(5,2)*f(2)-C(5,3)*f(3)...)，发现在题目这种会爆longlong的情况下无法做大数；又发现位置也很重要，会有些数不能被置为“pi=i”然后GG
实际上一位一位肯定没错，关键是要找到一种可以一块块加而非容斥的算式即可；并且还要至少先想到全貌而不是一个简单的错排。
f(n,m,k)表示n个位置，填出m个数，有k个数可以填出pi=i。 先发现f(n,m,k) = f(n-m,0,k-m) *C(k,m)，然后只需要考虑g(n,m)=f(n,0,m)
考虑取一个可以填成pi=i的位置p用除了会使得pi=i以外的n-1个数填，则k-1个可以pi=i的数填入一个会让状态变为g(n-1,m-2),n-k个不可的填入一个则会变为g(n-1,m-1)
得到通式g(n,m) = (m-1)*g(n-1,m-2)+(n-m)*g(n-1,m-1)
边界情况:m=1时g(n,m) = (n-m)*g(n-1,m-1); g(1,1)=0, g(0,0)=g(0,1)=1; 还有最重要的C(0，0）=1。 后面就是两重循环一位位填入。
G.
H.
I.
J.一个恒星提供两个函数，从角度a[i]开始向两边递减，因为地图是圆的关系，我们在经过0或2π时断裂，然后每个函数只要在开头记录s[i]结尾记录-s[i]用两个点保存，排序后，暴力算出0位置的答案，然后开始扫，用tots存当前的总系数，因为整个函数是由若干段一次函数组成，答案肯定在端点上，每次计算向下一个端点转移，保留最大值即可，注意2π不需要再算一次。
K.
L.
M.题目直接转化为求几个封闭的联通块，对于一个最小的菱形可以直接n2暴力求，稍大的联通块至少包含一个"."，观察发现规律"."与"."之间显然4联通，又因为在奇位上的符号只能是'\'或'/'，偶位反之那么当'.'四联通上是'\'该位置还与左上角和右下角联通,是'/'时，与右上角和左下角联通。直接bfs即可。注意有些直接与外界联通的联通块不需要统计进答案。