http://acm.tju.edu.cn/toj/showp3232.html简单题。。考虑全相等的特殊情况
http://acm.tju.edu.cn/toj/showp3233.html看明白后也是简单题。。。从左上搜，从右下搜，考虑重合的情况
http://acm.tju.edu.cn/toj/showp3234.html简单DP，比赛时候复制下标没改。。。花了10分钟才检查出。。
先排序：然后按从小到大的顺序进行DP,因为要严格递增，所有一个数只能影响比他大的数。。。
http://acm.tju.edu.cn/toj/showp3235.html递推，公式很快就出来。就是要大数，恶心死了。。没写过模板，临时写了一个。。TLE了，晕。。优化了几次后AC。。
= a[i-1] (P)
a[i] = a[i-1]*2 (L)
= a[i-1]*2 + cnt(R)
= a[i-1]*5 + cnt(*)
cnt为3的（*出现的的次数）次方，即：一个*是3，3个*就是27.。
http://acm.tju.edu.cn/toj/showp3236.html数独，只能用交叉线，还要判断有没有出错
我写了一个小时，用位运算，写的很飘逸
可惜在判断error的时候没有考虑完全，当时提交了3次WA。
今天早上稍微修改了下check的函数，就AC了。。。
唉。。要是当时这地方检查出来多好。。。
献上我的AC代码
#include<stdio.h>
#include<string>
#define inf 511 //9个数字全满
#include<stdlib.h>
int num[27]; //用27个数字记录下全局：横的9个，竖的9个，9个小九宫格
char map[10][10];
bool lowbit(int x) {
return (x&(x-1))==0;
}
bool add(int id,char ch)
{
int buf = 1<<(ch-'0'-1); //读入数据
if(num[id] & buf) //有重复
return true;
num[id] += buf;
return false;
}
bool fun(int a,int b)
{
int ans;
int buf;
int x,y,i,j;
ans = inf - (num[(a/3)*3 + (b/3) + 18]|num[a]|num[b+9]);//这格可以填的数
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(i==0 && j==0)
continue;
x = a/3*3 + (a+i)%3;
y = b/3*3 + (b+j)%3;
if(map[x][y]=='.')
{
buf = num[x] | num[y+9]; //这格不能填的数
ans &= buf; //这个可以填的数
}
}
if(!ans) //这格不能填
return false;
if(lowbit(ans)) //能填唯一的一个
{
num[a] += ans; //更新全局num
num[b+9] += ans;
num[(a/3)*3 + (b/3) + 18] += ans;
buf = 0;
while(ans) {
ans >>= 1;
buf ++;
}
map[a][b] = buf + '0';
return true;
}
return false;
}
bool check(int a,int b)
{
int ans;
int buf;
int x,y,i,j;
ans = inf - (num[(a/3)*3 + (b/3) + 18]|num[a]|num[b+9]);
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
if(i==0 && j==0)
continue;
x = a/3*3 + (a+i)%3;
y = b/3*3 + (b+j)%3;
if(map[x][y]=='.')
{
buf = num[x] | num[y+9];
ans &= buf;
}
}
if(!ans || !lowbit(ans))
return false;
if(ans == 1<<(map[a][b] - '1'))
return false;
return true; //只能填一个且和这格数字不相等，则有冲突
}
int main()
{
int i,j;
bool flag;
while(scanf("%s",map[0])==1)
{
for(i=1;i<9;i++)
scanf("%s",map[i]);
memset(num,0,sizeof(num));
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(map[i][j]!='.')
{
if(add(i,map[i][j])) //可以判断有没有重复的数字
goto loop; //适当的用下goto还是很好用的^-^
if(add(j+9,map[i][j]))
goto loop;
if(add((i/3)*3 + (j/3) + 18,map[i][j]))
goto loop;
}
}
}
flag = true;
while(flag)
{
flag = false;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(map[i][j]=='.' && fun(i,j))
flag = true;
else if(map[i][j]!='.' && check(i,j))
goto loop;
}
}
}
for(i=0;i<9;i++)
puts(map[i]);
continue;
loop:
puts("ERROR");
}
return 0;
}
posted on 2009-04-05 11:16
shǎ崽 阅读(344)
评论(1) 编辑 收藏 引用