浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛部分题题解

· 教程大全 · 273565

A.锯锯锯锯锯锯锯锯

题目传送门
锯锯锯锯锯锯

题意见题干

思路：

如果每输入一组数据就进行一次运算的话，肯定会超时。那么我们可以把所有数据先输入，然后对每个数据进行标记。然后把输入的数据进行排序。循环1到1e8，如果输入的数据被遍历到了就记录答案。最后计算即可。（比赛的时候怎么没想到呢，可恶！！！）

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,mod=1e9+7;
map<int,bool>mp;
map<int,LL>mmp;
int a[N],b[N],cnt=0;
int f[N*2];
LL quick_pow(LL x,LL y)
{
    LL res=1;
    while(y)
    {
        if(y%2) res=res*x%mod;
        y=y/2;
        x=x*x%mod;
    }
    return res;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        mp[a[i]]=1;
        mp[b[i]]=1;
        f[++cnt]=a[i];
        f[++cnt]=b[i];
    }
    sort(f+1,f+1+cnt);
    LL x=1;
    mmp[0]=1;
    int k=1;
    for(int i=1;i<=1e8;i++)
    {
        x=(x*x+x)%mod;
        while(f[k]<i&&k<=cnt) k++;
        if(f[k]==i) mmp[i]=x;
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]<b[i]) swap(a[i],b[i]);
        LL res=mmp[a[i]]*quick_pow(mmp[b[i]],mod-2)%mod;
        printf("%lld\n",res);
    }
    system("pause");
    return 0;
}

B.每日咕咚

题目传送门

每日咕咚

题意见题干

思路：

每个同学在每个位置的概率都为1/n，那么简单求期望就好。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    double x,v;
    scanf("%d%lf%lf",&n,&x,&v);
    double dis=n*x;
    double ans=0;
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            double y;
            scanf("%lf",&y);
            ans=ans+dis/(y-v);
        }
    }
    printf("%.2f",ans/n);
    //system("pause");
    return 0;
}

D.涛涛和策策的游戏

题目传送门：
涛涛和策策的游戏

题意见题干

思路：

比赛时读错了题意，我本以为因数也需要是给出的数字，打完再读了一遍，发现只要是被选出数字的因数即可（我是菜逼）。然后题目就转化为了简单的尼姆博弈。算出每个数的质因子数量，然后进行异或即可。异或结果是1则策策赢，否则涛涛赢。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e6+10;
int a[N];
int idx=0,primes[M],ans[M];
int sum[N];
void solve(int num)
{
    int k=1;
    int p=a[num];
    while(primes[k]*primes[k]<=p)
    {
        while(p%primes[k]==0)
        {
            sum[num]++;
            p=p/primes[k];
        }
        k++;
    }
    if(p>1) sum[num]++;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i<=M;i++)
    {
        if(ans[i]==0) primes[++idx]=i;
        for(int j=1;j<=idx&&i*primes[j]<=M;j++)
        {
            ans[i*primes[j]]=1;
            if(i%primes[j]==0) break;
        }
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        solve(i);
        res=res^sum[i];
    }
    if(res==0) printf("TT txdy!\n");
    else printf("CC yyds!\n");
    system("pause");
    return 0;
}

F. 学长的白日梦

题目传送门
学长的白日梦

题意见题干

思路：

快速幂+快速乘

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL mod=9999999967;
int t;
LL x,y;
LL quick_mul(LL x,LL y)
{
    LL res=0;
    while(y)
    {
        if(y&1) res=(res+x)%mod;
        x=(x+x)%mod;
        y=y/2;
    }
    return res;
}
LL quick_pow(LL x,LL y)
{
    LL res=1;
    while(y)
    {
        if(y&1) res=quick_mul(res,x)%mod;
        x=quick_mul(x%mod,x%mod)%mod;
        y=y/2;
    }
    return res;
}
int main()
{  
    scanf("%d",&t);
    while(t--)
    {
        scanf("%llu%llu",&x,&y);
        if(x==1) printf("1\n");
        else
        {
            LL res=quick_pow(x,y);
            printf("%llu\n",res);
        }
    }
    //system("pause");
    return 0;
}

I.来解方程吧

题目传送门
来解方程吧

题意见题干

思路：

高斯消元法求线性方程组

AC Code

