http://acm.tju.edu.cn/toj/showp3232.html簡(jiǎn)單題。?？紤]全相等的特殊情況
http://acm.tju.edu.cn/toj/showp3233.html看明白后也是簡(jiǎn)單題。。。從左上搜，從右下搜，考慮重合的情況
http://acm.tju.edu.cn/toj/showp3234.html簡(jiǎn)單DP，比賽時(shí)候復(fù)制下標(biāo)沒(méi)改。。?；?0分鐘才檢查出。。
先排序：然后按從小到大的順序進(jìn)行DP,因?yàn)橐獓?yán)格遞增，所有一個(gè)數(shù)只能影響比他大的數(shù)。。。
http://acm.tju.edu.cn/toj/showp3235.html遞推，公式很快就出來(lái)。就是要大數(shù)，惡心死了。。沒(méi)寫過(guò)模板，臨時(shí)寫了一個(gè)。。TLE了，暈。。優(yōu)化了幾次后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的（*出現(xiàn)的的次數(shù)）次方，即：一個(gè)*是3，3個(gè)*就是27.。
http://acm.tju.edu.cn/toj/showp3236.html數(shù)獨(dú)，只能用交叉線，還要判斷有沒(méi)有出錯(cuò)
我寫了一個(gè)小時(shí)，用位運(yùn)算，寫的很飄逸
可惜在判斷error的時(shí)候沒(méi)有考慮完全，當(dāng)時(shí)提交了3次WA。
今天早上稍微修改了下check的函數(shù)，就AC了。。。
唉。。要是當(dāng)時(shí)這地方檢查出來(lái)多好。。。
獻(xiàn)上我的AC代碼
#include<stdio.h>
#include<string>
#define inf 511 //9個(gè)數(shù)字全滿
#include<stdlib.h>
int num[27]; //用27個(gè)數(shù)字記錄下全局：橫的9個(gè)，豎的9個(gè)，9個(gè)小九宮格
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); //讀入數(shù)據(jù)
if(num[id] & buf) //有重復(fù)
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]);//這格可以填的數(shù)
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]; //這格不能填的數(shù)
ans &= buf; //這個(gè)可以填的數(shù)
}
}
if(!ans) //這格不能填
return false;
if(lowbit(ans)) //能填唯一的一個(gè)
{
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; //只能填一個(gè)且和這格數(shù)字不相等，則有沖突
}
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])) //可以判斷有沒(méi)有重復(fù)的數(shù)字
goto loop; //適當(dāng)?shù)挠孟耮oto還是很好用的^-^
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ǎ崽 閱讀(347)
評(píng)論(1) 編輯 收藏 引用