2020HDU暑期多校第一场¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| N/A | 4 | 6 | 12 |
A¶
upsolved by
题意¶
题解¶
B¶
upsolved by
题意¶
题解¶
C¶
upsolved by
题意¶
题解¶
D¶
solved by 2sozx Bazoka13 JJLeo
题意¶
统计多少个长度为 \(n\) 的由小写字母构成的串 \(S\) 的回文子串数最少。
题解¶
\(n\le3\) 答案为 \(26^n\) ；\(n>3\) 答案为 \(A(26,3)\).
\(n\le3\) 时显然。\(n>3\) 时可以构造 \(abcabc\cdots\) 这样回文子串个数仅有三个，答案即为 \(A(26,3)\)
E¶
solved by 2sozx JJLeo
题意¶
给定 \(N,C,k\) 求 \(F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)\)，其中 \(F\) 为斐波那契数列。 \(N,C\le10^{18},k\le10^5\)
题解¶
斐波那契数列通项公式 \(F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)\) ，且 \(5\) 是 \(10^9+9\)的二次剩余，因此我们可以预处理出来 \(x=\frac{1}{\sqrt{5}},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}\)，对于所求的式子可以通过二项式展开来求
对于后面的求和显然可以通过等比数列求和公式计算，因此我们只需枚举 \(i=0\sim k\) 即可，注意特判公比为 \(1\) 的情况。
F¶
upsolved by JJLeo
题意¶
\(n\)个点\(m\)条边的无向图，每个点有一个权值，\(q\)次操作，每次更改一个点权值，或询问与一个点相邻所有点权值组成集合的\(\operatorname{mex}\)。\((n,m,q \le 10^5)\)
题解¶
将度数\(\ge \sqrt{n}\)的节点称为大节点，其它节点称作小节点。对于每个大节点开一个其对应度数大小的树状数组用于统计\(\operatorname{mex}\)（当然还需要一个相同大小的数组记录每个元素的出现次数）。当每个节点权值发生改变时，只需更改相邻的大节点。询问时，大节点直接用树状数组求\(\operatorname{mex}\)即可，小节点直接将相邻节点权值暴力排序求即可。
G¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
I¶
solved by 2sozx
题意¶
每个赛车有初始位置以及加速度，初速度是零，问那几辆车取得过暂时的第一，并列不算第一。\(N\le 50000\)
题解¶
此题加速度与速度的意义本质上是相同的，可以当做是一次函数，因此可以按照 \(p\) 从大到小排序，\(a\) 按照从大到小排序，之后单调栈即可。
J¶
upsolved by
题意¶
题解¶
K¶
upsolved by JJLeo
题意¶
求字符串每个前缀的最小后缀，多组数据。\(\sum|s| \le 2 \times 10^7\)
题解¶
对字符串进行Lyndon分解，考虑在Duval算法中三个下标的含义：\(i\)为\(s_2\)开头，\(j\)为\(s_3\)开头，\(k\)为当前考虑和\(j\)匹配的位置。如果\(s[k]=s[j]\)，说明\(s[k \cdots j]\)作为Lyndon串的一个循环同构，最小后缀不会出现在其中，只需将\(k\)对应的最下后缀下标进行位移即可，即此时最小后缀的下标\(pos[j]=pos[k]+j-k\)；如果\(s[k]<s[j]\)，此时\(s[i \cdots j]\)构成一个Lyndon串，因此\(pos[j]=i\)。另外，每次\(i\)变化后，可以得到\(pos[i]=i\)。进行上述三种维护即可。
L¶
solved by Bazoka13
题意¶
给一个凸多边形花园，手动除草需要费用\(A\)，用圆形除草机费用\(B\),使用除草机要确保圆始终在多边形内部，求最小费用。
题解¶
显然如果\(A \leq B\)的话可以直接手动除草，否则就把每条边向内垂直移动圆的半径的长度，求一个半平面交，没有交说明只能手动，有交就求出来交的面积\(+\)交的周长\(*\)圆的半径\(+\)圆的面积，手动面积用总面积减一下即可。
记录¶
-???min：听说这场题巨恶心
0min：分题看题
10+min：一起看D发现有规律，MJX冲D
18min：MJX WA
20min：MJX 发现输出格式出大问题，AC，MJX ZYF看 I
40+min：MJX冲I
53min：MJX WA2 后AC，ZYF 看K可做
81min：ZYF WA，CSK 看 L发现可做冲L
107min：CSK AC L，MJX ZYF开始疯狂冲E
290min：发现爆long long ，改用 __int128，开始CE
298min：WA n 后终于过了E
总结¶
- csk:这就是North Korea的题🐎，出了一道几何就做不动了，K题想到Lyndon但是没想到做法，这种平常没怎么见过的还是要补补
- MJX:这是MJX犯病的第二天，真就疯狂出问题。
- ZYF:这是ZYF划水的第一天，看来最近太摸鱼了。