Fzu第十三届程序设计竞赛

发表于   |   分类于

FZU 2229 Calculus Midterm

链接

Calculus Midterm

题意

计算总分判断即可

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
int main()
{
    int x,y,z;
    while(scanf("%d%d%d",&x,&y,&z)!=EOF){
        int ans=x*3+y*2+z*6;
        if(ans<60)
            printf("Exam was too hard.\n");
        else
            printf("I passed the exam.\n");
        printf("%d\n",ans);
    }
    return 0;
}

FZU 2230 翻翻棋

链接

翻翻棋

分析

计算红方和黑方之间所需的最小步数，若为偶数，黑方赢，否则红方赢

参考代码

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
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int main()
{
    int T;
    scanf("%d",&T);
    int x1,y1,x2,y2;
    while(T--){
        for(int i=0;i<4;i++){
            char s[10];
            scanf("%s",s);
            for(int j=0;j<8;j++){
                if(s[j]=='.'){
                    x1=i;
                    y1=j;
                }
                else if(s[j]=='*'){
                    x2=i;
                    y2=j;
                }
            }
        }
        int tmp=abs(x1-x2)+abs(y1-y2);
        if(tmp%2==0)
            printf("Black win\n");
        else
            printf("Red win\n");
    }
    return 0;
}

FZU 2231 平行四边形数

链接

平行四边形数

题意

给定n个点坐标，求能组成多少平行四边形

分析

最直接的思想是每次枚举四个点，根据平行四边形的判定定理判断，可是时间复杂度挺高O(n^4).
思路二：求出所有边的边长，每次枚举对边，根据对边平行且相等来判定，时间复杂度也一样。
稍微优化：将边按边长排序，枚举时若两边不相等，就不用往后继续了。但是最坏情况复杂度也一样。
可能这个题数据太弱，这样做A了。还有一个更好的思路：
根据平行四边形对角线互相平分，求出每条线段的中点，若有m条线段中点相同，
则可构成m*(m-1)/2个平行四边形。这样时间复杂度为O(n^2)

参考代码

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
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define eps 1e-5
#define N 505
struct Point{
    double x,y;
}p[N];
struct Edge{
    int u,v;
    double dis;
}edge[N*N];
bool cmp(Edge a,Edge b)
{
    return a.dis<b.dis;
}
double Distance(Point a,Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool isPal(Edge a,Edge b)  //判断两向量是否平行
{
    Point s;
    s.x=p[a.v].x-p[a.u].x;
    s.y=p[a.v].y-p[a.u].y;

    Point t;
    t.x=p[b.v].x-p[b.u].x;
    t.y=p[b.v].y-p[b.u].y;
    if(fabs(s.x*t.y-s.y*t.x)<eps)
        return true;
    return false;
}
bool check(int a,int b)
{
    if(edge[a].u==edge[b].u||edge[a].u==edge[b].v||edge[a].v==edge[b].u||edge[a].v==edge[b].v)
        return false;
    return isPal(edge[a],edge[b]);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                edge[cnt].u=i;
                edge[cnt].v=j;
                edge[cnt++].dis=Distance(p[i],p[j]);
            }
        }
        sort(edge,edge+cnt,cmp);
        int now=0,ans=0;
        for(int i=0;i<cnt;i++){
            now=i+1;
            while(now<cnt&&fabs(edge[i].dis-edge[now].dis)<eps){
                if(check(i,now))
                    ans++;
                now++;
            }
        }
        printf("%d\n",ans/2);
    }
    return 0;
}

FZU 2232 炉石传说

链接

炉石传说

题意

给定GG学长的n个随从的生命值及攻击力，对手的n个随从的生命力及攻击力，问GG学长能否一回合杀死对手所有随从，且自己的随从都存活。

分析

二分图的最大匹配
根据题意，每个随从A与对手随从B对战，要想A杀死B，且A不死，则A的攻击力要不小于B的生命值，且A的生命值要大于B的攻击力。即n个随从的匹配都满足此条件就能达到目的。
二分图的最大匹配—匈牙利算法，若最大匹配数等于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
40
41
42
43
44
45
46
#include<stdio.h>
#include<string.h>
#define N 105
struct stu{
    int att;
    int lf;
};
struct stu a[N],b[N];
bool used[N];
int link[N],n;
int dfs(int pos)
{
    for(int i=1;i<=n;i++){
        if(!used[i]&&a[pos].att>=b[i].lf&&a[pos].lf>b[i].att){
            used[i]=true;
            if(link[i]==-1||dfs(link[i])){
                link[i]=pos;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&a[i].lf,&a[i].att);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&b[i].lf,&b[i].att);
        memset(link,-1,sizeof(link));
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(used,0,sizeof(used));
            ans+=dfs(i);
        }
        if(ans==n)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

FZU 2236 第十四个目标

链接

第十四个目标

题意

已知n个数，求严格递增子序列的个数，如(1,3,2)的严格递增子序列有(1)、(3)、(2)、(1,3)、(1,2)，共5个。

分析

树状数组+dp
设dp[i]为以i结尾的递增子序列的个数，则$dp[i]=\Sigma{dp[j]}+1$,其中j<i且a[j]<a[i]
即对于j<i,a[j]<a[i],a[j]会对a[i]贡献dp[j]的贡献值。但是其复杂度O(n^2)效率太低
可以用树状数组优化成 O(nlgn),题目数据挺大到1e9,所以需Hash处理

参考代码

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
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define N 100010
#define mod 1000000007
using namespace std;
typedef long long LL;
LL c[N];
int a[N],id[N],m;
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,int val)
{
    for(int i=x;i<=m;i+=lowbit(i))
        c[i]=(c[i]+val)%mod;
}
LL query(int x)
{
    LL ans=0;
    for(int i=x;i>=1;i-=lowbit(i))
        ans=(ans+c[i])%mod;
    return ans;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            id[i]=a[i];
        }
        sort(id+1,id+n+1);
        m=unique(id+1,id+n+1)-id;  //去重编号
        LL ans=0;
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++){
            int pos=lower_bound(id+1,id+m,a[i])-id;  //二分查找编号
            int sum=(query(pos-1)+1)%mod;
            ans=(ans+sum)%mod;
            update(pos,sum);
        }
        printf("%lld\n",ans);
    }
    return 0;
}