复旦2012ACM校赛

挺久之前做的题了,具体过程忘掉了,最近终于看懂了划分树,补了一道模版题。
A:
HDU 4245
一开始理解错了题意,以为只能是单向映射,没想到是双向的,在原代码基础上修改导致代码打的很渣。

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<string>
#include<algorithm>
#include<map>
using namespace std;
map<string,string> a;
void pre(){
a["Ab minor"]="G# minor";
a["G# minor"]="Ab minor";
a["A# major"]="Bb major";
a["Bb major"]="A# major";
a["A# minor"]="Bb minor";
a["Bb minor"]="A# minor";
a["C# major"]="Db major";
a["Db major"]="C# major";
a["Db minor"]="C# minor";
a["C# minor"]="Db minor";
a["D# major"]="Eb major";
a["Eb major"]="D# major";
a["D# minor"]="Eb minor";
a["Eb minor"]="D# minor";
a["Gb major"]="F# major";
a["F# major"]="Gb major";
a["Gb minor"]="F# minor";
a["F# minor"]="Gb minor";
a["G# major"]="Ab major";
a["Ab major"]="G# major";
return;
}
int main(){
ios::sync_with_stdio(false);
pre();
string s;
int t=0;
while(getline(cin,s)){
cout<<"Case "<<++t<<": ";
if(a.count(s)) cout<<a[s]<<endl;
else cout<<"UNIQUE"<<endl;
}
return 0;
}

C:
HDU 4247

1
2
3
4
5
6
7
8
9
10
11
12
13
14
读题之后感觉是这么做,就交了,然后就过了。
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
long long a[4],t=0;
while(cin>>a[0]>>a[1]>>a[2]>>a[3]){
sort(a,a+4);
cout<<"Case "<<++t<<": ";
cout<<a[2]+a[3]<<endl;
}
return 0;
}

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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100010;
int tree[20][MAXN];//表示每层每个位置的值
int sorted[MAXN];//已经排序好的数
int toleft[20][MAXN];//toleft[p][i]表示第i层从1到i有数分入左边
void build(int l,int r,int dep){
if(l==r)return;
int mid=(l+r)>>1;
int same=mid-l+1;//表示等于中间值而且被分入左边的个数
for(int i=l;i<=r;i++)//注意是l,不是one
if(tree[dep][i]<sorted[mid]) same--;
int lpos=l;
int rpos=mid+1;
for(int i=l;i<=r;i++){
if(tree[dep][i]<sorted[mid]) tree[dep+1][lpos++]=tree[dep][i];
else if(tree[dep][i]==sorted[mid]&&same>0){
tree[dep+1][lpos++]=tree[dep][i];
same--;
}
else tree[dep+1][rpos++]=tree[dep][i];
toleft[dep][i]=toleft[dep][l-1]+lpos-l;
}
build(l,mid,dep+1);
build(mid+1,r,dep+1);
}
//查询区间第k大的数,[L,R]是大区间,[l,r]是要查询的小区间
int query(int L,int R,int l,int r,int dep,int k){
if(l==r)return tree[dep][l];
int mid=(L+R)>>1;
int cnt=toleft[dep][r]-toleft[dep][l-1];
if(cnt>=k){
int newl=L+toleft[dep][l-1]-toleft[dep][L-1];int newr=newl+cnt-1;
return query(L,mid,newl,newr,dep+1,k);
}
else{
int newr=r+toleft[dep][R]-toleft[dep][r],newl=newr-(r-l-cnt);
return query(mid+1,R,newl,newr,dep+1,k-cnt);
}
}
int main(){
int n,m,t=0;
while(~scanf("%d",&n)){
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++){
scanf("%d",&tree[0][i]);
sorted[i]=tree[0][i];
}
sort(sorted+1,sorted+n+1);
build(1,n,0);
scanf("%d",&m);
printf("Case %d:\n",++t);
int s,t,k;
while(m--){
scanf("%d%d",&s,&t);
k=(t-s+2)/2;
printf("%d\n",query(1,n,s,t,0,k));
}
}
return 0;
}

