2018AStar Qualification Round 简要题解(部分)

题目链接:http://acm.hdu.edu.cn/listproblem.php?vol=54

1001.调查问卷

  • 状态压缩枚举问题集合判断即可
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1000+10;
int T,n,m,k,i,j,status,cas=1,cnt[2200];
char s[N][20];
int main(){
    for (read(T);T--;){
        read(n),read(m),read(k);
        for (i=1;i<=n;i++) scanf("%s",s[i]);
        printf("Case #%d: ",cas++);
        if (n*(n-1)/2<k){
            puts("0");
            continue;
        }
        memset(cnt,0,sizeof(cnt));
        int limit=1<<m;
        int res=0;
        for (status=1;status<limit;status++){
            int tot=n*(n-1)/2;
            for (i=1;i<=n;i++){
                int num=0;
                for (j=0;j<m;j++)if(status&(1<<j)){
                    if (s[i][j]=='B') num^=1<<j;
                }
                cnt[num]++;
            }
            for (i=0;i<=2048;i++)if(cnt[i]){
                tot-=cnt[i]*(cnt[i]-1)/2;
                cnt[i]=0;
            }
            if (tot>=k) res++;
        }
        printf("%d\n",res);
    }
    return 0;
}

1002.子串查询

  • 字典序最小肯定是一个字符,所以前缀和存一下字符出现的次数,然后查询就从小到大查询,有出现就输出即可。
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e5+10;
int T,n,q,i,j,l,r,cas=1,cnt[N][26];
char s[N];
int main(){
    for (read(T);T--;){
        read(n),read(q);
        scanf("%s",s+1);
        for (i=1;i<=n;i++){
            for (j=0;j<26;j++) cnt[i][j]=0;
            cnt[i][s[i]-'A']++;
        }
        for (i=1;i<=n;i++){
            for (j=0;j<26;j++) cnt[i][j]+=cnt[i-1][j];
        }
        printf("Case #%d:\n",cas++);
        for (;q--;){
            read(l),read(r);
            for (j=0;j<26;j++){
                if (cnt[r][j]-cnt[l-1][j]>0){
                    printf("%d\n",cnt[r][j]-cnt[l-1][j]);
                    break;
                }
            }
        }
    }
    return 0;
}

1003.整数规划

  • 本质上就是在求二分图带权最小匹配,回顾KM算法即可知道,所以跑一下BFS版的KM即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=200+10;
const int INF=2000000000;
int T,i,j,x,n,cas=1,cost[N][N],lx[N],ly[N],match[N],slack[N],pre[N];
bool vy[N];
void augment(int root){
    fill(vy+1,vy+n+1,false);
    fill(slack+1,slack+n+1,INF);
    int py;
    match[py=0]=root;
    do{
        vy[py]=true;
        int x=match[py],yy;
        int delta=INF;
        for (int y=1;y<=n;y++){
            if (!vy[y]){
                if (lx[x]+ly[y]-cost[x][y]<slack[y]){
                    slack[y]=lx[x]+ly[y]-cost[x][y];
                    pre[y]=py;
                }
                if (slack[y]<delta){
                    delta=slack[y];
                    yy=y;
                }
            }
        }
        for (int y=0;y<=n;y++){
            if (vy[y]){
                lx[match[y]]-=delta;
                ly[y]+=delta;
            }
            else{
                slack[y]-=delta;
            }
        }
        py=yy;
    }while(~match[py]);
    do{
        int cnt=pre[py];
        match[py]=match[cnt];
        py=cnt;
    }while(py);
}
ll KM(){
    for (int i=1;i<=n;i++){
        lx[i]=ly[i]=0;
        match[i]=-1;
        for (int j=1;j<=n;j++) lx[i]=max(lx[i],cost[i][j]);
    }
    ll ans=0;
    for (int i=1;i<=n;i++) augment(i);
    for (int i=1;i<=n;i++){
        ans+=lx[i];
        ans+=ly[i];
    }
    return ans;
}
int main(){
    for (read(T);T--;){
        read(n);
        for (i=1;i<=n;i++){
            for (j=1;j<=n;j++){
                read(cost[i][j]);
                cost[i][j]=-cost[i][j];
            }
        }
        printf("Case #%d: %lld\n",cas++,-KM());
    }
    return 0;
}

