====== 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题第一发是错解。