#include<bits/stdc++.h>
using namespace std;
#define maxn 505
#define D double
D a[maxn][maxn];
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n+1;++j)
        {
            scanf("%lf",&a[i][j]);
        }
    }
    for(int i=1;i<=n;++i)
    {
        int max=i;
        for(int j=i+1;j<=n;++j)
        {
            if(fabs(a[j][i])>fabs(a[max][i]))
            {
                max=j;
            }
        }
        for(int j=1;j<=n+1;++j)//交换
        {
            swap(a[i][j],a[max][j]);
        }
        for(int j=1;j<=n;++j)
        {
            if(j!=i)
            {
                D temp=a[j][i]/a[i][i];
                for(int k=i+1;k<=n+1;++k)
                {
                    a[j][k]-=a[i][k]*temp;
                    //a[j][k]-=a[j][i]*a[i][k]/a[i][i];
                }
            }
        }
    }
    int flag=0;
    int num=0;
    for(int i=1;i<=n;++i)
    {
        if(a[i][i]==0&&a[i][n+1]!=0) flag=1;
        else if(a[i][i]!=0) num++;
    }
    if(flag==1) printf("No Solution");
    else if(num!=n) printf("Multiple Solution");
    else
    {
        for(int i=1;i<=n;++i)
        {
            printf("%.2lf ",a[i][n+1]/a[i][i]);
        }
    }
    //system("pause");
    return 0;
}

K.dousha的篮球时间

题目传送门
dousha的篮球时间

题意见题干

思路：

考虑删除的数的两边的01情况即可

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,q;
int a[N];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%1d",&a[i]);
    int num=0;
    int idx=1;
    while(idx<=n)
    {
        while(a[idx]==0&&idx<=n)
        {
            idx++;
            continue;
        }
        int k=0;
        while(a[idx]==1&&idx<=n)
        {
            idx++;
            k++;
            continue;
        }
        if(k>0) num++;
    }
    printf("%d\n",num);
    int m;
    if(n==1)//如果只有一个元素
    {
        while(q--)
        {
            scanf("%d",&m);
            a[1]=a[1]^1;
            printf("%d\n",a[1]);
        }
    }
    else
    {
        while(q--)
        {
            int m;//改变的位置
            scanf("%d",&m);
            if(m==1)
            {
                if(a[m]==0&&a[m+1]==0)
                    num++;
                if(a[m]==1&&a[m+1]==0)
                    num--;
            }
            else if(m==n)
            {
                if(a[m]==0&&a[m-1]==0) num++;
                if(a[m]==1&&a[m-1]==0) num--;
            }
            else
            {
                if(a[m]==1)
                {
                    if(a[m-1]==1&&a[m+1]==1)
                        num++;
                    if(a[m-1]==0&&a[m+1]==0)
                        num--;
                }
                if(a[m]==0)
                {
                    if(a[m-1]==0&&a[m+1]==0)
                        num++;
                    if(a[m-1]==1&&a[m+1]==1)
                        num--;
                }
            }
            a[m]=a[m]^1;
            printf("%d\n",num);
        }
    }
    //system("pause");
    return 0;
}

L.吃火锅

题目传送门
吃火锅

题意见题干

思路：

