青少年编程知识记录 codecoming

【题解】数字三角问题

【题目描述】

给字一个由n行数字组成的数字三角形（等腰三角形）。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。

【输入描述】

数字三角形的行数和数字三角形

【输出描述】



最大的路径和

【样例输入1】

5  7  8 3  9 8 7  1 2 3 4  4 5 6 7 8

【样例输出1】

33

【样例输入2】

5  7  3 8  8 1 0  2 7 4 4  4 5 2 6 5

【样例输出2】

30

【样例解释】

对于样例1，路径是7 8  8 3 7

作者:亿万年的星光 分类:题解目录 浏览:

2021年青岛市程序设计竞赛试题（初中组）决赛

A.趣味三角(triangle.cpp) 

【题目描述】 

今天，新高一的OIer们第一次进入了机房。z老师想让他们喜欢上OI，于是给了他们每个人一个三角形。 这时候，小q秃发奇想，拿着手中的三角形，给大家出了一道题，请你帮助他们给小q一个正确的答案。 小q给了你两个整数 ，请输出杨辉三角前x行的所有数的和模a的值。 如果你不知道杨辉三角是什么，请看样例解释。 

【输入格式】

 每个测试点有多组测试数据。 每个测试点第一行一个正整数n表示数据组数。 接下来n行每行两个正整数a,x 表示一次询问。 

【输出格式】 

共T行，每行一个正整数，表示答案。 

【样例输入】

3  5 6  7 2  2 998244353



【样例输出】

3  3  1



【样例解释】

 杨辉三角如下： 

第一行： 1  第二行： 1 1  第三行： 1 2 1  第四行： 1 3 3 1  第五行： 1 4 6 4 1  第六行：  1 5 10 10 5

这个三角的生成方式如下： 1. 第 行（ 是正整数）有 个数。 2. 记第 行从左到右数第 个数为 （ 都是正整数），则

可见前6 行的和为63 ,对5 取模后结果为3 。 前2 行的和为3 ,对 7取模后结果为3 。

【说明提示】

对于10% 的数据，满足 n<=5； 

对于20% 的数据，满足T=1,n<=50 ； 

对于40% 的数据，满足T<=10,n<=100； 

对于60% 的数据，满足n<=106 ； 

对于80% 的数据，满足N<=1018 ； 

对于100%的数据，满足 T<103,m<108,n<101000 保证 m为质数



作者:亿万年的星光 分类:题解目录 浏览:

【算法】动态规划（二）——数字三角形问题

1.问题描述及状态定义

数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：

从第一行开的数开始走，每次可以往下或右走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和最大?

作者:亿万年的星光 分类:算法 浏览:

【算法】动态规划(一)

1.基本概念在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前
作者:亿万年的星光 分类:算法 浏览:

【题解】冒泡排序计数

【题目描述】

考虑冒泡排序的一种实现。

bubble-sort  (A[],  n)

>   round  =  0

>   while  A  is  not  sorted

>   >   round  :=  round  +  1

>   >   for  i  :=  1  to  n  -  1

>   >   >   if  (A[i]  >   A[i  +  1])

>   >   >   >   swap(A[i],  A[i  +  1])

求1  ..  n的排列中，有多少个排列使得A被扫描了K遍，亦即算法结束时round  ==  K。



答案模20100713输出。

【输入描述】

输入包含多组数据。每组数据为一行两个整数N，K。 



数据规模和约定

T  < =  10  ^  5。

1  < =  K  <   N  <   10  ^  6。

【输出描述】

对每组数据，输出一行一个整数表示答案。 

【样例输入】

3  3 0  3 1  3 2

【样例输出】

1  3  2
作者:亿万年的星光 分类:题解目录 浏览:

2021 年青岛市程序设计竞赛试题（小学组）决赛

1.方程求解



【描述】

输入正整数 a，b，c。

求有多少组 x 和 y 满足 a*x+b*y=c 。x 和 y 都是非负整数。

【输入】

一行，包含三个正整数 a，b，c，两个整数之间用单个空格隔开。

【输出】

满足 a*x+b*y=c 的 x 和 y 的组数。

【输入样例】

2 3 18

【输出样例】

4

【样例说明】

有以下 4 组 x 和 y 满足 2*x+3*y=18:

x=0,y= 6

x=3,y= 4

x=6 ,y=2

x=9,y= 0

【数据范围】

50%的数据，1<=a,b,c<=1000；

100%的数据，1<=a,b,c<=100000。

作者:亿万年的星光 分类:C++知识 浏览:

【题解】山区建小学

【题目描述】政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di(为正整数)，其中，0<i<m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学(设0<n≤m<500。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。【输入】第1行为m和n，其间用空格间隔第2行为m−1 个整数，依次表示从一
作者:亿万年的星光 分类:题解目录 浏览:

【题解】踩方格

【题目描述】有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；b、走过的格子立即塌陷无法再走第二次；c、只能向北、东、西三个方向走；请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。【输入】允许在方格上行走的步数n(n≤20)。【输出】计算出的方案数量。【输入样例】2【输出样例】7
作者:亿万年的星光 分类:题解目录 浏览:

【题解】移动路线

【题目描述】X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从   左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。   对于1行1列的方格矩阵，蚂
作者:亿万年的星光 分类:题解目录 浏览:

【题解】队列问题

4.队列问题（lru.cpp）

【题目描述】

有一个大小为n的页面缓存队列，初始为空，当计算机访问页面时，若缓存队列没有该页面，则加入到缓存队列中，若队列已满，则将删除访问时间最远的页面。

有Q次询问，每次询问输入一个整型x,表示访问页面x。若缓存队列中有则输出yes,否则输出no。

【输入描述】

第一行，2个空格隔开正整数n,Q

以下Q行：每行是一个整型x。

【输出描述】

Q行，每行可能为yes或者no

【样例输入】

3 10  1  2  1  3  5  6  1  5  2  6



【样例输出】

no  no  yes  no  no  no  no  yes  no  no



【样例解释】

【数据范围】

60%的数据：n<=1000,Q<=1000；

100%的数据：n<=100000,Q<=100000

作者:亿万年的星光 分类:题解目录 浏览: