just wtt
百度首页 | 百度空间
 
文章列表
 
2008-07-23 15:33
菜菜菜菜菜菜菜(631695609) 15:28:55
第33届ACM/ICPC亚洲区预选赛(杭州赛区)_网络选拔赛(10月18日)
第33届ACM/ICPC亚洲区预选赛(成都赛区)_网络选拔赛(10月19日)
菜菜菜菜菜菜菜(631695609) 15:29:29
哈尔滨赛区      9月20日        10月11日

北京赛区        9月27日     10月25日

杭州赛区        10月18日              11月22日

成都赛区        10月19日              11月29日

合肥赛区          9月28日              11月15日
 
2008-07-23 11:05
我是个懒人,就直接copy聊天记录了,呵呵
思路是:
用0表示没放,1表示放了。横放则左右两格都是1,竖放则上格是0,下格是1。
这种记录state的方法决定了:如果上下两行的state是确定的,那么放法唯一。
Fun(state,n)表示n这行的状态是state的时候有多少种放法。
那么我们要求的就是Fun(2^m-1,n).
Fun(state,n)就等于sigma Fun(last,n-1),last取遍所有可以取到的状态。
限制last取值的因素有两个:
1、state中是0的位置,last中一定是1,否则出现没填满的情况。
2、把state和last取&,也就是last是0的位,state也变0,看有没有影响到state,让它出现单1不能横放。
结束条件是n==1,且state能横放。

还有一个要注意的问题就是结果要用64位整型保存。


#include <cstdio>

const int large = 1<<11;
int m,n;
__int64 result[12][12];
__int64 dp[large][12];
int power;

__int64 Fun( const int state, const int n )
{
    if ( n == 1 )
    {
         int flag = 1;
         for ( int i = 0; i < power; ++i )
         {
             if ( (state&(1<<i)) == 0 )continue;
             if ( i+1 == m )
             {
                  flag = 0;
                  break;
             }
             if ( (state&(1<<(i+1))) == 0 )
             {
                  flag = 0;
                  break;
             }
             ++i;
         }
         if ( flag ) return 1; //若能横放
         return 0;
    }
   
     int last = ~state;//last是last状态1起码的状态
     last &= ( (1<<m) -1 );//我一开始忘记了加这一句,last全都是负的,哈哈
     __int64 s = 0;
     if ( dp[state][n] != -1 ) return dp[state][n];
    
     for ( int i = 0; i < power; ++i )
     {
         int flag = 1;
         int tmp = state&i;
         if ( (i&last) != last ) continue; //last限制因素1
         for ( int j = 0; j < m; ++j )//last限制因素2
         {
             if ( (tmp&(1<<j)) == 0 ) continue;
             if ( j+1 == m )
             {
                  flag = 0;
                  break;
             }
             if ( (tmp&(1<<(j+1))) == 0 )
             {
                  flag = 0;
                  break;
             }
             ++j;
         }
         if ( flag ) s+= Fun( i, n-1 );
     }
    
     dp[state][n] = s;
     return s;
}

int main()
{
    while ( scanf( "%d%d", &m, &n ), !( m == 0 && n == 0 ) )
    {
          int s = 0;
          if ( (m*n)%2 ) //面积
          {
               puts( "0" );
               continue;
          }
          if ( m > n ) //使n大m小
          {
               int tmp = m;
               m = n;
               n = tmp;
          }
          if ( result[n][m] != 0 ) //算过就不要再算了
          {
               printf( "%I64d\n", result[n][m] );
               continue;
          }
          power = 1<<m;
          //初始化
          for ( int i = 0; i < large; ++i )
          {
              for ( int j = 0; j <= n; ++j )
              {
                  dp[i][j] = -1;
              }
          }
         
          result[n][m] = Fun( power-1, n ); //最后一行放满
          printf( "%I64d\n", result[n][m] );
    }
   
    return 0;
}
 
