2020牛客暑期多校训练营第四场
链接
https://ac.nowcoder.com/acm/contest/15789
B Basic Gcd Problem
题意
定义 \[ f_c(x)= \begin{cases} max_{i=1}^n c\cdot f_c(\gcd(i,x)) &x\gt1\\ 1&x=1 \end{cases} \]
输入c和x
题解
f函数迭代次数越多，则值越大，也就是x取gcd的次数越多越好，所以每次选择x的最大因子即可。最终使用快速幂解决。
C Count New String
题意
给你一个字符串S，定义f(s,x,y)是一个字符串，长度为y-x+1，他的第k个字符串为\(max_{i=x,x+1...x+k}S_i\)
你要计算\(A=\lbrace f(f(s,x_1,y_1),x_2-x_1+1,y_2-x_1+1)| 1\le x_1\le x_2 \le y_2 \le y_1\le n \rbrace\)
题解
对于第一层而言，只需要考虑所有后缀即可。于是成了给你n个后缀，你需要计算这些后缀的本质不同的子串，由于后缀间的最长公共后缀很长，所以在后缀自动机上要记录每个后缀对应的last结点。从那个地方开始拓展即可。
F Finding the Order
题意
有两条平行线，一条上有AB两个点，另一条有CD两个点。
问你是AB与CD同向，还是AB与DC同向。
题解
考虑梯形ABCD，有\(AC+BD>AD+BC\)
考虑梯形ABDC，有\(AD+BC>AC+BD\)
H Harder Gcd Problem
题目描述
给你1到n这n个数，每个数只能用一次，你要选出m个数对，数对的两个数两两互素，问你最多选多少个数对。
数据范围
\(n<2\times10^5\)
题解
从大到小考虑奇素数p，取出他的所有倍数，可以证明，如果至少有两个，则一定有\(p\)和\(2p\), 如果有奇数个，则拿出2p，然后两两配对，如果有偶数个，则两两配对。
最后剩下来的一定全是偶数和一个1，直接两两配对即可。