2006年10月05日

CDT 3.1.1 Now Available! – September 29, 2006 – CDT 3.1.1 runs on Eclipse 3.2.x or Callisto. It can be downloaded from the Callisto Update site of by following the instructions on the CDT Download page by following the Downloads link on the left.

I am in the middle of Phoenix’ing the CDT web site. More content will appear here over the next few weeks. In the meantime more information about the CDT project can be found on the CDT Wiki and the old page is still available here.

Thanks for your patience, Doug Schaefer, CDT Project Lead

URL:http://download.eclipse.org/tools/cdt/releases/callisto/dist/3.1.1/

在WA了N次,TLE了M此之后,终于AC了.
DP状态转移方程:opti, j = opti, j − 1 + opti − j, j.
实际处理时需要用滚动数组保存状态,否则会因为寻址时间的增加而导致程序运行的时间暴增。
Source Code:
#include <stdio.h>

const int MAX = 4505;
const int M = 1000000007;

int n, m, res;

void DP()
{
    int i, j, tmp;
    int opt[MAX][2]={0};
    int now = 0;
  
    for(j=1; j<=n; j++){
        now = 1 – now;
        for(i=1; i<=m; i++){
          
            if(i<j) tmp = 0;
            else if(i==j) tmp = 1;
            else tmp = opt[i-j][now];
          
            opt[i][now] = opt[i][1-now] + tmp;
            if(opt[i][now]>=M) opt[i][now] -= M;
        }
    }
    res = opt[m][now];
}

int main()
{
//    freopen("1","r",stdin);
    scanf("%d%d", &n, &m);
    DP();
    printf("%d\n", res);
    return 0;
}

2006年10月03日

先计算任意两个单词之间的最大重合cost[i][j]

    * 用next_permutation可以过,但这样做没意思,时间消耗也大

    * 状态空间DP,传递方程:best[i][status] = max(best[i][status] , best[j][ps]+cost[i][j]);

DP时漏了一句调了N久
if((status&(1<<i))==0){   
        continue;
}

POJ1137 The New Villa典型的BFS,需要记录路径,状态记录有点烦
昨天状态的哈希函数写错了,没来得及改,今晚稍微改了一下,AC
用一个二维数组used[11][1<<11]记录状态,第一维记录目前所在的房间,第二维记录开着的灯
source code:

#include <stdio.h>
#include <string.h>

const int MAX = 5000;
struct Node{
    int now_room;//the room which you are in right now
    int action[3];//switch_on, switch_off, enter;
    bool on_light[11];//the lights which are lit are set to true
    int step;//steps
    int last;//the parent node
}queue[MAX];
bool light[11][11];//true means there are switchs in the room
bool cnn[11][11];//true means you can go to one room from another
bool used[11][1<<11];//hash table, count the states which are visited
int front, rear;
int bdrm, s, d;//bedroom , switchs and doors

bool lights_off()//test whether all lights are off
{
    int i;
    for(i=1;i<bdrm;i++){
        if(queue[rear].on_light[i]){
            return false;
        }
    }
    return true;
}

void BFS()
{
    Node cur;
    int i, j, index;
   
    front = rear = 0;
    queue[rear].now_room = 1;
    queue[rear].step = 0;
    queue[rear].last = -1;
    queue[rear].on_light[1] = true;
    used[1][1<<1] = true;
    rear++;// init the queue
   
    if(bdrm==1)return;//don’t forget this point
    while(front!=rear){
        cur = queue[front];
        front++;//couldn’t be a cycle queue,coz to note down the paths
        for(i=1;i<=2*bdrm;i++){
            queue[rear] = cur;
            queue[rear].step = cur.step + 1;
            queue[rear].last = front – 1;
            //count the lights which are on
            index = 0;
            for(j=1;j<=bdrm;j++){
             if(cur.on_light[j]){
              index |= 1<<j;
             }
            }
            for(j=0;j<3;j++){
             queue[rear].action[j] = 0;
            }
            if(i<=bdrm){//enter a room
                if(cnn[cur.now_room][i]==false||cur.on_light[i]==false){
                    continue;
                }
                if(used[i][index]==true){
                 continue;
                }
                used[i][index] = true;
                queue[rear].now_room = i;
                queue[rear].action[2] = i;
                if(i==bdrm&&lights_off()){
                 rear++;
                    return ;
                }
                rear++;
            }else{//switch on or off a light
             index ^= 1<<(i-bdrm);// ^ is good ^_^
             if(used[cur.now_room][index]){
              continue;
             }
            
                if(cur.on_light[i-bdrm]&&light[cur.now_room][i-bdrm]){//turn off a light
                    used[cur.now_room][index] = true;
                    queue[rear].on_light[i-bdrm] = false;
                    queue[rear].action[1] = i-bdrm;
                    if(cur.now_room==bdrm&&lights_off()){
                     rear++;
                     return;
                    }
                    rear++;
                }else if(!cur.on_light[i-bdrm]&&light[cur.now_room][i-bdrm]){//turn on a light
                    used[cur.now_room][index] = true;
                    queue[rear].action[0] = i-bdrm;
                    queue[rear].on_light[i-bdrm] = true;
                    rear++;
                }
            }
        }
               
    }
}

