首页 > ACM题库 > HDU-杭电 > hdu 1967 Sudoku-分治-[解题报告]C++
2013
12-26

hdu 1967 Sudoku-分治-[解题报告]C++

Sudoku

问题描述 :

Oh no! Bill just realized that the sudoku puzzle he had spent the last ten minutes trying to solve essentially was last week’s puzzle, only rotated counterclockwise. How cheap! Couldn’t the magazine afford to make a new one every week? Of course, he had no way of knowing about this before he started to solve it, as the holes to fill with digits were other than last week. Nevertheless, realizing that this week’s puzzle was a simple derivative of last week’s certainly took the fun out of solving the rest of it.

The sudoku board consists of 9*9 cells. These can be grouped into 3*3 regions of 3*3 cells each. Some of the cells are filled with a digit 1 through 9 while the rest of them are left empty. The aim of the game is to fill each empty cell with a digit 1 . . . 9 so that every row, every column and every region contains each of the numbers 1 . . . 9 exactly once. A proper sudoku puzzle always has exactly one solution.

Help Bill avoid unpleasant surprises by creating a program that checks whether an unsolved sudoku puzzle is in fact derived from an earlier puzzle by simple operations.

The allowed operations are:
1. Rotating the entire puzzle clockwise or counterclockwise.
2. Swapping two columns within a 3 * 9 column segment.
3. Swapping two rows within a 9 * 3 row segment.
4. Swapping entire row or column segments.
5. Applying a permutation f of the digits 1 . . . 9 to every cell (i.e. replace x by f (x) in every cell).

An operation is considered being performed on the sudoku solution (rather than on the unsolved puzzle) and always guarantees that if the board before the transformation was a solution to a sudoku puzzle, it still is afterwards.

输入:

The input starts with the number of test cases 0 <= N <= 50 on a single line.

Then for every test case follow nine lines describing last week’s puzzle solution, fromtop to bottom. Each line corresponds to a row in the puzzle and consists of nine digits (1 . . . 9), describing the contents of the cell from left to right.

Last week’s solution is followed by nine lines describing this week’s unsolved puzzle. Here, also, every line corresponds to a puzzle row and every digit (0 . . . 9) describes the contents of a cell. 0 indicates that the cell is empty. The rows are presented ordered from top to bottom, and within each row, the cells are ordered from left to right.

After every test case except the last one follows a blank line. Every unsolved puzzle is guaranteed to be uniquely solvable and last week’s solution is always a proper sudoku solution.

输出:

The input starts with the number of test cases 0 <= N <= 50 on a single line.

Then for every test case follow nine lines describing last week’s puzzle solution, fromtop to bottom. Each line corresponds to a row in the puzzle and consists of nine digits (1 . . . 9), describing the contents of the cell from left to right.

Last week’s solution is followed by nine lines describing this week’s unsolved puzzle. Here, also, every line corresponds to a puzzle row and every digit (0 . . . 9) describes the contents of a cell. 0 indicates that the cell is empty. The rows are presented ordered from top to bottom, and within each row, the cells are ordered from left to right.

After every test case except the last one follows a blank line. Every unsolved puzzle is guaranteed to be uniquely solvable and last week’s solution is always a proper sudoku solution.

样例输入:

2
963174258
178325649
254689731
821437596
496852317
735961824
589713462
317246985
642598173
060104050
200000001
008305600
800407006
006000300
700901004
500000002
040508070
007206900
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
010900605
025060070
870000902
702050043
000204000
490010508
107000056
040080210
208001090

样例输出:

Yes
No

Steps 4.1主要都是二分和三分的问题,二分这种思想很重要也很常用.另外,在浮点数运算时一定要注意精度问题.


4.1.1 HDU 2199 Can you solve this equation

函数单调递增,当f(0)>0或者f(100)<0时无解,二分答案即可,精度要到1e-6


4.1.2 HDU2899 Strange Function

