省赛选拔赛——个人赛第三场

发表于 分类于 Disqus：

Rank 11。
打得不理想，开场23分钟跟了学长1Y了H题之后，再没出题。赛后补了两道能力之内的题。
B：POJ 2431
比赛时，感觉能出，但一直改G题，没时间想，最后也没提交。
用优先队列储存当前能到达的加油站，每次当无法前进时，取油量最多的停留。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=10010;
struct node{
    int dis,fuel;
    bool operator < (const node &x) const {
        return dis>x.dis;
    }
};
node a[maxn];
priority_queue<int,vector<int>,less<int> > stop;
int main(){
    int n;
    while(~scanf("%d",&n)){
        memset(a,0,sizeof(a));
        while(!stop.empty()) stop.pop();
        for(int i=0;i<n;++i)
            scanf("%d%d",&a[i].dis,&a[i].fuel);
        sort(a,a+n);
        int L,P,cnt=0,pos=0;
        bool flag=true;
        scanf("%d%d",&L,&P);
        while(L>0){
            L-=P;
            if(L<=0) break;
            while(pos<n&&a[pos].dis>=L)
                stop.push(a[pos].fuel),++pos;
            if(stop.empty()){flag=false;break;}
            P=stop.top();
            stop.pop();
            ++cnt;
        }
        printf("%d\n",flag?cnt:-1);
    }
    return 0;
}

G：POJ 2436
有D种病，N头牛，给牛挤奶，所有挤奶的牛的病的总数不能超过K。
病的总数D≤15，所以可以枚举子集之后遍历每头牛，比赛时，思路是对的，但是一直TLE。赛后参考学长代码，发现要进行状态压缩，之前只做过一道要状态压缩的题，这 次完全没想到。还有一个可以优化的地方，在枚举子集时，只需要对当前疾病数等于K的进行统计，因为这样一定是最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int cow[maxn],a[16];
int solve(const int &n,const int &s){
    int cnt=0;
    for(int i=0;i<n;++i)
        if((s|cow[i])==s) ++cnt;
    return cnt;
}
int main(){
    int N,D,K;
    for(int i=0;i<16;++i) a[i]=1<<i;
    while(~scanf("%d%d%d",&N,&D,&K)){
        memset(cow,0,sizeof(cow));
        for(int i=0;i<N;++i){
            int k,id;
            scanf("%d",&k);
            while(k--){
                scanf("%d",&id);
                cow[i]|=a[id-1];
            }
        }
        int ans=0,s=1<<D;
        for(int i=0;i<s;++i){
            int cnt=0;
            for(int j=0;j<D;++j)
                if(i&a[j]) ++cnt;
            if(cnt==K) ans=max(ans,solve(N,i));
        }
        printf("%d\n",ans);
    }
    return 0;
}

H：POJ 2437
给出木板长度、沼泽个数和每个沼泽的左右端点，沼泽互补相交，求使用木板的最少个数。简单贪心，对区间排序之后，遍历每个区间铺就好了。比赛时提交的代码，求铺当前区 间个数，用了个无脑循环，600+ms，险些超时，赛后修改后提交47ms。以后这种问题要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
struct mud{
    int l,r;
    bool operator < (const mud &x) const {
        return l<x.l;
    }
}a[maxn];
int main(){
    int n,l;
    while(~scanf("%d%d",&n,&l)){
        for(int i=0;i<n;++i) scanf("%d%d",&a[i].l,&a[i].r);
        sort(a,a+n);
        int pos=0,cur=0,cnt=0;
        while(pos<a[n-1].r){
            if(pos<a[cur].l) pos=a[cur].l;
            //原本这写的while(pos<a[cur].r) pos+=l,++cnt; 差点超时。
            if(pos<a[cur].r){
                int t=a[cur].r-pos,num=t/l;
                if(t%l) ++num;
                pos+=l*num,cnt+=num;
            }
            ++cur;
        }
        printf("%d\n",cnt);
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

相关文章