2018HPU暑期集训第二次积分赛_场外同步赛

  • 2018-07-30
  • 41
  • 0

又是斐波那契数列??(HPUOJ 1471)

题目:

大家都知道斐波那契数列吧?斐波那契数列的定义是这样的: f_0 = 0; f_1 = 1; f_i = f_{i-1} + f_{i-2} 现在给你一个数x,聪明的你一定知道这是斐波那契数列中的第几项。 (数据保证x一定有对应的项y,且 2 <= y < 1e4)

Input:

第一行一个整数T,表示测试组数。
之后的T行,每行一个数x

Output:

对于每个测试数据,输出一行表示数x是第几项

Sample Input:

2
2
5

Sample Output:

3
5

题目链接

递推算出1e4之内的所有斐波那契数列,建立map映射映射到下标即可。

我以为最大数据会很大还写了一个string大数加法斐波那契数列,结果TLE…

太蠢了……这道题目直接用unsigned long long就可以。

AC代码:

Simplest (HPUOJ 1473)

题目:

给你一段由数字0 – 9组成的字符串,请你输出它的最简自然数形式

Input:

第一行一个T,表示T组测试数据.(1 ≤ T ≤ 100)
每一组数据占一行,每一行一串字符 S. (1 ≤ strlen(S) ≤ 100000)

Output:

输出字符串对应的最简自然数形式

Sample Input:

2
2018722
02018722

Sample Output:

2018722
2018722

题目链接

字符串读取,把数字前面的0去掉即可,注意特判0。

AC代码:

zz’s math problem Ⅰ (HPUOJ 1474)

题目:

有些人心如花木,皆向阳而生
|《剑来》
zz很喜欢数学,但是他又是一个数学渣,我们称这种生物叫做学渣,
zz又碰到了一个数学小问题,定义一个函数P (x)
例如:P (123) = 1! ∗ 2! ∗ 3! 现在需要找到的就是最大的大于等于x大的数z的函数值和x相等,
即P (z) = P (x) 当然z这个数不能包含1或者0
还请输出最大的符合要求数z(不一定比x大)

Input:

第1行输入T (1 ≤ T ≤ 20)组数据
第2行输入n(1 ≤ n ≤ 100),表示x的数字个数
第3行输入正整数 x

Output:

输出最大的z(数据保证x内含大于1的数,所以z必定有解)

Sample Input:

2
4
1234
3
555

Sample Output:

33222
555

题目链接

对每一个数进行分解,分解为非0、1数字的阶乘相乘,把所有分解的数字按照降序输出即可。

AC代码:

zz’s math problem Ⅱ (HPUOJ 1475)

题目:

zz作为一个数学盲也认为这个数学题真的很简单, 学弟学妹们终于可以顺利签到了qwq
给出N个正整数a_1,a_2,…,a_N
我们寻找一个这个表达式的最大的值 f(m)=(m mod a1)+(m mod a2)+…+(m mod aN)

mod的意思即为A/B的余数

Input:

1行输入T(1≤T≤20)组数据
2行输入N(1≤N≤1e3)
3行输入n个数字a_i(1≤ai≤1e5),

Output:

输出f的最大值

Sample Input:

1
3
3 4 6

Sample Output:

10

题目链接

一定有一个数num使所有num\%a_i=a_i-1成立。

AC代码:

Operation on sequence (HPUOJ 1478)

题目:

井底之蛙,偶见圆月,便欣然忘忧。

\hspace{5cm}—《剑来》

为什么总是要为难学弟学妹呢,zz并不想这样,zz决定把出一道简单的题来福利学弟学妹们。

一组下标从1开始的数组s,进行q次操作:

考虑两种操作:

1 r,将子序列a[1] 到 a[r] 从小到大排序

2 r,将子序列a[1] 到 a[r] 从大到小排序

Input:

第一行输入T组数据 T(1≤T≤10)

第一行输入两个数字 n,q(1≤n,q≤1e4)

第二行包含n个整数 a_i(−1e9≤a_i≤1e9) — 初始序列

然后q行表示m个操作. 第i行包含两个整数 op(1≤op≤2), r(1≤r≤n)

Sample Input:

2
3 1
1 2 3
2 2
4 2
1 2 4 3
2 3
1 2

Sample Output:

2 1 3
2 4 1 3

题目链接

从后往前查找,只进行范围比之前大的操作。

AC代码:

Operation on sequence (HPUOJ 1477)

题目:

真·签到题
输入一个表达式A op B op操作为′+′,′−′,′∗′ ,A,B为整数

Input:

第一行输入T 组数据T(1≤T≤1e2)
第二行输入A op B (−1e9≤A,B≤1e9) — 初始序列

Output:

输出表达式结果并换行即可

Sample Input:

1
1 + 1

Sample Output:

2

题目链接

emm……

AC代码:

又是划分问题 (HPUOJ 1480)

题目:

给你一个正整数n,将其划分,要求划分成的数必须是2的幂,有多少种划分方法??
结果可能很大,我们输出对1e9+7取模的结果

Input:

一个正整数n,代表要划分的数;
1<=n<=1e7

Output:

输出可划分的方法数

Sample Input:

15
67

Sample Output:

26
2030

Hint:

当n=6时,我们可以将其划分为
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
1 1 4
2 4
这6种划分方法

题目链接

和这道题一样

POJ 2229 HDU 2709 Sumsets

AC代码:

台阶问题 (HPUOJ 1479)

题目:

有 N 级的台阶,你一开始在底部,每次可以向上迈最多 K 级台阶(最少 1 级),问到达第 N 级台阶有多少种不同方式。

Input:

多组输入,两个正整数N(N ≤ 1000),K(K ≤ 100)。

Output:

一个正整数,为不同方式数,由于答案可能很大,你需要输出 ans mod 100003 后的结果。

Sample Input:

5 2

Sample Output:

8

题目链接

每次走n阶楼梯可以选择先走一格,再走剩下n-1格即为f[n-1],或者先走2格,再走剩下n-2格即为f[n-2],以此类推,把每种走法都加起来即为结果。

AC代码:

括号括号 (HPUOJ 1476)

题目:

小明今年上大学,在大学里发现有很多同学都女朋友,两人整天都在一起腻歪,小明看到后感觉很孤单,现在,给你一行括号序列,你来判断一下其中的括号是否配对。

Input:

多组输入,每一组第一行输入一个数T(0<<N≤≤100),表示有T组测试数据。后面的T行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有”[“, “]”, “(“, “)” 四种字符

Output:

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No。

Sample Input:

3
[(])
(])
([])

Sample Output:

No
No
Yes

题目链接

栈的入门题目括号匹配。

AC代码:

评论

还没有任何评论,你来说两句吧