DDOSvoid's Blog

题目描述

简要题意：给定一个 $n\times m$ 的矩阵 $X$ 和一个 $m\times n$ 的矩阵 $Y$，现在有 $q$ 次询问，每次询问给定 $u,v,d$，求 $\sum_{i=0}^d(XY)^i_{u,v}$

$n\le 1000,m\le 20, q\le 50$

题目描述

https://codeforces.com/problemset/problem/780/F

简要题意：给定一个有向图有自环无重边，边有两种类型 $0$ 和 $1$，求最长路径，如果最长路径大于 $1e18$ 则视为 $-1$，同时走到路径的边的类型有如下限制，$0$，$01$，$0110$，$01101001$，即长度为 $2^n$ 的路径是由长度为 $2^{n-1}$ 的路径和长度为 $2^{n-1}$ 取反拼接得到

$n\le 500,m\le 2n^2$

题目描述

https://www.luogu.com.cn/problem/P4299

简要题意：给定 $n$ 个点，现在有 $m$ 次操作，操作有三种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证连边后仍然是森林；第二种操作给定一个点 $x$，求 $x$ 所在连通块的重心，如果有两个重心输出编号较小的那个；第三种操作求所有连通块重心的编号的异或和

$n\le 10^5,m\le 2\times 10^5$

题目描述

https://loj.ac/p/6038

简要题意：现在有 $n$ 个点，同时有 $m$ 次操作，操作有两种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证加入边之后仍然是森林；第二种操作给定一个点 $x$，问 $x$ 所在的联通块内与它距离最远的点的距离

$n\le 3\times 10^5,m\le 5\times 10^5$，强制在线

例题

1. 简要题意：下边界有 $n$ 个给定点，上边界有 $m$ 个给定点，可以从任意一个点发出一条激光，激光碰到边界会反射，激光到达边界必须打到整数点，问最多可以打到几个给定点

   $n,m\le 10^5$

   简要题解：能够发现当固定起始点之后只需要确定间距 $T$

   注意到当 $T$ 含有大于 $1$ 的质因子的时候将其除掉之后一定能有更多的反射点

   所以我们只需要枚举间距点为 $2$ 的幂即可

   时间复杂度 $O(n\log^2 n)$

   CF 1041F Ray in the tube

2. 简要题意：给定整数 $x,a,b,p$，求有多少正整数 $n$，满足 $na^n\equiv b(\bmod p)$

   $2\le p\le 10^6+3,1\le a,b<p,1\le x\le10^{12}$，保证 $p$ 是素数

   简要题解：$na^n\equiv b(\bmod p)$，对于 $a^n$ 我们知道循环节肯定是 $\varphi(p)$，这里保证 $p$ 是素数，有 $\varphi(p)=p-1$

   对于 $n$，它的循环节显然是 $p$，那么我们知道 $na^n$ 的循环节就是 $p(p-1)$是，所以我们只需要求 $p(p-1)$ 内有多少合法的 $n$ 即可

   我们令 $n=k(p-1)+r,k\in[0,p-1],r\in[0,p-1]$

   那么 $na^n\equiv b(\bmod p)$ 可以得到 $k\equiv r-ba^{-r}(\bmod p)$，我们枚举 $r$，可以得到给定范围的 $k$，进而得到 $n$

   CF 919E Congruence Equation

3. 简要题意：现在有 $q$ 个询问，每次询问区间 $[l,r]$ 内有多少个满足条件的 $x=a^p(a>0,p>1)$

   $q\le 10^5,1\le l\le r\le 10^{18}$

   简要题解：首先将区间询问转换成前缀差分，然后我们发现对于 $p\ge 3$ 数会很少，大概是 $O(10^6)$，这个东西可以直接预处理，而对于 $p=2$ 的数，直接就等于 $\lfloor\sqrt n\rfloor$，注意 $cmath$ 自带的 $sqrt$ 精度不太行，可以手写一个二分来开根或者使用 $sqrtl$

   CF 955C Sad powers

