构造一个环使其成为回文串的切割数最大。 当超过两种颜色的数量为奇数时无法构造出回文串，直接输出。 根据切割的特点，容易想到构造回文串形式的单位循环节，则答案为循环节的数量，其中循环节的最大数量为各颜色数量的 gcd。 这里需要分类讨论一下（记各颜色数量的GCD为 d）：（1）循环节中存在奇数数量颜色，循环节个数等于d，结果不可能再大于这个数。（2）循环节中不存在奇数数量颜色，循环节个数等于d/2，但是还可以从循环节的中间切割，例如 baab baab 切割后为 abba abba，答案乘以2，仍为d。 代码如下： #include<bits/stdc++.h> using name...

求q次询问下最短异或和为0子区间长度。 根据异或性质容易将条件转化为前缀和 sum[l-1]=sum[r] 的形式，用数组a记录一下前缀异或和最近出现的位置，则问题可以转化为维护单点贡献的形式。 考虑从1移动右端点，则随着右端的更新，将以此端点结尾的对应区间长度值赋给下标为左端点的求值数组，这样就可以使对区间的访问变为对左端点贡献的访问，询问答案即为对求值数组中区间 [l,r] 中最小值的查询，用线段树维护即可。 根据更新顺序，只能采用按r值从小到大的离线询问。 代码如下： #include<bits/stdc++.h> #define ls p<<1,l,mid #d...

题目链接 题意：有一n行m列的矩阵，每次从这n行中取出行首或行尾的数，一个数的权值为 val*2^i，该次得分为这n行取值总和，共取m次，求最大权值和。 题解： 虽然数据较大，但用 int128 完全可以存下。由于取行首或行尾操作容易用转移方程描述，考虑动态规划。设 pw[i]为对应2的幂，a[i][j]表示i行j列数值， b[i][l][r] 表示第i行左边取了l个数，右边取了r个数的最大得分。则状态转移方程为 b[i][l][r] = max( b[i][l-1][r]+a[i][l] * pw[l+r]，b[i][l][r-1]+a[i][m-r+1] * pw[l+r] )，对应...

题目链接 题意：在m秒中有n只蚯蚓不断被分割，即每秒中长度最长的一只会被分割成两段，其余蚯蚓长度会增加q。求出每秒所分割的蚯蚓长度和最后各蚯蚓长度，按照格式要求输出。 题解： 暴力维护肯定会T，可以按照相对的思想，只对分割的蚯蚓操作，即分割蚯蚓长度少增加了q，大小关系不变，真正的长度等于队列元素加上“总位移”，“总位移”用一个变量记录就好。由于m为7e6且纯用优先队列的话常数较大，考虑优化程序。由于是按照长度从大到小分割，所分的两段可以分为两类且满足单调性，用两个队列O(m)就可以维护。这样我们用三个队列表示未分割、所分割两类的蚯蚓长度，每次只需比较三个队首大小，就可求出最长蚯蚓。总体...

题目链接 题意：初始有一零结点，权值为0，根据相应操作维护这棵动态有根树。操作 1：输入格式 1 i ，表示使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1。操作 2：输入格式 2 i a ，表示使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。操作 3：输入格式 3 i，输出节点i权值。 题解：因为树的结点是动态变化的，无法在线维护，先求出总连接情况，然后考虑用特殊方法维护结点值。对于固定连接情况的树，其权值情况可通过树链剖分维护出来。通过结点加入的先后顺序关系，容易想到在一结点诞生时记录其权值，待询问时求出此时权值再减去诞生时权值即为该结点的真...

这题内存炸了？好多原先可以AC的代码都被卡了。