【dfs+分治】VK Cup 2012 Round 1

VK Cup 2012 Round 1"/>

【dfs+分治】VK Cup 2012 Round 1

这道题的思路真是太神奇了，在参考某大牛的代码后恍然大悟，对其思维无限膜拜啊……用了分治法，具体思路看代码……

题目

#include<iostream>
using namespace std;
template<class T> T Max(T x,T y){return x>y?x:y;}
template<class T> T Min(T x,T y){return x<y?x:y;}
int dfs(int l1,int r1,int l2,int r2,int k)
{int m;m=1<<k;if(l1>r1||l2>r2)return 0;if(l1>l2||l1==l2&&r1<r2)return dfs(l2,r2,l1,r1,k);              //使第一段在第二段的后面if(r1>=r2)return r2-l2+1;              //这里表示第二段完全包含在第一段里，这时它们相同的长度就是第二段的长度了if(l2>m)return dfs(l1,r1,l2-m,r2-m,k);              //使第一段和第二段同在2^k-1的长度里if(r1<m&&r2<m)return dfs(l1,r1,l2,r2,k-1);              //找2^k-1的长度并使第一段和第二段都在里面return Max(Max(dfs(l1,r1,l2,m-1,k),dfs(1,r2-m,l1,r1,k)),r1-l2+1);              //这里对于第二段表示有三种选择，1是（l2，m-1）表示的是第m个字符以回的，2是（m+1，r2）表示的是第m个字符以后的（可以用（1，r2-m））表示，3是包括第m个字符在内的
}
int main()
{//freopen("a.txt","r",stdin);int l1,r1,l2,r2;scanf("%d%d%d%d",&l1,&r1,&l2,&r2);printf("%d\n",dfs(l1,r1,l2,r2,30));return 0;
}