BZOJ 3109[Zjoi2013]K大数查询
3110: [Zjoi2013]K大数查询
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 12028 Solved: 3644
[Submit][Status][Discuss]
Description
有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
Input
第一行N，M
接下来M行，每行形如1 a b c或2 a b c
Output
输出每个询问的结果
Sample Input
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3
Sample Output
2
1
HINT
【样例说明】
第一个操作 后位置 1 的数只有 1 ， 位置 2 的数也只有 1 。 第二个操作 后位置 1
的数有 1 、 2 ，位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是
1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3
大的数是 1 。
N,M<=50000,N,M<=50000
a<=b<=N
1操作中abs(c)<=N
2操作中c<=Maxlongint
题解：暴力搜索+剪枝；
整理一下判断条件：
1.这一行是否有重复的数
2.这一列是否有重复的数
3.这一个小九宫格中是否有重复的数
4.是否符合大于小于的条件
现在我分别用 h[i][j] ,l[i][j] ,g[i][j] 来表示第i行，第i列，第i个小九宫格中数字j是否重复。还有一个大于小于号的问题后面再说，让我们先来看一下读入。
输入格式： 一共15行，包含一个新数独的实例。第奇数行包含左右方向的符号（<和>），第偶数行包含上下方向的符号（^和v）
说是奇数行包含左右方向的符号，偶数行包含上下方向的符号，其实如果你仔细的看一下题目或者样例输入的话，应该不难发现输入格式的描述略有问题，有的行与输入描述是相反的。。。（如果已经改过来了就当我没说）
其实可以这样看：输入是有15行的，你可以把这15行分成3组，每组5行，这样描述就对了，每一组的奇数行和偶数行按描述进行读入即可。
读入符号之后，先看这个符号属于哪一个小九宫格（因为不同小九宫格的符号是不相关的），然后就要用到下面这个数组了:
f[i][x][y]
它表示第i个小九宫格中第x个数和第y个数是否有大小关系。
读入的时候如果是”>”或者”v”就在相应的位置保存1，如果是”<“或”^”就保存2。
那么这样一来符号的问题就不是问题了，在选数的时候多加一个循环判断一下这个数周围的大小关系是否合法不就行了？
参考代码为：
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int a[10][10],h[10][10],l[10][10],g[10][10],m,n,c,f[10][10][10];
void dfs(int x,int y)
{
if(x==9&&y==10)
{
for(int i=1;i<=9;++i)
{
for(int j=1;j<=9;++j) printf("%d ",a[i][j]);
cout<<endl;
}
return;
}
if(y==10) x=x+1,y=1;
for(int i=1;i<=9;++i)
{
bool bl=0;
int g1=((x-1)/3)*3,g2=(y-1)/3,g3=g1+g2;
if(g[g3][i]==1||h[x][i]==1||l[y][i]==1) continue;
for(int j=1;j<=9;++j)
{
int ii=(x-1)%3*3+(y-1)%3+1;
if(f[g3][ii][j]==1)
{
int xj=g3/3*3+(j-1)/3+1,yj=g3%3*3+(j-1)%3+1;
if(a[xj][yj]!=0)
if(i<a[xj][yj])
{
bl=1;
break;
}
}
if(f[g3][ii][j]==2)
{
int xj=g3/3*3+(j-1)/3+1,yj=g3%3*3+(j-1)%3+1;
if(a[xj][yj]!=0)
if(i>a[xj][yj])
{
bl=1;
break;
}
}
}
if(bl==1) continue;
g[g3][i]=1;h[x][i]=1;l[y][i]=1;
a[x][y]=i;
dfs(x,y+1);
a[x][y]=0;
g[g3][i]=0;h[x][i]=0;l[y][i]=0;
}
}
int main()
{
int ci=0;
char s;
for(int i=1;i<=3;++i)
{
for(int k=1;k<=5;++k)
{
if(k%2==1)
{
for(int j=1;j<=6;++j)
{
int q1=(i-1)*3,q2=(j-1)/2,q3=q1+q2;
cin>>s;
if(s=='>')
{
int qq=(k-1)/2*3+(j-1)%2+1;
f[q3][qq][qq+1]=1;
f[q3][qq+1][qq]=2;
}
else
{
int qq=(k-1)/2*3+(j-1)%2+1;
f[q3][qq][qq+1]=2;
f[q3][qq+1][qq]=1;
}
}
}
else
{
for(int j=1;j<=9;++j)
{
int q1=(i-1)*3,q2=(j-1)/3,q3=q1+q2;
cin>>s;
if(s=='v')
{
int qq=(k-1)/2*3+(j-1)%3+1;
f[q3][qq][qq+3]=1;
f[q3][qq+3][qq]=2;
}
else
{
int qq=(k-1)/2*3+(j-1)%3+1;
f[q3][qq][qq+3]=2;
f[q3][qq+3][qq]=1;
}
}
}
}
}
dfs(1,1);
return 0;
}