H:
HDU 4252
给出每个点的高度,求最少有几个建筑。具体记不清了,只记得当时出的很快。

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
#include<cstdio>
#include<algorithm>
#include<set>
using namespace std;
set<int> a;
int main(){
int n,t=0;
while(~scanf("%d",&n)){
a.clear();
int cnt=0;
for(int i=0;i<n;++i){
int cur;
scanf("%d",&cur);
if(!cur) ++cnt,a.clear();
else{
if(a.count(cur)) ++cnt;
set<int>::iterator it1=a.lower_bound(cur),it2=a.end();
a.erase(it1,it2);
a.insert(cur);
}
}
printf("Case %d: %d\n",++t,n-cnt);
}
return 0;
}

J:
HDU 4254
比赛时没推出来公式,赛后听说是这个公式,原理还不知道。。

1
2
3
4
5
6
7
8
#include<cstdio>
int main(){
int t=0;
double p,q;
while(~scanf("%lf%lf%lf",&p,&p,&q))
printf("Case %d: %.4lf\n",++t,(q+1)/(p+2));
return 0;
}

K:
HDU 4255
蛇形填数,之后BFS,坑在于,有可能素数连起来一直到了边界,导致判断出错,一开始数组开小了,WA了一次,不知道为什么不是RE,后来改大数组,大力出奇迹就过了

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
68
69
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
const int maxn=210;
const int go[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int g[maxn][maxn],vis[maxn][maxn];
bool np[maxn*maxn]={1,1};
struct point{
int x,y;
point(int x=0,int y=0):x(x),y(y){}
}a[maxn*maxn+1];
queue<point> q;
void pre(){
int k=maxn*maxn;
for(int i=2;i<k;++i)
if(!np[i]) for(int j=i*i;j<k;j+=i) np[j]=true;
int tot=k;
int x,y;
g[x=0][y=maxn-1]=k;a[tot]=point(x,y);
while(tot>0){
while(x+1<maxn&&!g[x+1][y]){
--tot;++x;
if(!np[tot]) continue;
g[x][y]=tot;a[tot]=point(x,y);
}
while(y-1>=0&&!g[x][y-1]){
--tot;--y;
if(!np[tot]) continue;
g[x][y]=tot;a[tot]=point(x,y);
}
while(x-1>=0&&!g[x-1][y]){
--tot;--x;
if(!np[tot]) continue;
g[x][y]=tot;a[tot]=point(x,y);
}
while(y+1<maxn&&!g[x][y+1]){
--tot;++y;
if(!np[tot]) continue;
g[x][y]=tot;a[tot]=point(x,y);
}
}
return;
}
int main(){
pre();
int st,ed,t=0;
while(~scanf("%d%d",&st,&ed)){
memset(vis,-1,sizeof(vis));
while(!q.empty()) q.pop();
q.push(a[st]);
vis[a[st].x][a[st].y]=0;
while(!q.empty()){
if(vis[a[ed].x][a[ed].y]!=-1) break;
point cur=q.front();q.pop();
for(int i=0;i<4;++i){
int x=cur.x+go[i][0],y=cur.y+go[i][1];
if(vis[x][y]!=-1||!g[x][y]) continue;
q.push(a[g[x][y]]);
vis[x][y]=vis[cur.x][cur.y]+1;
}
}
printf("Case %d: ",++t);
if(vis[a[ed].x][a[ed].y]!=-1) printf("%d\n",vis[a[ed].x][a[ed].y]);
else printf("impossible\n");
}
return 0;
}

L:
HDU 4256
水题,打表过。

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<string>
#include<map>
using namespace std;
map<string,int> a;
void pre(){
a["I"]=1;
a["II"]=2;
a["III"]=3;
a["IV"]=4;
a["V"]=5;
a["VI"]=6;
a["VII"]=7;
a["VIII"]=8;
a["IX"]=9;
a["X"]=10;
a["XI"]=11;
a["XII"]=12;
return;
}
int main(){
ios::sync_with_stdio(false);
pre();
string s;
int t=0;
while(cin>>s){
cout<<"Case "<<++t<<": "<<a[s]<<endl;
}
return 0;
}

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