hihocoder编程练习赛6+多重背包的各种姿势

题目现在在题库的1361~1364
比赛链接http://hihocoder.com/contest/hihointerview18/problems

01：Playfair密码表
模拟题，秒
注意没有字母J

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
    //freopen("fuck.in","r",stdin);
    string st;
    cin>>st;
    int len = st.length();
    bool vis[200];
    memset(vis,0,sizeof(vis));
    char a[30];
    int pos = 0;
    for (int i=0;i<len;i++){
        if (st[i]=='J')st[i]='I';
        if (vis[st[i]])continue;
        vis[st[i]] = 1;
        a[pos++] = st[i];
    }
    for (char i='A';i<='Z';i++){
        if (vis[i]||i=='J')continue;
        a[pos++] = i;
    }
    for (int i=0;i<25;i++){
        printf("%c",a[i]);
        if (i%5==4)puts("");
    }
    return 0;
}

02：修补木桶
二分最矮的木桶高度
然后模拟修木桶的过程

#include<cstdio>
#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int n,m,len,a[N],b[N];
bool repair(int start,int h){
    int cnt = 0;
    for (int i=start;i<=start+n;i++)
        if (b[i]<h){i+=len-1;cnt++;}
    return cnt <= m;
}
bool check(int h){
    for (int i=1;i<=n+len;i++)b[i]=a[i];
    for (int i=1;i<=len;i++)
        if (repair(i,h))return 1;
    return 0;
}
int main(){
    freopen("fuck.in","r",stdin);
    scanf("%d%d%d",&n,&m,&len);
    for (int i=1;i<=n;i++){scanf("%d",&a[i]);}
    for (int i=n+1;i<=n+len;i++)a[i]=a[i-n];
    int L=0,R=INF,ans;
    for (;L<=R;){
        int mid=(L+R)>>1;
        if (check(mid)){L=mid+1;ans = mid;}
        else R = mid-1;
    }
    printf("%d
",ans);
    return 0;
}

03没看，，，04抠的时间长的，赛后也懒了，坑待填吧

04：奖券兑换
小数据01背包
大数据多重背包
用二进制或者单调队列都可以
这里贴个二进制的

//hihocoder 1364
//by cww97
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5 + 10;
int vis[12][12];
struct node{
    int v,w;
    node(){}
    node(int x,int y):v(x),w(y){}
}a[N];//1~top
int f[N];

int main(){
    //freopen("fuck.in","r",stdin);
    int n,m,x,y,top = 0;
    scanf("%d%d",&n,&m);
    memset(vis,0,sizeof(0));
    for (;n--;){
        scanf("%d%d",&x,&y);
        vis[x][y] ++ ;
    }
    for (int i=1;i<=10;i++)
      for (int j=1;j<=10;j++){
        int cnt = vis[i][j];
        if(!cnt)continue;
        for (int k=0;k<20;k++)if (cnt>(1<<k)){
            a[++top]=node(i*(1<<k),j*(1<<k));
            cnt-=(1<<k);
        }
        if (cnt)a[++top]=node(i*cnt,j*cnt);
      }

    for (int i=1;i<=top;i++)
      for (int j=m;j>=a[i].v;j--)
        f[j]=max(f[j],f[j-a[i].v]+a[i].w);

    int ans = 0;
    for (int i=0;i<=m;i++)ans=max(ans,f[i]);
    printf("%d
",ans);
    return 0 ;
}

关于单调队列
http://www.cnblogs.com/JoeFan/p/4165956.html

http://blog.csdn.net/flyinghearts/article/details/5898183

写了个，WA的版本，不知道自己哪里写残了，呜呜呜
（更新内容，在后面有通过的代码）

//hihocoder 1364
//by cww97
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6 + 10;
int vis[12][12];
struct node{
    int v,w,n;
    node(){}
    node(int x,int y,int z):v(x),w(y),n(x){}
}a[N];//1~top

int f[N],Q1[N],Q2[N];//queue
inline void pack(int V,int v,int w,int n){
    /*
    if (n==0||w==0)return;
    if (n==1){//01±³°ü
        for (int i=V;i>=v;i--)
            f[i]=max(f[i],f[i-v]+w);
        return;
    }
    if (n*v>=V-v+1){//ÍêÈ«±³°ü(n>=V/v)
        for (int i=v;i<=V;i++)
            f[i]=max(f[i],f[i-v]+w);
        return;
    }*/
    for (int j=0;j<v;j++){
        int s1=1,t1=0 ;
        int s2=1,t2=0 ;
        for (int k=j,cnt=0;k<=V;k+=v,cnt++){
            if (t1==n+s1){//Q1 full
                if (Q2[s2]==Q1[s1])s2++;
                s1++;
            }
            int tmp = f[k]-cnt*w;
            Q1[++t1] = tmp ;
            while(s2<=t2&&Q2[t2]<tmp)--t2;
            Q2[++t2] = tmp ;
            f[k]=Q2[s2]+cnt*w;
        }
    }
}

int main(){
    //freopen("fuck.in","r",stdin);
    int n,m,x,y,top = 0;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        if(vis[x][y]) a[vis[x][y]].n++;
        else {
            vis[x][y] = ++top ;
            a[top]=node(x,y,1);
        }
    }
    for (int i=1;i<=top;i++)
        pack(m,a[i].v,a[i].w,a[i].n);
    int ans = 0;
    for (int i=0;i<=m;i++)
        ans = max( ans, f[i]);
    printf("%d
",ans);
    return 0;
}

单调栈
POJ2559

#include<cstdio>
#include<iostream>
#include<algorithm>
typedef long long LL;
const int N=1e5+10;
LL L[N],R[N],h[N],sta[N];
using namespace std;
int main(){
    //freopen("fuck.in","r",stdin);
    for (int n;~scanf("%d",&n)&&n;){
        for (int i=1;i<=n;i++)scanf("%I64d",&h[i]);
        h[0] = h[n+1] = 0;
        int top = 0;
        for (int i=1;i<=n+1;i++){
            for (;1;){
                int pos = sta[top];
                if (h[pos]<=h[i])break;
                R[pos]=i;
                top--;
            }
            L[i] = sta[top];
            sta[++top] = i ;
        }
        LL ans = 0;
        for (int i=1;i<=n;i++)
            ans=max(ans,h[i]*(R[i]-L[i]-1));
        printf("%I64d
",ans);
    }
    return 0;
}

POJ1276
多重背包
二进制转化成01背包版本

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100007;
struct node {
    int v,w,n;
    node(){}
    node(int x,int y,int z){
        v=x,w=y,n=z;
    }
}a[N];
int f[N];

int main(){
    //freopen("fuck.in","r",stdin);
    int cash,n,x,y;
    for (;~scanf("%d%d",&cash,&n);){
        int A = 0;
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            for (int t=0;(1<<t)<x;t++){
                int tt=1<<t;
                a[++A]=node(y*tt,y*tt,1);
                x -= tt;
            }
            if (x)a[++A]=node(y*x,y*x,1);
        }

        memset(f,0,sizeof(f));
        for (int i=1;i<=A;i++)
            for (int j=cash;j>=a[i].v;j--)
                f[j]=max(f[j],f[j-a[i].v]+a[i].w);

        int ans = 0;
        for (int i=0;i<=cash;i++) ans=max(ans,f[i]);
        printf("%d
",ans);
    }
    return 0;
}

fyh的STL单调队列版本

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100007;
struct node {
    int v,w,n;
    node(){}
    node(int x,int y,int z){
        v=x,w=y,n=z;
    }
}a[N];
int f[N];

int Q1[N],Q2[N];
void pack(int V,int v,int w,int n){
    if (n==0||v==0)return;
    if (n==1) {//01背包
        for (int i=V;i>=v;--i)
            if (f[i]<f[i-v]+w)f[i]=f[i-v]+w;
        return;
    }
    if (n * v >= V - v + 1) {   //完全背包(n >= V / v)
        for (int i = v; i <= V; ++i)
            if(f[i]<f[i-v]+w)f[i]=f[i-v]+w;
        return;
    }
    for (int mod=0;mod<v;mod++){
        deque<pair<int,int> >Q;
        for (int j=mod;j<=V;j+=v){
            int add=j/v*w;
            int low=max(0,j/v-n);
            for (;!Q.empty()&&Q.front().fi<low;)
                Q.pop_front();
            int cur = f[j] - add;
            for (;!Q.empty()&&Q.back().se<cur;)
                Q.pop_back();
            Q.push_back(make_pair(j/v,cur));
            int tmp = Q.empty()?0:Q.front().se;
            f[j] = max(f[j],tmp+add);
            //printf("f[%d]=%d
",f,f[j]);
        }
    }
}

int main(){
    //freopen("fuck.in","r",stdin);
    int cash,n,x,y;
    for (;~scanf("%d%d",&cash,&n);){
        for(int i=1;i<=n;i++){    //init
            scanf("%d%d", &x, &y);
            a[i] = node(y,y,x) ;
        }
        memset(f,0,sizeof(f));    //pack
        for (int i=1;i<=n;i++)
            pack(cash,a[i].v,a[i].w,a[i].n);
        int ans = 0;              //getAns
        for (int i=0;i<=cash;i++) ans=max(ans,f[i]);
        printf("%d
",ans);
    }
    return 0;
}

最后，，真-单调队列来了
贴了前面blog的板，自己不知道怎么写残了

结论：这个写法应该是最快的了，用了数组指针来写队列
写一些极致追求效率的算法的时候，千万别用STL

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100007;
struct node {
    int v,w,n;
    node(){}
    node(int x,int y,int z){
        v=x,w=y,n=z;
    }
}a[N];
int f[N];

int va[N], vb[N];//MAX_V
void pack(int V,int v,int w,int n){
    if (n==0||v==0) return;
    if (n==1){//01背包
        for (int i=V;i>=v;--i)
            f[i]=max(f[i],f[i-v]+w);
        return;
    }
    if (n*v>=V-v+1){//完全背包(n >= V / v)
        for (int i=v;i<=V;++i)
            f[i]=max(f[i],f[i-v]+w);
        return;
    }
    for (int j = 0 ; j < v ; ++j ){
        int *pb = va, *pe = va - 1;
        int *qb = vb, *qe = vb - 1;
        for (int k=j,i=0;k<=V;k+=v,++i){
            if (pe==pb+n){
                if(*pb == *qb) ++qb;
                ++pb;
            }
            int tt = f[k] - i * w;
            *++pe = tt;
            while (qe>=qb&& *qe<tt)--qe;
            *++qe = tt;
            f[k] = *qb + i * w;
        }
    }
}

int main(){
    //freopen("fuck.in","r",stdin);
    int cash,n,x,y;
    for (;~scanf("%d%d",&cash,&n);){
        for(int i=1;i<=n;i++){    //init
            scanf("%d%d", &x, &y);
            a[i] = node(y,y,x) ;
        }
        memset(f,0,sizeof(f));    //pack
        for (int i=1;i<=n;i++)
            pack(cash,a[i].v,a[i].w,a[i].n);
        int ans = 0;              //getAns
        for (int i=0;i<=cash;i++) ans=max(ans,f[i]);
        printf("%d
",ans);
    }
    return 0;
}

还个欠账，hihocoder那题，我改成blog上的板，还是WA
加了两个memset，过了，，艹，，明明在int main外面定义的
只有一组数据，应该自己初始化好的全是0的啊
操李奶奶，下次用G++或者写奇怪的OJ的时候记得初始化吧

//hihocoder 1364
//by cww97
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e7 + 10;
int vis[12][12];
struct node{
    int v,w,n;
    node(){}
    node(int x,int y,int z){
        v=x;w=y;n=z;
    }
}a[N];//1~top

int f[N],va[N], vb[N];//MAX_V
void pack(int V,int v,int w,int n){
    if (n==0||v==0) return;
    if (n==1){//01背包
        for (int i=V;i>=v;--i)
            f[i]=max(f[i],f[i-v]+w);
        return ;
    }
    if (n*v>=V-v+1){//完全背包(n >= V / v)
        for (int i=v;i<=V;++i)
            f[i]=max(f[i],f[i-v]+w);
        return ;
    }
    for (int j = 0 ; j < v ; ++j ){
        int *pb = va, *pe = va - 1;
        int *qb = vb, *qe = vb - 1;
        for (int k=j,i=0;k<=V;k+=v,++i){
            if (pe==pb+n){
                if(*pb == *qb) ++qb;
                ++pb;
            }
            int tt = f[k] - i * w;
            *++pe = tt;
            while (qe>=qb&& *qe<tt)--qe;
            *++qe = tt;
            f[k] = *qb + i * w;
        }
    }
}

int main(){
    //freopen("fuck.in","r",stdin);
    int n,m,x,y,top = 0;
    scanf("%d%d",&n,&m);
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++){   //init
        scanf("%d%d",&x,&y);
        if(vis[x][y]) a[vis[x][y]].n++;
        else {
            vis[x][y] = ++top ;
            a[top]=node(x,y,1);
        }
    }
    memset(f,0,sizeof(f));    //pack
    for (int i=1;i<=top;i++)
        pack(m,a[i].v,a[i].w,a[i].n);
    int ans = 0;              //getAns
    for (int i=0;i<=m;i++)ans=max(ans,f[i]);
    printf("%d
",ans);
    return 0;
}

最后
下图的第一次A是用二进制写的，
第二发是blog里的单调队列的板，
第三发是发现之前MAXN太大了（1kw），改成10W之后再交的一次
可以发现，单调队列比二进制还是快很多的
承旭老师的原话是：快一个log
当然，别用STL，，，噗（fyh）
最后一发WA是把上面WA的版本（自己写的单调栈）加两个memset
结果还是WA，不管了，反正以后遇到简单题直接手写二进制，
卡的比较紧的话，看板吧，反正开卷（逃）