ExcaIibur

分类

题解(5)

/ 注册

全部文章（共5篇）

CF613C Necklace（字符串构造）

构造一个环使其成为回文串的切割数最大。当超过两种颜色的数量为奇数时无法构造出回文串，直接输出。根据切割的特点，容易想到构造回文串形式的单位循环节，则答案为循环节的数量，其中循环节的最大数量为各颜色数量的 gcd。这里需要分类讨论一下（记各颜色数量的GCD为 d）：（1）循环节中存在奇数数量颜色...

2020-12-18

1 651

NC50444 老瞎眼 pk 小鲜肉（线段树思维）

求q次询问下最短异或和为0子区间长度。根据异或性质容易将条件转化为前缀和 sum[l-1]=sum[r] 的形式，用数组a记录一下前缀异或和最近出现的位置，则问题可以转化为维护单点贡献的形式。考虑从1移动右端点，则随着右端的更新，将以此端点结尾的对应区间长度值赋给下标为左端点的求值数组，这样就可...

2020-12-17

0 693

NC16645 矩阵取数游戏（动态规划）

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

2020-08-24

2 1112

NC16430 蚯蚓（队列）

题目链接题意：在m秒中有n只蚯蚓不断被分割，即每秒中长度最长的一只会被分割成两段，其余蚯蚓长度会增加q。求出每秒所分割的蚯蚓长度和最后各蚯蚓长度，按照格式要求输出。题解：暴力维护肯定会T，可以按照相对的思想，只对分割的蚯蚓操作，即分割蚯蚓长度少增加了q，大小关系不变，真正的长度等于队列...

2020-08-22

0 772

NC23051 华华和月月种树(树剖+离线)

题目链接题意：初始有一零结点，权值为0，根据相应操作维护这棵动态有根树。操作 1：输入格式 1 i ，表示使节点 i 长出了一个新的儿子节点，权值为0，编号为当前最大编号 +1。操作 2：输入格式 2 i a ，表示使节点 i 的子树中所有节点（即它和它的所有子孙节点）权值加 a 。操作 3：...

2020-08-20

0 651