竞赛讨论区 > 【题解】牛客网NOIP赛前集训营-普及组(第二场)
头像
Key酱不是喵
发布于 2019-04-19 14:35
+ 关注

【题解】牛客网NOIP赛前集训营-普及组(第二场)

A你好 a+b

输入2个整数a和b
保证输入的a和b在long long范围之内,即满足 -9223372036854775808 <= a, b <= 9223372036854775807
计算a+b的值,即这两个数字的和。
如果a+b在long long范围之内,即满足 -9223372036854775808 <= a + b <= 9223372036854775807
那么输出一行一个整数表示a+b的结果。
如果a+b不在long long范围之内,即越界了,那么输出"hello, %lld\n",包含引号。

做法
编程技巧题目
首先如果A和B一个是负数,一个是非负数,肯定不会越界。 如果都是非负数,我们需要判断 A + B <= C 考虑到A+B会越界,可以改写为A <= C - B
同样的,如果都是负数,我们需要判断 A + B >= C 考虑到A+B会越界,可以改写为A >= C - B
其他的方法,比如long double,高精度也是可以的。 double应该是不行的。

输出那个奇怪的字符串,主要就是考察转义
输出反斜杠是\\ 
输出双引号是\” 
输出百分号是%%
B最后一次
题目大意
牛牛最近学习了质数的概念。
质数指在大于1的自然数中,除了1和它本身以外不再有其他因数。
输入一个n,输出小于等于n最大的质数。

解法
主要就是一个暴力判断质数
对于一个合数n来说,一定有一个质因数<=sqrt(n)
所以可以O(sqrt(n))的时间判断一个数字n是不是质数
然后如果n不是,执行n -= 1,继续判断就可以了。

C选择颜色
题面
n个人排成一个环形,每个人要从c种颜色中选择一个。
牛牛希望相邻的人选择的颜色是不同的
问有多少种方案。
输出方案数对10007取模的结果。
人是有顺序的,环旋转同构算不同的方案。

解法
print (pow(c - 1, n, p) + (c - 1) * pow(-1, n, p)) % p
结论可以找规律得到,证明就是DP+化简。
假设第一个人颜色固定,
设f[i]为前i个人颜色都决定好了,第i个人和第1个人颜色相同,的方案数 设g[i]为前i个人颜色都决定好了,第i个人和第1个人颜色不同,的方案数
(注意g[i]实际上是c-1个状态,但是因为这c-1个状态数值一样,只需要记一个)
转移方程
* f[i] = (c - 1) * g[i - 1] * g[i] = f[i - 1] + (c - 2) * g[i - 1]
化简之后得到 g[i] = (c - 1) * g[i - 2] + (c - 2).* g[i - 1] 解递推,可以得到上面的结论。

D合法括号序列
题面
键盘上有左括号(,右括号),和退格键-,共三个键。
牛牛希望按键n次,使得输入的字符串恰好一个合法的括号序列。
每按一次左括号(,字符串末尾追加一个左括号( 每按一次右括号),字符串末尾追加一个右括号) 每按一次退格键-,会删掉字符串的最后一个字符,
特别地,如果字符串为空,牛牛也可以按退格,但是什么都不会发生。
输出方案数对p取模,注意p可能不是质数。
注:只要按键方法不同,就是不同的方案,即使得到的序列一样。

做法
这个题可以分为两部分,
• 一部分是讨论最后合法括号序列的长度2k。 • 二部分是有多少种输入他的方式。
对于第一部分,是基本的卡特兰数。
对于第二部分,注意到:
输入一个长度为2k的字符串,无论序列是什么,方案数是一定的。
也就是说方案数只和想输入的字符串长度有关,和具体是什么没关系
设f[i][j]为按键i次,输入了长度为j的序列。
f[i][j] = f[i - 1][max(j - 1, 0)] + 2 * f[i - 1][j + 1]
最后枚举k,统计答案即可。

std
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40354342&scrollToDetail=1







全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