A.团队改名

tag:思维

题意：

给定一个字符串，每次将字符串字母中的 换成 ，问最终的字符串

题解：

由于字符串中的字符我们可以将其字符 从而将 转换成

之后可以用一个数组，就类似并查集的 数组，用 表示第 个字符在转换后的新的字符是什么

然后其实对于一个转换操作就是

int nowx = x - 'a';
int nowy = y - 'a';
for(int i=0;i<26;i++)
{	
	if(now[i] == nowx)
		now[i] = nowy;
	else if(now[i] == nowy)
		now[i] = nowx;
}

时间复杂度：O(m + n)

B.又一个gcd问题

tag:数学，思维

题意：

给定两个数 ，求一个序列 使得

题解：

若 为最小值，则说明每一个 的因子中都含有这个 gcd，所以这些数相加，必然也有这个 gcd

所以我们判断是否有解仅需判断max(a,b) % min (a,b) 若 其余数为 则有解，若不为 0 必没有解。

有解的时候，若 max(a,b) == min (a,b) 则仅需输出 这个值 即是答案。

若不相等的时候，其实仅需两个数， 即可

时间复杂度:

C.圣杯战争

tag:猜结论，思维

题意：

给定两个数 ，可以进行任意次操作使得其中一个数加质数，另一个数减去相同的质数。但是加减后的结果不能为负数。问最终可不可能 。

题解:

对于任意一次操作， 的总和是不变的，那么最终若要两个数相同，即其和必然为偶数，否则无解

很容易我们可以想到 这两个特殊的质数，因为这样我们就可以构造出一边 另一边 的结果。

但是使用这个的前提是 ,我们仅需特判 和 从 的组合即可。

会发现其中仅有 0 2 这个偶数是不行的。特判即可。

时间复杂度:

D.分蛋糕

tag:贪心，思维

题意：

给两个数组 ，可以任意排列这个数组，然后一个一个拿数，每拿一个数，后面 数组中每个数 。问最后吃完所有蛋糕所能获得的最大总能量。

题解：

由于我们要吃完所有蛋糕，那么其实可以先把所有蛋糕都吃完，然后我们再考虑此时 数组，显然此时 数组全为负，若取其绝对值可以变成一个 的任意排列，若要这个排列与 组合尽可能小 ，不难发现我们仅需将 数组排序后， 数组中 大的数与 中较小的组合，显然是最优的，最后与之前所有的蛋糕相减即为解。

时间复杂度:

E. 特殊的机器人

tag: 倍增/维护序列，bfs

题意：

给定一个机器人的指令序列，然后按照指令序列进行移动，有效移动就增加能量，能量可以让机器人走到传送门的时就传送，每次传送就使得能量 -1 知道为 0，

题解：

该道题的传送门间可能有回环，且 ，所以该题显然不能暴力求解。那么如何快速找到一个传送门再当前 能量 下能传送到的位置呢？

题解1：

倍增，我们可以使用 表，预处理出所有的结果，然后对于每次查询，就直接查询非字符 * 的前一步。就和树上跑公共祖先一眼，找到祖先结点的子结点。

最后当倍增到结束后判断 当前能量是否为 以及传送的下一个位置是否是 . 若同时满足则继续传送到下一个即可。

题解2：

由于传送门间有回环的时候，这个回环可能只有进来的链，没有出去的链(这是因为一条边只有一条出边导致的)，所以我们可以预处理环内的序列，然后对于每次询问，仅需在环内序列取模去找最终结果即可。

然后对于仅为链的序列，也可以存储其序列，然后快速查找。

时间复杂度：

F.拼多多

tag:二进制枚举/dfs

题意：给定 种属性以及 个人，选择其中 个人，使得选择的 个人中的 (属性价值 属性个数) 最大。

题解：

二进制枚举，使用 __builtin_popcount() 来判断当前是否是 个人，然后去用 桶 暴力看每种属性有多少人拥有，最后从桶中查找 的属性，将桶所存储的数 属性价值 即可。

这个二进制枚举也可以用 替换

时间复杂度:

G. ykf 造小人

tag: dp，思维

题意：

问一个数字拆成若干个数字，使得数字之间是非递减关系，且每个数字是3的倍数的方案数。

题解：

我们先不考虑非递减关系和每个数是 的倍数 这两个条件，这样就使得变成一个很基础的 dp 问题。

即一个数字拆分的方案数。此时仅需

: 表示从以 i 为起点、j为终点的分割方案数。

然后每次二重循环，第一层为起点，第二层为终点。

当第一层起始位 0 的时候，就不转移。不为零时

然后我们加一个为 3 的倍数这个条件。

