第九届北航程序设计大赛网络预赛——水题题解

迈不过友情╰ 2022-09-18 14:58 178阅读 0赞

比赛链接：http://acm.buaa.edu.cn/contest/117/home/

噩梦般的期末七连考刚刚过半，按现在的进度估计我cet6是要果考了，求过。。。。

本次比赛是复习期间断断续续做的，弱菜我冥思苦想只搞出6题，实在太弱……比赛结束后雷神告诉了我另外几道的思路，考完之后希望能有时间挑战下。

**A BUAA 759 晴天小猪是点赞狂魔**

题目链接：http://acm.buaa.edu.cn/problem/759/

一直没怎么练过概率题，不过这题还是比较好想的。

思路：每条新鲜事抽象成一段区间，于是n条就变成了n+1个端点，从n+1个点任选两个点就构成题目中要求的一段，总数用组合数可以算出。所有可能的组合中，每一小段被选的次数：第k小段会被选k\*(n+1-k)次。最终结果就是选的次数乘以权值求和，再除组合数。

#include <cstdio>
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            long long n;
            scanf("%lld",&n);
            long long c=n*(n+1)/2,sum=0;
            int k=n+1;
            for (long long i=1;i<=n;i++)
            {
                long long data;
                scanf("%lld",&data);
                sum+=data*i*(k-i);
            }
            printf("%.3lf\n",1.0*sum/c);
        }
        return 0;
    }

**B BUAA 765**  **晴天小猪的披萨**

题目链接：http://acm.buaa.edu.cn/problem/765/

二分图模板题，需要思路的参见：[Poj 3041 Asteroids + Poj 2226 Muddy Fields(二分图与一类选方格题目)][Poj 3041 Asteroids _ Poj 2226 Muddy Fields]

#include <cstdio>
    #include <cstring>
    
    const int N=505;
    bool map[N][N];
    bool vis[N];
    int match[N];
    
    int n,m,k;
    
    bool Dfs (int u)
    {
    	for (int v=1;v<=m;v++)
    		if (vis[v] == false && map[u][v])
    		{
    			vis[v]=true;
    			if (match[v]==0 || Dfs(match[v]))
    			{
    				match[v]=u;
    				return true;
    			}
    		}
    	return false;
    }
    
    int main ()
    {
        while (~scanf("%d%d%d",&n,&m,&k))
        {
            int i,temp1,temp2,sum=0;
            memset(map,false,sizeof(map));
            memset(match,0,sizeof(match));
            for (i=1;i<=k;i++)
            {
                scanf("%d%d",&temp1,&temp2);
                map[temp1][temp2]=true;
            }
            for (i=1;i<=n;i++)
            {
                memset(vis,false,sizeof(vis));
                if (Dfs(i))
                sum++;
            }
            printf("%d\n",sum);
        }
    	return 0;
    }

**E BUAA 735**  **晴天小猪来刷人人**

题目链接：http://acm.buaa.edu.cn/problem/735/

这题具体看代码吧，现在只记得当时乱写一通然后调了好久。。。。

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=1000005;
    
    int data[N],dis[N];
    int poor[N];
    int n,m;
    
    int Deal (int k)
    {
        int left=0,right=k-1,mid,ans;
        while (left<=right)
        {//二分判定一个空段k，可以利用m次补签，最早可以和什么位置构成连续
            mid=(left+right)>>1;
            if (poor[k-1]-poor[mid]<=m) //其实是以这一空段的开始为结束，所以用前一段的数据
            {
                ans=mid;
                right=mid-1;
            }
            else
                left=mid+1;
        }
        return dis[k]-dis[ans]+m;
    }
    
    int main ()
    {
        int T,i;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d%d",&n,&m);
            for (i=1;i<=n;i++)
                scanf("%d",&data[i]);
            data[n+1]=-1;   //
            int cnt=0; //不连续的段数
            int pre=1;//pre记录上一次开始连续签到(连续1天也算)时的起始位置
            for (i=2;i<=n+1;i++)
                if (data[i]!=data[i-1]+1)
                {
                    cnt++;
                    dis[cnt]=i-pre;//记录在连续的这段时间内(不含当天)有多少天不需要补签
                    poor[cnt]=data[i]-data[i-1]-1;//记录两次之间隔了多少天
                    pre=i;
                }
     //       for (i=1;i<=cnt;i++) printf("%d %d\n",dis[i],poor[i]);
            if (cnt==1)
            {
                printf("%d\n",n+m);
                continue;
            }
            for (i=1;i<=cnt;i++)  //前缀和优化
            {
                dis[i]+=dis[i-1];
                poor[i]+=poor[i-1];
            }
            int ans=0;
            for (i=1;i<=cnt;i++)  //枚举每一个空段
                ans=max(ans,Deal(i));
            printf("%d\n",ans);
        }
        return 0;
    }

