FOJ-2011年11月月赛

学长给开题做的,随机队员时运气不好,把自己队的随走了一个,就剩zcy和我两个人打的。开局还行,但是毕竟人少,没法很快连续出题,后来出题速度就慢了。
A:
FZU 2054
水题,判断最大值在哪边,输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10010;
int main(){
int t;
scanf("%d",&t);
while(t--){
int t1,t2;
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
t1=max(a,b),t1=max(t1,c);
scanf("%d%d%d",&a,&b,&c);
t2=max(a,b),t2=max(t2,c);
printf("%d\n",t1>t2?1:2);
}
return 0;
}

B:
FZU 2055
一开始我敲,敲了一半发现错了,后来zcy敲的。发现自己之前想麻烦了,数据量少,直接暴力就行。

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
#include<iostream>
#include<string>
using namespace std;
string s[108],p,t;
int n,op;
bool path(string p,string d){
int len=p.length();
if(len>=d.length()) return false;
for(int i=0;i<len;++i){
if(p[i]!=d[i]) return false;
}
return true;
}
bool duc(string t,string d){
int lt=t.length(),ld=d.length();
if(lt>ld) return false;
for(int i=lt-1,j=ld-1;i>=0;--i,--j){
if(t[i]!=d[j]) return false;
}
return true;
}
void judge(string p,string t){
for(int i=0;i<n;++i)
if(path(p,s[i])&&duc(t,s[i]))
cout << s[i] <<endl;
return ;
}
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--){
cin >> n >> op;
for(int i=0;i<n;++i)
cin >> s[i];
for(int i=0;i<op;++i){
cin >> p >> t;
judge(p,t);
}
}
return 0;
}

C:
FZU 2056
比赛时没想到,赛后问了学长思路,DP所有矩形的面积,二分搜索最大边长。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,m,lim;
int d[maxn][maxn];
bool ok(int h){
for(int i=h;i<=n;++i)
for(int j=h;j<=m;++j)
if(d[i][j]-d[i-h][j]-d[i][j-h]+d[i-h][j-h]<=lim) return true;
return false;
}
int main(){
int t;scanf("%d",&t);
while(t--){
memset(d,0,sizeof(d));
scanf("%d%d%d",&n,&m,&lim);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j){
int k;
scanf("%d",&k);
d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+k;
}
int top=min(n,m),bott=0,best=0;
while(bott<=top){
int mid=(top-bott)/2+bott;
if(ok(mid)) best=max(best,mid*mid),bott=mid+1;
else top=mid-1;
}
printf("%d\n",best);
}
return 0;
}

D:
比赛时看成是1w*1w的数据量,要写类似并查集的树。赛后补题时发现是1w * 100。
记录每个人的性别和孩子编号。然后查询就好。

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<cstdio>
#include<cstring>
using namespace std;
const int maxn=10010;
int ch[maxn],len;
bool sex[maxn];
char ans[maxn];
bool f(int k,int x,int y){
len=0;
while(ch[y]){
ans[len++]=sex[y]?'M':'F';
if(x==(y=ch[y])){
printf("%d ",k);
for(int i=len-1;i>=0;--i) putchar(ans[i]);
puts("");
return true;
}
}
return false;
}
int main(){
int t;scanf("%d",&t);
while(t--){
memset(ch,0,sizeof(ch));
memset(sex,0,sizeof(sex));
int n;scanf("%d",&n);
int num=n/2;
for(int i=0;i<num;++i){
int cur,f,m;
scanf("%d%d%d",&cur,&f,&m);
ch[f]=ch[m]=cur,sex[m]=true;
}
int q;scanf("%d",&q);
while(q--){
int x,y;
scanf("%d%d",&x,&y);
if(!f(1,x,y)&&!f(0,y,x)) printf("Relative\n");
}
}
return 0;
}

E:
FZU 2058
比赛时用STL写的O(nlogn)算法超时,最后没改数组写。
赛后得知可以用O(n)算法,所以赛后补了这道。两个指针从前后分别遍历数组,满足条件时统计个数。

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
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
int a[maxn];
int Scan(){
int res=0,ch,flag=0;
if((ch=getchar())=='-') flag=1;
else if(ch>='0'&&ch<='9') res=ch-'0';
while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
return flag?-res:res;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
getchar();
for(int i=0;i<n;++i) a[i]=Scan();
sort(a,a+n);
LL ans=0;
int l=0,r=n-1;
while(l<=r){
if(a[l]==a[r]){
if(a[l]+a[r]==m) ans+=LL(r-l)*(r-l+1)/2;
break;
}
if(a[l]+a[r]==m){
int ll=l,rr=r;
while(a[l]==a[ll]) ++l;
while(a[r]==a[rr]) --r;
ans+=LL(l-ll)*(rr-r);
}
else if(a[l]+a[r]>m) --r;
else ++l;
}
printf("%I64d\n",ans);
}
return 0;
}

H:
FZU 2061
比赛时准备找规律过掉这道题,快结束了得知找钱可以找好几张,之前推的不对。看也来不及推了,就和zj交流经验,再后来zcy按照zj说的过掉了这道题。。
打30~3n和的表。对每个输入遍历计数,输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<math.h>
int main(){
int num[36];
num[0]=1;
for(int i=1;i<20;++i)
num[i]=num[i-1]+pow(3,i);
int n;
while(~scanf("%d",&n)){
int ans=1;
for(int i=0;i<20;++i){
if(n>num[i]) ++ans;
else break;
}
printf("%d\n",ans);
}
return 0;
}

