2020-team12-035

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-0312standing.png, 1000px)]]
[[Image(2021-0312submissions.png, 1000px)]]




== 问题 ==

whn签到题没读彻底就上机导致罚时（记住像这样的题一题读10多分钟也正常，可以做笔记），ctc括号匹配写错导致莫名TLE。
有一些应该给whn的题目（博弈、几何）超出了whn的技能树……

== 题解 == 

A: 签到。

B: 签到，whn没有读清楚“输入错误只发生在调换前后数”，且不必要地将最后一个数与其他分开进行实现。

C: whn没能一眼看出来的签到：这种类似的连接结构要考虑每条传送带起点答案一定是区间。只需要对从左到右每条机械臂合并其连接的两个轨道的上下界即可。

D: 签到

E: 细节较多的暴力搜索，核心就是枚举8个字符分别对应的是什么然后结算等式是否合法。有处理括号和连续的负号这些细节，ctc遗憾没有写对括号匹配还因此遭遇奇怪TLE……

F: 思路较易，核心在于处理哪些”文件“中的边是要被加入的。以边为单位进行dfs。令g[i,j]表示两点是否有父子关系。那么dfs到一条边(u,v)时，需要加入①带有这条边的所有文件 ② 如果存在g[u0（可以等于u)][u]=1,那么每个v的儿子也应该是u0的儿子。完成以后判环即可，实现略有技巧。

G: 容易题，szb。

H: 读错题，较难树形DP，待补。

I: 思路较易，实现有些技巧的构造。可以想到两种比较优越的构造：(0,0),(n,m)加一个离对角线很近的点（用exgcd找）组成三角形， (0,0)(n-1,m)(n,m-1)加一个离原点很近的点（要在三角形内）组成凹四边形。
由于有时后一种构造会找不到(0,0)-(n,m)上的近点需要用前种构造。具体实现就是exgcd.

J: 确定圆心位置有三分套三分等方法，判多边形与圆的最大交技能点不足，需要日后学习。

K: 不对称博弈，技能点不足，需要日后学习。

[/wiki/2020-team12 返回]

问题

whn签到题没读彻底就上机导致罚时（记住像这样的题一题读10多分钟也正常，可以做笔记），ctc括号匹配写错导致莫名TLE。

有一些应该给whn的题目（博弈、几何）超出了whn的技能树……

题解

A: 签到。

B: 签到，whn没有读清楚“输入错误只发生在调换前后数”，且不必要地将最后一个数与其他分开进行实现。

C: whn没能一眼看出来的签到：这种类似的连接结构要考虑每条传送带起点答案一定是区间。只需要对从左到右每条机械臂合并其连接的两个轨道的上下界即可。

D: 签到

E: 细节较多的暴力搜索，核心就是枚举8个字符分别对应的是什么然后结算等式是否合法。有处理括号和连续的负号这些细节，ctc遗憾没有写对括号匹配还因此遭遇奇怪TLE……

F: 思路较易，核心在于处理哪些”文件“中的边是要被加入的。以边为单位进行dfs。令g[i,j]表示两点是否有父子关系。那么dfs到一条边(u,v)时，需要加入①带有这条边的所有文件 ② 如果存在g[u0（可以等于u)][u]=1,那么每个v的儿子也应该是u0的儿子。完成以后判环即可，实现略有技巧。

G: 容易题，szb。

H: 读错题，较难树形DP，待补。

I: 思路较易，实现有些技巧的构造。可以想到两种比较优越的构造：(0,0),(n,m)加一个离对角线很近的点（用exgcd找）组成三角形， (0,0)(n-1,m)(n,m-1)加一个离原点很近的点（要在三角形内）组成凹四边形。

由于有时后一种构造会找不到(0,0)-(n,m)上的近点需要用前种构造。具体实现就是exgcd.

J: 确定圆心位置有三分套三分等方法，判多边形与圆的最大交技能点不足，需要日后学习。

K: 不对称博弈，技能点不足，需要日后学习。

附加文件