我搬了几道洛谷的题
NOIP 2000 提高组 T4
题目描述
设有 N \times NN×N 的方格图 (N \le 9)(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 00。如下图所示(见样例):
某人从图的左上角的 AA 点出发,可以向下行走,也可以向右走,直到到达右下角的 BB 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 00)。
此人从 AA 点到 BB 点共走两次,试找出 22 条这样的路径,使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 NN(表示 N \times NN×N 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 00 表示输入结束。
输出格式
只需输出一个整数,表示 22 条路径上取得的最大的和。
输入输出样例
输入 #1复制
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出 #1复制
67
说明/提示
数据范围:1\le N\le 91≤N≤9。
2.小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 mm 行 nn 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标 (1,1)(1,1),小轩坐在矩阵的右下角,坐标 (m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 00 表示),可以用一个 [0,100][0,100] 内的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度之和最大。现在,请你帮助小渊和小轩找到这样的两条路径。
输入格式
第一行有两个用空格隔开的整数 mm 和 nn,表示班里有 mm 行 nn 列。
接下来的 mm 行是一个 m \times nm×n 的矩阵,矩阵中第 ii 行 jj 列的整数表示坐在第 ii 行 jj 列的学生的好心程度。每行的 nn 个整数之间用空格隔开。
输出格式
输出文件共一行一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。
输入输出样例
输入 #1复制
3 3
0 3 9
2 8 5
5 7 0
输出 #1复制
34
说明/提示
【数据范围】
对于 30%30% 的数据,满足 1 \le m,n \le 101≤m,n≤10。
对于 100%100% 的数据,满足 1 \le m,n \le 501≤m,n≤50。
【题目来源】
NOIP 2008 提高组第三题。
3.著名科学家卢斯为了检查学生对进位制的理解,他给出了如下的一张加法表,表中的字母代表数字。 例如:
\def\arraystretch{2} \begin{array}{c||c|c|c|c} \rm + & \kern{.5cm} \rm \mathclap{L} \kern{.5cm} & \kern{.5cm} \rm \mathclap{K} \kern{.5cm} & \kern{.5cm} \rm \mathclap{V} \kern{.5cm} & \kern{.5cm} \rm \mathclap{E} \kern{.5cm} \ \hline\hline \rm L & \rm L & \rm K & \rm V & \rm E \ \hline \rm K & \rm K
& \rm V & \rm E & \rm \mathclap{KL} \ \hline \rm V & \rm V & \rm E & \rm \mathclap{KL} & \rm \mathclap{KK} \ \hline \rm E & \rm E & \rm \mathclap{KL} & \rm \mathclap{KK} & \rm \mathclap{KV} \ \end{array}
+
L
K
V
E
L
L
K
V
E
K
K
V
E
KL
V
V
E
KL
KK
E
E
KL
KK
KV
其含义为:
L+L=LL+L=L,L+K=KL+K=K,L+V=VL+V=V,L+E=EL+E=E
K+L=KK+L=K,K+K=VK+K=V,K+V=EK+V=E,K+E=KLK+E=KL
\cdots⋯
E+E=KVE+E=KV
根据这些规则可推导出:L=0L=0,K=1K=1,V=2V=2,E=3E=3。
同时可以确定该表表示的是 44 进制加法。
输入格式
第一行一个整数 nn(3\le n\le93≤n≤9)表示行数。
以下 nn 行,每行包括 nn 个字符串,每个字符串间用空格隔开。)
若记 s_{i,j}s
i,j
表示第 ii 行第 jj 个字符串,数据保证 s_{1,1}=\texttt +s
1,1
=+,s_{i,1}=s_{1,i}s
i,1
=s
1,i
,|s_{i,1}|=1∣s
i,1
∣=1,s_{i,1}\ne s_{j,1}s
i,1
=s
j,1
(i\ne ji
=j)。
保证至多有一组解。
输出格式
第一行输出各个字母表示什么数,格式如:L=0 K=1 \cdots⋯ 按给出的字母顺序排序。不同字母必须代表不同数字。
第二行输出加法运算是几进制的。
若不可能组成加法表,则应输出 ERROR!。
输入输出样例
输入 #1复制
5
* L K V E
L L K V E
K K V E KL
V V E KL KK
E E KL KK KV
输出 #1复制
L=0 K=1 V=2 E=34
说明/提示
NOIP1998 提高组 第三题
4.题目背景
NOIP2000 提高组 T2
题目描述
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:
设有一个长度为 NN 的数字串,要求选手使用 KK 个乘号将它分成 K+1K+1 个部分,找出一种分法,使得这 K+1K+1 个部分的乘积能够为最大。
同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:
有一个数字串:312312,当 N=3,K=1N=3,K=1 时会有以下两种分法:
3 \times 12=363×12=36
31 \times 2=6231×2=62
这时,符合题目要求的结果是:31 \times 2 = 6231×2=62。
现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。
输入格式
程序的输入共有两行:
第一行共有 22 个自然数 N,KN,K。
第二行是一个长度为 NN 的数字串。
输出格式
结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。
输入输出样例
输入 #1复制
4 2
1231
输出 #1复制
62
说明/提示
数据范围与约定
对于 60%60% 的测试数据满足 6≤N≤206≤N≤20。
对于所有测试数据,6≤N≤40,1≤K≤66≤N≤40,1≤K≤6。