C++博客-止于自娱

[备忘]函数调用约定

YZY — Thu, 23 Jul 2009 02:58:00 GMT

常见的调用约定有： stdcall cdecl fastcall thiscall naked call
stdcall是pascal语言的默认调用约定，从右向左压栈，由被调用者负责清栈
cdecl是c语言的默认调用约定，从右向左压栈，由调用者负责清栈。

YZY 2009-07-23 10:58 发表评论

[基础算法复习]基数排序

YZY — Fri, 17 Jul 2009 11:49:00 GMT

基数排序每一遍对待排数的某一位进行计数排序，依次从最低位到最高位。
下面程序把非负数按16进制处理，每次取16进制的一位。这样比用10进制方便快捷很多。
缺点是不能处理负数。可以将所有数都增加一个基数所其成为正数。排序完成后，再减去这个基数。
但是对于32位最小的负数1<<31这样一个特例，是不行的。
用一个中间数组保存中间结果，每一遍排完后，交换两指针，这样可以避免多次数据复制。由于一共有8遍，结束后，array中为最后一次排完序的结果。

代码如下：

void _radix_sort(int *src,int *dst,int len,int offset);

int radix_sort(int *array,int begin,int end)
{
    if(array==NULL||begin>end) return 0;

    int len = end-begin+1;
    int *tmp = malloc(sizeof(int)*len);

    int *src,*dst;

    src = array;
    dst = tmp;

    int i;
    for(i=0;i<32;i+=4){
        _radix_sort(src,dst,len,i);
        tmp = src;
        src = dst;
        dst = tmp;
    }

    free(dst);

    return 1;
}

void _radix_sort(int *src,int *dst,int len,int offset)
{
    int cnt[16];
    memset(cnt,0,sizeof(cnt));

    int mask = 0xF<<offset;

    int i=0;
    for(i=0;i<len;++i){
        cnt[ (src[i]&mask)>>offset ] ++;
    }

    for(i=1;i<16;++i){
        cnt[i]+=cnt[i-1];
    }

    for(i=len-1;i>=0;--i){
        dst[--cnt[(src[i]&mask)>>offset]] = src[i];
    }
}

YZY 2009-07-17 19:49 发表评论

[备忘]'#'号的预处理

YZY — Fri, 17 Jul 2009 08:55:00 GMT

#define macro(x) {#x,do_##x}
macro(hello)
预处理后展开为:
{"hello",do_hello}

YZY 2009-07-17 16:55 发表评论

USACO 4.1 Fence Loops

YZY — Fri, 17 Jul 2009 06:26:00 GMT

摘要: 求无向图中的一个最小环的长度阅读全文

YZY 2009-07-17 14:26 发表评论

[基础算法复习]原地置换的间接排序

YZY — Thu, 16 Jul 2009 03:52:00 GMT

对于复制代价很高的元素，通过某种排序算法进行间接排序。
排序完成后，再一次复制回去。
这样需要一个中间数组，进行2N次复制。
通过原地置换，我们可以只使用一个中间变量，最多进行3N/2次复制即可达到目的。

如index[1]==3。那么，说明array[1]这个位置应该放的是array[3].我们将array[1]保存到tmp中。
然后array[1]=array[3].现在array[3]是可以放置的了。那么我们看array[3]应该放什么，如果index[3]==2,刚好我们把tmp放回去。
不然，我们继续按这个链找下去。
如果链长为x.那么我们需要x+1次复制。
链长最小为2.所以我们最多只需要3N/2次复制即可。

int indirect_sort(int *array,int len) {

    if(array==NULL||len<=0) return 0;

    //索引数组
    int *index = malloc(sizeof(int)*(len));
    if(index==NULL) return 0;

    int i,j,largest,tmp,tmp2;

    for(i=0;i<len;++i){
        index[i] = i;
    }

    //插入排序
    for(i=1;i<len;++i){
        tmp = index[i];
        for(j=i;j-1>=0&&array[index[j-1]]>array[tmp];--j){
            index[j] = index[j-1];
        }
        index[j] = tmp;
    }

    for(i=0;i<len;++i){
        //如果index[i]==i，说明array[i]已经放到了最终的地方。
        if( index[i] == i)
            continue;
        else{
            tmp = array[i];
            j = i;
            while( index[j]!=i ){
                //array[j]应该放的是array[index[j]]
                array[j] = array[index[j]];
                tmp2 = j;
                j = index[j];
                //原来的array[j]已经放好了
                index[tmp2] = tmp2;
            }
            array[j] = tmp;
            index[j] = j;
        }
    }

    return 1;
}

YZY 2009-07-16 11:52 发表评论

[基础算法复习]Shell排序

YZY — Thu, 16 Jul 2009 01:33:00 GMT

