ForFun以及剪刀深化

在网上看到一道题目,如何判断机器是低端发还是高端发?

当然,答案很简单:

1.我们利用union的排布是从低址开始的,可以写出如下程序:

union Endian{
int a;
char b;
};

Endian s;
s.a=6;
if(s.b==6) cout<<"Little_endian"<<endl;
else cout<<"Big_endian"<<endl;

2.当然，本菜想假如没那么灵光的话，其实用库函数也可以的[网络流是怎么排布的？我们在socket里面有个函数htons是拿来干什么的，所以下面的也是同样效果]

#include <Winsock2.h>
#pragma comment(lib, "Ws2_32.lib")

INT portId=1556;
if(htons(portId)==portId)
cout<<"Big_endian"<<endl;
else cout<<"Little_endian"<<endl;

算法正在忙些写，等把这两道题目搞定再说吧！

1.说话间，发现为什么错了，“是我想太多，你总这样说。。。”！这道题目就是这样的[数的加和每个加数其实是一致的，也可以说是等价的！希望大家能理解，至于算法框架嘛，其实本菜的两个框架，递归和指示头的都是对的！]PS：看到某位牛人贴出来的帖子，其实，有个地方可以改进下，不过发现改了也没什么效果，2，3MS的时间，它也测不出来！[但发现top榜上，还有0MS的，吓到起了，直觉告诉我，这道题目有公式，能优化的地方只有数学了！不过，今天主要练搜索，还好还好，没有太让我失望,在控制范围中搞定！]

http://acm.pku.edu.cn/JudgeOnline/problem?id=1011

Source Code

Problem: 1011		User: orlando22
Memory: 280K		Time: 16MS
Language: C++		Result: Accepted

Source Code

#include <iostream>

using namespace std;
const int MAXEL=64;
int arr[MAXEL], avt, size, sum, stick[MAXEL], st_size, head[MAXEL];//可改进的地方
bool success;
char bit[MAXEL];//bitset is less than 64

//declaration : optimization
void forsticks(int i);
void dfs(int begin, int i);
void cls();

//implementation
void forsticks(int i){
    if(i==st_size){
        success=true; return;
    }
    //i's sticks
    int b;
    if(i==0) b=size-1;
    else b=head[i-1]-1;
    if(b>=st_size-i-1){//cut-off branches，注意上下界的剪刀
        int k;
        for(k=b;k>=st_size-i-1; k--)
            if(!bit[k]&&stick[i]-arr[k]>=0) break;
        head[i]=k,bit[k]=1,stick[i]-=arr[k];
        dfs(k-1, i);
        head[i]=-1,bit[k]=0,stick[i]+=arr[k];
        if(success) return;//dummy implementaiton
        if(stick[i]-arr[k]==0) return;//数学和纯搜索的区别，加数和Vectex不是完全一致的！加数是顺序无关的！这点可以省去循环！
    }
}

void dfs(int begin, int i){
    if(success) return;
    if(stick[i]==0){
        forsticks(i+1); return;
    }
    if(begin>size||i>=st_size) return;//stupid code here!
    for(int k=begin; k>=0; k--){//arr[k] descending, so... no problem
        if(!bit[k]&&stick[i]-arr[k]>=0){
            bit[k]=1,stick[i]-=arr[k];
            dfs(k-1, i);//if stick[i]==0
            bit[k]=0,stick[i]+=arr[k];
            if(success) return;
            if(stick[i]-arr[k]==0) return;//ignore following item
        }
    }
}

void cls(){
    memset((void*)bit, 0, MAXEL);
    for(int i=0; i<st_size; i++) stick[i]=avt;
}

int main()
{
    //implementation
    int max;
    while(cin>>size&&size!=0){
        sum=0,max=INT_MIN;
        for(int i=0; i<size; i++){
            cin>>arr[i];//insert sorting
            int k=i, temp=arr[i];
            for(;k-1>=0&&temp<arr[k-1]; k--) arr[k]=arr[k-1];
            arr[k]=temp;
            if(temp>max) max=temp;
            sum+=temp;
        }
        success=false;
        for(int i=max; i<=sum; i++){
            if(sum%i!=0) continue;
            else{
                st_size=sum/i,avt=i;
                cls();
                forsticks(0);
                if(success){
                    cout<<avt<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

玫瑰花茶的下午