凸函数,三分法可以做.我是先求导,它的导数是单调的,所以求出导数=0时的x,再代入原式就可以了


4.1.3 HDU1967 Pie 

问每个人最多可以分多大的Pie,先对面积进行排序,然后在0和最大的Pie面积之间二分求答案,对每一个值计算是否可以达到F+1块,当然,优先去切大块的Pie…另外需要注意的是,计算圆形面积时 PI=acos(-1) 直接写3.141592653会有精度问题


4.1.4 HDU2141 Can You Find it

二分查找,先计算出所有a+b的结果储存并排序,然后对k,去二分查找k-c (a+b=k-c) 500MS+

当然,更好的方法是用Hash表,查找复杂度O(1),这题就当练一下二分查找了..

#include <cstdio>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int maxn=505;
LL a[maxn],b[maxn],c[maxn],ab[maxn*maxn];
int cas=1,n,m,l,ks,k,low,high,mid;
bool findk(int x){
	low=0,high=l*n;
	while(high-low>1){
		int mid=(high+low)/2;
		if(ab[mid]==x)return true;
		if(ab[mid]>x)high=mid;
		else low=mid;	
	}
	return false;
}
int main(){
	while(scanf("%d%d%d",&l,&n,&m)!=EOF){
		for(int i=0;i<l;i++)scanf("%I64d",&a[i]);
		for(int i=0;i<n;i++)scanf("%I64d",&b[i]);
		for(int i=0;i<m;i++)scanf("%I64d",&c[i]);
		
		//储存a+b的结果并排序 
		for(int i=0;i<l;i++)
			for(int j=0;j<n;j++)
				ab[i*n+j]=a[i]+b[j];
		sort(ab,ab+l*n);
		
		printf("Case %d:\n",cas++);
		scanf("%d",&ks);
		while(ks--){
			scanf("%d",&k);
			int find=0;
			//在[a+b]中查找有没有等于c-k的值 
			for(int i=0;i<m;i++){
				if(findk(k-c[i])){find=1;break;}				
			}
			printf(find?"YES\n":"NO\n");
		}
					
	}	
	
}

4.1.5 HDU2298 Toxophily

直接当数学题做了(物理题?..)正交分解然后消去y变成一元二次方程,解这个方程就可以了.注意几点问题,delta<0时无解,在x==0时,方程不是一元二次方程,这时如果在原点就可直接到达,如果在y轴上则垂直上射,另外坐标在第一象限,解为正数,要选取较小的正数解..

这题虽说简单..想轻松A还是不太容易的….

#include <cstdio>
#include <cmath> 
using namespace std;
const double g=9.8;
int cas;
double x,y,v,a,b,c,ans1,ans2,delta;

int main(){
	scanf("%d",&cas);
	while(cas--){
		scanf("%lf%lf%lf",&x,&y,&v);
		//注意判断,x==0时,方程不是一元二次方程 
		if(x==0){
			if(y==0)printf("0.000000\n");
			if(y>0)printf("%.6lf\n",acos(-1)/2);
			continue;	
		}
		//转化为一元二次方程,未知数是tan(alpha); 
		a=g*x*x;
		b=-x*2*v*v;
		c=2*y*v*v+g*x*x;
		delta=b*b-4*a*c;
		//delta<0无解 
		if(delta<0)printf("-1\n");
		else{
			//选取较小的正解(x>=0,y>=0,tan(alpha)>=0) 
			ans1=(-b-sqrt(b*b-4*a*c))/2/a;
			ans2=(-b+sqrt(b*b-4*a*c))/2/a;
			if(ans2<0)printf("-1\n");
			else if(ans1<0)printf("%.6lf\n",atan(ans2));
			else printf("%.6lf\n",atan(ans1));
		}
	}
	return 0;	
}

4.1.6 HDU1597 Find the nth digit

水题一道,注意数据溢出问题


4.1.7 HDU2438 Turn The Corner

没有良好的数学功底真的很难做出这题,先要建系


