做题笔记 - Ad_hoc 1

时间之书(华中地区邀请赛 19th)

提供一种不一样的构造方法。

有一个比较直接的思路，即维护每一个点所属编号，然后找到每一个三角形三个端点所属编号，可以通过获取顶点编号进行 update 和 query 操作。用一个 map 存每个编号所对应的点的权值。对于 extend，不用做任何事情。

现在问题是，要将这些节点赋什么编号。有一个想法是，让每个三角形的三个顶点分别赋上 $(i,A),(i,B),(i,C)$ 的编号。这个想法的问题在于一个点可能是若干个三角形的公共顶点。这样重复编号会使得 update 操作需要改变以该点为顶点的所有三角形的对应编号对应值。这很麻烦，而且可能要修改很多三角形。有没有什么不重不漏的修改方法呢？

如下图，这是 extend 一个初始三角形两层的示意图：

为了方便，本章节将 $1$ 个点朝上，$2$ 个点分别朝下方左右的称为 正三角形， $1$ 个点朝下，$2$ 个点分别朝上方左右的称为 倒三角形。请勿与一般的正三角形概念混淆。

绿色点是大三角形的三个顶点，红色点是第一层 extend 新增的三个点，蓝色点是第二层 extend 新增的九个点。不难发现，除了大三角形的三个顶点，每一层新增的点集相当于上一层新增的正三角形的边中点点集。

在上图中，红色点点集 $\{D,E,F\}$ 恰好为第零层大三角形的三条边的中点，蓝色点点集 $\{G,H,I,J,K,L,M,N,P\}$ 恰好为第一层三个正三角形（即 $\triangle AEF/4,\triangle BDF/5,\triangle CDE/7$）的三条边的中点。

根据这个性质，我们可以规定每轮新增的在编号为 $i$ 的正三角形内的三个顶点编号为 $(4i+2,A),(4i+2,B),(4i+2,C)$。特别地，规定大三角形的三个顶点编号为 $(1,A),(1,B),(1,C)$。

接下来是如何求出一个三角形所代表的顶点编号。我们可以模拟 extend 的过程，维护 extend 每一层对应三角形的信息。比如，要查询 $\triangle25$，我们模拟 extend 的过程是 $\{\triangle1,\triangle6,\triangle25\}$。扩展到下一层显然要知道当前三角形的三个顶点编号。问题是在扩展到下一层时如何求出下一层三角形的三个顶点编号。由于顶点编号与三角形为正三角形还是倒三角形有关，那么我们根据当前三角形 $\triangle i$ 和下一层三角形 $\triangle 4i+k(k\in\{0,1,2,3\})$ 是正三角形还是倒三角形分类讨论：

为了方便，本章节将 $\triangle i$ 相邻的大小相同的最多三个三角形（如果有）称作 $\triangle i$ 的邻域三角形。

• 当 $\triangle i$ 和 $\triangle 4i+k$ 均为正三角形时，$\triangle 4i+k$ 的三个顶点为 $\triangle i$ 的一个顶点和 $\triangle 4i+2$ 的两个顶点（即编号为 $4i+2$ 的三个顶点其中之二）；
• 当 $\triangle i$ 为正三角形且 $\triangle 4i+k$ 为倒三角形时，$k=2$（恰好编号为 $4i+2$ 的三个顶点）；
• 当 $\triangle i$ 为倒三角形且 $\triangle 4i+k$ 为正三角形时，$k=2$，三个顶点为 $\triangle i$ 的三个邻域三角形 $\triangle j$ 的分别某条边的中点，即 $(4j+2,\alpha)$；
• 当 $\triangle i$ 和 $\triangle 4i+k$ 均为倒三角形时， 的三个顶点为 $\triangle i$ 的一个顶点和三个邻域三角形之二 $\triangle j$ 的分别某条边的中点，即 $(4j+2,\alpha)$。

然后我们会发现当且仅当 $\triangle i$ 是倒三角形时，我们需要同时维护邻域三角形的编号。注意要将编号次关键字 $A,B,C$ 的方向固定。

这里给出笔者的 $\text{get\_id}$ 函数供大家参考。