Shell排序使用一个递增序列h1,h2,h3...hk. h1==1。
从hk开始，每次将间隔hx的序列排好序，直到h1。间隔hx的序列排好序的数组可以称之为hx有序。
Shell排序有一个重要的性质是一个hx有序数组，必然是一个hx+1有序数组。
每一遍排序过程可以使用插入排序。

Shell排序的性能取决于递增序列的选择。下面代码的递增序列是len/2,len/4...,1.

int shell_sort(int *array,int begin,int end)
{
    if(array==NULL||begin>end) return 0;

    int len = end-begin+1;

    int i,j,gap,tmp;
    for(gap=len/2;gap>=1;gap/=2){
       for(i=begin+gap;i<=end;++i){
           j = i;
           tmp = array[j];
           while( j-gap>=begin&&array[j-gap]>tmp ){
               array[j] = array[j-gap];
               j-=gap;
           }
           array[j] = tmp;
       }
    }

    return 1;
}

YZY 2009-07-16 09:33 发表评论

[备忘]内存对齐问题

YZY — Wed, 15 Jul 2009 08:37:00 GMT

昨天和wub讨论，为什么struct对齐的时候，double类型的地址要以8对齐。
对齐的目的就是为了方便和加速处理器读取，那么只需要和字长对齐就可以了。
根据这两篇文章：《内存对齐与ANSI C中struct型数据的内存布局》vs《难以理解的《内存对齐与ANSI C中struct型数据的内存布局》》gcc和vc下是不同的。对于double类型，默认gcc的对齐模数是4,VC是8.
内存对齐是与处理器，编译器，编译选项相关的，因此单纯给出一个struct，问其sizeof是多少，这样的问法是不严谨的。回答该问题，应该加以说明运行环境。
vc的默认对齐模数是：sizeof(该类型)
gcc的默认对齐规则是：byte为1,char为2,其他均为4.
由上可知
struct s{
char c;
double d;
};

gcc下
sizeof(s) = 4+8 ＝ 12
vc下
sizeof(s) = 8+8 = 16

那么 struct s{
double d;
char c;
};
起初我认为c以后不需要填充，因此gcc下sizeof(s)=8+1 = 9。但事实应该是sizeof(s)==8+4 = 12。
因为对于数组来说，要保证数组的大小等于数组的个数乘以元素的大小。因此c之后也是需要填充的,这样后续的元素的地址才会是字长的倍数。

YZY 2009-07-15 16:37 发表评论

[基础算法复习]冒泡排序和选择排序

YZY — Wed, 15 Jul 2009 03:59:00 GMT

选择排序和冒泡排序很相似，时间复杂度相同，选择排序性能上要优于冒泡，一次选择过程中只交换一次，比较次数和冒泡相同。

冒泡排序：

int bubble_sort(int *array,int begin,int end)
{
    if(array==NULL||begin>end) return 0;

    int i,j;

    for(i=end;i>begin;--i){
        for(j=begin;j<i;++j){
            if( array[j]>array[j+1] ){
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
            }
        }
    }

    return 1;
}

选择排序：

int select_sort(int *array,int begin,int end) {

    if(array==NULL||begin>end) return 0;

    int i,j,largest,tmp;

    for(i=end;i>begin;--i){

        largest = i;
        for(j=begin;j<=i;++j){
            if( array[largest]<array[j] )
                largest = j;
        }
        tmp = array[i];
        array[i] = array[largest];
        array[largest] = tmp;
    }

    return 1;
}

YZY 2009-07-15 11:59 发表评论

[基础算法复习]归并排序

YZY — Wed, 15 Jul 2009 03:46:00 GMT

static void _merge( int * src, int begin, int end);

int merge_sort( int * array, int begin, int end)
{
     if (array == NULL || begin > end) return 0 ;

    int mid = begin + (end - begin) / 2 ;
   merge_sort(src,begin,mid);
   merge_sort(src,mid + 1 ,end);
   _merge(src,begin,end);

    return 1;
}

static void _merge( int * src, int begin, int end)
{
     int mid = begin + (end - begin) / 2 ;

     int b1 = begin;
     int e1 = mid;
     int b2 = mid + 1 ;
     int e2 = end;

     int * dest = malloc( sizeof ( int ) * (end - begin + 1 ));
     if (dest == NULL) return ;

     int i1;
     int i2;
     int i;
     for (i1 = b1,i2 = b2,i = begin;i1 <= e1 && i2 <= e2 && i <= end; ++ i){
         if (src[i1] < src[i2]){
            dest[i - begin] = src[i1];
            i1 ++ ;
        } else {
            dest[i - begin] = src[i2];
            i2 ++ ;
        }
    }

     for (;i <= end && i1 <= e1; ++ i, ++ i1)
       dest[i - begin] = src[i1];
     for (;i <= end && i2 <= e2; ++ i, ++ i2)
       dest[i - begin] = src[i2];

     for (i = begin;i <= end; ++ i)
        src[i] = dest[i - begin];

    free(dest);
}

