第七届福建省大学生程序设计竞赛题解

107 阅读 0 评论 71 点赞

我是靠谱客的博主搞怪云朵，最近开发中收集的这篇文章主要介绍第七届福建省大学生程序设计竞赛题解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

FZU - 2265

概率水题

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int a[10005];
    int b[10005];
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        cas++;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        double ans=0;
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        int pos=1;
        int j=1;
        for(int i=1;i<=n;i++)
        {
            while(j<=n)
            {
                if(a[i]<b[j])
                {
                    break;
                }
                j++;
            }
            ans=ans+(j-1)*1.0/n;
        }
		printf("Case %d: ",cas);
        printf("%0.2lfn",ans);
    }
    return 0;
}

FZU - 2267

strcmp的用法

#include<iostream>
#include<stdio.h>
#include<string.h>
#define maxn 100005
using namespace std;
int t;
int n,m;
char a[maxn];
char b[maxn];
int main()
{
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        cas++;
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++)
        {
            cin>>a[i];
        }
        a[n]='';
        for(int i=0; i<m; i++)
        {
            cin>>b[i];
        }
        b[m]='';
        printf("Case %d: ",cas);
        int i=0;
        int j=0;
        while(i<n&&j<m)
        {
            if(a[i]>b[j])
            {
                printf("%c",a[i++]);
            }
            else if(a[i]<b[j])
            {
                printf("%c",b[j++]);
            }
            else
            {
                int tmp=strcmp(a+i,b+j);
                if(tmp>0)
                {
                    while(i<n&&a[i]==b[j])
                    {
                        printf("%c",a[i++]);
                    }
                }
                else
                {
                    while(j<m&&a[i]==b[j])
                    {
                        printf("%c",b[j++]);
                    }
                }
            }
        }
        if(i<n)
        {
            while(i<n)
            {
                printf("%c",a[i++]);
            }
        }
        else
        {
            while(j<m)
            {
                printf("%c",b[j++]);
            }
        }
        printf("n");
    }
    return 0;
}

FZU - 2264

概率水题

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n;
    int a[20005];
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        cas++;
        scanf("%d",&n);
        for(int i=1;i<=2*n;i++)
        {
            scanf("%d",&a[i]);
        }
        double ans=n*0.5;
        printf("Case %d: ",cas);
        printf("%.2lfn",ans);
    }
    return 0;
}

FZU - 2266

水题

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int a[10005];
    int b[10005];
    int t;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        cas++;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i]+b[i]>10)
              ans++;
        }
		printf("Case %d: ",cas);
        printf("%dn",ans);
    }
    return 0;
}

FZU - 2268

水题

#include<iostream>
#include<stdio.h>
using namespace std;
int t;
int n;
int main()
{
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        cas++;
        int ans=0;
        scanf("%d",&n);
        while(n)
        {
            n=n/2;
            ans++;
        }
        printf("Case %d: ",cas);
        printf("%dn",ans);
    }
}

FZU - 2271

问最多去几条边，每两点之间的距离依旧是最短

在建边（imap）的时候保存最短边，并计数删去的边

可以先跑一个最短路，注意再开一个数组（map）保存，否则会破坏原先的边

然后遍历i和j，注意避免重复，然后imap[i][j]==inf，则说明原来就没边，那么肯定就不需要再去边了

如果map[i][j]<imap[i][j]，说明可以松弛，那么这条边可以去掉，如果map[i][j]==imap[i][j]，则找到

一个点k，若map[i][k]+map[k][j]==imap[i][j]，则说明去掉这条边不影响两点间的最短距离，因此可

以去掉。

#include<iostream>
#include<string.h>
#include<stdio.h>
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
int t;
int n,m;
int map[maxn][maxn];
int imap[maxn][maxn];
bool check[maxn][maxn];
int cnt;
void floyd()
{
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(map[i][k]+map[k][j]<map[i][j])
                {
                    map[i][j]=map[i][k]+map[k][j];
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&t);
    int u,v,s;
    int cas=0;
    while(t--)
    {
        cnt=0;
        cas++;
        memset(map,inf,sizeof(map));
        scanf("%d%d",&n,&m);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&u,&v,&s);
            if(map[u][v]==inf)
            {
                map[u][v]=map[v][u]=s;
            }
            else
            {
                cnt++;
                if(map[u][v]>s)
                {
                    map[u][v]=map[v][u]=s;
                }
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                imap[i][j]=map[i][j];
            }
        }
        floyd();
        for(int i=1; i<=n; i++)
        {
            for(int j=i+1; j<=n; j++)
            {
                if(imap[i][j]==inf)
                    continue;
                if(map[i][j]<imap[i][j])
                {
                    cnt++;
                    continue;
                }
                if(map[i][j]==imap[i][j])
                {
                    for(int k=1; k<=n; k++)
                    {
                        if(map[i][k]+map[k][j]==map[i][j])
                        {
                            cnt++;
                            break;
                        }
                    }
                }
            }
        }
        printf("Case %d: %dn",cas,cnt);
    }
    return 0;
}