旅行 果然树剖的题代码量都不小，不过还是学了一波动态开点，妙呀！ 题意：给定一棵带权带颜色的树，两种操作+两种询问： 操作1：更改某个点的颜***r> 操作2：更改某个点的权值 询问1：询问     x   ,   y    x,y   x,y两点间与     x    x   x同色的点的权值和 询问2：询问     x   ,   y    x,y   x,y两点间与     x    x   x同色的点的最大权值 思路：  树上操作先来个树剖肯定是不亏的！ 对于     1   e   5    1e5   1e5的颜色，每种颜色开一棵线段树，但由于空间肯定开不小，因此考虑动态开点...

Nikitosh和异或 因为下面这段代码卡了接近一小时！ int s=p&1<<i; // wrong int s=p>>i&1; // correct  题意：最大化两个异或对之和（还是看下面的题面吧） 思路：  预处理前缀最大异或对，然后从后往前求后缀最大异或对即可 当然整个过程都利用了     01   t   r   i   e    01trie   01trie性质，即在已经构建的     01   t   r   i   e    01trie   01trie上贪心地选择路径  题面描述 #include "bits/stdc+...

最长异或路径 板子题，但是如果把边权改成了点权的话好像就不好做了，暂时还没想好 题意：给定一棵带边权的树，求最大的异或路径。 思路：  令每个节点的权值为从根到当前节点的路径上边权异或值，则此问题就被转化为普通的最大异或对了 最大异或对就没啥说的了，按顺序（随便什么顺序）把每个点加入     01   t   r   i   e    01trie   01trie中，然后在每加入一个点前先判定当前点能与     01   t   r   i   e    01trie   01trie中异或的最大值（贪心得搞一下就行了），把所有求出的最大值再取一个最大值就是答案了  题面描述 #includ...

最大异或和 题意：转化后的题意是有一种操作+一种询问： 1. 操作：在序列末尾插入一个数 2. 询问：给定     l   ,   r   ,   x    l,r,x   l,r,x，求区间     l   ,   r    l,r   l,r中与     x    x   x异或能得到的最大异或值（转化后的题意） 思路：题意都被转化成这样了。。。应该就没啥难度了  用类似主席树的方式构建可持久化     01   t   r   i   e    01trie   01trie 然后还是简单的贪心跑     01   t   r   i   e    01trie   01trie 最后小...

Rotate Columns 题意：给定一个矩阵，可以对矩阵的任意列进行上下滑动（或称旋转），使最大化每一行的最大值 之和。      E   a   s   y    Easy   Easy      v   e   r   s   i   o   n    version   version：     n   ≤   4    n≤4   n≤4，     m   ≤   100    m≤100   m≤100      H   a   r   d    Hard   Hard      v   e   r   s   i   o   n    version   version：   ...

Into Blocks（不带修改的     E   a   s   y    Easy   Easy版本） 题意：给定一个序列，通过改变其中的数字使所有相同的数字在数组中都是相邻的，改变数字的方式为：将数组中某个数字全部修改为另外一个数字。求最少需要改变的元素 思路：  由于最终状态肯定是“一块一块”的，每一块中都是一样的数字 因此考虑预处理每种数字最靠右的位置，然后从左到右扫描整个序列 扫描的过程中以出现的数字的最靠右的位置为界限，并且每遇到一个新数字就更新界限 而当扫描到界限位置出，表明改变当前区域内的数字不会影响到后面的区域，因此找出当前区域内出现次数最多的数字，并且把其他数字都改为当前...

Counting Sequences I 拿着OEIS上的一个类似的序列（当时以为是相同的）怼了半天。。。欲哭无泪 题意：问有多少长度为     n    n   n的正整数序列满足它们的和等于它们的积（每一位置对应相同认为是同一序列） 思路：没啥思路，暴力即可  首先，序列中不等于     1    1   1的值不能太多，比如      2   12     2^{12}   212等于4096，显然乘积增长太快了！因此大多数序列都会被剪枝掉，保证了时间复杂度很低 枚举的过程按从大到小的方式进行枚举，在每个位置都检验一遍是否后面所有数字都取     1    1   1是刚好合理的 若合理...

