源程序 - 信奥网|信息学奥赛

0推荐

791浏览

信息学奥赛一本通T1385：并查集团伙

【题目描述】在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？【输入】第1行为n和m，1<n<1000,1≤m≤100 000；以下m行，每行为p x y，p的值为0

0
轩爸发布于 2020-05-15 16:20

0推荐

1198浏览

信息学奥赛一本通T1382：最短路径算法最短路

【题目描述】给定 M 条边， N 个点的带权无向图。求 1 到 N 的最短路。【输入】第一行：N,M(N≤100000，M≤500000)接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。【输出】一个整数，表示 1 到 N 的最短距离。【输入样例】4 4【输出样例】2【源程序】

0
轩爸发布于 2020-05-15 16:20

0推荐

1217浏览

信息学奥赛一本通T1381：最短路径算法城市路

【题目描述】罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。【输入】输入n, m，表示n个城市和m条路;接下来m行，每行a b c，表示城市a与城市b有长度为c的路。【输出】输出1到n

0
轩爸发布于 2020-05-15 16:20

0推荐

833浏览

【题目描述】给出一个有向图G=(V, E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环权值和都是正的，我们就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。【输入】第1行：一个正数n（2≤n≤80），表示图G的顶点总数。第2行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。第3至第n+2行，用一个邻接矩阵W给出了这个图。【输出

0
轩爸发布于 2020-05-15 10:20

0推荐

1193浏览

信息学奥赛一本通T1372：堆及其应用小明的账单

【题目描述】小明在一次聚会中，不慎遗失了自己的钱包，在接下来的日子，面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下，老板最终同意延缓账单的支付时间。可老板又提出，必须从目前还没有支付的所有账单中选出面额最大和最小的两张，并把他们付清。还没有支付的账单会被保留到下一天。请你帮他计算出支付的顺序。【输入】第1行：一个正整数N(N≤15,000)，表示小明补办银联卡总共的天数。第2行

0
轩爸发布于 2020-05-14 16:20

0推荐

750浏览

信息学奥赛一本通T1373：堆及其应用鱼塘钓鱼

【题目描述】有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。假设能钓到鱼的数

0
轩爸发布于 2020-05-14 16:20

0推荐

806浏览

信息学奥赛一本通T1370：堆及其应用最小函数值

【题目描述】有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix2+Bix+Ci(x∈N∗)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。【输入】第一行输入两个正整数n和m。以下n行每行三个正整数，其中第ii行的三个数分别位Ai、Bi和Ci。输入数据保证Ai≤10，Bi≤100，Ci≤10000。【输出】将这n个函数所有可以生成的函数值排

0
轩爸发布于 2020-05-14 10:20

0推荐

1539浏览

信息学奥赛一本通T1362：队列家庭问题

【题目描述】有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关.系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)此时，6个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为一个家庭，第一个家庭的人数为最多。

0
轩爸发布于 2020-05-13 16:20

0推荐

1130浏览

信息学奥赛一本通T1361：队列产生数

【题目描述】给出一个整数n（n≤2000）和k个变换规则（k≤15）。规则： ① 1个数字可以变换成另1个数字； ② 规则中，右边的数字不能为零。例如：n=234，k=2规则为2 → 5，3 → 6上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数。求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。

0
轩爸发布于 2020-05-13 16:20

0推荐

856浏览

信息学奥赛一本通T1360：队列奇怪的电梯

【题目描述】大楼的每一层楼都可以停电梯，而且第i层楼（1≤i≤N）上有一个数字Ki(0≤=Ki≤=N）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如：3 3 1 2 5代表了Ki（K1=3,K2=3,……），从一楼开始。在一楼，按“上”可以到4楼，按“下”是不起作用的，因为没有-2楼。那么，从A楼到B楼至少要按几次按钮呢？【

0
轩爸发布于 2020-05-13 10:20

0推荐

1294浏览

信息学奥赛一本通T1359：队列围成面积

【题目描述】编程计算由“*”号围成的下列图形的面积。面积计算方法是统计*号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10×10的二维数组中，有“*”围住了15个点，因此面积为15。【输入】10×10的图形。【输出】输出面积【输入样例】0 0 0 0 0 0 0 0 0 0【输出样例】15【源程序】

0
轩爸发布于 2020-05-13 10:20

3推荐

1913浏览

信息学奥赛一本通T1356：栈计算

【题目描述】小明在你的帮助下，破密了Ferrari设的密码门，正要往前走，突然又出现了一个密码门，门上有一个算式，其中只有“(”，“)”，“0-9”，“+”，“-”，“*”，“/”，“^”，求出的值就是密码。小明数学学得不好，还需你帮他的忙。(“/”用整数除法)【输入】共1行，为一个算式。【输出】共1行，就是密码。【输入样例】1+(3+2)*(7^2+6*9)/(2)【输出样例】258【源程序】

0
轩爸发布于 2020-05-13 10:20

0推荐

969浏览

信息学奥赛一本通T1351：最小生成树家谱树

【题目描述】有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的孩子的信息。输出一个序列，使得每个人的后辈都比那个人后列出。【输入】第1行一个整数N（1≤N≤100），表示家族的人数；接下来N行，第I行描述第I个人的儿子；每行最后是0表示描述完毕。【输出】输出一个序列，使得每个人的后辈都比那个人后列出；如果有多解输出任意一解。【输入样例】5【输出样例】2 4 5 3 1【源程序】

0
轩爸发布于 2020-05-12 16:20

0推荐

680浏览

信息学奥赛一本通T1350：最小生成树最短网络

【题目描述】农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000。【输入】第一行：农场的个

0
轩爸发布于 2020-05-12 10:20

0推荐

590浏览

信息学奥赛一本通T1347：并查集格子游戏

【题目描述】Alice和Bob玩了一个古老的游戏：首先画一个n × n的点阵（下图n = 3）接着，他们两个轮流在相邻的点之间画上红边和蓝边：直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了(n ≤ 200)，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？【输入】输入数据第一行为两个整数n和

0
轩爸发布于 2020-05-12 10:20