• 背包问题分析,要做就做好玩的,挑战下楼教主的“八题”之一,应该是“多重背包0-1化”吧!

方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为 1,2,4,…,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。 什么意思,嘿嘿,有趣的思路,很强,关键在这里:将原问题转化为了复杂度为O(V*∑log n[i])的01背包问题

楼教主的题目果真不同凡响,模型很简单,优化很复杂![其实模型也不简单了,先参考了DD牛的背包九讲,早上很快写出来一个版本]。

1。解法一:用多重背包转0-1背包的方法,转化为二进制处理,切记“边界条件”要小心!C[i]->1,2,4….C[i]-(前面的和),道理很简单,开复喜欢问这个,比如一箱苹果之类的,就一个二进制,复杂度是O(nmsum(logc)).然后,提交,不出所料,TLE!看来一定要把后面那个去掉sum(logc).这个老兄的Blog上有个优化,可以看下,但我没想好怎么写,所以暂时不管了。Coins分析[教主八题最简单的一道]

0-1背包转化很重要,代码如下:

pku上被直接鄙视,TLE!

Source Code

Problem: 1742

User: orlando22

Memory: N/A

Time: N/A

Language: C++

Result: Time Limit Exceeded//这行红字,心都在滴血!
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXN=100,MAXM=100000,MAXB=3200;
    int bit[MAXB];
    int n,m,a[MAXN],c[MAXN];
    int Two[12]={0,1,2,4,8,16,32,64,128,256,512,1024};//1000, start with 1
    
    //bit macro
    #define SET(i) (bit[(i)>>5]|=(1<<((i)&0x1ff)))
    #define TEST(i) (bit[(i)>>5]&(1<<((i)&0x1ff)))
    #define MASK1 0x55555555
    #define MASK2 0x33333333
    #define MASK4 0x0f0f0f0f
    #define MASK8 0x00ff00ff
    #define MASK16 0x0000ffff
    
    //declaration
    int countof1();
    //implementation
    int countof1(){
        int sum=0, ac=m/32+1;
        for(int i=0; i<ac; i++){
            int t=bit[i];
            t=(t&MASK1)+((t>>1)&MASK1);
            t=(t&MASK2)+((t>>2)&MASK2);
            t=(t&MASK4)+((t>>4)&MASK4);
            t=(t&MASK8)+((t>>8)&MASK8);
            t=(t&MASK16)+((t>>16)&MASK16);
            sum+=t;
        }
        return sum;
    }
    
    int main()
    {
        //implementation
        while((cin>>n)&&(cin>>m)&&n&&m){
            for(int i=0; i<n; i++) cin>>a[i];
            for(int i=0; i<n; i++){
                cin>>c[i];
                if(c[i]>m/a[i]) c[i]=m/a[i];
            }
            memset((void*)bit, 0, sizeof(bit));
            SET(0);
            for(int i=0; i<n; i++){
                //for each a[i] split into c[i] 1,2,4...
                for(int j=1, left=c[i]; left>0; left-=Two[j], j++){//for Two[j] bits
    				if(left>=Two[j]){
                        //0-1 knapsack
                        for(int k=m; k>=Two[j]*a[i]; k--){
                            if(!TEST(k)&&TEST(k-Two[j]*a[i])) SET(k);
                        }
    				}
                    else{//left knapsack
                        for(int k=m; k>=left*a[i]; k--){
                            if(!TEST(k)&&TEST(k-left*a[i])) SET(k);
                        }
                    }
                }
            }
            cout<<countof1()-1<<endl;
        }
        return 0;
    }
    

2。第二种想法是参考了Ramber牛的一个想法,原文如下:[感概!男人不容易呀,我还是看了这么多东西才过一题的,上次那道DP动规的状态压缩题目,有个版本就是楼教主的Tony’s Tour,确实很难,改天再收拾你!]