vector<pi>get_id(int x){
	vector<int>v;
	while(x>1){
		v.push_back(x&3);
		x>>=2;
	}
	reverse(v.begin(),v.end());
	pi d0=pi(1,0),d1=pi(1,1),d3=pi(1,3);int t0=0,t1=0,t3=0;bool flag=0;
	for(auto c:v){
		int mid=(x<<2)|2;
		if(c==0){
			if(!flag){
				d1=pi(mid,3);
				d3=pi(mid,1);
				t0=t1=t3=0;
			}else{
				d1=pi((t3<<2)|2,3);
				d3=pi((t1<<2)|2,1);
				t0=mid,t1=(t1<<2)|3,t3=(t3<<2)|1;
			}
		}else if(c==1){
			if(!flag){
				d0=pi(mid,3);
				d3=pi(mid,0);
				t0=t1=t3=0;
			}else{
				d0=pi((t3<<2)|2,3);
				d3=pi((t0<<2)|2,0);
				t0=(t0<<2)|3,t1=mid,t3=(t3<<2)|0;
			}
		}else if(c==2){
			if(!flag){
				d0=pi(mid,0);
				d1=pi(mid,1);
				d3=pi(mid,3);
				t0=(x<<2)|0,t1=(x<<2)|1,t3=(x<<2)|3;
			}else{
				d0=pi((t0<<2)|2,0);
				d1=pi((t1<<2)|2,1);
				d3=pi((t3<<2)|2,3);
				t0=t1=t3=0;
			}
		}else if(c==3){
			if(!flag){
				d0=pi(mid,1);
				d1=pi(mid,0);
				t0=t1=t3=0;
			}else{
				d0=pi((t1<<2)|2,1);
				d1=pi((t0<<2)|2,0);
				t0=(t0<<2)|1,t1=(t1<<2)|0,t3=mid;
			}
		}
		flag^=c==2;
		x=(x<<2)|c;
	}
	return {d0,d1,d3};
}

Magical Tiered Cake(CF2232D)

来源：CF Round 1101 D

难度：2000

汉诺塔问题变形。Ad - hoc。

先考虑什么时候是无解的。当存在 $a_i\ge i$ 时，发现第 $i$ 个盘子无论如何都动不了（因为在它自身能动之前上面永远小于 $i$ 个盘子）。

特殊情况 $\forall i\in[1,n],a_i=0$ 就是普通的汉诺塔问题。

接下来考虑一般情况，我们希望对于一般情况也能像汉诺塔问题一样递归处理。然后我们可以找到一样的递归动机，即最大的一个盘子移动的目标位置顶上不能有任何比它还大的盘子。那么就考虑最大的一个盘子什么时候是能动的。设此时需要处理有 $k$ 个盘子的子问题，将所有盘子从 A 地移动到 C 地，B 地可以作为中转点。那么当 $a_k=0$ 时，照原样汉诺塔问题，即需要把上面的 $k-1$ 个盘子都移动到 B 地才能动第 $k$ 个盘子。即操作：

$$solve(k-1,A\to B),move(k,A,C),solve(k-1,B\to C)$$

。当 $a_k\gt 0$ 时，有一个比较简单直接的方法就是先把最上面的 $k-1-a_k$ 个盘子先移到 B，然后从 A 移第 $k$ 个盘子到 C，再把 B 的 $k-1-a_k$ 个盘子移回 A，最后把还在 A 的 $k-1$ 个盘子移到 C。即操作：

$$solve(k-1-a_k,A\to B),move(k,A,C),solve(k-1-a_k,B\to A),solve(k-1,A\to C)$$

。不难证明这样的步数一定在 $2^k$ 以内。

Two Arithmetic Progressions

来源：AT_arc221_a

难度：1686

我们发现，由 $\gcd(a,b)=\gcd(b,a\bmod b)$ 可以对 $A$ 和 $C$ 进行消元。消到 $C$ 为零，也就是形如求 $\gcd(Ai+B,D)$ 的形态。

接下来想一想如何求出 $\gcd(Ai+B,D)$。当 $D$ 是负数是，取正即可。为零的情况放到章末再讨论。可以发现，我们通过枚举 $D$ 的约数 $d$，对每一个约数判断是否能够整除 $Ai+B$，然后再稍微容斥一下可以求出 $\gcd$ 的和。所以现在我们要快速求出所有 $Ai+B$ 被 $d$ 整除的个数。我们发现对于 $i$ 满足 $d\mid Ai+B$ 的解集必然是一个无限等差数列，所以我们只要找到最小的 $i$ 就行。

对于 $d\mid Ai+B$ 可以转换为 $-Ai+dy=B$，也就是解一个同余方程。这里我们可以用 exgcd 解决。

如果有误，或者更好的解法，欢迎私信骚扰。