国产欧美日本一区二区三区,亚洲国产成人不卡,日韩亚洲国产精品

[备忘]函数调用�U�定

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

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

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

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

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

基数排序每一遍对待排数的某一位进行计数排序，依次从最低位到最高位�?br />下面�E�序把非负数�?6�q�制处理�Q�每�ơ取16�q�制的一位。这��h��?0�q�制方便快捷很多�?br />�~�点是不能处理负数。可以将所有数都增加一个基数所其成为正数。排序完成后�Q�再减去�q�个基数�?br />但是对于32位最��的负数1<<31�q�样一个特例，是不行的�?br />用一个中间数�l�保存中间结果，每一遍排完后�Q�交换两指针�Q�这样可以避免多�ơ数据复制。由于一共有8遍，�l�束后，array中�ؓ最后一�ơ排完序的结果�?br />
代码如下�Q?br />

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

摘要: 求无向图中的一个最��环的长�?nbsp; 阅读全文

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

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

对于复制代�h很高的元素，通过某种排序��法�q�行间接排序�?br />排序完成后，再一�ơ复制回厅R�?br />�q�样需要一个中间数�l�，�q�行2N�ơ复制�?br />通过原地�|�换�Q�我们可以只使用一个中间变量，最多进�?N/2�ơ复制即可达到目的�?br />
如index[1]==3。那么，说明array[1]�q�个位置应该攄��是array[3].我们��array[1]保存到tmp中�?br />然后array[1]=array[3].现在array[3]是可以放�|�的了。那么我们看array[3]应该放什么，如果index[3]==2,刚好我们把tmp攑֛�厅R�?br />不然�Q�我们��l�按�q�个链找下去�?br />如果��N��为x.那么我们需要x+1�ơ复制�?br />��N��最��ؓ2.所以我们最多只需�?N/2�ơ复制即可�?br />

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�Q�说明array[i]已经攑ֈ�了最�l�的地方�?/span>
        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]已经攑֥��?/span>
                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�?br />从hk开始，每次��间隔hx的序列排好序�Q�直到h1。间隔hx的序列排好序的数�l�可以称之�ؓhx有序�?br />Shell排序有一个重要的性质是一个hx有序数组�Q�必然是一个hx+1有序数组�?br />每一遍排序过�E�可以��用插入排序�?br />
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 发表评论

[备忘]内存寚w��问题

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

昨天和wub讨论�Q��ؓ什么struct寚w��的时候，double�c�d��的地址要以8寚w��?br />寚w��的目的就是�ؓ了方便和加速处理器��d��Q�那么只需要和字长寚w��可以了�?br />�Ҏ��q�两��文章：《内存对齐与ANSI C中struct型数据的内存布局�?/font>vs《难以理解的《内存对齐与ANSI C中struct型数据的内存布局�?/a>�?/a>gcc和vc下是不同的�?span style="font-size: 12pt; color: black;">对于double�c�d��Q�默认gcc�?/span>寚w��模数�?,VC�?.
内存寚w��是与处理器，�~�译器，�~�译选项相关的，因此单纯�l�出一个struct�Q�问其sizeof是多��，�q�样的问法是不严谨的。回�{�该问题�Q�应该加以说明运行环境�?br />vc的默认对齐模数是�Q�sizeof(该类�?
gcc的默认对齐规则是�Q�byte�?,char�?,其他均�ؓ4.
�׃��可知
struct s{
char c;
double d;
};

gcc�?br />sizeof(s) = 4+8 �Q?12
vc�?br />sizeof(s) = 8+8 = 16

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

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

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

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

选择排序和冒泡排序很�怼��Q�时间复杂度相同�Q�选择排序性能上要优于冒��Q�一�ơ选择�q�程中只交换一�ơ，比较�ơ数和冒泡相同�?br />
冒��排序�Q?br />

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;
}

选择排序�Q?br />

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);
}