剩余类优化的动态规划算法
状态仍然是F[i,j]表示用前i种钱币是否能拼出面值j。考虑在计算第i阶段时,面值为d[i],数量为n[i]。从状态转移方程中,我们发现F[i,j]所依赖的所有状态,都属于模d[i]的一个剩余类[j mod d[i]],即不同剩余类内的状态不相互影响。于是,我们可以将第i个阶段的状态按剩余类划分,每次只对一个剩余类的状态进行更新。意思很清楚,和BOP上的一道题目有异曲同工之妙,小菜总怀疑BOP的牛人抄了人家的代码,或者说BOP的牛人就是传说中的那几个过掉八题的牛人,后者居多!羡慕的流口水中!下面根据上面的描述,小菜写了个挨着边边过的代码!

Source Code

Problem: 1742

User: LLV

Memory: 692K

Time: 2891MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXN=101,MAXM=100001,MAXB=3200;
    int md[MAXM];
    int n,m,a[MAXN],c[MAXN];
    int bit[MAXB];
    
    #define SET(i) (bit[(i)>>5]|=(1<<((i)&0x1ff)))
    #define TEST(i) (bit[(i)>>5]&(1<<((i)&0x1ff)))
    #define MASK1 0x55555555
    #define MASK2 0x33333333
    #define MASK4 0x0f0f0f0f
    #define MASK8 0x00ff00ff
    #define MASK16 0x0000ffff
    
    //declaration
    int countof1();
    //implementation
    inline int countof1(){
        int sum=0, ac=m/32+1;
        for(int i=0; i<ac; i++){
            int t=bit[i];
            t=(t&MASK1)+((t>>1)&MASK1);
            t=(t&MASK2)+((t>>2)&MASK2);
            t=(t&MASK4)+((t>>4)&MASK4);
            t=(t&MASK8)+((t>>8)&MASK8);
            t=(t&MASK16)+((t>>16)&MASK16);
            sum+=t;
        }
        if(bit[0]&0x1) sum--;
        return sum;
    }
    
    
    int main()
    {
        //implementation
        while((cin>>n)&&(cin>>m)&&n&&m){
            for(int i=1; i<=n; i++) cin>>a[i];
            for(int i=1; i<=n; i++){
                cin>>c[i];
                if(c[i]>m/a[i]) c[i]=m/a[i];
            }
            memset((void*)bit, 0, sizeof(bit));
            SET(0)=1;
            for(int i=1; i<=n; i++){
                for(int j=0; j<m+1; j++){//看来看去,越看越觉得和BOP那道一样
                    if(TEST(j)) md[j]=c[i];//1...c[i] with md[i]
                    else md[j]=-1;
                }
                for(int j=0; j<m+1-a[i]; j++){
                    if(md[j+a[i]]==-1&&md[j]>0)
                        SET(j+a[i]),md[j+a[i]]=md[j]-1;
                }
            }
            cout<<countof1()<<endl;
        }
    
        return 0;
    }
  • 好了,把这几天的题目都贴出来,然后继续学习图论了![水题居多]

    陨石的秘密[和NOI的吧,脑袋锈掉料]

方程很重要,做掉了才发现有个高手,早就做掉了!比了下方程,学到不少,还发现自己程序的一个错!

sdp[p1,p2,p3,d]={
	0 (p1==p2==p3==0||d<0这个疏忽贡献了一个WA)
	F[p1-1,p2,p3,d-1] (p1>=1)
	F[p1,p2-1,p3,d-1] (p1==0 && p2>=1)
	F[p1,p2,p3-1,d-1] (p1==0 && p2==0 && p3>=1)}//动规的题怎么做,大家的代码都一样!

fdp[p1,p2,p3,d]=Σ(sdp[x1,x2,x3,d]*fdp[p1-x1,p2-x2,p3-x3,d]) (0<=x1<=p1,0<=x2<=p2,0<=x3<=p3且x1,x2,x3不同时为0)

初始条件:fdp[0,0,0,i]=1 (0<=i<=D)

最终的结果就是:(fdp[L1,L2,L3,D]-fdp[L1,L2,L3,D-1]+11380) %11380,注意在计算数值的时候提前%11380,避免大数和负数的产生

Source Code

