FOJ-2011年11月月赛

发表于 分类于 Disqus：

学长给开题做的，随机队员时运气不好，把自己队的随走了一个，就剩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博客，格式可能有所偏差。 **

相关文章