做一些小优化，只创建一次临时数组。

void _mergesort(int *array,int *tmp,int start,int end);

void mergesort(int *array,int len)
{
    int i,*tmp;

    if(array==NULL||len==0)
        return;

    tmp = (int*)malloc(sizeof(int)*len);

    _mergesort(array,tmp,0,len-1);

    free(tmp);
}

void _mergesort(int *array,int *tmp,int start,int end)
{
    int mid = (start+end)/2;
    int i,j,k;

    if(start>=end)
        return;

    _mergesort(array,tmp,start,mid);
    _mergesort(array,tmp,mid+1,end);

   i = start;
   j = mid+1;

   for(k=start;k<=end&&i<=mid&&j<=end;++k){
       if(array[i]<array[j]){
           tmp[k] = array[i];
           i++;
       }else{
           tmp[k]= array[j];
           j++;
       }
   }

   for(;i<=mid;++i)
       tmp[k++]=array[i];

   for(;j<=end;++j)
       tmp[k++]=array[j];

  memcpy(&array[start],&tmp[start],sizeof(int)*(end-start+1));
}

YZY 2009-07-15 11:46 发表评论

[基础算法复习]堆排序

YZY — Wed, 15 Jul 2009 01:50:00 GMT

static void _build_heap( int * array, int len);
static void _adjust_heap( int * array, int idx, int len);

int heap_sort( int * array, int begin, int end)
{
     if (array == NULL || begin > end) return 0 ;

     // 自此以后，index从1开始。
    array -- ;
     int len = end - begin + 1 ;
    _build_heap(array,len);

     int tmp;
     int i;

     for (i = 1 ;i < len; ++ i){
        tmp = array[len - i + 1 ];
        array[len - i + 1 ] = array[ 1 ];
        array[ 1 ] = tmp;
        _adjust_heap(array, 1 ,len - i);
    }
}

// input: 任意数组 output:大顶堆
static void _build_heap( int * array, int len)
{
    int i;
    for (i = len / 2 ;i >= 1 ; -- i){
        _adjust_heap(array,i,len);
   }
}

// 使重新使array满足堆特性
static void _adjust_heap( int * array, int idx, int len)
{
     int left;
     int right;
     int larger = idx;
     int tmp = array[idx];

    left = (idx << 1 );
    right = left + 1 ;

     while ( left <= len){
         if (right <= len && array[right] > array[left]){
            larger = right;
        } else {
            larger = left;
        }

         if ( array[larger] > tmp ){
            array[idx] = array[larger];
            idx = larger;
            left = (idx << 1 );
            right = left + 1 ;
        } else {
             break ;
        }
    }

    array[idx] = tmp;
}

YZY 2009-07-15 09:50 发表评论

[基础算法复习]快速排序

YZY — Tue, 14 Jul 2009 13:58:00 GMT

最基础的快速排序
优点：编码简单，清晰
缺点：对于排好序的输入，时间复杂度为O(n^2)

static int partition(int *array,int start,int end);

int quicksort(int *array,int start,int end)
{
    if(array==NULL||start>end) return 0;

    int t = partition(array,start,end);

    quicksort(array,start,t-1);
    quicksort(array,t+1,end);

    return 1;
}

static int partition(int *array,int start,int end)
{
    int pivot = array[start];

    int i = start;
    int j = end;

    while( i<j ){
        while( j>i&& array[j]>=pivot) j--;
        array[i] = array[j];
        while( j>i&& array[i]<=pivot ) i++;
        array[j] = array[i];
    }

    array[i] = pivot;
    return i;
}

改进：小数组直接用插入排序实现，中枢值取(begin,mid,end)三者的中间值，对有序数组排序仍为O(nlogn)。减少了边界条件检查
缺点：编码复杂。

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define SMALL_N 10

static int partition(int *array,int begin,int end);

void _quicksort(int *array,int begin,int end);

void insertsort(int *array,int len)
{
    int i;
    if(array==NULL||len==0)
        return;

    for(i=1;i<len;++i){
        int temp = array[i];
        int j;
        for(j=i;j>=1&&temp<array[j-1];--j){
            array[j] = array[j-1];
        }
        array[j] = temp;
    }

}

int quicksort(int *array,int len)
{
    if(array==NULL||len==0)
        return;

    _quicksort(array,0,len-1);
}

void _quicksort(int *array,int begin,int end)
{
    int pivot;
    int pivot_pos;

    if(end-begin+1<=SMALL_N){
        insertsort(&array[begin],end-begin+1);
        return;
    }

    pivot_pos = partition(array,begin,end);
    _quicksort(array,begin,pivot_pos-1);
    _quicksort(array,pivot_pos+1,end);
}