2008-07-20 11:52
POJ 2411 Mondriaan's Dream 解题报告
(原文链接http://hi.baidu.com/newmyl/blog/item/b1d3c609fd6009206b60fbb1.html)

这题的DFS+DP解法:

      当高度和宽度都为奇数时显然答案为0, 这个用面积的奇偶性就很容易得证记f[i][s1]为第i-1行全满且第i行状态为s1时的种数,便有如下递推关系:
f[i][s1] = sigma(f[i-1][s2]);
其中(s1, s2)整体作为一个放置方案, 这样f[h+1][0]即是答案了

      对于每一个位置,我们有三种放置方法:

1.       竖直放置

2.       水平放置

3.       不放置

d为当前列号 ,初始化d, s1, s2都为0;对应以上三种放置方法,s1, s2的调整为:

1. d = d + 1, s1 << 1 | 1, s2 << 1;

2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;

3. d = d + 1, s1 << 1,   s2 << 1 | 1;

先就第一种情况解释一下,另外的两种情况可以类推

S1<<1|1即为把s1的二进制表示后面加上一个1,对就于本题来说就是(d+1)列上放置,s2<<1即为把s2的二进制表示后面加上一个0,对于本题来说就是(d+1)列上不放置。

       但为什么s1、s2会如此变化呢?s1对应于本行的状态,s2对应于上一行的状态,能竖直放置意味着上一行的(d+1)列是空着的,因此此时上一行的状态为s2<<1,同时竖置放置了之后,则本行(d+1)行放置了东西,状态于是变为s1<<1|1;

当d == w时保存状态

对于初始时的f值,可以假设第0行全满,第一行只有两种放法:

1. 水平放置 d = d + 2, s << 2 | 3;
2. 不放置   d = d + 1, s << 1;
另外,利用滚动数组,可以减少空间的开销

还有一个可以提高较率的地方,当输入的 w > h 时,对调,因为横向的运算是指数

级的, 而列向的是线性的.

附代码:
# include <stdio.h>
# include <string.h>

__int64 a[2][3000];
int t,n,m;

void dfs(int d,int mm) //d表示列数,mm表示状态
{
    if(d==m)
    {
        a[0][mm]++;
        return;
    }
    if(d+1<=m)
        dfs(d+1,mm<<1);
    if(d+2<=m)
        dfs(d+2,mm<<2|3);
}

void DFS(int d,int mm,int nn)//mm对应于上一行状态,nn对应于下一行状态
{
    if(d==m) //若全部的列都确定状态,就把此状态的放法数加到nn状态里
    {
        a[t][nn]+=a[(t+1)%2][mm];
        return;
    }
    if(d+1<=m) //如上所说
    {
        DFS(d+1,mm<<1,nn<<1|1);
        DFS(d+1,mm<<1|1,nn<<1);
    }
    if(d+2<=m)
        DFS(d+2,mm<<2|3,nn<<2|3);
}
int main()
{
    int i;
    while(scanf("%d%d",&n,&m)&&n&&m)
    {
        if((n*m)%2) //根据面积
        {
            printf("0\n");
            continue;
        }
        if(n>m)
            n^=m,m^=n,n^=m; //交换
        memset(a,0,sizeof(a));
        dfs(0,0);//初始化第一行
        for(i=2;i<=n;i++)
        {
            t=(i+1)%2; //滚动数组的第一个下标计算
            DFS(0,0,0);
            memset(a[(t+1)%2],0,sizeof(a[0]));//清空另一行
        }
        printf("%I64d\n",a[(n+1)%2][(1<<m)-1]); //输出最后一行全部放满的结果。
    }
    return 0;
}
别附打表代码:

# include <stdio.h>
__int64 a[11][11]={0,1,0,1,0,1,0,1,0,1,0,1,2,3,5,8,13,21,34,55,89,144,0,3,0,11,0,41,0,153,0,571,0,1,5,11,36,95,281,781,2245,6336,18061,51205,0,8,0,95,0,1183,0,14824,0,185921,0,1,13,41,281,1183,6728,31529,167089,817991,4213133,21001799,0,21,0,781,0,31529,0,1292697,0,53175517,0,1,34,153,2245,14824,167089,1292697,12988816,108435745,1031151241,8940739824,0,55,0,6336,0,817991,0,108435745,0,14479521761,0,1,89,571,18061,185921,4213133,53175517,1031151241,14479521761,258584046368,3852472573499,0,144,0,51205,0,21001799,0,8940739824,0,3852472573499,0};
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n&&m)
   printf("%I64d\n",a[n-1][m-1]);
