第九届蓝桥杯 试题D：第几个幸运数

试题 D：第几个幸运数

本题总分: 10分

[问题描述]

到 x 星球旅行的游客都被发给一个整数，作为游客编号。

x 星的国王有个怪癖，他只喜欢数字 3,5 和 7。

国王规定，游客的编号如果只含有因子：3,5,7 就可以获得一份奖品。 前 10 个幸运数字是： 3 5 7 9 15 21 25 27 35 45 ，因而第 11 个幸运数字是：49

小明领到了一个幸运数字 59084709587505。

去领奖的时候，人家要求他准确说出这是第几个幸运数字，否则领不到奖品。

请你帮小明计算一下，59084709587505 是第几个幸运数字。

消息的传递

我们的郭嘉大大在曹操这过得进遙自在, 但是有一天曹操给了他一个任务，在建邮城内有 N 个袁绍的奸细，将他们从 1 到 N 进行 编号, 同时他们之间存在一种传递关系, 即若 C**i,j=1, 则奸细 i 能将消息直接传递给奸细 j。

现在曹操要发布一个假消息, 需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息, 问我们至少要传给几个奸细?

输入格式:

第一行为 N, 第二行至第 N+1 行为 N×N 的矩阵 ( 若第 I 行第 J 列为 1, 则奸细 I 能将消息直接传递给奸细 J, 若第 I 行第 J 列为 0 , 则奸细 I 不能将消息直接传递给奸细 J) 。

输出格式:

只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

输入样例:

1
2
3
4
5
6
7
8
9

8
0 0 1 0 0 0 0 0
1 0 0 1 0 0 0 0
0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0

输出样例:

1

2

数据范围与提示

N≤1000

洛谷P1464 Function

题目描述

对于一个递归函数w(a,b,c)w(a,b,c)

• 如果a \le 0a≤0 or b \le 0b≤0 or c \le 0c≤0就返回值11.
• 如果a>20a>20 or b>20b>20 or c>20c>20就返回w(20,20,20)w(20,20,20)
• 如果a<ba<b并且b<cb<c 就返回w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)
• 其它的情况就返回w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)

这是个简单的递归函数，但实现起来可能会有些问题。当a,b,ca,b,c均为15时，调用的次数将非常的多。你要想个办法才行.

absi2011 : 比如 w(30,-1,0)w(30,−1,0)既满足条件1又满足条件2 这种时候我们就按最上面的条件来算 所以答案为1

输入格式

会有若干行。

并以-1,-1,-1−1,−1,−1结束。

保证输入的数在[-9223372036854775808,9223372036854775807][−9223372036854775808,9223372036854775807]之间，并且是整数。

输出格式

输出若干行，每一行格式：

1

w(a, b, c) = ans

注意空格。

题目描述

棋盘上 AA 点有一个过河卒，需要走到目标 BB 点。卒行走的规则：可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。

棋盘用坐标表示，AA 点 (0,0)(0,0)、BB 点 (n,m)(n,m)，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 AA 点能够到达 BB 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

输入格式

一行四个正整数，分别表示 BB 点坐标和马的坐标。

输出格式

一个整数，表示所有的路径条数。

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 44 科。因此要开始刷习题集，每科都有一个习题集，分别有 s1,s2,s3,s4s1,s2,s3,s4 道题目，完成每道题目需要一些时间，可能不等（A1,A2,…,As1A1,A2,…,A**s1，B1,B2,…,Bs2B1,B2,…,B**s2，C1,C2,…,Cs3C1,C2,…,C**s3，D1,D2,…,Ds4D1,D2,…,D**s4）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 22 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

洛谷 p1249 最大乘积

题目大意

将N分解成若干个互不相同数字之和，求乘积的最大值。

思路

利用 lna + lnb = ln(a + b)，将乘积的最大值转换为和的最大值。题目就可以化解为，从1, 2, 3…n中选出一些数是他们的和最大。

相当于是一个01背包问题和一个高精度乘法。

题目描述

一个正整数一般可以分为几个互不相同的自然数的和，如 3=1+23=1+2，4=1+34=1+3，5＝1+4=2+35＝1+4=2+3，6=1+5＝2+46=1+5＝2+4。

现在你的任务是将指定的正整数 nn 分解成若干个互不相同的自然数的和，且使这些自然数的乘积最大。