专题题解 - XR-4

本场比赛平均质量尚可，难度比之前想象中简单一些。

设计一道提交答案题作为正题以外的消遣，这一点我认为是很好的，虽然我暂且不打算写那题。

打 * 号表示没有写的题，可能是不打算写了，也可能是暂时没来得及写。

---

A. 模拟赛

难度：$\bigstar$

题目大意：

有 $n$ 个人在 $k$ 天中分别按顺序做 $m$ 套模拟赛，给定每个人做每套题的时间，求每天需要准备多少套模拟赛。

$1\leq n,k,m\leq 1000$

题目解法：

模拟，时间复杂度为 $O((n+k)m)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int n,m,k,a[MAXN][MAXN],b[MAXN][MAXN];
int main () {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			scanf("%d",&a[i][j]);
			b[a[i][j]][j]=1;
		}
	}
	for (int i=1;i<=k;i++) {
		int ans=0;
		for (int j=1;j<=m;j++) {if (b[i][j]) {ans++;}}
		printf("%d ",ans);
	}
	printf("\n");
	return 0;
}

---

B. 歌唱比赛

难度：$\bigstar$

题目大意：

给定长度为 $n$ 的由 $\texttt{X,Y,Z}$ 构成的字符串 $S$，构造两个十进制下 $n$ 位的可以有前导零的自然数 $x,y$（或报告无解），满足：

• $S$ 的第 $n-i+1$ 位为 $\texttt{X}$ 当且仅当 $x$ 的最后 $i$ 位构成的数比 $y$ 的最后 $i$ 位构成的数大；
• $S$ 的第 $n-i+1$ 位为 $\texttt{Y}$ 当且仅当 $x$ 的最后 $i$ 位构成的数比 $y$ 的最后 $i$ 位构成的数小；
• $S$ 的第 $n-i+1$ 位为 $\texttt{Z}$ 当且仅当 $x$ 的最后 $i$ 位构成的数和 $y$ 的最后 $i$ 位构成的数一样大；

$1\leq n\leq 10^6$

题目解法：

有解当且仅当 $\texttt{Z}$ 所在位置构成一段后缀，仅使用 $0,1$ 就可以完成构造，时间复杂度为 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
char c[MAXN],a[MAXN],b[MAXN];
int main () {
	scanf("%s",c+1);
	int flg=1,n=strlen(c+1);
	for (int i=n;i>=1;i--) {
		if (c[i]!='Z') {flg=0;}
		if (flg==0&&c[i]=='Z') {printf("-1\n");return 0;}
		a[i]=(c[i]=='X')+'0',b[i]=(c[i]=='Y')+'0';
	}
	for (int i=1;i<=n;i++) {putchar(a[i]);}
	putchar('\n');
	for (int i=1;i<=n;i++) {putchar(b[i]);}
	putchar('\n');
	return 0;
}

---

C. 题

难度：$\bigstar$

题目大意：

给定自然数 $a,b$，求自然数对 $(x,y)$ 的数量（或报告有无穷多组），使得：$y^2-x^2=ax+b$。

$a\leq 10^8, b\leq 10^{15}$

题目解法：

枚举 $c=y-x$，那么 $2cx+c^2=ax+b$，也就是 $(2c-a)x=b-c^2$，如果 $2c-a=b-c^2=0$ 则有无穷组解，否则若 $(2c-a)(b-c^2)\ge 0$ 且 $(2c-a)\mid b-c^2$，那么就找到了一组解 $(\dfrac{b-c^2}{2c-a},\dfrac{b-c^2}{2c-a}+c)$。

注意到 $2c\leq a$ 或 $c^2\leq b$ 至少有一成立，时间复杂度为 $O(a+\sqrt b)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,ans;
int main () {
	scanf("%lld%lld",&a,&b);
	for (ll i=0;i<=50000000;i++) {
		ll c=2*i-a,d=b-i*i;
		if (c==0&&d==0) {printf("inf\n");return 0;}
		if (c<=0&&d>0) {continue;}
		if (c>=0&&d<0) {continue;}
		if (d%c==0) {ans++;}
	}
	printf("%lld\n",ans);
	return 0;
}

---

D. 复读

难度：$\bigstar\bigstar$

题目大意：

有一个无穷高度的满二叉树，给定其中一个包含根结点 $1$ 的大小为 $n$ 的连通块，你可以设定一个由 $\texttt{L,R,D}$ 三种指令构成的指令序列，一个机器人会从根出发，按顺序执行序列中的指令，执行完最后一条指令后会回到第一条指令，并一直这样循环：

• 指令 $\texttt{L}$ 表示走到当前点的左儿子；
• 指令 $\texttt{R}$ 表示走到当前点的右儿子；
• 指令 $\texttt{U}$ 表示走到当前点的父结点。