Problem: 1187

User: orlando22

Memory: 448K

Time: 469MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXL=11, MAXD=31, MOD=11380;
    int f[MAXL][MAXL][MAXL][MAXD];
    int l1,l2,l3,d;
    
    //fdp functions
    int fdp(int l1, int l2, int l3, int d);
    int sdp(int l1, int l2, int l3, int d);
    //implementation
    int fdp(int l1, int l2, int l3, int d){
        if(d<0) return 0;//要注意这里
        if(f[l1][l2][l3][d]!=-1) return (f[l1][l2][l3][d]);
        int sum=0;
        for(int x1=0; x1<=l1; x1++){
            for(int x2=0; x2<=l2; x2++){
                for(int x3=0; x3<=l3; x3++){
                    int lx1=l1-x1,lx2=l2-x2,lx3=l3-x3;
                    if(x1==0&&x2==0&&x3==0) continue;
                    sum+=(sdp(x1,x2,x3,d)*fdp(lx1,lx2,lx3,d))%MOD;
                    sum%=MOD;
                }
            }
        }
        return (f[l1][l2][l3][d]=sum);
    }
    int sdp(int l1, int l2, int l3, int d){
        //l1,l2,l3 not all zero, eliminate invalid items
        if(l1>=1) return fdp(l1-1,l2,l3,d-1);//left l1-1>=0
        else if(l2>=1) return fdp(0,l2-1,l3,d-1);//left l2-1>=0
        else if(l3>=1) return fdp(0,0,l3-1,d-1);//left l3-1>=0
    }
    
    int main()
    {
        //implementation
        cin>>l1,cin>>l2,cin>>l3,cin>>d;
        memset((void*)f, 0xff, sizeof(f));
        for(int i=0; i<=d; i++) f[0][0][0][i]=1;
        int mnum=(fdp(l1,l2,l3,d)-fdp(l1,l2,l3,d-1)+MOD)%MOD;
        cout<<mnum<<endl;
    
        return 0;
    }
  • 这个要放这里,青蛙过河,很经典的一个规划对象转化模型[第一反应是用桥做规划对象,结果还是变成荷叶了],边界要小心!说实话,那天敲得
有些晕,不过意思是倒了得,一个WA,然后过了!
User: orlando22 , Problem : 10032
Language : GNU C++ , Judge Result: Accepted
Source Code
#include <iostream>

using namespace std;
const int MAX=101, MAXS=11;
//1 <= S <= T <= 10,1 <= M <= 100
int l, s, t, m, x[MAX], a[MAX][MAXS], best;//s=10*(10-1)->90
bool rb[MAX];//[0...MAX-1]-[s,t](1...10)
bool *b=rb+10;

//declaration
int compare(const void* t1, const void* t2);
bool can(int distance);
//impelementation
int compare(const void* t1, const void* t2){
    return (*(int*)t1-*(int*)t2);
}
bool can(int distance){
    if(distance<0) return false;
    if(distance>=s*(s-1)) return true;//here!issues
    return (b[distance]);
}

