信息学奥赛一本通T1378：最短路径算法 最短路径
【题目描述】给出一个有向图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
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 885 )
轩爸
信息学奥赛一本通T1256：广度优先搜索（BFS） 献给阿尔吉侬的花束
【题目描述】阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单
- 0
- 0
- 轩爸
- 发布于 2020-05-02 16:20
- 阅读 ( 884 )
CCF关于举办2023NOI春季测试的通知
NOI春季测试将于2023年3月4日在各省同步举行。本次测试成绩旨在为那些未举办NOIP2022的省份在计算NOI2023省选总成绩时提供依据，其他举办过NOIP的省份也可选择参加。本次测试单独评价，成绩与NOIP无关。 测试时间为2023年3月4日（周六）8:30-13:00（4.5小时），测试共有4道题目，采用机试方式。 参加人员数量及报名条件由各省根据省内情况自定。 此通知。 中国计算机学会...
- 0
- 0
- 轩爸
- 发布于 2022-12-16 21:18
- 阅读 ( 882 )
中国初中生队出征ISIJ2021，斩获佳绩
2021国际初中生信息学竞赛（International School for Informatics “Junior”，ISIJ2021）于2021年7月1日-11日举行。由于疫情的持续影响，本次比赛在全球各地以线上形式同步举办。本次比赛吸引了十多个国家和地区的共记210名选手和教练参加。CCF派出由36名选手组成中国代表队出征国际初中生竞赛。这也是CCF第四次组织中国代表队参加该国际比赛。 I...
- 0
- 0
- 轩爸
- 发布于 2021-07-16 07:18
- 阅读 ( 882 )
信息学奥赛一本通T1388：并查集 家谱
【题目描述】现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。【输入】由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6
- 0
- 0
- 轩爸
- 发布于 2020-05-16 10:20
- 阅读 ( 882 )
信息学奥赛一本通T1276：动态规划经典问题 编辑距离
【题目描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种： 1、删除一个字符； 2、插入一个字符； 3、将一个字符改为另一个字符。对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。【输入】第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。【输出】只有一个正整数，为最少字符操
- 0
- 1
- 轩爸
- 发布于 2020-05-04 16:20
- 阅读 ( 882 )
预告：钻石教练李曙开讲
2020年5月，培训正式推出！在之前的培训中，我们接触到了程序的循环结构这一知识，在接下来的两周时间，我们将继续深入学习循环。第六期培训将于6月9日如期而至。本次主讲人为NOI钻石教师、南京外国语学校李曙，他将就程序的循环嵌套相关问题进行讲解。培训视频将于6月9日16点在NOI官网更新，敬请期待！讲师介绍 李曙，CCF会员，南京外国语学校信息学竞赛教练，专职于信息学竞赛的教学和带队工作。NOI钻石...
- 0
- 0
- 轩爸
- 发布于 2020-06-04 10:21
- 阅读 ( 881 )
信息学奥赛一本通T1441：深搜的剪枝技巧 生日蛋糕
【题目描述】7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1≤i≤M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i＜M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=Sπ,请编程对给出的N和M，找出蛋糕的制作方案（适当的
- 0
- 0
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 881 )
信息学奥赛一本通T1428：贪心算法 数列分段
【题目描述】对于给定的一个长度为N的正整数数列A[i]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。【输入】第1行包含两个正整数N，M，表示了数列A[i]的长度与每段和的最大值；第2行包含N个空格隔开的非负整数A[i]，如题目所述。【输出】一个正整数，输出最少划分的段数。【输入样例】5 6 【输出样例】3【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 879 )
信息学奥赛一本通T1230：贪心算法 寻找平面上的极大点
【题目描述】在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x≥a,y≥b;用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。本题规定：n不超过100，并且不考虑点的坐标为负数的情况。【输
- 0
- 0
- 轩爸
- 发布于 2020-04-29 16:20
- 阅读 ( 878 )
信息学奥赛一本通T1385：并查集 团伙
【题目描述】在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？【输入】第1行为n和m，1<n<1000,1≤m≤100 000；以下m行，每行为p x y，p的值为0
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 877 )
信息学奥赛一本通T1394：最小生成树 连接格点
【题目描述】有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。【输入】第一行输入两个正整数m和n。以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1−x2|+|y1−y2|=1。【输出】输出使得连通所有点还需
- 0
- 0
- 轩爸
- 发布于 2020-05-16 16:20
- 阅读 ( 874 )
信息学奥赛一本通T1238：分治算法 一元三次方程求解
【题目描述】形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在−100至100之间)，且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。【输入】一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。【输出】一行，包含三个实数，为该
- 0
- 0
- 轩爸
- 发布于 2020-04-30 16:20
- 阅读 ( 868 )
信息学奥赛一本通T1377：最短路径算法 最优乘车
【题目描述】H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 866 )
信息学奥赛一本通T1268：背包问题 完全背包问题
【题目描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。【输入】第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输
- 0
- 0
- 轩爸
- 发布于 2020-05-03 16:20
- 阅读 ( 866 )
预告：金牌教练贾志勇开讲
2020年5月，培训正式推出！在之前的培训中，我们接触了并查集的知识。下周，我们将开始学习倍增法的知识。第二十三期培训将于10月6日如期而至。本次主讲人为NOI金牌教师、北京市第八十中学贾志勇，他将就倍增法及其应用的相关问题进行讲解。培训视频将于10月6日16点在NOI官网更新，敬请期待！讲师介绍 贾志勇，CCF会员，北京市第八十中学高级教师，NOI金牌教师，纪念NOI创建30周年杰出社会服务奖获...
- 0
- 0
- 轩爸
- 发布于 2020-09-29 16:20
- 阅读 ( 865 )
信息学奥赛一本通T1279：动态规划经典问题 橱窗布置
【题目描述】假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果i<j，则花束i必须放在花束j左边的花瓶中。例如，假设杜鹃花的
- 0
- 0
- 轩爸
- 发布于 2020-05-04 16:20
- 阅读 ( 865 )
信息学奥赛一本通T1193：递推算法 吃糖果
【题目描述】名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力，0<N<20)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。例如：如果N=1，则名名第1天就吃掉它，共有1种方案；如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；如果N=3，则名名第1天可以吃1
- 0
- 0
- 轩爸
- 发布于 2020-04-26 10:20
- 阅读 ( 865 )
ISIJ 2022收官，中国初中生再展风采
2022国际初中生信息学竞赛（International School in Informatics “Junior”，ISIJ 2022）于2022年7月1日-10日在塔吉克斯坦举行。本次活动是自2020年疫情以来，ISIJ首次恢复现场竞赛，同时，活动也向受疫情管控无法参加现场竞赛的国家和地区代表队开放线上参赛。ISIJ 2022共有来自十多个国家和地区的315位选手参加，其中线下164人，线上...
- 0
- 0
- 轩爸
- 发布于 2022-07-16 23:15
- 阅读 ( 864 )
