本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目名称 题目难度 T1 CityWalk 入门 T2 集合操作 普及- T3 乌尔达哈城市分布图 普及- T4 恰好 普及/提高- T5 符文锁 普及/提高- T6 集合操作2 普及/提高-
题解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CITYWALK
题目大意
给予一个H×WH \times WH×W的二维矩阵，给予两个顶点(x1,y1)(x_1,y_1)(x1 ,y1 )与(x2,y2)(x_2,y_2)(x2 ,y2 )，要求求出两个顶点的曼哈顿距离。
题解思路
本题本质为求曼哈顿距离的问题，在输入矩阵的时候记录两个顶点的坐标，然后计算两个坐标的曼哈顿距离即可。
曼哈顿距离计算公式 = ∣x1−x2∣+∣y1−y2∣|x_1 - x_2| + |y_1 - y_2|∣x1 −x2 ∣+∣y1 −y2 ∣
参考代码
集合操作
题目大意
我们需要实现一个集合，支持以下操作：
1. 插入元素：将元素 x 加入集合。
2. 删除元素：从集合中删除 c 个 x，如果 x 的数量不足 c，则删除所有 x。
3. 查询差值：输出集合中最大值与最小值的差。
题解思路
本道题采用multiset解决更为方便。 - oiwiki中对于multiset介绍
1. 选择合适的数据结构:
我们可以选择一种特殊的数据结构multiset来储存元素，该数据结构的各项函数与set的操作几乎一致，并且支持保存重复元素与自动排列，可以最高效的获取最大值与最小值。
2. 操作实现：
* 插入操作：直接将元素插入 multiset。
* 删除操作：使用 multiset 的 erase 方法删除指定数量的元素。
* 查询操作：通过 multiset 的 begin() 和 rbegin() 获取最小值和最大值，计算差值。
时间复杂度:
1. 插入操作: O(logO(logO(log $ n)$
2. 删除操作: O(logO(logO(log $ n + c)$
3. 查询操作: O(1)O(1)O(1)
参考代码
乌尔达哈分布图
题目大意
给出nnn个结点, mmm条边的无向图，每条边连接两个结点，结点编号从111到nnn。
求解每个结点的出度数量与其出边相连的结点的编号，从小到大输出。
题解思路
本道题考查图论储存当中的静态链表-邻接表的应用。
首先，我们可以用邻接表来存储图的结构。对于每个结点uuu，我们可以用一个数组aua_uau 来存储它的出边的结点编号。
然后，我们可以遍历每个结点uuu，对它的出边进行排序，然后输出它的出度数量与其出边相连的结点的编号。
时间复杂度为O(nlogm)O(n\log m)O(nlogm)，空间复杂度为O(n+m)O(n+m)O(n+m)。
参考代码
恰好
题目大意
给出一个NNN，求解有多少个公差为1的等差数列，使得它们的和为NNN。
题解思路
数列 [A,A+1,…,B−1,B][A, A + 1, \dots, B - 1, B][A,A+1,…,B−1,B] 的和为 (A+B)(B−A+1)2\dfrac{(A + B)(B - A + 1)}{2}2(A+B)(B−A+1) （可理解为将 [A,A+1,…,B−1,B][A, A + 1, \dots, B - 1, B][A,A+1,…,B−1,B] 与 (A+B)(B−A+1)2\dfrac{(A + B)(B - A + 1)}{2}2(A+B)(B−A+1) 相加）。(每个元素加上 [B,B−1,…,A+1,A][B, B-1, \dots, A + 1,
A][B,B−1,…,A+1,A] 即可理解）。
因此，这个问题等价于求解
(A+B)(B−A+1)=2N(A≤B). (A + B)(B - A + 1) = 2N \quad (A ≤ B). (A+B)(B−A+1)=2N(A≤B).
这里， A+B,B−A+1A + B, B - A + 1A+B,B−A+1 都是 2N2N2N 的除数，因为它们都是整数。
现在，列举分解成两个正整数的方法，如 2N=x×y2N=x \times y2N=x×y ，并求解
{A+B=xB−A+1=y \begin{cases} A + B = x\\ B - A + 1 = y\\ \end{cases} {A+B=xB−A+1=y
从而求出整数解的个数。
它的解是
A=(x−y+1)/2, B=(x+y−1)/2A = (x - y + 1)/2,\ B = (x + y - 1)/2A=(x−y+1)/2, B=(x+y−1)/2
如果 xxx 和 yyy 的奇偶性不同，它的解就是 A=(x−y+1)/2, B=(x+y−1)/2A = (x - y + 1)/2,\ B = (x + y - 1)/2A=(x−y+1)/2, B=(x+y−1)/2 ；否则，就没有这样的整数解。
因此，答案就是将 2N2N2N 分解成两个不同奇偶性整数的方法数。
由于 2N2N2N 的除数可以用 O(N)O(\sqrt N)O(N ) 的时间复杂度枚举出来，所以这个问题总共可以用 O(N)O(\sqrt N)O(N ) 的时间解决。
另外，由于 2N2N2N 的质因数至少有一个 222 ，所以 xxx 和 yyy 中的任何一个（但不是两个）的被除数都是 222 。
因此，答案是（ MMM 的被除数） ×2{}\times 2×2 ，其中 M=M =M= （ NNN 重复除以 2 直到它不能被 222 分割）。
参考代码
符文锁
题目大意
告知你最多存在 NNN 个编号为1,2,…,N1,2,\dots,N1,2,…,N 的数字，你需要使用这些数字打开宝箱。
宝箱需要使用至少MMM个正确的数字打开(无关先后顺序)，每个数字的状态可以是真或假。
告诉你已经进行过MMM次的开箱的结果与使用的数字，要求你计算一下到底有几种打开宝箱的可能的数字组合方案，并且不与开箱结果冲突。
题解思路
符文的范围为 N≤15N \le 15N≤15 且测试次数 M≤100M \le 100M≤100 。因此我们可以得出正确的符文最多有 2N2^N2N 种组合。
我们可以对所有的 2N2^N2N 组合进行 MMM 次测试，并计算正确组合的数量。
这里需要进行 2N×M≤3.3×1062^N \times M \le 3.3 \times 10^62N×M≤3.3×106 次测试。即使对一个测试执行 NNN 次操作，总操作数的边界也是 5×1075 \times 10^75×107 。
为了对 2N2^N2N 个组合进行暴力破解，位枚举。
比如使用 循环遍历 i=0,1,…,2N−1i=0,1,\dots,2^N-1i=0,1,…,2N−1 。如果 2k2^k2k 中 iii 的位置是 000 ，我们就假设 (k+1)(k+1)(k+1)项 符文是一个假符文；如果是 111 ，我们就假设它是一个真符文。这样，我们就可以穷举所有的组合。
参考代码
集合操作2
题目大意
给定一个长度为 A=A1,A2,...,ANA = {A_1,A_2,...,A_N}A=A1 ,A2 ,...,AN 的序列 ，需要处理 qqq 次操作，操作类型分为以下三种：
赋值操作：1 x，将序列 AAA 中的所有元素赋值为 xxx。
添加操作：2 x y，将 xxx 加到 AyA_yAy 上。
查询操作：3 y，输出AyA_yAy 的值。
需要按照操作的顺序依次执行，并输出所有查询操作的结果。
题解思路
该项问题属于区间修改问题，解决问题的方法很多，这里可以采用时间戳解决该项问题，代码量最小，或者你也可以建立对应的树状数组或者线段树长度为 NNN 的序列进行范围更新和点检索，则解决问题的总时间约为 O(N+QlogN)O(N+Q\log N)O(N+QlogN)
参考代码
* 线段树参考代码