然后列出小车上边一条边的方程,然后求这个方程和y=X的交点的最大值,很明显是个凸函数,用三分法解…不知道为什么,一开始用二分left,right,在二分mid和right的三分做一直WA,后来改成平均三分就A了..理论上来说应该都没问题啊..

#include <cstdio>
#include <cmath>
using namespace std;
double x,y,l,d,mid,midmid,low,high;
double cal(double jd){
	return (l*sin(jd)+d/cos(jd)-x)/tan(jd); 
}
int main(){
	/*
		以右下角为原点建立坐标系,Y=Xtan(a)+l*sin(a)+d/cos(a)
		再将Y=x代入,求X关于角度a的最大值(0<=a<=PI/2); 
	*/ 
	while(~scanf("%lf%lf%lf%lf",&x,&y,&l,&d)){
		high=acos(-1.0)/2.0,low=0.0;
		//三分法求极值 
		while(high-low>1e-4){
			mid=(high-low)*1.0/3.0+low;
			midmid=(high-low)*2.0/3.0+low;
			if(cal(mid)>cal(midmid))high=midmid;
			else low=mid;
		}		
		printf(y-cal(low)>0?"yes\n":"no\n");
	}
	return 0;	
}



4.1.8 HDU3400 Line belt

一道三分的好题,嵌套三分求解..不看大牛的文章真想不到这题是用三分法做的..

这篇文章解释的比较详细http://hi.baidu.com/myzone2009/blog/item/1f9560ccdf5d045d0eb34535.html

我是以T为自变量的,这样有一个小问题,求不在线段上走的距离时会除距离,既然有除法就要注意除0问题,所以在求距离时要加上一个小精度..否则就会WA..

#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
/*
	F(X)=G(X)+H(Y)
	G(X)单调,H(Y)是凸函数,则F(X)也是凸函数
	其中G(X)是在AB上的时间,H(Y)是在CD上的时间加上飞机上的时间 


*/
double ax,ay,bx,by,cx,cy,dx,dy,p,q,r;
double l1,l2,h1,h2,m11,m12,m21,m22;
double dis(double x1,double y1,double x2,double y2){
	return sqrt(1e-6+(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double cal(double m1,double m2){
	double x1,x2,y1,y2;
	x1=ax+m1*p*(bx-ax)/dis(ax,ay,bx,by);
	y1=ay+m1*p*(by-ay)/dis(ax,ay,bx,by);
	x2=dx+m2*q*(cx-dx)/dis(cx,cy,dx,dy);
	y2=dy+m2*q*(cy-dy)/dis(cx,cy,dx,dy);
	return dis(x1,y1,x2,y2)/r;
}
double calsf(double m){
	l2=0,h2=dis(cx,cy,dx,dy)/q;
	while(h2-l2>1e-6){
		m21=(h2-l2)*1.0/3.0+l2;	
		m22=(h2-l2)*2.0/3.0+l2;	
		if(m21+cal(m,m21)<m22+cal(m,m22))h2=m22;
		else l2=m21;
	}
	return h2+cal(m,h2);
}

int main(){
	int cas;
	scanf("%d",&cas);
	while(cas--){
		scanf("%lf%lf%lf%lf",&ax,&ay,&bx,&by);	
		scanf("%lf%lf%lf%lf",&cx,&cy,&dx,&dy);
		scanf("%lf%lf%lf",&p,&q,&r);
		
		l1=0,h1=dis(ax,ay,bx,by)/p;
		while(h1-l1>1e-6){
			m11=(h1-l1)*1.0/3.0+l1;	
			m12=(h1-l1)*2.0/3.0+l1;
			if(m11+calsf(m11)<m12+calsf(m12))h1=m12;
			else l1=m11;
		}
		
		printf("%.2lf\n",h1+calsf(h1));
	}
	return 0;	
}


解题转自:http://blog.csdn.net/swm8023/article/details/6765190


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。