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

Rank 5,AC5道,全部1Y。
开场读错了A题,打了就交,直接WA。后来一路跟题,出了几个水题。刷完水题之后,卡在一道BFS上,浪费了不少时间,导致两道简单DP出得特别晚。后来卡D题的BF
S,没有想到进行预处理,也一直没有AC。
C:POJ 3668
出了H之后,继续跟榜,25分钟1Y。
给出n个点,求有多少个不平行的直线。枚举每两个点的连线,用set储存斜率,判断是否有斜率不存在的情况后,求和输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<set>
using namespace std;
const int maxn=200;
struct point{
int x,y;
point(int x=0,int y=0):x(x),y(y){}
}a[maxn];
set<double> k;
int main(){
int n;
while(cin>>n){
k.clear();
bool flag=false;
for(int i=0;i<n;++i)
cin>>a[i].x>>a[i].y;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(a[i].x==a[j].x) flag=true;
else k.insert((double)(a[i].y-a[j].y)/(a[i].x-a[j].x));
cout<<k.size()+flag<<endl;
}
return 0;
}

D:POJ 3669
m颗流星,每颗毁坏目标点和目标点周围四个点,给出流星的落点和时间,求从原点走到安全地方的最短时间。首先进行预处理,记录每个点被毁坏的时间,然后BFS求解。
比赛时没有想到预处理的方式,WA好几次最后也没出,赛后补的这道题。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
const int maxn=310;
const int inf=0x3f3f3f3f;
const int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int m,g[maxn][maxn],vis[maxn][maxn];
queue<pii> q;
void boom(int x,int y,int t){
g[x][y]=min(g[x][y],t);
for(int i=0;i<4;++i){
int a=x+go[i][0],b=y+go[i][1];
if(a>=0&&a<maxn&&b>=0&&b<maxn)
g[a][b]=min(g[a][b],t);
}
return;
}
int main(){
while(~scanf("%d",&m)){
while(!q.empty()) q.pop();
memset(g,0x3f,sizeof(g));
memset(vis,-1,sizeof(vis));
for(int i=0;i<m;++i){
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
boom(x,y,t);
}
pii tmp=make_pair(0,0);
q.push(tmp);
vis[0][0]=0;
while(!q.empty()){
tmp=q.front();
q.pop();
if(g[tmp.first][tmp.second]==inf) break;
for(int i=0;i<4;++i){
int a=tmp.first+go[i][0],b=tmp.second+go[i][1];
if(vis[a][b]!=-1||g[a][b]<=vis[tmp.first][tmp.second]+1) continue;
if(a>=0&&a<maxn&&b>=0&&b<maxn){
vis[a][b]=vis[tmp.first][tmp.second]+1;
q.push(make_pair(a,b));
}
}
}
if(g[tmp.first][tmp.second]==inf) printf("%d\n",vis[tmp.first][tmp.second]);
else printf("-1\n");
}
return 0;
}

E:POJ 3670
跟F题很像的一道题,把F的代码粘贴两次,之后修改下就过了,145分钟1Y。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n){
int ans=0,ans1=maxn,ans2=maxn,one=0,n_one=0,two=0,three=0;
for(int i=0;i<n;++i){
cin>>a[i];
if(a[i]==1) ++one;
//else ++n_one;
}
int pos=0;
for(int i=0;i<n;++i){
if(a[i]==1) --one;
if(ans1>one+n_one) pos=i;
ans1=min(one+n_one,ans1);
if(a[i]!=1) ++n_one;
}
for(int i=pos;i<n;++i)
if(a[i]==2) ++two;
for(int i=pos;i<n;++i){
if(a[i]==2) --two;
ans2=min(two+three,ans2);
if(a[i]==3) ++three;
}
ans=ans1+ans2;
ans1=maxn,ans2=maxn,one=0,n_one=0,two=0,three=0;
for(int i=0;i<n/2;++i)
swap(a[i],a[n-1-i]);
for(int i=0;i<n;++i)
if(a[i]==1) ++one;
//else ++n_one;
pos=0;
for(int i=0;i<n;++i){
if(a[i]==1) --one;
if(ans1>one+n_one) pos=i;
ans1=min(one+n_one,ans1);
if(a[i]!=1) ++n_one;
}
for(int i=pos;i<n;++i)
if(a[i]==2) ++two;
for(int i=pos;i<n;++i){
if(a[i]==2) --two;
ans2=min(two+three,ans2);
if(a[i]==3) ++three;
}
cout<<min(ans1+ans2,ans)<<endl;
}
return 0;
}

F:POJ 3671
D题卡了好久,一直WA,在119分钟最后一次D题提交WA之后,去做这道,130分钟1Y。
给出一个有1、2组成的序列,求最少改动几个数字使得前面是1,后面是2。
简单DP,没写状态转移方程,直接遍历求每个位置改动的最小值输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=30010;
int a[maxn];
int main(){
ios::sync_with_stdio(false);
int n;
while(cin>>n){
int ans=maxn,one=0,two=0;
for(int i=0;i<n;++i){
cin>>a[i];
if(a[i]==1) ++one;
}
for(int i=0;i<n;++i){
if(a[i]==1) --one;
ans=min(one+two,ans);
if(a[i]==2) ++two;
}
cout<<ans<<endl;
}
return 0;
}

G:POJ 3672
AC了C题之后,看到有出这个的,又跟了。30分钟1Y。
输入u、f、d表示上坡、平地、下坡,求给定时间的最长路程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<string>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int maxn=200;
int main(){
int m,t,u,f,d;
while(cin>>m){
int cnt=0;
cin>>t>>u>>f>>d;
for(int i=0;i<t;++i){
cin.get();
if(cin.get()=='f') m-=2*f;
else m-=(u+d);
if(m<0) break;
++cnt;
}
cout<<cnt<<endl;
}
return 0;
}

H:POJ 3673
简单求和,A题WA之后,看榜上有人AC之后马上跟的,12分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
string s1,s2;
while(cin>>s1>>s2){
long long sum=0;
for(int i=0;i<s1.size();++i)
for(int j=0;j<s2.size();++j)
sum+=(s1[i]-'0')*(s2[j]-'0');
cout<<sum<<endl;
}
return 0;
}

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