UOJ Round做题记录

~~我又懒的新建文章了~~

据说这些题还不错，就来做做。

【UR #1】缩进优化

对于确定的$x$，答案是：

$\sum_{i=1}^{n}\lfloor \frac{a_i}{x}\rfloor +a_i- \lfloor \frac{a_i}{x}\rfloor \cdot x$

也就是说要算$\sum \lfloor a_i/x\rfloor $。

其实只需要考虑题目给出来的模型就好了，每次枚举$k$，会对答案造成$\sum [a_i\geqslant kx]$的贡献，开个桶后缀和一下就可以$O(1)$求。

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

code。

【UR #1】外星人

设$f_i$表示当前值为$i$，并且$>i$的数全部处理完毕的方案数。

考虑枚举$j$，可以转移到$f_{i\bmod j}$，那么现在$(i\bmod j,i]$的数都不会影响答案了，可以随便填，乘个组合数就好了。

code。

【UR #2】猪猪侠再战括号序列

因为给了$n$次操作，可以考虑把序列构造成(((())))的形式。

每次找到最左边那个右括号，然后找到离它最近的右边的左括号，翻转这一段，这样最多只有$n$次操作。

显然翻转的右端点单调递增，注意到翻转的时候中间的一段全都是右括号，所以每次翻转只需要交换两个值，复杂度$O(n)$。

code。

【UR #3】核聚变反应强度

次大公约数就是$\gcd$除掉一个最小的质因子。

所以先把$a_1$分解，然后对后面先求个$\gcd$，然后拿质数从小到大试一下能不能除就好了。

code。

【UR #3】铀仓库

根据调整法容易得知选的点上必然有箱子。

考虑二分答案，问题转化成了求叠出$k$个箱子的最小时间。

注意到确定起点之后选的箱子一定是连续的一段，并且这段的左右端点随着起点的增加是单调递增的，所以可以用两个指针维护一下，顺便维护下两端的使用个数，因为两端不一定选满了。

计算答案可以把式子写出来之后，发现只需要维护$a_i$的前缀和和$a_i\cdot x_i$的前缀和即可。

复杂度$O(n\log (\sum a_i))$。

code。

【UR #4】元旦三侠的游戏

简单博弈题，直接爆搜加个记忆化就能过了。

注意特判下$b=1,a>\sqrt n$的情况，这种情况下只能$a$加一，那么状态数就被减少到了$\sqrt n$。

code。

【UR #4】元旦激光炮

好神奇的题啊，看了题解才会的。

考虑令$p=\lfloor \frac{k}{3}\rfloor$，然后对$a,b,c$都询问一遍$p$这个位置的值，假设最小的是$a$，显然$a$最大的排名为$3p-2$，那么就是说$a$及小于$a$的数都不可能是答案，所以我们可以直接删掉$a$的前$p$位，那么可以得到一个$k=k-p$的子问题。

当$k\leqslant 2$的时候直接暴力问就好了。

这样最多问$\lceil \log_{3/2} n\rceil +6$次，足矣通过此题。

code。

【UR #5】怎样提高智商

很有意思的构造题，如果我们每一道题都填A 0 0 0 0，答案就是$4\cdot 3^{n-1}$，因为除了最后一题其他的都有三种填法。

~~证明咕咕咕了，可以去看官方题解~~

code。

【UR #5】怎样跑得更快

感觉这种题都挺套路的。。。做起来还是比较简单的。

首先把式子变换一下，套一个莫反上去：

