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

2024-02-04 14:48
文章标签 竞赛 部分 程序设计 浙江 题解 选拔赛 大学 农林 天梯 第十九届

本文主要是介绍浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛部分题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}

这篇关于浙江农林大学第十九届程序设计竞赛暨天梯赛选拔赛部分题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/677865。

相关文章

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
C - Word Ladder题解

C - Word Ladder题解

C - Word Ladder 题解 解题思路： 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数（也就是需要变换多少次） 开始替换时： tips: 字符串下标以0开始 我们定义两个变量a和b，用于记录当前遍历到的字符 首先是判断：如果这时a已经==b了，那么就跳过，不用管； 如果a大于b的话：那么我们就让s中的第i项替换成b，接着就直接输出S就行了。 这样
阅读更多...
笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

笔记整理—内核！启动！—kernel部分（2）从汇编阶段到start_kernel

kernel起始与ENTRY(stext)，和uboot一样，都是从汇编阶段开始的，因为对于kernel而言，还没进行栈的维护，所以无法使用c语言。_HEAD定义了后面代码属于段名为.head .text的段。         内核起始部分代码被解压代码调用，前面关于uboot的文章中有提到过（eg:zImage）。uboot启动是无条件的，只要代码的位置对，上电就工作，kern
阅读更多...
C语言程序设计(数据类型、运算符与表达式)

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型： 二、常量和变量 2.1常量和符号常量 在程序运行过程中，其值不能被改变的量称为常量。 常量区分为不同的类型： 程序中用＃define（预处理器指令）命令行定义变量将代表常量，用一个标识符代表一个常量，称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元，用来存放数据，在程序运行期间，这些值是可以 改变的。 变
阅读更多...
【秋招笔试】9.07米哈游秋招改编题-三语言题解

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新 🍄 题面描述等均已改编，如果和你笔试题看到的题面描述
阅读更多...
C语言程序设计(选择结构程序设计)

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①＜（小于） ②＜＝（小于或等于） ③＞（大于） ④＞＝（大于或等于 ） ⑤＝＝（等于） ⑥！＝（不等于） 说明： 前4个优先级相同，后2个优先级相同，关系运算符的优先级低于算术运算符，关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式（可以是算术表达式或关系表达式，逻辑表达式，赋值表达式，字符
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2