**F BUAA 747**  **晴天小猪砌墙**

题目链接：http://acm.buaa.edu.cn/problem/747/

读入数据时记录每一个位置左侧最高到多高，然后反向扫一遍记录每个位置右侧最高到多高，然后计算……

#include <cstdio>
    #include <cstring>
    #define min(a,b) ((a)<(b)?(a):(b))
    #define max(a,b) ((a)>(b)?(a):(b))
    
    const int N=1000005;
    const int INF=2000000;
    int data[N],l[N],r[N];
    
    int main ()
    {
        int T,n;
        scanf("%d",&T);
        while (T--)
        {
            long long sum=0;
            int i,left=0,right=0;
            scanf("%d",&n);
            memset(l,0,sizeof(l));
            memset(r,0,sizeof(r));
            for (i=1;i<=n;i++)
            {
                scanf("%d",&data[i]);
                l[i]=left;
                left=max(left,data[i]);
            }
            for (i=n;i>0;i--)
            {
                r[i]=right;
                right=max(right,data[i]);
            }
            for (i=1;i<=n;i++)
            {
                int del=min(l[i],r[i]);
                if (del>data[i])
                    sum+=del-data[i];
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

**I BUAA 732**  **晴天小猪仰慕上古神犇GG**

题目链接：http://acm.buaa.edu.cn/problem/732/

又是概率。。。YY了一个算法，不一定对……

思路：设在某一轮轮到A答题，其获胜概率为K，于是简单模拟一下可得：K=a\*(1-b)+a\*b\*K，然后化简一下求出K……

#include <cstdio>
    
    int Gcd (int x,int y)
    {
        return !y?x:Gcd(y,x%y);
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            int x=a*(100-b);
            int y=10000-a*b;
            int k=Gcd(x,y);
            int t=Gcd(y-x,y);
            printf("%d/%d %d/%d\n",x/k,y/k,(y-x)/t,y/t);
        }
        return 0;
    }

**K BUAA 727**  **晴天小猪向昂神学习**

题目链接：http://acm.buaa.edu.cn/problem/727/

又见序列处理。。。。树状数组优化+DP，估计不是正解……

思路：先将数据离散化到比较小的范围，这样就可以用树状数组处理了，记得树状数组从1开始。树状数组用来记录DP时需要的最大值，可以实现快速更新，快速查找。具体见代码。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define lowbit(x) ((x)&(-(x)))
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    
    const int N=100005;
    int data[N],dis[N];//离散化数组
    int tot; //离散化后的数字上限
    int dp[N];//dp[i]记录以i为截止，最长连续上升子串的长度
    int f[N]; //f[i]记录以i为开始，最长连续上升子串的长度
    int bit[N]; //树状数组
    
    void Update (int k,int val)
    {
        while (k<=tot)  //是<=tot,也即离散化后数字上限
        {
            bit[k]=max(bit[k],val);
            k+=lowbit(k);
        }
    }
    
    int Cal (int k)
    {
        int ans=0;
        while (k>0)
        {
            ans=max(ans,bit[k]);
            k-=lowbit(k);
        }
        return ans;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            int i,n;
            scanf("%d",&n);
            for (i=1;i<=n;i++)
            {
                scanf("%d",&data[i]);
                dis[i]=data[i];
            }
            memset(dp,0,sizeof(dp));
            memset(f,0,sizeof(f));
            memset(bit,0,sizeof(bit));
            sort(dis+1,dis+n+1);
            tot=unique(dis+1,dis+n+1)-(dis+1);
    
            for (i=1;i<=n;i++)  //离散化
                data[i] = lower_bound(dis+1,dis+n+1,data[i])-(dis);
            dp[1]=1;
            for (i=2;i<=n;i++)
                if (data[i]>data[i-1])
                    dp[i]=dp[i-1]+1;
                else
                    dp[i]=1;
            f[n]=1;
            for (i=n-1;i>=1;i--)
                if (data[i]<data[i+1])
                    f[i]=f[i+1]+1;
                else
                    f[i]=1;
            int ans=0,tmp;
            for (i=1;i<=n;i++)
            {
                tmp=Cal(data[i]-1);
                ans=max(ans,tmp+f[i]);
                Update(data[i],dp[i]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[Poj 3041 Asteroids _ Poj 2226 Muddy Fields]: http://blog.csdn.net/whyorwhnt/article/details/9722431