差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2022-2023:teams:kunkunkun:2022-codeforces-2 [2022/08/06 17:17]
sd_ltt 创建
+++ 2022-2023:teams:kunkunkun:2022-codeforces-2 [2022/09/01 22:09] (当前版本)
purplewonder
@@ 行 3: / 行 3: @@
 给出一个图，通过对于每个 $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题第一发是错解。

CVBB ACM Team

用户工具

站点工具

差别

页面工具