int main()
{
    //implementation
    int n;
    cin>>n;
    while(n--){
        cin>>l, cin>>s, cin>>t, cin>>m;
        for(int i=1; i<=m; i++) cin>>x[i];
        //sorting for x
        qsort((void*)(x+1), m, sizeof(int), compare);
        int tmp=m;
        for(int i=1; i<=m; i++) if(x[i]>l)tmp--;
        m=tmp;//remove invalid steps
        //special case s==t
        if(s==t){
            best=0;
            for(int i=1; i<=m; i++) if(x[i]%s==0) best++;
            cout<<best<<endl;continue;
        }
        //DP
        memset((void*)rb, 0, sizeof(bool)*MAX);
        b[0]=true;
        for(int i=1; i<=90; i++){//from anywhere non-reachable, s(s-1)
            for(int j=s; j<=t; j++) b[i]=(b[i]||b[i-j]);//这里要算个公式不过不难!
        }
        //intilization
        for(int i=0; i<=m; i++)
            for(int j=0; j<t; j++) a[i][j]=m+1;
        x[0]=0,a[0][0]=0;//x[0] having a step
        for(int i=1; i<=m; i++){
            for(int j=0; j<t; j++){//a[i][j]
                if(x[i]-j<=x[i-1]){//can't reach step[i-1]
                    a[i][j]=a[i-1][j-x[i]+x[i-1]];//back to x[i-1] distance让我有点晕的转化
                }
                else{
                    for(int v=0; v<t; v++){
                        if(can(x[i]-j-x[i-1]+v)&&a[i-1][v]<a[i][j]){//change min
                            a[i][j]=a[i-1][v];
                        }
                        if(j==0) a[i][j]++;
                    }
                }
            }
        }
        best=m+1;
        for(int i=0; i<t; i++) if(a[m][i]<best) best=a[m][i];
        cout<<best<<endl;
    }

    return 0;
}

  • 以为是动规,结果写出来是BFS,然后超时了,结果发现自己很幼稚,还是要优化下撒!双向搜索不正确,应该可以更快的,先把BFS的代码贴下,超时的!

TLE让人很伤心!

Source Code

Problem: 1184

User: orlando22

Memory: N/A

Time: N/A

Language: C++

Result: Time Limit Exceeded
  • Source Code
    #include <iostream>
    using namespace std;
    const int MAX=1000000, SIX=6;
    int s, t;
    typedef struct State{
        int s, step, pos;
    }State, *PState;
    bool hash[MAX][SIX];//hash checking
    State queue[MAX];
    State start;
    int qhead,qtail,qsize,steps;
    
    //declaration
    void Qin(State cur);
    State Qpop();
    //implemenation
    void Qin(State cur){
        if(hash[cur.s][cur.pos]) return;
        hash[cur.s][cur.pos]=true;
        if(cur.s==t){steps=cur.step;return;}
        if(++qhead==MAX) qhead=0;
        queue[qhead]=cur,++qsize;
    }
    State Qpop(){
        State cur=queue[qtail];
        qsize--;
        if(++qtail==MAX) qtail=0;//cycle queue
        return cur;
    }
    
    int main()
    {
        State cur, nv;
        int seg[SIX], cnum, cstep, cpos, nnum, ct;
        //implementation
        while((cin>>s)&&(cin>>t)){
            start.step=0,start.s=s,start.pos=0,qhead=-1,qtail=0,qsize=0,steps=-1;
            memset((void*)hash, 0, sizeof(hash));
            Qin(start);
            while(qsize){
                cur=Qpop();
                if(steps!=-1) break;
                cnum=cur.s,cstep=cur.step,cpos=cur.pos;
                ct=1;//calculate the pos's 10...0,开始还想用字符串,太菜了!
                for(int i=SIX-1; i>=0; i--){
                    seg[i]=cnum%10;cnum/=10;
                    if(i>cpos) ct*=10;
                }
                //OK, let's start with dummy work
                if(cpos>0){//seg[cpos]<->seg[0]
                    nnum=cur.s;
                    nnum=nnum-100000*(seg[0]-seg[cpos])-ct*(seg[cpos]-seg[0]);
                    nv.pos=cur.pos,nv.s=nnum,nv.step=cur.step+1;
                    Qin(nv);
                }
                if(cpos<5){//seg[cpos]<->seg[5]
                    nnum=cur.s;
                    nnum=nnum-(seg[5]-seg[cpos])-ct*(seg[cpos]-seg[5]);
                    nv.pos=cur.pos,nv.s=nnum,nv.step=cur.step+1;
                    Qin(nv);
                }
                if(seg[cpos]<9){//add
                    nnum=cur.s;
                    nnum+=ct;
                    nv.pos=cur.pos,nv.s=nnum,nv.step=cur.step+1;
                    Qin(nv);
                }
                if(seg[cpos]>0){//substract
                    nnum=cur.s;
                    nnum-=ct;
                    nv.pos=cur.pos,nv.s=nnum,nv.step=cur.step+1;
                    Qin(nv);
                }
                if(cpos>0){//left
                    nv.s=cur.s,nv.pos=cpos-1,nv.step=cur.step+1;
                    Qin(nv);
                }
                if(cpos<5){//right
                    nv.s=cur.s,nv.pos=cpos+1,nv.step=cur.step+1;
                    Qin(nv);
                }
            }
            cout<<steps<<endl;
        }
    
        return 0;
    }
    
  • 棋盘分割,本来没啥子说头的,但是由于我很无辜的贡献了1个WA,所以还是要说下的