那其实仅需用一个前缀和，然后在转移的时候加一个条件 即可

然后我们再加入一个非递减的条件

那其实转移的时候，我们需要判断 与 这两个之间的大小比较。

首先字符串长的且没有前导零的必然比字符串短的大。

其次对于长度相同如何快速判断两个之间的大小呢。

有一个 的方法，就是用 求 然后通过 可以求出第一个不相同的位置，然后比较即可。

又或者 的方法，就是用 表来求出 lcp。

综上就能得到最终达到答案。

时间复杂度：

H.磁力链接

tag：01trie，模拟

题意：

每一次 Join 都是加入一个节点 到数组 ，每次Download 都是询问是在当前数组 中找到与文件 异或最小的节点 。输出节点 对应的 地址。

题解：

先写 base_32转换 和 16进制转换 ，然后对于每次 Join 都在 上去加点，对于每次 Download 就在树上查点，查点的方法就是尽可能和当前的位相同即可。最后查到点输出字符串即可。

时间复杂度:

I. 《Small Orange 有个朋友》

tag:模拟

题意：

给定三个串，每个串中都有一个不同位置上的字符不同，问原串。

题解：

循环对于每一位，找到两个相同字符输出即可。

时间复杂度:

J.我有异或症

tag:线段树，线性基，思维，随机

题意：

给定一个数组 ,以及 次操作，操作 1 为区间赋值，区间 2 为查询区间中子序列的最大异或和。

题解：

可以构造64棵线段树，然后对于每颗线段树，我们对每个数字都随机一下是否存在，然后线段树维护数的存在，以及维护区间的异或和。

然后对于操作一，就简单的区间修改。

对于操作二，仅需从 64 颗线段树中查询区间 的异或值，然后放入线性基即可。

证明随机的正确性: 考虑维护 64 个序列，每个序列的第 个元素有 的概率为 有的概率为 。 做查询时，只需对每个序列都求出区间异或和，然后假装这些元素形成的线性基是原区间的线性基即可。

显然我们得到的线性基应是真正线性基的子空间。所以只需证明 其有高概率是真正的线性基即可。

首先我们可以将证明归约至区间线性基恰好能表示 的 情况

如果我们的线性基不完整，那么一定存在一个 维向量 使得 和线性基中的所有元素点乘均为 。这对于一个序列来说概率是 ， 个都满足就是。

因此如果想要在一组询问中有高概率获得正确答案，那么需要 个序列。 组询问就是 个。 时间复杂度 --抄自<浅谈非确定性算法>

时间复杂度:

K.和平，或平

tag：二分，前缀和

题意：

给定一个数组 以及 次询问，每次询问给定一个 与 需要找到一个最大区间使得:

题解：

我们可以前缀和二进制下每一位 与 的个数。然后对于当前位 仅需向前二分一个位置，然后对于第 位看看前缀和是否为区间长度，若相等则这一位在这个区间上的与值为 ，然后或起来看这一段的与值是多少和 比较即可。

或值与以上解法不同的地方仅为 前缀和是否不为 即可。

时间复杂度:

L 可恶的英语课

tag: 优先队列

题意：

要求判断能否对给定字符串重新排列，使其满足每个长度为 的子串中无重复字符（即构造 “完美串”），若能则输出满足条件的字符串，否则输出-1。

思路

特殊情况：当 大于字符串长度时，原字符串没有长度为 的子串，所以直接输出原字符串即可。当 为 1 时，原字符串也满足条件，直接输出即可；

对于其他情况，我们先记录每个字母在字符串中出现的次数，将出现过的字符及其次数存到优先队列 中，按出现次数从高到低排序。在构造完美串时，每次取数量最多的字符来构造，因为任意相邻 个字符不能相同，所以使用当前字符后，需要将它移出优先队列中，暂时存放在队列 中。当构造的字符串长度达到 时，将 中的元素一个一个放回 中继续构造。若最终构造的字符串 长度与原字符串相等，则构造成功，直接输出 字符串 即可；否则输出 -1。

时间复杂度：

M 红灯停，绿灯行

tag: 分层图

题意：

每个安全区为点，道路为边，边权即为通过这条边需要的时间，求从起点到达终点需要的最短时间。

思路：

因为 有两次无视道路危险的能力，所以可以把整个图分为三层，分别表示没使用技能，使用一次技能，和使用两次技能。 在每次通过道路时，若可以直接安全通过，则直接通过，边权为 。若不能直接安全通过，则有两种选择，第一种选择是等待到安全时间再通过边权为 。第二种是在还有技能的情况下使用技能直接通过 边权为。 根据这几种情况，对整个图跑一遍最短路，即可得到最快的方案。

时间复杂度 ：