void outres()
{
    int i, res[100], j;
    rear–;
    printf("The problem can be solved in %d steps:\n",queue[rear].step);
    for(i=rear, j=0;i!=-1;i=queue[i].last,j++){
        res[j] = i;
    }
    for(j–;j>=0;j–){
        if(queue[res[j]].action[0]){
            printf("- Switch on light in room %d.\n",queue[res[j]].action[0]);
        }else if(queue[res[j]].action[1]){
            printf("- Switch off light in room %d.\n",queue[res[j]].action[1]);
        }else if(queue[res[j]].action[2]){
            printf("- Move to room %d.\n",queue[res[j]].action[2]);
        }
    }
}

int main()
{
    int i, j, k, villa = 1;
    //freopen("1","r",stdin);
    //freopen("2","w",stdout);
    while(scanf("%d%d%d",&bdrm, &d, &s), bdrm+d+s){
        printf("Villa #%d\n",villa);villa++;
        memset(cnn, 0, sizeof(cnn));
        memset(light, 0, sizeof(light));
        for(i=0;i<d;i++){
            scanf("%d%d",&j, &k);
            cnn[j][k] = cnn[k][j] = true;
        }
        for(i=0;i<s;i++){
            scanf("%d%d",&j, &k);
            if(j==k)continue;//couldn’t turn off the light in which room you are in
            light[j][k] = true;
        }
       // memset(queue, 0, sizeof(queue));//去掉这一句,终于变成了0ms
        memset(used, false, sizeof(used));
        BFS();
        if(front==rear){
            printf("The problem cannot be solved.\n\n");
        }else{
            outres();
            printf("\n");
        }
    }
    return 0;
}

原题链接:POJ1159Palindrome
以前基本没怎么写过DP
虽然是不难的一道DP题,但确实能感觉到DP的效率
不过优化了很长时间,也只能340ms,勉强排在第七名
不知道为什么自顶向下DP和自底向上DP的时间为什么差别那么大
代码在下面,如果有谁可以对自顶向下DP提出优化意见,欢迎在下面留言,或通过POJ上面我的ID跟我联系~

#include <stdio.h>
#define Min(a,b) (a<b?a:b)
const int MAX = 5001;
char ch[MAX];
short dp[MAX][MAX]={0};
int main()
{
   int lenth, i, j;
   scanf("%d%s",&lenth, ch+1);
   for(i=lenth;i>0;i–){//自底向上
      for(j=i+1;j<=lenth;j++){
         if(ch[i]==ch[j]){
            dp[i][j] = dp[i+1][j-1];
         }else{
            dp[i][j] = Min(dp[i+1][j],dp[i][j-1])+1;
         }
      }
   }
   printf("%d\n",dp[1][lenth]);
   return 0;
}
/*
int DP(int pre, int post)//自顶向下
{
   if(dp[pre][post]) return dp[pre][post];
   if(post<=pre) return dp[pre][post] = 1;
   if(ch[pre]==ch[post]) return dp[pre][post] = DP(pre+1, post-1);
   return dp[pre][post] = Min(DP(pre+1, post), DP(pre, post-1))+1;
}
int main()
{
   int res, lenth;
   scanf("%d%s",&lenth, ch);
   res = DP(0, lenth-1);
   printf("%d\n",res-1);
   return 0;
}
*/

麻烦的BFS题,以前看过但没做出来的一道题
昨天从daringQQ那里学会了用优先队(priority_queue),又想起看到过介绍说这道题可以用优先队列+A*做法,在计算中心作了两个小时没做出来
回来做了一晚上,郁闷得不得了,最后一刻终于Accepted了
本题的难度在于状态太多难处理,还有里面很多细节问题需要细心处理