可以把每个城市看成一个个的点。可以想到在自己城市吃火锅最便宜的那个点，一定不会跑到其他城市去吃火锅，于是可以从这个点出发，跑最短路。这个问题就转化成了图论的问题，每个点的初始值都是在自己城市吃火锅的成本，然后把这些点都加进优先队列中，跑堆优化的dijkstra即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n,m;
int u,v,w;
LL price[N];
int ans[N];
struct Node
{
    int to;
    int next;
    LL w;
}node[N*2];
int cent=0,head[N];
void add(int u,int v,LL w)
{
    node[cent].to=v;
    node[cent].w=w;
    node[cent].next=head[u];
    head[u]=cent++;
}
struct tree
{
    int id;
    LL num;
};
priority_queue<tree>que;
bool operator<(const tree &a,const tree &b)
{
    return a.num>b.num;
}
void dijkstra()
{
    while(!que.empty())
    {
        tree now=que.top();
        que.pop();
        ans[now.id]=0;
        for(int i=head[now.id];~i;i=node[i].next)
        {
            int to=node[i].to;
            if(price[to]>price[now.id]+2*node[i].w)
            {
                price[to]=price[now.id]+2*node[i].w;
                if(ans[to]==0)
                {
                    ans[to]=1;
                    que.push({to,price[to]});
                }
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&price[i]);
        que.push({i,price[i]});
        ans[i]=1;
    }
    dijkstra();
    for(int i=1;i<=n;i++)
        printf("%lld ",price[i]);
    //system("pause");
    return 0;
}

M.灾难预警

题目传送门
灾难预警

题意见题干

思路：

bfs+优先队列

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int maze[N][N],n;
int ans[N][N];
struct node
{
    int x,y;
    int h;
};
priority_queue<node>que;
bool operator<(const node &a,const node &b)
{
    return a.h<b.h;
}
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int bfs()
{
    node start;
    start.x=1,start.y=1,start.h=maze[1][1];
    que.push(start);
    ans[1][1]=1;
    while(!que.empty())
    {
        node now=que.top();
        que.pop();
        if(now.x==n&&now.y==n) return now.h;
        for(int i=0;i<4;i++)
        {
            int dx=now.x+dir[i][0],dy=now.y+dir[i][1];
            if(dx<1||dx>n||dy<1||dy>n) continue;
            if(ans[dx][dy]==1) continue;
            node f;
            f.x=dx,f.y=dy,f.h=min(now.h,maze[dx][dy]);
            que.push(f);
            ans[dx][dy]=1;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&maze[i][j]);
    int res=bfs();
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int y;
        scanf("%d",&y);
        if(y<=res) printf("Wuhu\n");
        else printf("Hmmm\n");
    }
    //system("pause");
    return 0;
     
}

N.yyds!

题目传送门
yyds

题意见题干

思路：

简单的字符串模拟

AC Code

#include<bits/stdc++.h>
using namespace std;
string str;
int main()
{
    cin>>str;
    int len=str.length();
    int num1=0,num2=0,num3=0;
    for(int i=0;i<len;i++)
    {
        if(str[i]=='y')num1++;
        else if(str[i]=='d') num2++;
        else if(str[i]=='s') num3++;
    }
    while(num1>0||num2>0||num3>0)
    {
        if(num1)
        {
            printf("y");
            num1--;
        }
        if(num1)
        {
            printf("y");
            num1--;
        }
        if(num2)
        {
            printf("d");
            num2--;
        }
        if(num3)
        {
            printf("s");
            num3--;
        }
    }
    //system("pause");
    return 0;
}

本文地址：https://blog.csdn.net/Stevenwuxu/article/details/109268170

相关推荐：

LeetCode 题解优化：高效求解最长回文子串（动态规划法）

本文详解leetcode第5题“最长回文子串”的内存与时间双重优化方案，摒弃暴力递归+重复校验的低效思路，采用空间可控的二维dp方法，在o(n²)时间与o(n²)空间内稳定通过所有测试用例。 本文详解leetcode第5题“最长回文子串”的内存与时间双重优化方案，摒弃暴力递归+重复校验的低效思路，采...

LeetCode 题解：优化最长回文子串的内存与时间复杂度

本文深入剖析暴力递归解法导致内存超限（mle）的根本原因，详解基于动态规划的o(n²)空间优化实现，并提供可直接提交的高效、稳定代码。 本文深入剖析暴力递归解法导致内存超限（mle）的根本原因，详解基于动态规划的o(n²)空间优化实现，并提供可直接提交的高效、稳定代码。 在LeetCode第5题「最...

.NET，C#和ASP.NET的关系

.NET，C#和ASP.NET的关系　　估计有很多人没有搞清楚，包括我自己，也是搞不大清，找了篇文章，大家随便看看，概念性问题，一看就明白的。1.NET是一个平台，一个抽象的平台的概念。　.NET平台其本身实现的方式其实还是库，抽象层面上来看是一个平台。　个人理解.NET核心就只是.NETFrame...

在进行C51程序设计时如何精确延时的常见方法介绍

单片机因具有体积小、功能强、成本低以及便于实现分布式控制而有非常广泛的应用领域。单片机开发者在编制各种应用程序时经常会遇到实现精确延时的问题，比如按键去抖、数据传输等操作都要在程序中插入一段或几段延时，时间从几十微秒到几秒。有时还要求有很高的精度，如使用单总线芯片DS18B20时，允许误差范围在十几...

C++培训：C语言链接表分析

　　C++培训之前有同学再问C语言链接表怎么破?今天小编把这个知识点给大家分享出来，有疑问的可以多看看!　　　　相信学了c语言的人对链表或多或少有了解，链表也是数据结构的重要内容，今天就来聊聊最简单的单向动态链表的建立与输出。首先要了解什么是链表，链表是程序设计中一种重要的动态数据结构，是动态地进行...

PHP案例之聊天室设计

原文[下载/浏览]：http://www.xilinjie.com/university/124内容介绍一、概述聊天室，是网友间交流互动的最主要渠道之一。在聊天室中，网友之间可以互不认识，可以根据自己的爱好畅所欲言，甚至可以充当文学作品上的美女侠士。对商务网站，常常利用聊天室来吸引用户加入，这也成为...

PHP案例 网页计数器设计

原文[下载/浏览]：http://www.xilinjie.com/university/125内容介绍一、概述网页计数器是用来统计网站的访问次数并把结果公布在访问的网页上的。它是让Web访问者和网页管理者获知网页（站）的人气指数的最直接地方法。网上有很多免费资源都提供网页计数器的代码，只要把它嵌入...

PHP案例 网站会员管理设计

原文[下载/浏览]：http://www.xilinjie.com/university/123内容介绍一、概述会员管理的网页功能在现今网站构建上相当的重要，尤其是对于一些需要付费来取得会员认证的公司和个人网站。为了避免误闯的用户及有心的***，会员认证及管理的方式的确有其存在的必要。因此，设计一个...