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

Rank 6,一共AC了6题,其中5道1Y。
感觉这场比赛打得还可以,能出的题都出了,就是一开始选题出现了问题,先去做了DP,导致很多水题出的晚了,时间上占了劣势,好在前5道题AC的题都是1Y,没有很多
罚时。AC6题之后,看其他题都没什么思路,与学长们在知识储量上的劣势马上表现出来了,学长们继续打代码、出题,我只剩翻书、刷榜了,一直到结束。
A:POJ 2385
接苹果的题,是个DP。思路比较好想,27分钟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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int a[maxn];
int d[maxn][35][2];
int main(){
int t,w;
while(~scanf("%d%d",&t,&w)){
memset(d,0,sizeof(d));
memset(a,0,sizeof(a));
int ans=0;
for(int i=0;i<t;++i) scanf("%d",&a[i]),--a[i];
for(int i=t-1;i>=0;--i){
for(int j=0;j<=w;++j){
if(j){
d[i][j][0]=max(d[i+1][j-1][1]+(a[i]==1),d[i+1][j][0]+(a[i]==0));
d[i][j][1]=max(d[i+1][j-1][0]+(a[i]==0),d[i+1][j][1]+(a[i]==1));
}
else d[i][j][0]=d[i+1][j][0]+(a[i]==0),d[i][j][1]=d[i+1][j][1]+(a[i]==1);
}
}
for(int i=0;i<=w;++i)
ans=max(ans,d[0][i][0]);
printf("%d\n",ans);
}
return 0;
}

B:POJ 2386
出了A题之后,看别人都A了好几道别的题了,就马上去做这道。
DFS判连通的题,模板题。44分钟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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=110;
const int go[8][2]={{-1,-1},{0,-1},{1,-1},{-1,0},{1,0},{-1,1},{0,1},{1,1}};
char g[maxn][maxn];
int m,n,a[maxn][maxn];
bool vis[maxn][maxn];
void dfs(int u,int v,int cnt){
if(u<1||u>n||v<1||v>m) return;
for(int i=0;i<8;++i){
int a=u+go[i][0],b=v+go[i][1];
if(!vis[a][b]&&g[a][b]=='W'){
vis[a][b]=true;
dfs(a,b,cnt);
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(g,0,sizeof(g));
memset(vis,0,sizeof(vis));
int cnt=0;
for(int i=1;i<=n;++i){
cin.get();
for(int j=1;j<=m;++j)
g[i][j]=cin.get();
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(!vis[i][j]&&g[i][j]=='W'){
vis[i][j]=true;
dfs(i,j,++cnt);
}
cout<<cnt<<endl;
}
return 0;
}

C:POJ 2387
清完水题开始做的,最小生成树的题,模板题,一开始忽略了,同结点之间可能有多条路径WA了2次。97分钟AC。

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<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1010;
const long long inf=0x3f3f3f3f;
long long w[maxn][maxn],v[maxn];
long long d[maxn];
int main(){
int t,n;
while(cin>>t>>n){
memset(v,0,sizeof(v));
memset(w,0x3f,sizeof(w));
for(int i=0;i<t;++i){
long long u,v,len;
cin>>u>>v>>len;
u=n-u,v=n-v;
w[u][v]=w[v][u]=min(len,w[u][v]);
}
for(int i=0;i<n;++i) d[i]=(i==0?0:inf);
for(int i=0;i<n;++i){
long long x,m=inf;
for(int y=0;y<n;++y) if(!v[y]&&d[y]<=m) m=d[x=y];
v[x]=1;
for(int y=0;y<n;++y) d[y]=min(d[y],d[x]+w[x][y]);
}
cout<<d[n-1]<<endl;
}
return 0;
}

D:POJ 2388
水题。求小于等于当前数的数的个数。48分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10010;
int a[maxn];
int main(){
int n;
while(cin>>n){
for(int i=0;i<n;++i) cin>>a[i];
sort(a,a+n);
cout<<a[n/2]<<endl;
}
return 0;
}

E:POJ 2389
大数相乘,套模板。57分钟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
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
using namespace std;
struct Big{
int len;
long long data[1001];
void clear(){
memset(this,0,sizeof(*this));
}
long long & operator [](int k){
return data[k];
}
Big operator * (Big A){
Big temp;
temp.clear();
temp[0]=data[0]*A[0];
temp.len=len+A.len-1;
for(int i=1;i<=len;i++)
for(int j=1;j<=A.len;j++){
temp[i+j-1]+=A[j]*data[i];
temp[i+j]+=temp[i+j-1]/10000;
temp[i+j-1]%=10000;
}
while(temp[temp.len+1]) ++temp.len;
while(!temp[temp.len]) --temp.len;
if(!temp.len) temp.len=1;
return temp;
}
};
istream& operator >> (istream &in,Big& b){
b.clear();
string s,s0;
if(!(in>>s)) return in;
b[0]=s[0]=='-'?-1:1;
if(s[0]=='-'||s[0]=='+') s0=s.substr(1);
else s0=s;
b.len=((int)s0.size()+3)/4;
int k=(int)s0.size()%4;
if(!k) k=4;
for(int i=0;i<k;i++){
b[b.len]*=10;
b[b.len]+=s0[i]-'0';
}
for(int i=b.len-1;i>0;i--)
b[b.len-i]=1000*(s0[4*(i-1)+k]-'0')+100*(s0[4*(i-1)+k+1]-'0')+10*(s0[4*(i-1)+k+2]-'0')+s0[4*(i-1)+k+3]-'0';
if(b.len==1&&!b[1]) b[0]=1;
return in;
}
ostream& operator << (ostream &out,Big& b){
if(b[0]==-1) printf("-");
printf("%lld",b[b.len]);
for(int i=b.len-1;i>=1;i--)
printf("%04lld",b[i]);
return out;
}
int main(){
Big a,b,c;
while(cin>>a>>b){
c=a*b;
cout<<c<<endl;
}
return 0;
}

F:POJ 2390
水题,算利率。51分钟1Y。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10010;
int a[maxn];
int main(){
double a,b,c;
while(cin>>a>>b>>c){
a/=100.0;
a+=1;
a=pow(a,c);
cout<<(int)(a*b)<<endl;
}
return 0;
}

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