大体思路:
把光标移动和交换数字作为一个阶段,数字加减作为另一阶段,两者分开处理
然后再用普通的BFS即可
如果想到到光标向左移动的情况不用考虑,可以减少一很大一部分无用状态入队

后来改为优先队列实现,run memory略有减少,由于时间已经是0ms了,而且本题不是很需要用优先队列,所以看不出多大差异
用STL封装的prioity_queue和调用堆排序自己写的优先队列的时间和空间消耗基本没多大区别

刚刚发现在数组开的比较大时用memset()函数会使得run memory急剧增加,run time也略有增加,所以在不需要多次对数组清零的情况下还是尽量少用memset比较好

前天晚上学会了并查集,今晚学会了Dijkstra和Floyd算法
不过POJ1847本来是很简单的一道题,却花了一个多小时才AC
不过这算是平生第一次写Dijkstra算法的题目,现学现用~
没有用堆,用的普通的时间复杂度为O(n^3)的Dijkstra,如果用堆Dijkstra的时间复杂度可减为O(n^2logn)。不过总之run time已经是0ms了,改不改无所谓了
代码:
 //Dijkstra POJ1847
#include <stdio.h>
#include <string.h>
const int MAX = 100;
int dist[101], arcs[101][101], check[101];
int N, A, B;
int lenth;
int no;
void find_dist()
{
   int i;
   lenth = MAX;
   for(i=1;i<=N;i++){
      if(check[i] && arcs[i][no]!=-1 && dist[i]+arcs[i][no]<lenth){
         lenth = dist[i]+arcs[i][no];
      }
   }
}
void LeastSwtch_DJS()
{
   int i, k, min;
   check[A] = 1;
   dist[A] = 0;
   for(i=1;i<N;i++){
      min = MAX;
      for(no=1;no<=N;no++){
         if(!check[no]){
            find_dist();
            if(lenth<min){
               k = no;
               min = lenth;
            }
         }
      }
     if(min==MAX){
        return ;
     }
     dist[k] = min;
     check[k] = 1;
     if(k==B){
        return ;
     }
   }
}
int main()
{
   int i, j, rail, swtch;
   scanf("%d%d%d", &N, &A, &B);
   memset(dist, -1, sizeof(dist));
   memset(arcs, -1, sizeof(arcs));
   memset(check, 0, sizeof(check));
   for(i=1;i<=N;i++){
      scanf("%d",&rail);
      for(j=0;j<rail;j++){
         scanf("%d", &swtch);
         if(j==0){
            arcs[i][swtch]=0;
         }else{
            arcs[i][swtch]=1;
         }
      }
   }
   LeastSwtch_DJS();
   printf("%d\n",dist[B]);
   return 0;
}

pku1011 Sticks不愧是search+ 强剪枝的经典~
是2362 Square的加强版,搜索策略大同小异,但pku1011对剪枝的要求远远高于pku2362~~
从0点作到4点,剪了N次枝,从TLE到WA,终于以OmsAC了~~~
思路是按分段数从给定值开始依次减小搜索。
本题中所用到的剪枝技巧:
剪枝1:分段数res肯定能被总长度sum整除
剪枝2:每段的长度不可能大于初始分段的最大值
剪枝3:将输入的数据从大到小排序,因为一支长度为L的完整木棍肯定比几支短木棍拼成的同样长度的用处小(短小的用途更灵活一点)
剪枝4 :找到结果之后在能返回的地方马上返回递归的上一层
剪枝5:相同长度的木棍不要搜索多次,用当前的这支搜下去得不出结果,那么用下一支同样长度的还是得不到结果
剪枝6:相当关键的剪枝,就是栽在这个剪枝上面两个多小时。判断当前长度是不是大于每段应该的长度,如果大于则没必要往下递归
剪枝7:不用说了,前面的肯定都用过了,所以从level+1开始
剪枝8: if(all-times+1<res-no)判断当前剩下的段数是否还足以拼成需要拼得的段数
剪枝9:如果从当前最长的长度开始往下搜索一遍得不到正确结果则返回,因为每段都要用上,如果搜索不成功,那么以比它短的开始也一定不能得到全局的成功。
代码:
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;

int all,find1,res,times,used[65],stick[65];
int maxlen,lenth,sum;