1004.点集划分

  • 不会

1005.序列计数

  • DP[i][j]表示到j为止上升子序列长度为i的方案数,然后用树状数组优化一下就可以做到O(n^2logn),同时考虑到随机数据下最长上升子序列长度不会很大,及时退出即可。
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=1e4+10;
const int P=1000000007;
int T,n,i,cur,len,cas=1,ans[N],p[N],sum[N],dp[N][2];
inline void up(int&a,int b){a+=b;if(a>=P)a-=P;}
inline int lowbit(int x){return x&(-x);}
void update(int pos,int v){
    for (;pos<=n;pos+=lowbit(pos)) up(sum[pos],v);
}
int get(int x){
    int res=0;
    for (;x>0;x-=lowbit(x)) up(res,sum[x]);
    return res;
}
int main(){
    for (read(T);T--;){
        read(n);
        for (i=1;i<=n;i++){
            read(p[i]);
            dp[i][0]=1;
            ans[i]=0;
        }
        cur=0;
        for (ans[1]=n,len=2;len<=n;len++){
            if (ans[len-1]==0) break;
            for (i=1;i<=n;i++){
                int tmp=get(p[i]-1);
                up(ans[len],tmp); 
                update(p[i],dp[i][cur]);
                dp[i][cur^1]=tmp;
            }
            cur^=1;
            for (i=1;i<=n;i++) sum[i]=0;
        } 
        printf("Case #%d: ",cas++);
        for (i=1;i<=n;i++){
            printf("%d%c",ans[i],i==n?'\n':' ');
        }
    }
    return 0;
}

1006.三原色图

  • 先求出MST,然后加边贪心的加就可以了,要注意特判MST不存在的情况。
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100+10;
struct Edge{
    int u,v,w,tp;
    bool operator<(const Edge&rhs)const{
        return w<rhs.w;
    }
};
int T,n,m,a,b,w,i,tp,fa[N],ans[N],cas=1;
bool vis[N];
char s[2];
vector<Edge>edges;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
void cal(int TP){
    sort(edges.begin(),edges.end());
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) fa[i]=i;
    int cnt=0,res=0;
    for (int i=0;i<(int)edges.size();i++){
        Edge& e=edges[i];
        if (TP==0&&e.tp==3) continue;
        if (TP==1&&e.tp==1) continue;
        int u=e.u,v=e.v;
        u=Find(u),v=Find(v);
        if (u^v){
            fa[u]=v;
            res+=e.w;
            cnt++;
            vis[i]=1;
        }
        if (cnt>=n-1) break;
    }
    if (cnt<n-1) return;
    if (ans[cnt]==-1) ans[cnt]=res;
    ans[cnt]=min(ans[cnt],res);
    for (int i=0;i<(int)edges.size();i++)if(!vis[i]){
        Edge& e=edges[i];
        res+=e.w;
        if (ans[++cnt]==-1) ans[cnt]=res;
        else ans[cnt]=min(ans[cnt],res);
    }
}
int main(){
    for (read(T);T--;){
        read(n),read(m);
        memset(ans,-1,sizeof(ans));
        edges.clear();
        for (i=1;i<=m;i++){
            read(a),read(b),read(w);
            scanf("%s",s);
            if (s[0]=='R') tp=1;
            else if (s[0]=='G') tp=2;
            else tp=3;
            edges.PB((Edge){a,b,w,tp});
        }
        if (m>=n-1) cal(0),cal(1);
        printf("Case #%d:\n",cas++);
        for (i=1;i<=m;i++) printf("%d\n",ans[i]);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注