做一些小优化�Q�只创徏一�ơ��时数�l��?br />

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 ;

     // 自此以后�Q�index�?开始�?/span>
    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: ��L��数组 output:大顶�?/span>
static void _build_heap( int * array, int len)
{
    int i;
    for (i = len / 2 ;i >= 1 ; -- i){
        _adjust_heap(array,i,len);
   }
}

// 佉K��C��array满��堆特�?/span>
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

最基础的快速排�?br />优点�Q�编码简单，清晰
�~�点�Q�对于排好序的输入，旉��复杂度�ؓ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;
}

改进�Q�小数组直接用插入排序实玎ͼ�中枢值取(begin,mid,end)三者的中间��|��Ҏ��序数�l�排序仍为O(nlogn)。减��了边界条�g��?br />�~�点�Q�编码复杂�?br />

#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 发表评论

�Q�d��忘］��装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

�q�题有些难。虽然知道是动态规划题�Q�但是不知道要开多大的数�l�，后来看analysis用一�?56大小的数�l��@环��用，�Ҏ��很��y妙�?br />先将box�q�行排序�?br />如果box里面的数的最大公�U�数不�ؓ1的话�Q�那么所有组成的敎ͼ�只可能是�q�个公约数的倍数�Q�因此没有上限，输出�?.
用last记录最��的“不能组成的数”。这样当last之后有boxs[0]个连�l�数都可以组成的话，那么所有的数都可以�l�成�?br />last+1...last+box[0]可以�l�成的话�Q�那么每个数都加一个box[0],那么��C��轮的box[0]个数也可以组成，以此�c�L��?br />

#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

一开始把题意理解错了�Q�以为刻在同一张光盘上的歌曲的旉��序不变��可以了�?br />事实上不仅同光盘上的歌曲写入旉��要按��序�Q�前一张光盘上的歌曲不能比后一张歌曲写入时间要晚�?br />
数据量比较少�Q�用回溯法，dp也行�?br />

#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;
    }

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

    for(int i=last;i<disk_num;++i){
         //如果当前歌曲需要刻录，那只需��d��W�一张能装得下的光盘上�?br />        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轴的直线扫描三角形，求交点，然后计算中间点的敎ͼ�求和卛_��?br />

#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

摘要: �l�出一个树的中序遍历和先序遍历�Q�求它的后序遍历�?nbsp; 阅读全文

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

USACO 3.3 A Game

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

动态规划法�?br />用dp[player][start][end]表示player在[start..end]会取得的最大倹{�?br />如果player==0�Q�那么player有主动权�Q�它要么选start,要么选end.昄��Q�它要选��得对手得分最��的那一个�?br />当它选start�Ӟ��Ҏ��所能到的最大��gؓdp[1][start+1][end]。当它选end�Ӟ��Ҏ��所选的最大值是dp[1][start][end-1].
。所以我们选dp[1][start+1][end]和dp[1][start][end-1]中小的那一个�?br />如果player==1�Q�那只能被动的等0先选了�?在剩下区�D�中�Q�又作�ؓ先选的角色�Q�即player0�?br />当只有一个数字的时候，player0��只有选这个，player1��没得选，�q�回0.
代码如下�Q?br />

#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

又在�W�一题上�׃��很多旉��Q�这�ơ更夸张。。用�?0多分钟。。。最后提交时只有150分了。�?br />�W�二题，一看挺��单，��是求质因数的个敎ͼ�然后看能�?的几�ơ幂整除�?br />一开始匆忙写了一个，然后提交�Q?00分�?br />代码如下�Q?br />

              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�q�时�Q�N一直在变，应该保存下N或者直接求sqrt(N)。一开始不太确定sqrt能否处理long long�Q�因此用�怹�的方法。后来cha人的时候，发现一个也犯了同样的错误，马上构�?6=2*2*2*7,cha�?br />于是�Ҏ��下面�Q�提交，只有299分了。。�?br />

              int getLevel(long long N)
                  {

                  int res = 0;
                  long long T = N; //增加�q�一行           �?/span>
                  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;
                  }

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

              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++; //增加�q�一�?br />
                  int r=0;
                  while(res/4!=0){
                                  res/=4;
                                  r++;
                   }

                  return r;
                  }

最后房间只有一��了第二题�?br />�q�好cha�?个，不然rating要跌不少了。�?br />�q�好rating�q�是涨了一点点。�?br />太粗心了�Q�不然就应该能进div1了。�?br />

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)�Q�边长�ؓm的正方�Ş是否完整。那�?br />如果dp[i][j][m]完整�Q�则当且仅当dp[i][j][m-1],dp[i+1][j][m-1],dp[i][j+1][m-1],dp[i+1][j+1][m-1]的正方�Ş也是完整�?��M��囑ְ�很清��C��)。由于我们从上到下，从左到右扫描每个点，在每一轮i,j用过一�ơ，��׃��会再使用�Q�所以只需用二�l�数�l�保存dp[i][j]�Q�即可�?br />旉��复杂度�ؓO(n^3),�I�间复杂度�ؓO(n^2)。analysis中有个时间复杂度为O(n^2),�I�间O(n)的解法�?br />

