2021“MINIEYE杯”中国大学生算法设计超级联赛(8) 杭电多校8 题解

打到一半听教练说是学弟出的题... orz学弟tql~ ## 目录 | 题号 | 题目 | 知识点 | 完成度 | | ---- | ------------------------------------------------------------ | ------ | ------------------------ | | 1003 | HDU7058 [Ink on paper](https://acm.hdu.edu.cn/showproblem.php?pid=7058) | - | - | | 1009 | HDU7064 [Singing Superstar](https://acm.hdu.edu.cn/showproblem.php?pid=7064) | AC自动机/字符串哈希 | √ | | 1004 | HDU7059 [Counting Stars](https://acm.hdu.edu.cn/showproblem.php?pid=7059) | 线段树 | - | | 1008 | HDU7063 [Square Card](https://acm.hdu.edu.cn/showproblem.php?pid=7063) | 计算几何 | √ | | 1005 | HDU7060 [Separated Number](https://acm.hdu.edu.cn/showproblem.php?pid=7060) | - | - | | 1002 | HDU7057 [Buying Snacks](https://acm.hdu.edu.cn/showproblem.php?pid=7057) | - | - | | 1001 | HDU7056 [X-liked Counting](https://acm.hdu.edu.cn/showproblem.php?pid=6994) | - | - | | 1010 | HDU7065 [Yinyang](https://acm.hdu.edu.cn/showproblem.php?pid=7065) | x | x | | 1007 | HDU7062 [A Simple Problem](https://acm.hdu.edu.cn/showproblem.php?pid=7062) | x | x | ## 1009 HDU7064 [Singing Superstar](https://acm.hdu.edu.cn/showproblem.php?pid=7064) ### 题意 已知一个歌词串（匹配串） $s(1\le|s|\le10^5)$ ， $n$ 个 $SuperstarWords$ （模式串），问每个模式串在匹配串中不相交出现了多少次。 ### 思路1 - 字符串哈希 对母串中所有长度小于等于30的串做字符串哈希，对相同哈希值的串暴力统计答案，每个询问直接查询对应哈希值的答案，然而我换了好多模数都没对，遂放弃 ### 思路2 - AC自动机 我们知道 `KMP` 能进行单模式串的字符串匹配，但有多个模式串时，便需要使用AC自动机来解决。 简单介绍一下 `AC` 自动机，他是在 `trie` 树上跑 `KMP` ，也就是计算出 `trie` 树上的 $next$ 数组——即 $fail$ 失配数组，然后在 `trie` 树上失配后便可以调到 $fail$ 数组所指的位置。 本题需要注意的是，他要求匹配到的模式串两两不相交，那么也就是说匹配到后要看看是不是和上次重叠，用数组存一下上次的位置即可解决。 相关链接：[P5357 【模板】AC自动机（二次加强版）](https://www.luogu.com.cn/problem/P5357) ### code - AC自动机 ```cpp #include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 1e6 + 7; int t, n, trie[maxn][26], ok[maxn], top, fail[maxn], ans[maxn], len[maxn], lst[maxn], orz[maxn]; char ss[maxn], sq[maxn]; inline void insert(char *s, int j) { int now = 0; for (register int i = 0; s[i]; i++) if (!trie[now][s[i] - 'a']) now = trie[now][s[i] - 'a'] = ++top; else now = trie[now][s[i] - 'a']; len[j] = strlen(s); lst[j] = -1; ans[j] = 0; if (ok[now]) orz[j] = ok[now]; else orz[j] = 0, ok[now] = j; } queue<int> Q; inline void build() { for (register int i = 0; i < 26; i++) if (trie[0][i]) Q.push(trie[0][i]); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (register int i = 0; i < 26; i++) if (trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i], Q.push(trie[u][i]); else trie[u][i] = trie[fail[u]][i]; } } inline void query(char *s) { int now = 0; for (register int i = 0; s[i]; i++) { now = trie[now][s[i] - 'a']; for (register int j = now; j; j = fail[j]) { if (ok[j] && lst[ok[j]] + len[ok[j]] <= i) ans[ok[j]]++, lst[ok[j]] = i; } } for (int i = 1; i <= n; ++i) if (orz[i]) printf("%d\n", ans[orz[i]]); else printf("%d\n", ans[i]); } int main() { for (scanf("%d", &t); t--;) { for (int i = 1; i <= top; ++i) fail[i] = 0, ok[i] = 0; top = 0; memset(trie, 0, sizeof(trie)); scanf("%s", &sq); scanf("%d", &n); for (register int i = 1; i <= n; i++) scanf("%s", &ss), insert(ss, i); build(); query(sq); } return 0; } ``` ## 1008 HDU7063 [Square Card](https://acm.hdu.edu.cn/showproblem.php?pid=7063) ### 题意 平面上有两个圆 $\odot S,\odot B$ ，现在将边长为 $a$ 的正方形卡片随机扔向平面，然后进行自转，如果某一时刻卡片严格在 $S$ 中，则得分，如果某一时刻卡片严格在 $B$ 中，则有钱拿。如果求得分且有钱拿的概率与得分的概率之比。 ### 思路 首先，根据正方体自转的性质，不难发现所有严格在圆内的正方体中心可以围成一个小一点的圆，那么我么只要计算正方体中心是否在这个小一点的圆内即可判断是否有一时刻严格在圆内。 小圆的计算可以如下图：  粉色线即为 $r$ ，蓝色线为 ${a\over \sqrt 2}$ ，红点角大小为 $145^\circ$，绿色线 $x$ 即为所求。 根据余弦定理，可得： $$ \begin{aligned} \cos 145^\circ &= \frac{({a\over \sqrt 2})^2+x^2-r^2}{2\times x\times {a\over \sqrt 2}}\\ x &={{\sqrt{4 \times r^2 - a^2} - a} \over 2} \end{aligned} $$ 显然得分且有钱拿对应两个小圆交 $S'\cap B'$ 的面积，得分对应圆 $B'$ 的面积。 要注意几个特殊情况： - 两个小圆都不存在（这里也分两种情况，一种是开方前就为负，一种是算出半径来为负） - $S'$ 圆半径为0，且在 $B$ 圆内 ### code ```cpp #include <cmath> #include <cstdio> using namespace std; int t; double r[4], x[2], y[2], a; #define pi acos(-1.0) typedef struct node { double x; double y; } point; double AREA(point a, double r1, point b, double r2) { double d = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); if (d >= r1 + r2) return 0; if (r1 > r2) { double tmp = r1; r1 = r2; r2 = tmp; } if (r2 - r1 >= d) return pi * r1 * r1; double ang1 = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d)); double ang2 = acos((r2 * r2 + d * d - r1 * r1) / (2 * r2 * d)); return ang1 * r1 * r1 + ang2 * r2 * r2 - r1 * d * sin(ang1); } int main() { for (scanf("%d", &t); t--;) { scanf("%lf%lf%lf", &r[0], &x[0], &y[0]); scanf("%lf%lf%lf", &r[1], &x[1], &y[1]); scanf("%lf", &a); if (r[0] * 2 < a || r[1] * 2 < a) { puts("0.000000"); continue; } double r1 = (sqrt(4 * r[0] * r[0] - a * a) - a) / 2; double r2 = (sqrt(4 * r[1] * r[1] - a * a) - a) / 2; if (r1 < 0 || r2 < 0) { puts("0.000000"); continue; } if (r1 == 0 && r2 * r2 >= (x[0] - x[1]) * (x[0] - x[1]) + (y[0] - y[1]) * (y[0] - y[1])) { puts("1.000000"); continue; } printf("%lf\n", AREA({x[0], y[0]}, r1, {x[1], y[1]}, r2) / (pi * r1 * r1)); } } ```