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ǎ崽 閱讀(356)
評論(1) 編輯 收藏 引用