void dfs(int no, int curlen, int level);
void fit(int no)
{
    int i;
    if(find1==1 || no>res){//find1==1剪枝4
    find1 = 1;
    return ;
    }for(i=0; i<all; i++){
        if(!used[i]) break;
    }
    used[i] = 1;
    times++;
    dfs(no, stick[i], i);
    times–;
    used[i] = 0;
}//剪枝:以当前最大值开始搜索一遍,无结果,返回

void dfs(int no, int curlen, int level)
{
    if(curlen == lenth){
        fit(no+1);
        return ;
    }
    if(find1==1)//剪枝4
        return ;
    int i,j;
    for(i=level+1; i<all; i++){//剪枝7,level+1换为0则多出31ms
        if(!used[i] && curlen+stick[i]<=lenth){//剪枝6
            //就是忘了这个最基本的 curlen+stick[i]<=lenth剪枝导致TLE了一晚上
            if(all-times+1<res-no)//剪枝8,去掉多出15ms
                return ;
            used[i] = 1;
            times++;
            dfs(no, curlen+stick[i], i);
            times–;
            used[i] = 0;
            j=i;
            if(find1==1)//剪枝4,去掉多出15ms
                return ;
            while(i<all && stick[j]==stick[i])//剪枝5,去掉则TLE
                i++;
            if(i==all)return ;
            if(i!=j)i–;
        }
    }
}

void work()
{
    if(sum%res!=0)//剪枝1
        return ;
    lenth = sum / res;
    if(maxlen > lenth)//剪枝2
        return ;
    times = 0;
    fit(1);
}

int main()
{
    int i;
    while(1){
        sum = 0;
        maxlen = 0;
        scanf("%d", &all);
        if(all==0)
            break;
        for(i=0; i<all; i++){
            scanf("%d", &stick[i]);
            if(maxlen<stick[i])
                maxlen = stick[i];
            sum += stick[i];
        }
        sort(stick, stick+all, greater<int>());//剪枝3
        memset(used, 0, sizeof(used));
        times = 0;
        for(res=all; res>0; res–){
            find1 = 0;
            work();
            if(find1==1)
                break;
        }
        printf("%d\n",sum / res);
    }
    return 0;
}

2006年10月02日

原题链接:Biorhythms
以前在zju上面做过,由于zju是限制10s所以随随便便就过了
 
昨天的比赛中有一题是关于中国剩余定理的,今天查了一下,其内容为:
 
若某数x分别被d1、、…、dn除得的余数为r1、r2、…、rn,则可表示为下式:
x=R1r1+R2r2+…+Rnrn+RD
其中R1是d2、d3、…、dn的公倍数,而且被d1除,余数为1;
R1 、R2…、Rn是d1、d2、…、dn-1的公倍数,而且被dn除,余数为1;
D是d1、d2、…、的最小公倍数;
R是任意整数,可根据实际需要决定;
且d1、、…、必须互质,以保证每个Ri(i=1,2,…,n)都能求得.
 
实际上POJ1006就是中国剩余定理的典型应用
根据上面的条件求出常数R1 = 5544,R2 = 14421,R3 = 1288,D = 21252
每次给的数据中的前三个值即相当于上面的余数。
则显然:
res = R1 * Physical + R2 * Emotion + R3 * Intelligence + RD – givenDate
并且0 =< res <= D
 
原代码如下:
#include <stdio.h>
int main()
{
   int R1 = 5544, R2 = 14421, R3 = 1288, R = 21252;
   int ph, em, in, day;
   int res,i;
   for(i=1; 1; i++){
      scanf("%d%d%d%d", &ph, &em, &in, &day);
      if(ph==-1)break;
      res = (R1 * ph + R2 * em + R3 * in – day) % R;
      res = (res + R – 1) % R + 1;
      printf("Case %d: the next triple peak occurs in %d days.\n", i, res);
   }
   return 0;
}
/****************************************************
//find the value of R1, R2 and R3 according to 中国剩余定理
int main()
{
   int i;
   int R1, R2, R3;
   for(i=1, R1=28*33; 1; i++)
   if(R1*i%23==1)break;
   R1 *= i;
   for(i=1, R2=23*33; 1; i++)
      if(R2*i%28==1) break;
   R2 *= i;
   for(i=1, R3=23*28; 1; i++)
      if(R3*i%33==1) break;
   R3 *= i;
   printf("R1 = %d \nR2 = %d\nR3 = %d\n",R1,R2,R3);
   return 0;
}
*****************************************************/