Hdu暑期多校训练5

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

引入参数$$y$$原式可化为$$a=bx-py$$

然后由$$0 < a < b$$

得到$$bx-py > 0$$和$$bx-py < b$$

再分离变量得到$$\frac{b}{y} > \frac{p}{x}$$和$$\frac{b}{y} < \frac{p}{x-1}$$

然后这个取个倒数就是$$\frac{x-1}{p} < \frac{y}{b} < \frac{x}{p}$$

现在题目要求最小化$$b$$,法雷序列的模板解决

复杂度$$O(T \log n)$$

B

考虑建两个01Trie树,然后dfs统计答案

$$dfs(x,y)$$表示在a的Trie上到第$$x$$个点,b的Trie上到第$$y$$个点

每次先尝试同朝左、右子树走,如果子树中还有没用完的值,那么一左一右走

然后在叶子节点处合并

这个的复杂度可以这样计算:假设同左同右跑满,那每层是$$O(n \log n)$$

然后一左一右只会出现一种情况(A左B右或者A右B左),否则与最大化同左同右的贪心矛盾

然后这个可以$$T(n)=T(n/2)+O(n \log n)$$ , $$T(n)=O(n \log n)$$

C

D

考虑这是个分段函数,那么我们就求出分段点,然后维护系数解方程

手写分数类实现

E

小的爆搜

大的发现是$$n$$开头,后面next_permutation

F

exkmp模板题

G

考虑这条折线,一定是$$x->1->n->y$$的

然后$$x->1$$和$$n->y$$的方案唯一

因此只需要考虑中间$$x+1->y-1$$的方案

发现每三个格子有两种走法(三次向上走1或者上2下1上2)

然后可以得到递推关系$$f[i]=f[i-1]+f[i-3]$$

预处理这个东西就行了

H

$$n \leq 4$$ 时,一定可以

考虑如果存在对称,那么一定属于两种情况之一:相邻点或者间隔一个点

然后大力判,注意可能会出现共线、共点、自交等各种奇怪的情况

I

考虑用原根g的若干次方来表示a,b,即$$g^{aa}=a,g^{bb}=b$$,则问题转化成$$aa·x=bb(mod\ p-1)$$可以用扩展欧几里得解决,因此关键就在于如何得到aa,bb

因为$$p=2^{c_1}·3^{c_2}+1$$,所以采用神秘算法Pohlig-Hellman(密码学中的基础算法),考虑不停累乘使得最终得到1,从而得到aa,bb

J