基础算法思想——分治

周一buff+昨晚还有cf，今天感觉非常疲惫。等等，还没补题呢······ 原本以为这周的题会比较好写，但是几道题写下来并非如此。这篇博客就简单写一下关于分治思想。

分治，就可以简单理解为“分而治之”。题目大多需要进行递归，非常的灵活，需要仔细对程序进行设计。下面用几道例题来熟悉一下。

幂次方

来源：P1010 NOIP 1998 普及组] 幂次方 - 洛谷

思路

题目比较好懂，把一个非常大的数分为以1和2为最小单位，与2相乘当做连接的一个形式。虽然看着非常的混乱复杂，但是可以一点点剖析其背后的规律。首先根据137=2⁷+2³+2⁰可以得出：其实是根据二进制由大到小进行分解的。每分解出来一个数就要进行递归。剩下的数继续进行递归。在递归中有以下几个步骤：

• 当剩下的数为1时直接输出2(0)
• 当剩下的数为2时直接输出2
• 如果不是前两种，需要继续对当前的幂进行分解。先输出2( 进入当前数字的递归
• 里面的数再进入函数得到
• 输出 ）本块结束
• 将本块的数字减掉
• 本块数字处理完毕了，如果此时还有数用+号连接

代码

void dfs(int x)
{
	for(int i=20; i>=0; i--)
	{
		if(pow(2,i)<=x)
		{
			if(i==0) cout<<"2(0)";
			else if(i==1) cout<< "2";
			else
			{
				cout<<"2(";
				dfs(i);//继续分解此时的次方
				cout<<")";
			}
			x-=pow(2,i);//减去这一块的数字,后面继续分解
			if(x) cout<<"+";//如果这一块的数字没处理完用+号和后面连接
		}
	}
}
void solve()
{
	cin >> n;
	dfs(n);
}

外星密码

来源：P1928 外星密码 - 洛谷

思路

本题和幂次方类型非常相似，需要将操作的每一部分进行剖析。大概分为以下步骤：

• 如果是\n说明输入结束需要退出
• 如果是左括 [ 就开始处理：

​ 1、输入数字t

​ 2、进行递归获得内部的字符串

​ 3、将字符串连t次到s1

• 如果是右括号 ] 次段结束，return s1
• 如果上面那些全都不是的话正常相连就行了

代码

string f()
{
	string s1="",s2;char ch;
	while(cin >> ch)
	{
		if(ch=='\n') break;
		if(ch=='[')
		{
			int t;
			cin >> t;
			s2=f();
			while(t--) s1+=s2;
			// return s1;
		}
		else if(ch==']') return s1;
		else s1+=ch;
	}
	return s1;
}
void solve()
{
	cout << f();
	return ;
}

南蛮图腾

来源：P1498 南蛮图腾 - 洛谷

本题是一个图形题，需要找规律进行模拟。

思路

很明显n每增加1就要把当前的图形分别向左下，右下复制一次。但是问题来了，向右下复制没问题，但是向左下直接就超界了。所以我们要对图形进行倒置处理，这样的话图形的左边和上边是不会动的，只会向右边和下面移动。首先把最基础的图形给存进去，然后每次分别向右方和右下复制一个。

代码

void solve()
{
	int n,w=4,cnt=1;
	cin >> n;
	memset(a,' ',sizeof(a));
	a[1][1]=a[2][2]='/';
	a[1][2]=a[1][3]='_';
	a[1][4]=a[2][3]='\\';
	while(cnt<n) //复制图腾 
	{
		for(int i=1;i<=w/2;i++)
			for(int j=1;j<=w;j++)
				a[i+(w/2)][j+(w/2)]=a[i][j+w]=a[i][j];	//转移式 
				// 右下					右边
		w*=2;
		cnt++;
	}
	for(int i=w/2; i>=1; i--)//倒置输出
	{
		for(int j=1; j<=w; j++)
			cout << a[i][j];
		cout << endl;
	}
}

由于分治大多需要递归，有好多步骤需要放在同一个函数里。所以要在函数中理清楚逻辑，将繁琐的规则一步步拆解。