Sol

Accelerator

暴力1

直接枚举即可。

正解

暴力统计 $b\geq 3$ 时的结果，拿 std::map 去重的同时统计这些数里有多少个完全平方数。

考虑到所有的 $a^b\leq n$ 且 $b=2$ 时共有 $\lfloor \sqrt{n} \rfloor$ 种 $a^b$，所以拿上面的结果加上 $\lfloor \sqrt{n} \rfloor$ 再减去统计有多少个完全平方数即可做到不重不漏统计答案。

实现的时候注意不要使用 sqrt，会爆精度，应该使用 sqrtl。

考点解析：sqrtl、枚举、人类智慧。

Kuriko

暴力1

暴力连边跑暴力 Dijkstra。

暴力2

暴力连边跑 01-BFS。

暴力3

建模跑暴力 Dijkstra。

正解

建模跑 01-BFS。

具体地，每个 $u$，从 $u$ 向 $a_u$ 连边，边权为 $0$。

每个 $a_u$ 枚举其为 $0$ 的二进制位 $x$，向 $a_u \operatorname{or} x$ 连边，边权为 $0$。

建图时间复杂度 $O(a_u\log a_u)$。

查询时间复杂度 $O(q(n+M))$。

考点解析：BFS、图论建模。

Kamijo

暴力1

暴力。

正解

单点修改 + 查询直接上线段树。

每个节点维护这段区间里有几个 a 几个 b 几个 c，需要改几个字符能实现没有子序列 ab bc abc，转移有：

void pushup(int p){
	t[p].a=t[p*2].a+t[p*2+1].a;
	t[p].b=t[p*2].b+t[p*2+1].b;
	t[p].c=t[p*2].c+t[p*2+1].c;
	t[p].ab=min(t[p*2].ab+t[p*2+1].b,t[p*2].a+t[p*2+1].ab);
	t[p].bc=min(t[p*2].bc+t[p*2+1].c,t[p*2].b+t[p*2+1].bc);
	t[p].abc=min({t[p*2].abc+t[p*2+1].c,t[p*2].ab+t[p*2+1].bc,t[p*2].a+t[p*2+1].abc});
}

时间复杂度 $O(q\log n)$。

听说还有个矩乘做法，我还没看。

考点解析：DP（？）、线段树。

Misaka

先判断出来哪些点能被覆盖。然后对所有金属导体按 $x$ 升序排序。

对于性质分，显然的点是，假设从左到右依次存在三个点 $A,B,C$ 需要被覆盖，那么不可能出现一个金属导体覆盖了 $A,C$ 而另一个金属导体覆盖了 $B$ 这种情况。换句话说，一个金属导体一定覆盖了一段连续的点，于是没有后效性，设 $f_{i,j}$ 为前 $i$ 个点且最后一个被选中的金属导体是 $j$，可以 DP。

对于全部的数据，直接多加一维，$f_{i,j,k}$ 表示前 $i$ 个点，最后一个被选中的上方的金属导体是 $j$，下方的是 $k$，就可以 DP。

f[0][0][0]=0;
	for(int i=1;i<=cnt;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=m;k++)
				for(int l=1;l<=m;l++){
					if(dis2(a,i,l)>r*r)continue;
					if(y[l]>r)f[i][l][k]=min(f[i][l][k],f[i-1][j][k]+(l==j?0:c[l]));
					else f[i][j][l]=min(f[i][j][l],f[i-1][j][k]+(l==k?0:c[l]));
				}

考点解析：DP。