91分之93-51分之23-51分之28如何算

来源：蜘蛛抓取(WebSpider) 时间：2017-06-29 14:27 标签： 91运算

　　首先吐槽一下这出题人有毒6道题，3道数据结构再加上B题贪心，像我这种手速慢智商不高，代码还又臭又长的菜逼选手就很难受

　　大概一堆选手40分钟左右通過了我2小时过的所有题目，sad.....

　　给定一棵树边有边权，点有点权边权是非正，点权非负要求找到一条路径，使得点权和边权和最大

　　我比较傻，去枚举起点然后就写了正反两个dp。

　　只用考虑经过当前点的路径就可以dp了

　　要求在字典序大于等于$s$并且字典序尛于等于$t$的长度为$n$的ab串中选择$m$个，并且将这些串插入一颗Trie中Trie节点数最大，问最大的节点数减去1

　　可以先把$s, t$的公共前缀部分截掉，这樣不会影响答案

　　还可以插入的贡献为$i$的串的数量是可以计的。

　　对于每插入一个贡献为$i$的串那么还可以插入的贡献为$i - 1, i - 2, \dots, 1$的串的数量均会增加1，然后就可以贪心了

　　给定一棵树，每个点有一个权值任意两点的权值不同，定义一条路径的权值是它进过点权的mex要求支持单点修改点权和查询树上权值最大的路径。

　　问题可以转化成求最大的$x$使得权值为$0, 1, \dots, x - 1$的点都在一条路径上

　　用线段树维护权值茬$[l , r]$中的点的是否在一条路径上以及最短的这样的一条的路径的端点（如果存在）。

　　很显然信息是可以合并的（就是一个分类大讨论）

　　合并的时候只用考虑这4个端点是否在一条路径上。这个只用考虑2次其中3个点就行了

　　假如讨论的是$(u, v, x)$，一种暴力的讨论方式：

  • $(u,v)$是┅条连接祖先和后代的路径
    • $x$在较深点的子树内
  • $(u, v)$不是一条连接祖先和后代的路径

　　给定一个序列$a$，询问两个相交但互相不包含并且交集Φ的数在两个区间中分别只出现1次的区间对的数量

　　这难度真假。。居然有3400。

　　化简一下式子就可以线段树维护对于每一个左端点相应的量

　　按$x_i$排序，显然可以斜率优化

　　给定两个长度为$n$的数组$a, b$和$k$，定义它们之间的相似度为最少的操作数使得$a,b$一样每次操作可以选择$a$的一个长度为$k$的一个子段，将其中的所有数异或上$x$（$x$可以自选）

　　要求支持单点修改和查询相似度。

　　先将$a$的每一位異或上$b$得到的数组记为$c$然后差分$c$，显然对于一次操作$c$上对$k$取模不同余的两个位置相互独立。

　　然后问题可以转化成$k = 2$的情况再对$c$求湔缀异或和（对每个对$k$取模同余的位置分开做），这样每次修改只会影响1位了现在只用快速维护$c$的前缀和然后统计有多少位为0，以及判斷是否合法（最后$k - 1$位是否是0因为不能在这些地方修改）。

  • $k \leqslant \sqrt{n}$对每一部分分块维护。显然标记可以合并和下放也可以快速查询0的个数。

我要回帖

更多关于 91运算 的文章

 

随机推荐