牛客网NOIP赛前集训营-普及组（第二场）

时间：2022-09-20 05:34:43

T1

牛牛刚学习了输入输出，他遇到了一道这样的题目。
输入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，
1.a、b异号或者一个是0，那么输出a+b即可。
反之，用高精判断。
高精比较麻烦的。
如果上限是C，A+B<=C等价于A<=C-B即可。
下限同理可以处理。
甚至有人利用溢出原理。
a、b同号，如果a+b不是同号，那么就溢出了。
 
然后，输出"hello, %lld\n"怎么办？
考察转义。
输出"，就输出\"
输出%，就输出%%
输出\，就输出\\
所以，
printf("\"hello,%%lld\\n\"");
 

T2T3略

T4：
合法括号序列

键盘上有左括号(，右括号)，和退格键-，共三个键。
牛牛希望按键n次，使得输入的字符串恰好一个合法的括号序列。
每按一次左括号(，字符串末尾追加一个左括号(
每按一次右括号)，字符串末尾追加一个右括号)
每按一次退格键-，会删掉字符串的最后一个字符，
特别的，如果字符串为空，牛牛也可以按退格，但是什么都不会发生。

输出方案数对p取模，注意p可能不是质数。
注：只要按键方法不同，就是不同的方案，即使得到的序列一样。
对于所有数据： 2 <= n <= 1000, 2 <= p <= 10000
30分： n <= 40
70分： n <= 100
 
题解：
可以发现（我想不到），

方案数和具体括号序列无关，只和最终括号序列长度有关。

因为就这么多剩下的，那么管他是什么字符呢？

所以问题分成两个部分。

枚举括号序列的长度2k，

1.计算出来对于每一个长度2k，合法的括号序有多少个。

2.对于长度为2k的序列，方案数有多少。

乘法原理再加法原理即可。

对于1，是一个卡特兰数。

可以看：卡特兰数Catalan——定义、公式、模型总结

具体证明，可以直接转化成火车出栈顺序，或者走到（i，i）方案数。

预处理组合数。递推或者直接C(2n,n)-C(2n,n-1)

对于2，设f[i][j]表示，前i次操作后，序列长度为j的方案数。

f[i][j]=f[i-1][max(0,j-1)]+2*f[i-1][j+1]

为什么删除的操作转移有一个2

因为我们的f[i][j]其实也是一个可以变化成任意一个的合法序列，所以每个位置的填法要么是),或(，唯一确定的。

但是把这个位置删了，那么就可以“反悔”地把上一位随便填。

随机推荐

  1. 用AXIS2发布WebService的方法

    Axis2+tomcat6.0 实现webService 服务端发布与客户端的调用. 第一步:首先要下载开发所需要的jar包 下载:axis2-1.6.1-war.zip http://www.apa ...

  2. poj 3613 经过k条边最短路 floyd&plus;矩阵快速幂

    http://poj.org/problem?id=3613 s->t上经过k条边的最短路 先把1000范围的点离散化到200中,然后使用最短路可以使用floyd,由于求的是经过k条路的最短路, ...

  3. Mysql中的视图

    什么是视图 通俗的讲,视图就是一条SELECT语句执行后返回的结果集.所以我们在创建视图的时候,主要的工作就落在创建这条SQL查询语句上. 视图的特性 视图是对若干张基本表的引用,一张虚表,查询语句执 ...

  4. linux云计算集群架构学习笔记&colon;workstation 12&period;0 按装Red Hat Enterprise Linux 7&lpar;64位&rpar;

    安装RHEL7.2 步骤: 1.安装虚拟机,按以下截图安装即可  步骤2: Ret hat 7.2 操作系统安装 rhel7因为许可报错解决

  5. laravel框架中所用到的依赖注入

    用Laravel开发前前后后有2个月左右了,之前一直写Java,就像找到Java和PHP之前的共同点,用Java的某些原理去理解PHP会发现还是有很多共通之处的.Java的依赖注入已经是一个很常见的概 ...

  6. （转）KMP算法实现。超级赞！见过的最容易理解的

    网上有很多讲解KMP算法的博客,我就不浪费时间再写一份了.直接推荐一个当初我入门时看的博客吧:http://www.cnblogs.com/yjiyjige/p/3263858.html这位同学用详细 ...

  7. Redis的并发竞争问题的解决方案总结

    什么是Redis的并发竞争问题 Redis的并发竞争问题,主要是发生在并发写竞争. 考虑到redis没有像db中的sql语句,update val = val + 10 where ...,无法使用这 ...

  8. Activiti开发案例之activiti-app工作流导出图片

    前言 自从 Activiti 和 JBPM4 分家以后,Activiti 目前已经发展到了版本7,本着稳定性原则我们最终选择了6,之前还有一个版本5. 问题 在开发使用的过程中发现 Activiti ...

  9. CSS border-radius边框圆角

    在CSS3中提供了对边框进行圆角设定的支持,可对边框1~4个角进行圆角样式设置. 目录 1. 介绍 2. value值的格式和类型 3. border-radius 1~4个参数说明 4. 在线示例 ...

  10. python 目录切换

    #- * -coding: utf - - * - import os, sys path = "c:\\" # 查看当前工作目录 retval = os.getcwd() pri ...

相关文章