static int  mid3(int *array,int begin,int end)
{
    int mid = (end-begin)/2+begin;

    int tmp;

    tmp = array[mid];

    if(tmp<array[begin]){
        array[mid] = array[begin];
        array[begin] = tmp;
    }

    tmp = array[end];

    if(tmp<array[mid]){
        array[end] = array[mid];

        if(tmp<array[begin]){
           array[mid] = array[begin];
           array[begin] = tmp;
        }
        else{
            array[mid] = tmp;
        }
    }

    tmp = array[end-1];
    array[end-1] = array[mid];
    array[mid] = tmp;

    return array[end-1];
}

static int partition(int *array,int begin,int end)
{
    int pivot = mid3(array,begin,end);

    int i, j;

    int tmp;

    i = begin;
    j = end-1;

    while(1){
        while(array[++i]<pivot) ;
        while(array[--j]>pivot) ;

       if(i>j)
          break;

       tmp = array[j];
       array[j] = array[i];
       array[i] = tmp;
    }

    tmp = array[i];
    array[i] = array[end-1];
    array[end-1] = tmp;
    return i;
}

YZY 2009-07-14 21:58 发表评论

［备忘］封装printf

YZY — Sun, 12 Jul 2009 13:07:00 GMT

写一个函数封装printf以trace

void my_trace(const char *cmd,)
{
    va_list args;

    va_start(args,cmd);
    vprintf(cmd,args); //必须用vprintf
    va_end(args);
}

YZY 2009-07-12 21:07 发表评论

USACO 4.1 Beef McNuggets

YZY — Sun, 12 Jul 2009 06:58:00 GMT