4. 简要题意：现在有一个 $n\times m$ 的网格图，以及一个以 $(r_b,c_b)$ 为起点的机器人，机器人每一秒会走一步，其坐标的增量为 $(dr,dc)$，初始时 $dr=dc=1$，每当机器人撞到横向或者竖向的墙壁后，$dr$ 或者 $dc$ 会变成 $-1$，机器人在每个位置都有 $p$ 的概率探测与其在横坐标或者纵坐标相同的所有点，当机器人探测到目标点 $(r_d,c_d)$ 后结束，求期望时间

   $n\times m\le 10^5$

   简要题解：容易得到机器人的行动是有规律的，以 $lcm(n-1,m-1)$ 为一个循环，那么我们首先计算一个循环内期望，令其为 $tans$，同时一个循环内有 $k$ 次可能探测到目标点，第 $i$ 次的时间为 $t_i$，那么 $tans=\sum_{i=0}^{k-1}(1-p)^ipt_i=p\sum_{i=0}^{k-1}(1-p)^it_i$

   注意到第 $L$ 次循环的期望为 $(1-p)^{k(L-1)}\sum_{i=0}^{k-1}(1-p)^ip(t_i+(L-1)lcm)$

   化简一下得到 $(1-p)^{k(L-1)}(tans+(L-1)lcm\times p\sum_{i=0}^{k-1}(1-p)^i)$，同时我们令 $q=(1-p)^k$，那么最终答案

   $$\begin{aligned} ans&=\sum_{L=0}^{\infty}q^L(tans+L\times lcm\times p\sum_{i=0}^{k-1}(1-p)^i)\\ &=tans\sum_{L=0}^{\infty}q^L+lcm\times p\sum_{i=0}^{k-1}(1-p)^i\sum_{L=0}^{\infty}L\times q^L\\ &=\frac{1}{1-q}tans+lcm\times (1-(1-p)^k)\frac{q}{(1-q)^2} \end{aligned}$$

   注意到我们需要枚举一个循环内的所有可以探测到目标点的时间，所以时间复杂度为 $O(nm)$

   CF 1623D Robot Cleaner Revisit

5. 简要题意：给定一个长度为 $n$ 的数列 $a_i$，现在 $Alice$ 手上有一个数 $x$，$Bob$ 手上的数是 $x+3$，对于这个数列，每个人都从 $a_1$ 开始到 $a_n$ 按顺序操作，对于当前数 $a_i$，可以选择将手上的数 $x$ 加上 $a_i$，或者将 $x$ 异或上 $a_i$，现在给定一个数 $y$，求 $y$ 是 $Alice$ 操作得到的还是 $Bob$ 操作得到的，题目保证 $y$ 一定是其中一个人操作得到的

   $n\le 10^5$

   简要题解：注意到加法和异或对于数的奇偶性的影响是相同的，而 $Alice$ 和 $Bob$ 的两个数初始奇偶性就不同，所以我们从奇偶性出发判断就行了

   CF 1634B Fortune Telling

题目描述

https://www.luogu.com.cn/problem/P3513

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，求有多少种划分方案可以将这 $n$ 个点划分成两个集合 $S,T$，满足 $|S|,|T|\ge 1$ 且 $S$ 是一个团，$T$ 是一个独立集

$n\le 5000,m\le \frac{n\times (n-1)}{2}$

题目描述

https://uoj.ac/problem/188

简要题意：给定 $l,r$，求 $\sum_{i=l}^rf(i)$，其中 $f(i)$ 表示 $i$ 的非严格次大质因数，例如 $f(1)=1,f(3^2)=3$

$l,r\le 10^{11}$

题目描述

https://www.luogu.com.cn/problem/P3684

简要题意：给定一个 $n\times n$ 四连通网格图，有一些位置有障碍，现在有 $m$ 次询问，每次询问给定起点 $(x_1,y_1)$ 和终点 $(x_2, y_2)$，求一个最大的 $k$，满足存在一个从起点到终点的路径，使得路径上的每个点到离它最近的障碍点切比雪夫距离小于 $k$

$n\le 1000,m\le 3\times 10^5$

题目描述

https://codeforces.com/contest/1276/problem/F

简要题意：给定一个字符串 $S$，令字符串 $T_i$ 为 $S[1\cdots i-1]++S[i+1\cdots n]$，其中 $$ 为一个不同于 $[a,z]$ 的字符，求 $\lbrace S,T_1,\cdots,T_n\rbrace$ 的本质不同的子串个数

$|S|\le 10^5$

题目描述

https://codeforces.com/gym/102411/problem/L

简要题意：给定一个字符串 $S$，求其价值最大的子串的价值，定义一个字符串 $S$ 的价值为 $\frac{len(S)}{per(S)}$

$n\le 2\times 10^5$