随笔-72  评论-126  文章-0  trackbacks-0
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ǎ崽 阅读(343) 评论(1)  编辑 收藏 引用

评论:
# re: 第一轮PK。。。 2009-04-05 21:46 | AekdyCoin
太神牛了
仰慕0rz  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理