用户工具

站点工具


2022-2023:teams:kunkunkun:2022-codeforces-2

2022-2023 BUAA XCPC Team Supplementary Training 02

E-Export Estimate

给出一个图,通过对于每个 $p$ 通过特定的规则缩点,问每次缩点后图中的点和边的个数。
注意到第二种规则中 $i$ 点删去后 $a,b$ 的度数不会变化,对于每个点储存其连接的边中前三大的边,记为 $a\le b\le c$,当 $p\in (a,b]\cup (c,+\infty)$ 时该点会被删掉,特别的, 当 $p\in(a,b]$ 时还会额外删掉一条边,分别记录 $p\in(a,b],p\in(c,+\infty)$ 以及小于 $p$ 的边数,可以得到答案。当图中出现简单环时会使得环缩为一个带自环的点,倒序枚举 $p$ 预处理每个 $p$ 对应的简单环即可。

F

题目大意:给定一个$n\times n$的矩形$F[i][j]$,给定$F[1][i]$和$F[i][1]$的所有值,给定递推式 $$ F[i][j]=a*F[i][j-1]+b*F[i-1][j]+c $$ 求$F[n][n]$

可以单独考虑每个格子对$F[n][n]$的贡献

$F[1][1]$没有贡献

对于$F[1][i]$来说,贡献为

$$ C_{2*n-i-2}^{n-i}*F[1][i]*a^{n-i}*b^{n-1} $$

对于$F[i][1]$来说,贡献为

$$ C_{2*n-i-2}^{n-i}*F[i][1]*a^{n-1}*b^{n-i} $$

对于$F[i][j]$来说,贡献为 $$ c*C_{2*n-i-j}^{n-i}*a^{n-j}*b^{n-i} $$

前两部分的贡献可以直接算,第三部分的贡献如下 $$ \sum_{i=2}^n\sum_{j=2}^nc*C_{2*n-i-j}^{n-i}*a^{n-j}*b^{n-i}=c*\sum_{i=0}^{n-2}\sum_{j=0}^{n-2}C_{i+j}^i*a^i*b^j $$ 可以使用NTT求得答案

I

题目大意:给定二维平面内$n$个半径小于$1$的不相交的圆,有$q$次询问

每次询问给定一条线段,求线段与多少圆相交

平面很小,圆的半径也很小,可以直接枚举所有与线段距离不超过$1$的点,判断以该点为圆心的圆是否与线段相交

Replay

A和D都是偏签到的题目。

罗皓天发现E很可做,于是和高湘一一起跑去做了。没过多久也过了。

B题总有一种既视感,以为之前做过,但是始终想不到什么合理的做法。最后整了一个比较调和级数的解,然后就过了。

K题最开始也是没怎么想,直接拍了一个错解上去。之后仔细思考想清楚之后就过了。

越发感觉到,想清楚再写代码的重要性。简单来说就是不要急()

高湘一推出了F的式子,然后跑去大力搞F。然后我和罗皓天看着H题发愣。因为计算几何一般来说是高湘一做的。

这也算是体现了由一个人主要写题这个战术的优势吧,至少不会出现看着题目发呆的情况。

最后还是自己推了下式子,打算强推掉H。虽然写出来了,但是很丑陋,并且花了不少时间和罚时。果然不太能写计算几何。

F高湘一到最后也没过。

这场因为打的实在不咋样,所以后来开了个会,调整了一下战略。

之后的主要想法就是题目主要由我来写。一些我不太清楚的算法,再由两位队友负责。如果从比较贪心的思路来看的话,这样的战略算是比较合理的。去年打到后面我总是会出现很累状态下降的情况,但是至少今年到现在还没太明显有这样的趋势。大概已经习惯打五个小时的比赛了吧。如果有肯德基吃就更好了。

虽然调整战略之后,的确战绩比之前要好,不过如果从十二场全部打完之后复盘来看的话,似乎也很难说战绩变好了是调整战术的原因。没准就只是运气变好了,碰到更适合的题目而已。

Dirt

H题第一发求dy(斜率)的时候忘了除以x了。之后一直在调精度和eps。只能说的确做这种题不太熟练,犯了些比较低级的错误。

K题第一发是错解。

2022-2023/teams/kunkunkun/2022-codeforces-2.txt · 最后更改: 2022/09/01 22:09 由 purplewonder