FPU的控制字不同的,GCC默认用64位精度,VC默认用53位精度,用<float.h>,开头写_controlfp(PC_64,MCW_PC);

说不定VC也能过。hawk牛这段话是什么意思?去看下[FPU种类]
好了,这是judge online的默认FPU控制字造成的,所以我就用了个printf水过,开始用DP的,结果遇到和A-B剪刀一样的情况,懒得管了,直接用最优

剪刀过了!可以优化的,没有上下界估计,偷懒了!

Source Code

Problem: 1191

User: orlando22

Memory: 272K

Time: 297MS

Language: C++

Result: Accepted

Source Code

#include <iostream>
#include <math.h>
//pku  1191
using namespace std;
const int MAX=9, MAXL=16;
double s[MAX][MAX], chess[MAX][MAX];
int n;
double dmin;

//declaration
void dp(int x1, int y1, int x2, int y2, int times);
//implemenation
void dp(int x1, int y1, int x2, int y2, int times, double cf){
    double t, dcf;
    if(times==1){//only one chess for us
        t=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
        cf+=(t*t)/(double)n;
        if(cf<dmin) dmin=cf;
        return;
    }
    //times>1
    for(int y=y1+1; y<=y2; y++){
        t=s[x2][y2]-s[x1-1][y2]-s[x2][y-1]+s[x1-1][y-1];//[x2,y2]->[x1,y]
        dcf=(t*t)/(double)n; cf+=dcf;
        if(cf<dmin) dp(x1, y1, x2, y-1, times-1, cf);
        cf-=dcf;
        t=s[x2][y-1]-s[x1-1][y-1]-s[x2][y1-1]+s[x1-1][y1-1];//[x2,y-1]->[x1,y1]
        dcf=(t*t)/(double)n; cf+=dcf;
        if(cf<dmin) dp(x1, y, x2, y2, times-1, cf);
        cf-=dcf;
    }
    for(int x=x1+1; x<=x2; x++){
        t=s[x2][y2]-s[x-1][y2]-s[x2][y1-1]+s[x-1][y1-1];//[x2,y2]->[x,y1]
        dcf=(t*t)/(double)n; cf+=dcf;
        if(cf<dmin) dp(x1, y1, x-1, y2, times-1, cf);
        cf-=dcf;
        t=s[x-1][y2]-s[x1-1][y2]-s[x-1][y1-1]+s[x1-1][y1-1];//[x-1,y2]->[x1,y1]
        dcf=(t*t)/(double)n; cf+=dcf;
        if(cf<dmin) dp(x, y1, x2, y2, times-1, cf);
        cf-=dcf;
    }
    return;
}
//equation, take care of pre-calculation
inline double score(int x1, int y1, int x2, int y2){
    return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}

int main()
{
    //implementation, cout.precision(), clr
    memset((void*)&chess[0][0], 0, sizeof(double)*MAX*MAX);
    memset((void*)&s[0][0], 0, sizeof(double)*MAX*MAX);
    cin>>n;
    for(int i=1; i<MAX; i++)
        for(int j=1; j<MAX; j++)
            cin>>chess[i][j];
    //pre-caculation
    for(int i=1; i<MAX; i++)
        for(int j=1; j<MAX; j++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+chess[i][j];//OK
    dmin=(double)INT_MAX;
    dp(1,1,8,8,n,0.0);//8*8 only 7+7=15-1
    printf("%.3f\n", sqrt(dmin-(s[8][8]*s[8][8])/(double)(n*n)));

    return 0;
}

Advertisements