2020-team12-033

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(210306-standing.png, 1000px)]]
[[Image(210306-submission.png, 1000px)]]
[[Image(210306-submission2.png, 1000px)]]



== 问题 ==

whn被long long搞错
szb对拍打的很迟，强制在线的操作处理没有读清楚。
ctcE题正确做法莫名一直wa。。，被whn重构一遍直接过了...

== 题解 == 

A:表面几何，实际上由于坐标点都是整数可能的对称轴只有横竖和两条45度对角线，加上ox,oy乘2的处理以后坐标一目了然。
考虑一个点出现在轮廓上当且仅当它出现在矩形上奇数次（被两个矩形夹在中心的哪些点是反例但是好像没关系）
找到横坐标最值lx,rx与纵坐标最值ly,ry,那么可能的四条对称轴就直接出来了（斜着的两条对称轴也会过可能的横竖对称轴交点）。判断每个在轮廓上的点是否有对应的对称点即可。
记住坐标：已知对称轴交点(ox,oy)， (则对应直线y=x+oy-ox和y=-x+oy+ox, 点(x,y)的对称坐标为(y-(oy-ox),x+(oy-ox)), (ox+oy-y,ox+oy-x)...

B:判断奇偶的博弈签到题

C:看起来像是点分治，然而没时间写。待补。

D:签到

E:思维+贪心，先发现每个数在剩下的里面只要成为“中位数”一定会留到最后，问题转化为能否在一个位置的左/右侧多消掉若干个比他大（或小）的数使得它成为中位数。
然后就在左右侧扫，设要消大数，则逢大数计数器+1，否则-1（因为被打断了可以直接消，相当于抵消掉一个大数），达到3消除数++，小于0清零，每个数左右区间各扫一遍即可。

F: 待补。

G: 签到

H: 待补

I: 按权值分块...szb题。考场中一度未正确处理强制在线的操作，且打对拍过迟；如果A题卡住很可能做不出。

J: 数位dp，已知前面位数和为k，则后面一个数对f(x)的贡献可以直接算，且对x的贡献也可以预处理10的幂直接算；dp[i][0/1][j][k]维护做到第i位，前面数和为j，f(x)与x模意义下的差值k即可。
由于不知道longlong和int差4倍常数考场上磨了一年。

K: 疑似网络流，待补。

[/wiki/2020-team12 返回]

问题

whn被long long搞错

szb对拍打的很迟，强制在线的操作处理没有读清楚。

ctcE题正确做法莫名一直wa。。，被whn重构一遍直接过了...

题解

A:表面几何，实际上由于坐标点都是整数可能的对称轴只有横竖和两条45度对角线，加上ox,oy乘2的处理以后坐标一目了然。

考虑一个点出现在轮廓上当且仅当它出现在矩形上奇数次（被两个矩形夹在中心的哪些点是反例但是好像没关系）

找到横坐标最值lx,rx与纵坐标最值ly,ry,那么可能的四条对称轴就直接出来了（斜着的两条对称轴也会过可能的横竖对称轴交点）。判断每个在轮廓上的点是否有对应的对称点即可。

记住坐标：已知对称轴交点(ox,oy)， (则对应直线y=x+oy-ox和y=-x+oy+ox, 点(x,y)的对称坐标为(y-(oy-ox),x+(oy-ox)), (ox+oy-y,ox+oy-x)...

B:判断奇偶的博弈签到题

C:看起来像是点分治，然而没时间写。待补。

D:签到

E:思维+贪心，先发现每个数在剩下的里面只要成为“中位数”一定会留到最后，问题转化为能否在一个位置的左/右侧多消掉若干个比他大（或小）的数使得它成为中位数。

然后就在左右侧扫，设要消大数，则逢大数计数器+1，否则-1（因为被打断了可以直接消，相当于抵消掉一个大数），达到3消除数++，小于0清零，每个数左右区间各扫一遍即可。

F: 待补。

G: 签到

H: 待补

I: 按权值分块...szb题。考场中一度未正确处理强制在线的操作，且打对拍过迟；如果A题卡住很可能做不出。

J: 数位dp，已知前面位数和为k，则后面一个数对f(x)的贡献可以直接算，且对x的贡献也可以预处理10的幂直接算；dp[i][0/1][j][k]维护做到第i位，前面数和为j，f(x)与x模意义下的差值k即可。

由于不知道longlong和int差4倍常数考场上磨了一年。

K: 疑似网络流，待补。

附加文件