你需要保证机器人在根时不会遇到 $\texttt{U}$ 指令。

求出使得机器人到达给定连通块中所有点至少一次的最短指令序列长度。

$2\leq n\leq 2000$

题目解法：

首先有一个显然的结论：若从 $x$ 出发循环执行指令序列，那么机器人所处点永远在 $x$ 子树内部（否则从 $1$ 出发就不合法了）。

设从 $x$ 出发执行一轮指令后到达 $f(x)$，如果 $f(x)=x$ 那么 $f(1)=1$，也就是一轮就走完了所有点，那么我们不妨将 $f(1)$ 改为路径中的倒数第二个点，这样就少走了一步，所以最优指令序列一定有 $f(x)\ne x$。

那么我们又有一个观察：可以假设从 $x$ 出发执行一轮指令的过程中不经过 $f(x)$ 子树中的点（这是因为，否则我们可以将这个指令序列调整成等价等长而且符合该条件的序列）。

设以 $x$ 为根的子树是 $Sub(x)$。根据以上观察，从 $1$ 出发执行一轮指令需要经过 $Sub(1)-Sub(f(1))$ 中所有点，而从 $f(1)$ 出发的第二轮指令需要经过 $Sub(f(1))-Sub(f(f(1)))$ 中的所有点，以此类推。

为了找到最短的序列，我们可以将 $Sub(1)-Sub(f(1)), Sub(f(1))-Sub(f(f(1))),\ldots$ 这些子树叠合起来，使对应位置的点重合然后求“并”，得到的这个树假设有 $a$ 个结点，而 $f(1)$ 到 $1$ 的距离为 $b$，计算得序列长度为 $2\times a-b$。

枚举所有的 $f(1)$ 将答案取 $\min$ 即可，具体实现时只要通过 DFS 就可以完成子树并的计算。

事件复杂度为 $O(n^2)$。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2021;
int n,tot,cnt,nw,chn,siz,rt,ans,f[MAXN],ch[MAXN][2],th[MAXN][2],a[MAXN],b[MAXN],vis[MAXN];
char c[MAXN];
void dfs (int x) {
	if (c[nw]=='0') {nw++;return;}
	if (c[nw]=='1') {
		nw++;
		ch[x][0]=++tot;
		f[tot]=x;
		dfs(tot);
		return;
	}
	if (c[nw]=='2') {
		nw++;
		ch[x][1]=++tot;
		f[tot]=x;
		dfs(tot);
		return;
	}
	nw++;
	ch[x][0]=++tot;
	f[tot]=x;
	dfs(tot);
	ch[x][1]=++tot;
	f[tot]=x;
	dfs(tot);
	return;
}
void dfs2 (int x,int &rt) {
	if (!rt) {rt=++cnt;}
	//cout << "  " << x << "  " << rt << endl;
	if (ch[x][0]&&!vis[ch[x][0]]) {dfs2(ch[x][0],th[rt][0]);}
	if (ch[x][1]&&!vis[ch[x][1]]) {dfs2(ch[x][1],th[rt][1]);}
	return;
}
int main () {
	scanf("%s",c+1);
	n=strlen(c+1),nw=1;
	dfs(tot=1);
	ans=1e9;
	for (int i=2;i<=tot;i++) {
		chn=cnt=siz=rt=0;
		memset(vis,0,sizeof(vis));
		memset(th,0,sizeof(th));
		int tmp=i;
		while (tmp!=1) {
			if (ch[f[tmp]][0]==tmp) {b[++chn]=0;}
			else {b[++chn]=1;}
			tmp=f[tmp];
		}
		a[++siz]=vis[1]=1;
		while (tmp) {
			for (int i=chn;i>=1;i--) {tmp=ch[tmp][b[i]];}
			if (tmp) {a[++siz]=tmp,vis[tmp]=1;}
		}
		for (int j=1;j<=siz;j++) {dfs2(a[j],rt);}
		//cout << i << "  " << cnt << "  " << chn << endl;
		ans=min(ans,2*cnt-chn);
	}
	printf("%d\n",ans);
	return 0;
}

---

E. 混乱度

难度：$\bigstar\bigstar$

题目大意：

给定长度为 $n$ 的序列 $a_1,\ldots,a_n$，定义 $f(l,r)$ 为：设有 $r-l+1$ 种颜色的球，第 $i$ 种颜色有 $a_{l+i-1}$ 个，将它们排成一列的方案数（同颜色球不可区分）。

试求下式：

$$\sum\limits_{l=1}^n\sum\limits_{r=l}^n (f(l,r)\bmod p)$$

$1\leq n\leq 5\times 10^5, 0\leq a_i\leq 10^{18}, p\in \{2,3,5,7\}$

题目解法：

根据多重组合数，显然有：

