2021-team06-C210811

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210811-standings.png,800px)]]

== submission ==

[[Image(210811-submission3.png,800px)]]
[[Image(210811-submission2.png,800px)]]
[[Image(210811-submission1.png,800px)]]


== 概述 ==

solved: 12/15  dirt: 40%

rank: 5



==  ==

== 总结 ==

whn:
和第一场感觉差不多，大家虽有long long之类的小失误但基本做到了自己读出来的题可以自己完成。
N题因为zju的pollard-rho板子假了导致浪费了很多时间。事实上zju的板子是15年前就没在维护过的了，还是要准备自己的板子。
O题：分峰三分没博到*1...


== 题解 ==

A: 记f[x]表示当前有x个贴纸的期望步数，如果A>0，那么显然是从f[X+A]到f[X+B]转移过来，否则是从f[X]到f[X+B]转移，需要把等式右边的f[X]移过来化一两步式子。

B: 模拟。

C：待补

D：考虑对A正着做相邻差分+对M取模并倍长，B倒着做差分，然后每一对对m取模都相等就变成了b的差分数组和A匹配上n-1位，使用哈希或者KMP比较即可记录出有多少个变过的状态；比完以后，记dp[x][0/1]表示跳x步以后和或不和原序列相同的概率，矩阵乘法计算然后乘一下即可。

E：线段树合并

F：模拟

G：签到模拟

H：DP

I：简单树形DP。要想确定子树的值当且仅当自己和所有儿子的值只有一个不知道。记dp[x][0]表示不询问x的方案数，dp[x][1]表示询问x的方案数，则dp[x][1]可以由任意一个儿子取0,其他儿子取1后乘积而得，dp[x][0]既可以这样取得（最终由父亲节点那一侧确定），也可以由所有儿子取1取得。 

J：待补

K：在邻接矩阵意义下考虑问题。如果i已经有偶数条边，则最终划分出来的两组，和i的连边数必定奇偶相同，我们自然希望都为奇，于是置该行增广矩阵为1. 如果i有奇数条边，那么i的分类需要和奇数的相同，转化过来可以直接置a[i][i]为1.转化完以后高斯消元看看是否有解即可

L：签到

M：旋转坐标系以后二位数点

N：pollard-rho.

O: 由于每段贡献有一半区间是为0的线段，所以不能三分。考虑到最终的结果是某个单位向量对多边形的点积去除负值以后的结果，于是每条向量可以看成是对0到2pi上长度为pi的一段区间有一个覆盖贡献。扫描线维护并结算所有端点的答案即可。

[/wiki/2021-team6 返回]

Ranklist

submission

概述

solved: 12/15 dirt: 40%

rank: 5

总结

whn:

和第一场感觉差不多，大家虽有long long之类的小失误但基本做到了自己读出来的题可以自己完成。

N题因为zju的pollard-rho板子假了导致浪费了很多时间。事实上zju的板子是15年前就没在维护过的了，还是要准备自己的板子。

O题：分峰三分没博到*1...

题解

A: 记f[x]表示当前有x个贴纸的期望步数，如果A>0，那么显然是从f[X+A]到f[X+B]转移过来，否则是从f[X]到f[X+B]转移，需要把等式右边的f[X]移过来化一两步式子。

B: 模拟。

C：待补

D：考虑对A正着做相邻差分+对M取模并倍长，B倒着做差分，然后每一对对m取模都相等就变成了b的差分数组和A匹配上n-1位，使用哈希或者KMP比较即可记录出有多少个变过的状态；比完以后，记dp[x][0/1]表示跳x步以后和或不和原序列相同的概率，矩阵乘法计算然后乘一下即可。

E：线段树合并

F：模拟

G：签到模拟

H：DP

I：简单树形DP。要想确定子树的值当且仅当自己和所有儿子的值只有一个不知道。记dp[x][0]表示不询问x的方案数，dp[x][1]表示询问x的方案数，则dp[x][1]可以由任意一个儿子取0,其他儿子取1后乘积而得，dp[x][0]既可以这样取得（最终由父亲节点那一侧确定），也可以由所有儿子取1取得。

J：待补

K：在邻接矩阵意义下考虑问题。如果i已经有偶数条边，则最终划分出来的两组，和i的连边数必定奇偶相同，我们自然希望都为奇，于是置该行增广矩阵为1. 如果i有奇数条边，那么i的分类需要和奇数的相同，转化过来可以直接置a[i][i]为1.转化完以后高斯消元看看是否有解即可

L：签到

M：旋转坐标系以后二位数点

N：pollard-rho.

O: 由于每段贡献有一半区间是为0的线段，所以不能三分。考虑到最终的结果是某个单位向量对多边形的点积去除负值以后的结果，于是每条向量可以看成是对0到2pi上长度为pi的一段区间有一个覆盖贡献。扫描线维护并结算所有端点的答案即可。

附加文件