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

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博客 ,格式可能有所偏差。