#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

背包问题�Q�dp解决�?br />dp[i][j][k][m][n]表示�W?-4�U�物品分别购买i-n个时�Q�所需的最��费用�?br />那么对于每一个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中提出用最短�\径的�Ҏ��来解�Q�思�\很��y妙。把”装有不同种数和数量的物品“的��子看作�l�点�Q�把offer作�ؓ�?把购��C��件物品的原始��h��看成一�U�退化的offer)�Q�把��h��作�ؓ辚w��度。这样就转换成从��子(0,0,0,0,0)到所求结点的最短�\径问题�?br />
代码如下:

#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到”按物品出现��序所�l�的�~�号“的映射
int price[1000];//product id对应的物品�h�?br />int product_num;//物品��L��?br />int products[5];//存放product id
int amount[5];//product 所需的数�?br />
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;
    }

    //没有折扣时的��h��
    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�Q�谢谢网友“我也凑热闹"指出。由于map所有值都�?。所以未在商品列表中出现的商品的map值都�?�Q�即都映��ؓ�W�一个商品。现�Ҏ��map初始化�ؓ-1�Q��ƈ增加判断语句。此外将初始化dp的语句合�q�到后面�Q�以��化代码�?br />

#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 发表评论

�Q�问题解军_��忘］ping不通localhost

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

今天写一个socket��程序，��试一下，居然�q�不上去。然后ping localhost发现ping不通，但是能上外网�?br />��实很奇怪，搜了下，后来在ubuntu论坛上发玎ͼ�才想��h��我的/etc/network/interfaces文�g配置问题�?br />以前在手动改�q�个文�g的时候，��手把lo接口�l�删了。。�?br />难怪启动的时候x server一直报错，��d��上lo接口�Q�只/etc/init.d/networking restart�q�是不行的，重启马上��p��决了�?br />记录一下，备忘�?br />

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

USACO 3.2 Sweet Butter

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

摘要: �E�疏图的多源最短�\径问�?nbsp; 阅读全文

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

USACO 3.2 Magic Squares

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

BFS搜烦题。代码写的比较�ؕ�Q�用一个set来存储已�l�访问过的结炏V��analysis中的标程有不��可以学习的地方�Q�如几个操作的变换，用�{换数�l�来写，代码清晰明了�Q�encode�Ҏ��q��M��set。我通过保存整个树来输出解，标程通过反向操作�Q�来输出解，做法很��y妙�?br />

#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�U�，各个轮子��复位了。所以在360�U�内�Q�每�q�一�U�检��一下是否可以透过光即可�?br />用一个数�l�记录能透过0-359的轮子的个数�Q�当在某一度轮子的个数辑ֈ��?�Q�则说明光可以透过�Q�输出即可�?br />否则说明是不可能有光透过�?br />

#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 发表评论