$$f(l,r)=\dfrac{(\sum\limits_{i=l}^r a_i)!}{\prod\limits_{i=l}^r a_i!}=\prod\limits_{i=l}^r \binom {\sum\limits_{j=l}^i a_j}{a_i}$$

因为 $p$ 是素数，由 Kummer 定理知 $p\mid f(l,r)$ 当且仅当 $a_l,\ldots,a_r$ 做 $p$ 进制加法不进位。

先认为 $a_i>0$，可以对 $r-l+1$ 估出一个上界 $(p-1)\log_p A$，其中 $A$ 是 $a_i$ 的上界，这是因为 $p$ 进制下每一位只能填最多 $p-1$ 个 $1$，否则肯定要进位。

枚举 $l$ 后扫描 $r$，暴力计算复杂度是 $O(np\log_p^2 A)$ 的，因为组合数计算用到了 Lucas 定理递归。

但我们可以这样处理：对于每个 $a_i$ 记录其 $p$ 进制下非零位，每次从 $f(l,r-1)$ 算 $f(l,r)$ 时，只需要按照 Lucas 定理考虑 $a_r$ 的非零位，求这些位上的贡献乘起来就可以了，由于上面的 $p\log_p A$ 实际上就是非零位数和的上界，所以这样就将算组合数的复杂度也均摊掉了。

而 $a_i=0$ 的问题也不难解决，将 $0$ 构成的连续段缩成一个 $0$ 就可以了，这里的处理是平凡的，这题甚至不需要处理这些 $0$ 就可以通过现有数据。

时间复杂度为 $O(np\log_p A)$。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500010,MAXB=63;
int n,p,binom[10][10],s[MAXB],cnt[MAXN],b[MAXN][MAXB],c[MAXN][MAXB];
ll ans,a[MAXN];
int main () {
	scanf("%d%d",&n,&p);
	for (int i=0;i<=8;i++) {
		binom[i][0]=1;
		for (int j=1;j<=i;j++) {binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%p;}
	}
	for (int i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		int tmp=0;
		while (a[i]) {
			if (a[i]%p) {c[i][++cnt[i]]=tmp;b[i][cnt[i]]=a[i]%p;}
			tmp++,a[i]/=p;
		}
	}
	for (int i=1;i<=n;i++) {
		memset(s,0,sizeof(s));
		int nw=1,flg=1;
		for (int j=i;j<=n;j++) {
			for (int k=1;k<=cnt[j];k++) {
				if (s[c[j][k]]+b[j][k]>=p) {flg=0;break;}
				s[c[j][k]]+=b[j][k];
				nw=(nw*binom[s[c[j][k]]][b[j][k]])%p;
			}
			if (!flg) {break;}
			ans+=nw;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

---

*F. 文本编辑器

难度：$\bigstar\bigstar\bigstar$

题目大意：

给定包含 $m$ 个单词的词典 $\{s_i\}$，维护一个长度为 $n$ 的文本 $S$，支持 $q$ 个操作，操作有两种：

• 修改操作：给定 $l,r$ 和字符串 $T$，将 $S_l\ldots S_r$ 改为 $T$ 不断重复的结果（即 $T^{\infty}$ 的等长前缀）；
• 查询操作：给定 $l,r$，求所有词典中的单词在 $S_l\ldots S_r$ 中出现次数之和。

$1\leq n\leq 10^6, 1\leq m,q\leq 10^5, |s_i|\leq 50, \sum|s_i|\leq 2\times 10^5, \sum |T|\leq 10^6, |\Sigma|=62$

题目解法：

建立词典的 AC 自动机，设前缀 $S_1\ldots S_i$ 在 AC 自动机上走到的结点为 $p_i$，再设使得 $S_j\ldots S_i$ 是某个词典中单词的 $j$ 的数量为 $c_i$，那么显然 $c_i$ 就是 $p_i$ 在 Fail 树上的祖先中单词的个数。

设最长单词长度为 $L$，查询时首先将 $S_l\ldots S_{l+L-2}$ 这一段的答案暴力统计，然后加上 $\sum\limits_{i=l+L-1}^r c_i$ 就是答案（最前面一段因为可能会存在延申到 $l$ 之前的单词所以要单独处理）。

而修改时，我们同样暴力处理 $[l,l+L-2]$ 和 $[r+1,r+L-1]$ 这两个小段的 $p_i,c_i$ 的改变，对于中间的大段 $[l+L-1,r]$，显然其 $p_i,c_i$ 都有周期 $|T|$，我们只需要 $O(|T|)$ 计算出一个循环节即可。

用线段树维护区间的循环覆盖和单点修改，这里的单点修改由于是一次改一个区间，所以利用类似 Finger Search 的方法可以减少一个 $\log n$。

时间复杂度为 $O(\sum |s_i|\times |\Sigma|+\sum |T|+q(L+\log n))$。