$\begin{align*} \sum_{j = 1}^{n} \gcd(i, j)^c \cdot {\rm lcm}(i, j)^d \cdot x_j &\equiv b_i \pmod{p}\\ \sum_{j=1}^{n} \gcd(i,j)^{c-d}~j^dx_j &\equiv \frac{b_i}{i^d} \pmod{p}\\ \sum_{w|i}^nw^{c-d}\sum_{j=1}^{n/w} j^dw^dx_{jw}[\gcd(i/w,j)=1]&\equiv \frac{b_i}{i^d} \pmod{p}\\ \sum_{w|i}^nw^{c}\sum_{j=1}^{n/w} j^dx_{jw}\sum_{t|i/w,t|j}\mu(t)&\equiv \frac{b_i}{i^d} \pmod{p}\\ \sum_{w|i}^nw^{c}\sum_{wt|i}\mu(t)t^d\sum_{j=1}^{n/wt} j^dx_{jwt}&\equiv \frac{b_i}{i^d} \pmod{p}\\ \sum_{T|i}\left(\sum_{w|T}^nw^{c-d}\mu(\frac{T}{w})T^d\right)\sum_{j=1}^{n/T}j^dx_{jT}&\equiv \frac{b_i}{i^d} \pmod{p}\\ \end{align*}$

都是比较好懂的变换就不说了。注意到前面一块可以预处理，设：

$f(T)=\sum_{w|T}^nw^{c-d}\mu(\frac{T}{w})T^d\\ g(T,x)=\sum_{j=1}^{n/T}j^dx_{jT}$

这一来式子就很简洁了：

$\sum_{T|i}f(T)g(T,x)\equiv \frac{b_i}{i^d} \pmod{p}$

我们把$f(T)g(T,x)$当做一个未知数，那么这就是一个系数都为$1$的方程，注意到每个方程左边未知量总和为$\sum n/i=O(n\log n)$，所以可以暴力解方程，代码大概是这样的：

1 2	for(int i=1;i<=n;i++) for(int j=i+i;j<=n;j+=i) g[j]-=g[i];

然后把$f(T)$的系数除掉之后，可以得到一个每个方程形如：

$\sum_{j=1}^{n/T}j^dx_{jT}=g(T,x)$

右边是知道的，左边也只有$O(n\log n)$个项，所以也可以暴力解，代码长这样（你就把它当伪代码好了）：

1 2	for(int i=n;i;i--) for(int j=i+i;j<=n;j+=i) g[i]-=g[j]*pow(j/i,d);

然后就做完了，复杂度$O(n\log n)$。

注意判无解情况，无解只有可能是某个方程变成了$0\cdot x=1$形式。

多解情况其实不需要管，如果出现了一个$0\cdot x=0$的方程，代码会自动附成$0$的 ~~总觉得这句话很奇怪，但是就是不知道该怎么说，就这样吧~~。

code。

【UR #6】破解密码

发现可以得到一堆的方程，观察一下可以发现这个方程很好解：只需要把第$i$个方程乘上$26$再减去第$i+1$个方程，可以得到：

$(26^n-1)x_i=26h_{i-1}-h_i$

然后写完交一发发现被卡成$50$分。。。看了数据才发现是少考虑了$26^n=1$的情况。

这种情况下$h_i=26h_{i-1}$，所以我们只需要构造一个字符串满足$h_0$就好了，可以发现后面的一定满足条件，那么我们直接$26$进制拆分即可。

code。

【UR #6】智商锁

太神啦，我完全没想法只好看题解了。

题解给出来的做法是真的神奇，我复述一下好了：

首先我们随机$1000$个$12$个点的联通无向图，利用矩阵树求出生成树个数，为了让生成树个数多一点，我们多随机点边，具体来说每条边有$0.8$的概率会被加入。

然后对于每个$k$，我么试图找到一个四元组满足他们乘起来等于$k$，这里直接利用折半搜索即可。

这个做法的正确性是极其接近$1$的，具体证明可以看原题解~~（证明咕咕咕了）~~。

code。

【UR #7】水题生成器

我太菜了又不会做。。

看了题解发现我之前想的贪心是对的。。。就是说把约数全部搞出来然后从大到小贪心，能加就加，这样加的次数一定不超过$n$。

然后有一种更好的解法，考虑一个叫【反阶乘进位制】的东西，其实很好理解，就是说第$k$位的位值为$n^{\underline k}$，也就是下降幂 ~~所以我觉得这玩意叫下降幂进位制是不是更好~~，那么这个数可以分解成$\sum_{i=0}^{n}a_i\cdot n^{\underline i}$，显然可以知道$a_i<n-i$，否则可以进位。根据这个也很容易证明上面的贪心。

code。