2013
12-26

# 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

4.1.2 HDU2899 Strange Function

4.1.3 HDU1967 Pie

4.1.4 HDU2141 Can You Find it

#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

#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

#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

#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;
}

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，比楼主的要快。