return 0;
}
 
2008-07-18 18:09
Psytopic分析:您的性格类型是“ISFJ”(内向+实感+情感+判断)

沉静,友善,有责任感和谨慎。能坚定不移地承担责任。做事贯彻始终、不辞劳苦和准确无误。忠诚,替人着想,细心;往往记着他所重视的人的种种微小事情,关心别人的感受。努力创造一个有秩序、和谐的工作和家居 环境。

ISFJ型的人忠诚、有奉献精神和同情心,理解别人的感受。他们意志清醒而有责任心,乐于为人所需。 ISFJ型的人十分务实,他们喜欢平和谦逊的人。他们喜欢利用大量的事实情况,对于细节则有很强的记力。他们耐心地 对待任务的整个阶段,喜欢事情能够清晰明确。 ISFJ型的人具有强烈的职业道德,所以他们如果知道自己的行为真正有用时,会对需要完成之事承担责任。他们准确系统地完成任务。他们具有传统的价值观,十分保守。他 们利用符合实际的判断标准做决定,通过出色的注重实际的态度增加了稳定性。 ISFJ型的人平和谦虚、勤奋严肃。他们温和、圆通,支持朋友和同伴。他们乐于协助别人,喜欢实际可行地帮助他人。他们利用个人热情与人 交往,在困难中与他人和睦相处。ISFJ型的人不喜欢表达个人情感,但实际上对于大多数的情况和事件都具有强烈的个人反应。他们关心、保护朋友,愿意为朋友献身,他们有为他人服务的意识,愿意完成他们的责任和义 务。

您适合的领域有:领域特征不明显,较相关的如:医护领域、消费类商业、服务业领域

您适合的职业有:

· 内科医生
· 营养师
· 图书/档案管理员
· 室内装潢设计师
· 顾客服务代表
· 记账员
· 特殊教育教师
· 酒店管理
· 人事管理人员
· 电脑操作员
· 信贷顾问
· 零售业主
· 房地产代理或经纪人
· 艺术人员
· 商品规划师
· 语言病理学者
· 审计师
· 会计
· 财务经理
· 办公室行政管理
· 后勤和供应管理
· 中层经理
· 公务(法律、税务)执行人员
· 银行信贷员
· 成本估价师
· 保险精算师
· 税务经纪人
· 税务检查员
· 机械、电气工程师
· 计算机程序员
· 数据库管理员
· 地质
· 气象学家
· 法律研究者
· 律师
· 外科医生
· 药剂师
· 实验室技术人员
· 牙科医生
· 医学研究员

先找个地方记下来。这个苦命的孩子,多好的孩子噢
 
2008-07-13 20:36
我需要好好反省下!
 
     
 
留言板
 
36
又碰到一个,看来我们也挺有缘的。。
1784 backstreetlili 127 437







1787 wtthappy 127 508
2008-07-24 08:33
 
35
TT, 豪兄来也!
暑假过得开心哦。
2008-07-23 15:48
 
34
好 啊!
2008-07-20 10:46
 
33
来了,就要留下点东西,```````````
好好学习,天天向上哦!!
2008-07-20 09:38
 
32
2008-07-18 14:35
 
 
姓 名:    注册
网 址: (选填)
内 容:
验证码:
 
   
 
 
文章分类
 
 
 
 
 
 
 
 
 
     
 
最新动态
 
   
 
不知算不算侵权
 
 
 
 
 
 
 
 
     
 
好友最新文章
 
     
 
最近访客
 
 

www357105019

callchenxi

4751718

cjhwang

pigfanfan

威花饼

alpha__1986

亿熵
     
 
最新评论
   
文章评论|照片评论

 

好哪,那就来个原创的
 
 
 

怎么不自己写个?
 
漂亮
 
     
 
RSS订阅
 
   
 
我的搜藏
 
     
 
其它
 
已有人次访问本空间
 
订阅RSS  什么是RSS?

您也想拥有这样的空间?请点此申请。
     


©2008 Baidu