Rhyme scheme 赛后：原来就这么个简单题！ 题意：给定     n    n   n和     k    k   k，求大小为     n    n   n的集合的第     k    k   k小字典序划分（输出格式见下方题面） 思路：  令大小为     i    i   i的集合在选择第     j    j   j个位置时左边已经有     k    k   k个集合为     d   p   [   i   ]   [   j   ]   [   k   ]    dp[i][j][k]   dp[i][j][k] 则     d   p    dp   dp的转移方程为：...

超级钢琴 我能说这是主席树板子题嘛？ 题意：给定一个序列，求长度在     L    L   L与     R    R   R内的前     K    K   K大子串和。 思路：  既然有子串，肯定要先搞个前缀和，离散化之类的 然后我们建好主席树 而主要的思路在于贪心，我们可以枚举子串的左端点，然后在其合法的右端点中通过主席树找到最大的右端点（子串满足前缀和关系，每个右端点都会减去这个相同的左端点的前一个值） 把枚举得到的所有最大子串都放进优先队列中（维护左端点+最大子串），每次取出队头，就在答案中加上这个值，然后再以当前左端点利用主席树求区间第     j   +   1    j+1 ...

MET-Meteors 我决定以后二分的     m    m   m都写成     m   i   d    mid   mid！ 题意：郁闷死了。。。写不动题意了！ 思路：  首先正常的读入以及连边，注意     l   >   r    l>r   l>r时将     r    r   r加上     m    m   m，即用两个连在一起的数组表示循环 然后，怎么说呢？反正学会整体二分以后就感觉是板子题。。。 考虑当前     [   l   ,   r   ]    [l,r]   [l,r]时间段的左半部分的流星雨全部落下后，将     [   x   ,   y...

火星商店 从开这题开始，到真正A掉它竟然花了两周！主要是这题前置知识没有掌握，因此花了一周搞定了主席树专题，再花了些时间搞定了可持久化     t   r   i   e    trie   trie树，再就是期间有大大小小的比赛+补题。。。反正就是两周，哈哈哈！同时，刚刚A掉它之前还发现洛谷账号变成红名了，舒服！ 题意：有一排商店，每个商店都有许多商品。其中每个商店都有一种永久商品（随时都可以购买）。其次，每一天都会有一种操作，第     s    s   s个商店进了属性为     v    v   v的货物。每一天都可能有不止一个的询问，表示最近     d    d   d天内    ...

Megumi With String 这题我T了40次左右。。。拿着别人的AC代码双向修改，我的一直T，别人的一直A。。。甚至感觉除了变量名不一样，其他的都完全一样了，还是T 噩梦经历 最后发现是初始化函数写跪了 题意：给定一个已知串     S    S   S，再给出另外一个串（随机）的长度，求原串在每次尾部增加节点后另外一个串的价值（价值定义见题面吧） 思路：  由于原串的操作是尾部增添字符，显然与后缀自动机一致，因此考虑建立后缀自动机 由于一个长度为     i    i   i的     S    S   S的子串，在另外一个串中出现的期望次数为：       n   +   1  ...

Can You Solve the Harder Problem? 这题简直妙呀！可惜训练赛的时候     3   h    3h   3h我们就以为开不了题了。。。因此     3   h    3h   3h后     5    5   5题离场。。。吃完饭回来看了这题题解，看到了     S   u   f   f   i   x    Suffix   Suffix      s   t   r   u   c   t   u   r   e   s    structures   structures后秒懂！而且代码也简单！ 这题主要利用了后缀自动机的每个节点可以表达出原串本质不同的...

秩序魔咒 题意： 求两个串最长相同的回文子串的长度，并求出这种长度的子串有多少个 思路：  既然有回文串，自然会想到回文自动机或     m   a   n   a   c   h   e   r    manacher   manacher，而用回文自动机会变得非常板子！ 最长的很容易处理，而要在两个串中都出现，我们可以像后缀自动机那样将两个串连在一起，中间用两个不同且不会出现的字符连接（由于回文自动机内部要调用这个字符串，因此必须真正的将字符串进行连接）。 然后对前后的回文串打上不同的标记，最后统计在两个字符串中都出现过的回文子串即可。  题面描述 #include "bits/...