2020牛客国庆集训派对day7 部分题解

前言

• 从23号26号，终归还是找了时间来补了几道题，确实还是太菜了。只勉强A了6道，只要涉及到一些数论或是高级数据结构or 算法，基本上就没思路了。
  
  
  但总归还是得总结一下，也希望能对补题的同学尽绵薄之力

A Laminar Family

• 题意：有n个点组成的树，有n-1条边。给出m条树上的路径，判断他们是否相互包含。如果任意两条路径要么不相交，要么包含，则输出“yes”，反之，输出“no”
• 简要思考：
  1. 先明确是什么意思
     
     这是两条的情况，那么多条边怎么去判断呢？
     
     如果要去判断这几条边是否相交，只需要判断他所在的位置是否只有一种颜色的边(由图)，这就是为什么许多题解称之为区间染色类的原因。
  2. 解法：要判断是否只有一种颜色，那我们就将边的长度从大到小排序，每判断结束一次，就将那段区间标记为对应的颜色(序号)。如果某一条边对应的位置只有一种颜色，那么这一段区间的最大值和最小值是相等的。于是根据这个码出一个树剖+线段树
• 代码

B Abbreviation

• 题意：输入若干行字符串，将其中可缩写单词的大写字母输出并在其后输出空格加括号表示原单词组。一个可缩写单词的定义是——首字母是大写，其余字母是小写，如Ab,Acc(说明长度得>=2)。一个可缩写的单词组是至少包含两个可缩写单词且他们在原文本中的位置只相隔一个空格(被坑了好久)。
• 简要思考：
  1. 一个大模拟
  2. 梳理一下过程：输入此字符串，首先判断出每一个单词的开始与结束位置并判断此单词是否可被缩写。(配合代码理解，这道题就不贴代码了)
     
     之后从单词开头开始找
     如果它是一个可缩写单词，从他的结束位置+1开始判断，如果和下一个单词间隔了两个非字母符号，肯定不行，如果有逗号或是句号，肯定不行，如果超过单词长度了，肯定不行。如果找到合法的，记录一个cnt表示已经找到的合法可缩写单词的数目。如果找完之后只有一个，那只能原样输出，反之，提取出每一个单词的开头，然后输出
     如果不是可缩写单词，那就直接输出
     
     个人觉得思路较为清晰，也不知读者如何想(也许很少有人回来读这种比赛的题解吧)。

C Expect to Wait

• 题意：这是一个自行车调动问题。自行车的变动次数为n，在某一个时刻 t [ i ] 可能增加 peo [ i ]辆，也有可能有peo [ i ] 个人需要自行车。有m个询问，每次输入一个x表示初始自行车数量，求每一个人的等待时间总和
• 简要思考：
  1. QwQ，蛇皮题，居然给我卡了一个下午。
  2. 暴力就不说了，我们来思考一下如何求出总的等待时间。先画个图
     
     首先一条白线，表示每一个时刻的自行车变动情况
     
     也就是这种情况。然后当时我就恍然大悟——所谓的等待时间不就是对每一个人自行车数量为负的区间长度总和吗?
     
     即我要求染黑的这块区域的面积。我可以预处理出一个s数组，以自行车数量的从小到大排序，对于这m个询问来说，未付的情况即是 x + s [ i ] < 0 的情况。一个lower_bound查询+前缀和处理就能得到答案。而网上大多题解采用离线处理。
• 代码

D Foreign Postcards

• 题意：(先吐槽一下，垃圾百度翻译QwQ)有n张卡摆在桌子上，每次随机取出K张，如果他的最上方一张是反放的，把这k张全部翻一个面，然后对剩下的牌进行同样的操作。求最后面朝下的牌张数的期望
• 简要思考：
  1. 这是一个概率期望DP，那么就要把看似无限次数的转移换一种以有限步数求出来。
  2. 对于一张牌来说，他只有翻或不翻的两种情况。并且将其作为某k张的第一张的概率是能求出来的。如果他是"W",那么如果要将其翻转，有(1-p[i])的概率和第 i - 1 张一起翻，如果不翻转，他肯定不能作为第一张(因为第一张必须是正面朝上)，那么只能和第 i - 1 张都不翻。而如果他是"C",要翻转他，只能和第 i - 1 张一起翻，不翻转就直接加上他作为第一张的概率即可
  • 代码

J Adjustment Office

• 题意：(读者：怎么就变J了？ 我：这是一个悲伤的故事)有一个n*n的方格，每一个方格的数是其横坐标加上纵坐标，现在有m个询问
  R x:询问第x行的总和，并将这一行的所有数归0
  C x:询问第x列的总和，并将这一列的所有数归0

• 简要思考：

  1. 可以分别记录一下失去了的行(x)，列的总和(y)与个数，就能求得他们对某一行的影响

• 代码

K Binary vs Decimal

• 题意：(几经波折啊这道题，WA，MLE，md(美德))如果一个数的十进制是其二进制表示下的数的后缀，称其为bindecimal，求出第n小的bindecimal
• 简要分析
  1. 先说暴力，先直接在第列里加入一个1，然后每一操作的时候，对原数*10，加上0，或是1，再将其放入队列,每次判断一下是否合法即可，然后你会得到20分的好成绩
  2. 于是我尝试将其改为高精，很成功，但是MLE了，因为搜索量太大了
     
  3. 当我去网上搜题解时，出现最多的一句话是——一个合法数字的后缀也是合法的。但没有一个给出了解释。当我打开计算器，按出10,100,1000...时，我发现了神奇的规律：
     
     也就是说，如果一个数合法(假设1100)，除去他的最高位(100)，此时，他的后几位二进制位是不会变动的。(手模一下)那么，改变策略，由原来的枚举数字变成枚举后缀，逐一判断，得到答案
• 代码

后话

• 我发现我还需要加强的地方还有很多。而且，当今天的四川分数线出来时，我发现能进入NOIP进行考试的人200左右，竞争之大。距离NOIP已不到2个月了，我希望能在最后这一刻再冲一冲。

完~