这题有些难。虽然知道是动态规划题，但是不知道要开多大的数组，后来看analysis用一个256大小的数组循环使用，方法很巧妙。
先将box进行排序。
如果box里面的数的最大公约数不为1的话，那么所有组成的数，只可能是这个公约数的倍数，因此没有上限，输出为0.
用last记录最小的“不能组成的数”。这样当last之后有boxs[0]个连续数都可以组成的话，那么所有的数都可以组成。
last+1...last+box[0]可以组成的话，那么每个数都加一个box[0],那么新一轮的box[0]个数也可以组成，以此类推。

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("nuggets.in");
ofstream fout("nuggets.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int box_num;
int boxs[10];

bool ok[256];

int gcd(int a,int b)
{
    if(a<b) swap(a,b);

    int tmp;

    while(b!=0){
        tmp = a;
        a = b;
        b = tmp%b;
    }

    return a;
}

void solve()
{

    in>>box_num;
    for(int i=0;i<box_num;++i)
        in>>boxs[i];

    sort(&boxs[0],&boxs[box_num]);

    int t = boxs[0];

    for(int i=1;i<box_num;++i){
        t = gcd(t,boxs[i]);
    }

    if(t!=1){
        out<<0<<endl;
        return;
    }

    memset(ok,0,sizeof(ok));

    int last = 0;
    ok[0] = true;
    int i=0;

    while(true){
        if(ok[i%256]){
            ok[i%256] = 0;
            if(i-last>=boxs[0]){
                out<<last<<endl;
                return;
            }
            for(int x=0;x<box_num;++x){
                ok[(i+boxs[x])%256] = true;
            }
        }else{
            last = i;
        }
        ++i;
    }
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

Beef McNuggets

Hubert Chen

Farmer Brown's cows are up in arms, having heard that McDonalds is considering the introduction of a new product: Beef McNuggets. The cows are trying to find any possible way to put such a product in a negative light.

One strategy the cows are pursuing is that of `inferior packaging'. ``Look,'' say the cows, ``if you have Beef McNuggets in boxes of 3, 6, and 10, you can not satisfy a customer who wants 1, 2, 4, 5, 7, 8, 11, 14, or 17 McNuggets. Bad packaging: bad product.''

Help the cows. Given N (the number of packaging options, 1 <= N <= 10), and a set of N positive integers (1 <= i <= 256) that represent the number of nuggets in the various packages, output the largest number of nuggets that can not be purchased by buying nuggets in the given sizes. Print 0 if all possible purchases can be made or if there is no bound to the largest number.

The largest impossible number (if it exists) will be no larger than 2,000,000,000.

PROGRAM NAME: nuggets

INPUT FORMAT

Line 1:	N, the number of packaging options
Line 2..N+1:	The number of nuggets in one kind of box

SAMPLE INPUT (file nuggets.in)

OUTPUT FORMAT

The output file should contain a single line containing a single integer that represents the largest number of nuggets that can not be represented or 0 if all possible purchases can be made or if there is no bound to the largest number.

SAMPLE OUTPUT (file nuggets.out)

YZY 2009-07-12 14:58 发表评论

USACO 3.4 Raucous Rockers

YZY — Sat, 11 Jul 2009 03:48:00 GMT

一开始把题意理解错了，以为刻在同一张光盘上的歌曲的时间顺序不变就可以了。
事实上不仅同光盘上的歌曲写入时间要按顺序，前一张光盘上的歌曲不能比后一张歌曲写入时间要晚。

数据量比较少，用回溯法，dp也行。

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rockers.in");
ofstream fout("rockers.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int capacity[20];;
int songs[20];
int song_num,disk_num;

int res = 0;
int cur;

void backtracing(int depth,int last)
{
    if(depth==song_num){
        if(cur>res){
            res = cur;
        }
        return;
    }

    //如果后面所有的歌曲都加上还比最优值小，剪枝
    if(cur+song_num-depth<=res)
       return;

    for(int i=last;i<disk_num;++i){
         //如果当前歌曲需要刻录，那只需刻在第一张能装得下的光盘上。
        if( capacity[i]>=songs[depth]){
            cur++;
            capacity[i]-=songs[depth];
            backtracing(depth+1,i);
            capacity[i]+=songs[depth];
            cur--;
            break;
        }
    }

    // 不刻当前歌曲
    backtracing(depth+1,last);

}

void solve()
{
    int c;
    in>>song_num>>c>>disk_num;

    for(int i=0;i<song_num;++i)
        in>>songs[i];

    for(int i=0;i<disk_num;++i)
        capacity[i] = c;

    backtracing(0,0);

    out<<res<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-11 11:48 发表评论

USACO 3.4 Electric Fence

YZY — Fri, 10 Jul 2009 14:19:00 GMT

用一根平行x轴的直线扫描三角形，求交点，然后计算中间点的数，求和即可。

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("fence9.in");
ofstream fout("fence9.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

void solve()
{
    int n,m,p;
    in>>n>>m>>p;

    int res = 0;

    int s,e;
    for(int y=1;y<m;++y){
        s = n*y/m+1;
        e = ( y*(n-p)%m==0 ) ? (y*(n-p)/m-1+p) : floor(((double)y*(n-p)/m)+p);
      //  out<
        res += max(0,(e-s+1));
    }

    out<<res<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-10 22:19 发表评论

USACO 3.4 American Heritage

YZY — Fri, 10 Jul 2009 10:51:00 GMT

摘要: 给出一个树的中序遍历和先序遍历，求它的后序遍历。阅读全文

YZY 2009-07-10 18:51 发表评论

USACO 3.3 A Game

YZY — Thu, 09 Jul 2009 05:50:00 GMT

动态规划法。
用dp[player][start][end]表示player在[start..end]会取得的最大值。
如果player==0，那么player有主动权，它要么选start,要么选end.显然，它要选使得对手得分最少的那一个。
当它选start时，对手所能到的最大值为dp[1][start+1][end]。当它选end时，对手所选的最大值是dp[1][start][end-1].
。所以我们选dp[1][start+1][end]和dp[1][start][end-1]中小的那一个。
如果player==1，那只能被动的等0先选了。1在剩下区段中，又作为先选的角色，即player0。
当只有一个数字的时候，player0就只有选这个，player1就没得选，返回0.
代码如下：

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("game1.in");
ofstream fout("game1.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int dp[2][100][100];
int sequence[100];

int score(int player,int start,int end)
{
    if(dp[player][start][end]!=-1)
        return dp[player][start][end];

    if(start==end){
        if(player==0)
            dp[player][start][end] = sequence[start];
        else
            dp[player][start][end] = 0;
    }else{
        int t1 = score(0,start+1,end);
        int t2 = score(0,start,end-1);
        if(player==0){
            if(t1>t2){
                dp[player][start][end] = sequence[end]+score(1,start,end-1);
            }else{
                dp[player][start][end] = sequence[start]+score(1,start+1,end);
            }
        }else{
            if(t1>t2){
                dp[player][start][end] = score(0,start,end-1);
            }else{
                dp[player][start][end] = score(0,start+1,end);
            }
        }
    }

    return dp[player][start][end];
}

void solve()
{
    memset(dp,-1,sizeof(dp));

    int size;
    in>>size;

    for(int i=0;i<size;++i)
        in>>sequence[i];

    out<<score(0,0,size-1)<<" "<<score(1,0,size-1)<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-09 13:50 发表评论

SRM 444

YZY — Wed, 08 Jul 2009 13:29:00 GMT

又在第一题上花了很多时间，这次更夸张。。用了20多分钟。。。最后提交时只有150分了。。
第二题，一看挺简单，就是求质因数的个数，然后看能被4的几次幂整除。
一开始匆忙写了一个，然后提交，400分。
代码如下：

              int getLevel(long long N)
                  {

                  int res = 0;

                  for(long long i=2;i*i<=N;++i){
                           while(N%i==0){
                                         res++;
                                         N/=i;
                                         }
                           }

                  int r=0;
                  while(res/4!=0){
                                  res/=4;
                                  r++;
                   }

                  return r;
                  }

后来一看，i*i<=N这时，N一直在变，应该保存下N或者直接求sqrt(N)。一开始不太确定sqrt能否处理long long，因此用相乘的方法。后来cha人的时候，发现一个也犯了同样的错误，马上构造56=2*2*2*7,cha掉
于是改成下面，提交，只有299分了。。。

              int getLevel(long long N)
                  {

                  int res = 0;
                  long long T = N; //增加这一行
                  for(long long i=2;i*i<=T;++i){
                           while(N%i==0){
                                         res++;
                                         N/=i;
                                         }
                   }

                  int r=0;
                  while(res/4!=0){
                                  res/=4;
                                  r++;
                   }

                  return r;
                  }

结果还是被cha掉了。因为犯了一个严重的错误，没有算上最后一个质因数，这个质因数可能大于sqrt(N)。如88==2*2*2*11。
正确代码应该是

              int getLevel(long long N)
                  {

                  int res = 0;
                  long long T = N;
                  for(long long i=2;i*i<=T;++i){
                           while(N%i==0){
                                         res++;
                                         N/=i;
                                         }
                   }

                   if(N!=1) res++; //增加这一行

                  int r=0;
                  while(res/4!=0){
                                  res/=4;
                                  r++;
                   }

                  return r;
                  }

最后房间只有一人过了第二题。
还好cha了4个，不然rating要跌不少了。。
还好rating还是涨了一点点。。
太粗心了，不然就应该能进div1了。。

YZY 2009-07-08 21:29 发表评论

USACO 3.3 Home on the Range

YZY — Wed, 08 Jul 2009 09:44:00 GMT

dp题。用dp[i][j][m]表示左上角为(i,j)，边长为m的正方形是否完整。那么
如果dp[i][j][m]完整，则当且仅当dp[i][j][m-1],dp[i+1][j][m-1],dp[i][j+1][m-1],dp[i+1][j+1][m-1]的正方形也是完整的(画个图就很清晰了)。由于我们从上到下，从左到右扫描每个点，在每一轮i,j用过一次，就不会再使用，所以只需用二维数组保存dp[i][j]，即可。
时间复杂度为O(n^3),空间复杂度为O(n^2)。analysis中有个时间复杂度为O(n^2),空间O(n)的解法。

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("range.in");
ofstream fout("range.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

bool dp[250][250];
int side_len;

void input()
{
    in>>side_len;

    char t;

    for(int i=0;i<side_len;++i){
        for(int j=0;j<side_len;++j){
            while( in.get(t)&&isspace(t) );
            dp[i][j] = t-'0';
        }
    }
}

void solve()
{
    input();

    for(int w = 2;w<=side_len;++w){
        int cnt = 0;

        for(int i=0;i<side_len;++i){
            for(int j=0;j<side_len;++j){
                if(i+w<=side_len&&j+w<=side_len){
                    dp[i][j] = dp[i][j]&&dp[i+1][j]&&dp[i][j+1]&&dp[i+1][j+1];
                    if(dp[i][j])
                        cnt++;
                }
            }
        }

        if(cnt!=0){
            out<<w<<" "<<cnt<<endl;
        }
    }
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-08 17:44 发表评论

USACO 3.3 Shopping Offers

YZY — Tue, 07 Jul 2009 11:16:00 GMT

背包问题，dp解决。
dp[i][j][k][m][n]表示第0-4种物品分别购买i-n个时，所需的最小费用。
那么对于每一个offer
dp[i][j][k][m][n] = min ( dp[i][j][k][m][n], dp[i-o[0]][j-o[1]][k-o[2]][m-o[3]][n-o[4]]+offer.cost);

analysis中提出用最短路径的方法来解，思路很巧妙。把”装有不同种数和数量的物品“的篮子看作结点，把offer作为边(把购买一件物品的原始价格看成一种退化的offer)，把价格作为边长度。这样就转换成从篮子(0,0,0,0,0)到所求结点的最短路径问题。

代码如下:

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("shopping.in");
ofstream fout("shopping.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int dp[6][6][6][6][6];

struct offer{
    int pro_num;
    int price;
    int product[5];
    int amount[5];
};

int offer_num;
offer offers[100];
int map[1000]; //product id到”按物品出现顺序所给的编号“的映射
int price[1000];//product id对应的物品价格
int product_num;//物品总数目
int products[5];//存放product id
int amount[5];//product 所需的数量

void solve()
{
    in>>offer_num;

    for(int i=0;i<offer_num;++i){
        in>>offers[i].pro_num;
        for(int j=0;j<offers[i].pro_num;++j){
            in>>offers[i].product[j]>>offers[i].amount[j];
        }
        in>>offers[i].price;
    }

    int pro_idx = 0;

    in>>product_num;

    for(int i=0;i<product_num;++i){
        in>>products[i];
        in>>amount[i];
        in>>price[i];
        map[ products[i] ] = i;
    }

    //没有折扣时的价格
    for(int i=0;i<=5;++i)
        for(int j=0;j<=5;++j)
            for(int k=0;k<=5;++k)
                for(int m=0;m<=5;++m)
                    for(int n=0;n<=5;++n){
                        dp[i][j][k][m][n] =
                            price[0]*i+
                            price[1]*j+
                            price[2]*k+
                            price[3]*m+
                            price[4]*n;
                    }

    for(int i=0;i<=5;++i)
        for(int j=0;j<=5;++j)
            for(int k=0;k<=5;++k)
                for(int m=0;m<=5;++m)
                    for(int n=0;n<=5;++n){
                        int tmp[5];
                        for(int s=0;s<offer_num;++s){

                            memset(tmp,0,sizeof(tmp));
                            for(int t=0;t<offers[s].pro_num;++t){
                                tmp[map[offers[s].product[t]]] = offers[s].amount[t];
                            }

                            if(i>=tmp[0]&&j>=tmp[1]&&k>=tmp[2]&&m>=tmp[3]&&n>=tmp[4]){
                                dp[i][j][k][m][n] = min( dp[i][j][k][m][n],
                                        dp[i-tmp[0]][j-tmp[1]][k-tmp[2]][m-tmp[3]][n-tmp[4]]+
                                        offers[s].price);
                            }
                        }
                    }

    out<<dp[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

上面代码有个严重的bug，谢谢网友“我也凑热闹"指出。由于map所有值都为0。所以未在商品列表中出现的商品的map值都为0，即都映射为第一个商品。现改成将map初始化为-1，并增加判断语句。此外将初始化dp的语句合并到后面，以简化代码。

#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("shopping.in");
ofstream fout("shopping.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int dp[6][6][6][6][6];

struct offer{
    int pro_num;
    int price;
    int product[5];
    int amount[5];
};

int offer_num;
offer offers[100];
int map[1000];
int price[1000];
int product_num;
int products[5];
int amount[5];

void solve()
{
    in>>offer_num;

    for(int i=0;i<offer_num;++i){
        in>>offers[i].pro_num;
        for(int j=0;j<offers[i].pro_num;++j){
            in>>offers[i].product[j]>>offers[i].amount[j];
        }
        in>>offers[i].price;
    }

    int pro_idx = 0;

    in>>product_num;

    //2009.07.27修改
    memset(map,-1,sizeof(map));

    for(int i=0;i<product_num;++i){
        in>>products[i];
        in>>amount[i];
        in>>price[i];
        map[ products[i] ] = i;
    }

    for(int i=0;i<=5;++i)
        for(int j=0;j<=5;++j)
            for(int k=0;k<=5;++k)
                for(int m=0;m<=5;++m)
                    for(int n=0;n<=5;++n){

                         dp[i][j][k][m][n] =
                            price[0]*i+
                            price[1]*j+
                            price[2]*k+
                            price[3]*m+
                            price[4]*n;

                        int tmp[5];
                        for(int s=0;s<offer_num;++s){
                            memset(tmp,0,sizeof(tmp));
                            for(int t=0;t<offers[s].pro_num;++t){
                                //2009.07.27修改
                                if( map[offers[s].product[t]]!=-1)
                                    tmp[map[offers[s].product[t]]] = offers[s].amount[t];
                            }

                            if(i>=tmp[0]&&j>=tmp[1]&&k>=tmp[2]&&m>=tmp[3]&&n>=tmp[4]){
                                dp[i][j][k][m][n] = min( dp[i][j][k][m][n],
                                        dp[i-tmp[0]][j-tmp[1]][k-tmp[2]][m-tmp[3]][n-tmp[4]]+
                                        offers[s].price);
                            }
                        }
                    }

    out<<dp[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-07 19:16 发表评论

USACO 3.3 Riding The Fences

YZY — Tue, 07 Jul 2009 08:59:00 GMT

摘要: 欧拉路径阅读全文

YZY 2009-07-07 16:59 发表评论

［问题解决备忘］ping不通localhost

YZY — Mon, 06 Jul 2009 13:30:00 GMT

今天写一个socket小程序，测试一下，居然连不上去。然后ping localhost发现ping不通，但是能上外网。
确实很奇怪，搜了下，后来在ubuntu论坛上发现，才想起是我的/etc/network/interfaces文件配置问题。
以前在手动改这个文件的时候，顺手把lo接口给删了。。。
难怪启动的时候x server一直报错，添加上lo接口，只/etc/init.d/networking restart还是不行的，重启马上就解决了。
记录一下，备忘。

YZY 2009-07-06 21:30 发表评论

USACO 3.2 Sweet Butter

YZY — Mon, 06 Jul 2009 12:05:00 GMT

摘要: 稀疏图的多源最短路径问题阅读全文

YZY 2009-07-06 20:05 发表评论

USACO 3.2 Magic Squares

YZY — Mon, 06 Jul 2009 12:01:00 GMT

BFS搜索题。代码写的比较乱，用一个set来存储已经访问过的结点。analysis中的标程有不少可以学习的地方，如几个操作的变换，用转换数组来写，代码清晰明了，encode方法就省去了set。我通过保存整个树来输出解，标程通过反向操作，来输出解，做法很巧妙。

#include <iostream>
#include <fstream>
#include <set>
#include <queue>

using namespace std;

ifstream fin("msquare.in");
ofstream fout("msquare.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

int final[8];
set<int>visited;
char result[8*7*6*5*4*3*2*1+1];

struct queue_node{
    int current[8];
    queue_node *parent;
    char op;
};

void op(int *current,char c)
{
    int tmp;
    switch(c){
        case 'A':
            for(int i=0;i<4;++i)
                swap(current[i],current[7-i]);
            break;
        case 'B':
            tmp = current[3];
            for(int i=3;i>=1;--i)
                current[i] = current[i-1];
            current[0] = tmp;
            tmp = current[4];
            for(int i=4;i<=6;++i)
                current[i] = current[i+1];
            current[7] = tmp;
            break;
        case 'C':
            tmp = current[6];
            current[6] = current[5];
            current[5] = current[2];
            current[2] = current[1];
            current[1] = tmp;
            break;
    }
}

int cur_value(int *cur)
{
    int res = 0;
    for(int i=0;i<8;++i){
        res*=10;
        res+=cur[i];
    }

    return res;
}

void solve()
{
    for(int i=0;i<8;++i){
        in>>final[i];
    }

    queue<queue_node*> q;
    queue_node *node = new queue_node;
    for(int i=0;i<8;++i)
        node->current[i] = i+1;

    node->parent = NULL;

    q.push(node);

    while( !q.empty() ){
        queue_node *node = q.front();
        q.pop();

        int cur = cur_value(node->current);
        if( visited.find( cur) != visited.end())
            continue;
        visited.insert(cur);

        bool ok = true;
        for(int i=0;i<8;++i){
            if(node->current[i]!=final[i]){
                ok = false;
                break;
            }
        }

        if(ok){
            int i = 0;
            while(node->parent!=NULL){
                result[i++] = node->op;
                node=node->parent;
            }

            if(i==0){
                out<<0<<endl<<endl;
                exit(0);
            }

            out<<i<<endl;

            int j;
            i--;
            for(j=0;i>=0;i--,j++){
                out<<result[i];
                if(j%60==59) out<<endl;
            }

            if(j%60!=0)
                out<<endl;

            exit(0);
        }

        for(char c='A';c<='C';++c){
            queue_node * n = new queue_node;
            memcpy(n->current,node->current,sizeof(node->current));
            op(n->current,c);
            n->op = c;
            n->parent = node;
            q.push(n);
        }
    }
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-06 20:01 发表评论

USACO 3.2 Spinning Wheels

YZY — Sat, 04 Jul 2009 12:49:00 GMT

最多转360秒，各个轮子就复位了。所以在360秒内，每过一秒检测一下是否可以透过光即可。
用一个数组记录能透过0-359的轮子的个数，当在某一度轮子的个数达到了5，则说明光可以透过，输出即可。
否则说明是不可能有光透过。

#include <iostream>
#include <fstream>

using namespace std;

ifstream in("spin.in");
ofstream out("spin.out");

struct wedge{
    int start;
    int extent;
};

int speed[5];
wedge wedges[5][5];
int wedge_num[5];

void onesecond()
{
   for(int i=0;i<5;++i){
       for(int j=0;j<wedge_num[i];++j){
           wedges[i][j].start+=speed[i];
           wedges[i][j].start%=360;
       }
   }
}

bool isok()
{
    int tmp[360];

    memset(tmp,0,sizeof(tmp));

    for(int i=0;i<5;++i){
        for(int j=0;j<wedge_num[i];++j){
            for(int k=0;k<=wedges[i][j].extent;++k)
                tmp[(wedges[i][j].start+k)%360]++;
        }
    }

    for(int i=0;i<360;++i)
        if(tmp[i]==5)
            return true;

    return false;
}

void solve()
{
    for(int i=0;i<5;++i){
        in>>speed[i];
        in>>wedge_num[i];
        for(int j=0;j<wedge_num[i];++j){
            in>>wedges[i][j].start>>wedges[i][j].extent;
        }
    }

    if(isok()){
        out<<0<<endl;
        return;
    }

    for(int i=1;i<=360;++i){
        onesecond();
        if(isok()){
            out<<i<<endl;
            return;
        }
    }
    out<<"none"<<endl;
}

int main(int argc,char *argv[])
{
    solve();
    return 0;
}

YZY 2009-07-04 20:49 发表评论