I:
FZU 2062
开场我翻题时看到题目配图说是水题,就跟zcy说了,我提出思路,他感觉正确,就打了交过了。
一开始思路不太对,导致最后代码很挫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10010;
int d(int k){
if(k==1) return 1;
return d(k>>1)+1;
}
int main(){
int n;
while(~scanf("%d",&n))
printf("%d\n",d(n));
return 0;
}

J:
FZU 1859
zcy读到说是个画图的水题,我写出来,一块Debug之后过的。
对每个图分四份递归,然后输出就好。

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>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1030;
char g[maxn][maxn];
void draw(int n,int l1,int l2,int r1,int r2){
if(n==1){g[l1][r1]='@';return;}
int k=1<<(n-2);
draw(n-1,l1,l1+k,r1,r1+k);
draw(n-1,l2-k,l2,r1,r1+k);
draw(n-1,l2-k,l2,r2-k,r2);
return;
}
int main(){
int n;
while(~scanf("%d",&n)&&n){
memset(g,' ',sizeof(g));
draw(n,0,1<<(n-1),0,1<<(n-1));
int k=1<<(n-1);
for(int i=0;i<k;++i){
for(int j=k-1;j>=0;--j)
if(g[i][j]=='@') {g[i][j+1]=0;break;}
puts(g[i]);
}
puts("");
}
return 0;
}

K:
比赛时以为是用线段树做,所以敲了线段树,用书上模板坑了好久。赛后学长说可以DP求,补了一个用DP过的。
n=1000,m=100000。
线段树的建树复杂度O(nlogn),查询复杂度O(mlogn),总复杂度O(mlogn)。
DP处理数据复杂度O(n2),查询复杂度O(1),总复杂度O(n2)。
还是DP更快一些。
更重要的是,个人感觉DP好写,写线段树容易出错。

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
70
71
72
73
74
75
//DP版:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int d[maxn][maxn];
int main(){
int tt=0,n;
while(~scanf("%d",&n)){
memset(d,0,sizeof(d));
for(int i=1;i<=n;++i) scanf("%d",&d[i][i]);
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j)
d[i][j]=max(d[i][j-1],d[j][j]);
}
int q;scanf("%d",&q);
printf("Case #%d:\n",++tt);
while(q--){
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",l<=r?d[l][r]:max(d[1][r],d[l][n]));
}
puts("");
}
return 0;
}


//线段树版:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1010;
int cnt,n,d[(1<<12)-1];
void init(int n_){
cnt=0,n=1;
while(n<n_) n<<=1,++cnt;
memset(d,-1,sizeof(d));
}
int q(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return -1;
if(a<=l&&r<=b) return d[k+1];
return max(q(a,b,2*k+1,l,(l+r)/2),q(a,b,2*k+2,(l+r)/2,r));
}
int main(){
int tt=0;
while(~scanf("%d",&n)){
int tmp=n;
init(n);
for(int i=1<<cnt;i<(1<<cnt)+tmp;++i) scanf("%d",&d[i]);
int t=cnt-1;
while(t>=0){
int num=1<<(cnt-t);
for(int i=1<<t;i<1<<(t+1);++i)
d[i]=max(d[i*2],d[i*2+1]);
--t;
}
int m;
scanf("%d",&m);
printf("Case #%d:\n",++tt);
for(int i=0;i<m;++i){
int l,r;
scanf("%d%d",&l,&r);
--l,--r;
int ans=-1;
if(l>r) ans=max(q(0,r+1,0,0,n),q(l,n,0,0,n));
else ans=q(l,r+1,0,0,n);
printf("%d\n",ans);
}
printf("\n");
}
return 0;
}

写在后面:
开场我从前往后读,zcy从后往前读。
前面的中文,读得快,我看A水,直接打了交,A1y(3)。然后继续看B是模拟,不想写模拟,跳过。C不会,D以为要建树,跳过。
E~K是英文题,挨个点着看了一遍。看到I,图上说这是水题,我就读了一遍,跟zcy讲了题意。我们感觉可做,但因为是数学,准备先放一放,一会再做。继续读题。
读别的题时,灵光乍现,感觉是二分一类的做法,跟zcy说了一下,他感觉对。就敲了,一开始想成分奇偶讨论了,所以写成递归,后来发现只需要数位数就行。提交I1y( 13)。
再后来,我敲B,zcy读题,读到J水,跟我说了。原本准备敲完B之后再弄,但是后来发现B敲错了。就开始做J,一块Debug之后过了,提交,交在E题上了,重交J 1y(55)。至此打得还不错,三道都是1y,都是FB。
再往后就有点乱了,开始看E,用map写的,不过脑补复杂度O(nlogn),应该是STL差个常数。跳过,看其他题。
zcy给我讲K题意,我以为是线段树,我开始敲K。敲了好久样例不过。下机器,zcy敲B。Debug过程中,zcy在我的多次干扰下过掉了B,B1y(150)。
之后我继续上机改K,两次WA之后,K3y(168)。
再往后我们几乎没正经打了,尝试了使用hash_map/hash_set过E,CE,找CB头文件粘上,依然CE。后来的时间大部分都在猜H题解法,直到最后与其他 队成员交流经验,莫名其妙的过掉了,中途CE两次,H3y(295)。
赛后问了学长其他几道题的做法,补了几道题。

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