前言本文讲解的是逆元的基本概念以及模意义下的乘法逆元，并介绍如何使用拓展欧几里得法，费马小定理法，线性递推法求乘法逆元。一、什么是逆元当我们在计算 a-b 时，可以将其视为 a+(-b) ；当我们计算 a/b 时，可以将其视为 a × (1/b) ，也就是乘以其倒数。逆元可以理解为在同余情况下的倒数。在数论中，如果一个线性同余方程 $ax \equiv 1 (\mod p)$ ，则称 x 为 a mod p 意义下的逆元，记作 $a^{-1}$ 或 inv(a) 。在同余的情况下，除去一个数，等于乘以这个数的逆元，即 a/b(mod p) = a × inv(b)(mod p) 。需要注意，逆元仅在所求数与模数互质，乘法逆元有两个性质：在特定模数下唯一，不存在多解乘法逆元是完全积性函数，也就是说 $inv(a) \times inv(b) = inv(a \times b)$二、乘法逆元的作用逆元有什么用呢？我们常常遇到一些题目要求结果对一个大质数 $p$ 取模，这是因为答案很大，出题人为了不麻烦大家写高精，就采取这样的方法。加减法和乘法对取模运算都是封闭的，所以我们可以步步取模来避免溢出，下图可以看出，一次取模和步步取模的结果是相同的。 但是当我们遇到除法的时候，步步取模就行不通了。根据下图可以看出，如果套用加减乘的步步取模公式，算出来的答案和一次取模的答案不一样。为什么除法是错的呢，证明也很简单：设 $a=k_0p+a' , b=k_1p+b' , k_0,k_1 \in Z$ ，可得 $(a\%p/b\%p) = (a'/b') = (a-k_0p)/(b-k_1p) \neq a/b$ 。 但是对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，我们就需要运用逆元了。根据上一节的概念可知，在模 p 意义下，$a/b$ 可以变形为 $a \times inv(b)$ 。实际上在模 10 意义下，$inv(3) = 7$ ，所以上图的式子可以转化为下图来运算：三、如何求逆元这里介绍三种计算逆元的方法：拓展欧几里得，费马小定理，线性递推。拓展欧几里得法拓展欧几里得法求逆元是一种较常用的求逆元方法，只要 $a$ 和模数 $p$ 互质，我们就可以使用它。实际上他与求同余方程的原理是一样的。当我们看到 $a \times inv(a) \equiv 1 (\mod p)$ 时，可以联想到方程 $a \times inv(a) + p \times y = 1$ 与 $a \times inv(a) \equiv 1 (\mod p)$ 是等价的。当 $a$ 与 $p$ 不互质时，方程无解，即没有逆元；当其互质时，将两者代入拓展欧几里得求一组可行解即可。为了防止负数，最后要做一步处理 $inv(a) = (inv(a)\%m + m)\%m$ 。ll exgcd(ll a, ll b, ll &x, ll &y)// 拓欧 { if (b == 0) { x = 1; y = 0; return a; } ll d = exgcd(b, a % b, y, x); y -= (a / b) * x; return d; } ll inv(ll a, ll p) { ll x, y; if (exgcd(a, p, x, y) != 1) // 无解的情形 return -1; return (x % p + p) % p; }费马小定理法费马小定理是数论中比较重要的定理，它的叙述如下：若 $p$ 是质数，且 $gcd(a,p) = 1$ ，则有 $a^{p-1} \equiv 1(\mod p)$我们从逆元的定义推导，可得 $a \times inv(a) \equiv 1 \equiv a^{p-1} (\mod p)$ ，于是有 $inv(a) \equiv a^{p-2}(\mod p)$ 。于是我们直接对 $a^{p-2}$ 计算快速幂即可。可以注意到，费马小定理求逆元只有在 $p$ 是质数的情况有效。inline ll qpow(ll a, ll n, ll p)// 快速幂 { ll ans = 1; while (n) { if (n & 1) ans = ans % p * a % p; a = a % p * a % p; n >>= 1; } return ans; } inline ll inv(ll a, ll p) { return qpow(a, p - 2, p); }线性递推法一般情况下上面两种方法就是我们常用的求逆元方法，但有些时候，题目如果要求连续一段大区间的所有数字的逆元，则有可能超时。这里 介绍逆元的线性递推求法（需保证$p$是质数）。设 $p = aq + r$ ，即 $q = \lfloor p/a \rfloor , r = p\mod a$ 。在模$p$意义下，有 $aq + r \equiv 0 (\mod p)$移项整理得 $a = -r \times inv(q) (\mod p)$ 。则 $inv(a) = -q \times inv(r) (\mod p)$ 。即 $inv(a) = -\lfloor p/a \rfloor \times inv(p \mod a) (\mod p)$ 。观察上面的式子可以发现一个数的逆元可以由比它小的数的逆元递推而来，因此我们可以用递推或者递归求解，时间复杂度为 $O(N)$ 。// 递推写法 int inv[1000000]; void find_inv(int n,int p)//求1~n所有数模p意义下的逆元 { inv[1]=1;//1的逆元就是1本身 for(int i=2;i<=n;i++) inv[i]=(long long)(p-p/i)*(inv[p%i])%p; // (p-p/i)为了防止负数 //注意longlong，否则有可能导致溢出 }// 递归写法 // 多次对不同的p使用需要清空Inv数组 ll Inv[MAXN] = {0, 1}; inline ll mod(ll a, ll p) { return (a % p + p) % p; } ll inv(ll a, ll p) { if (Inv[a]) return Inv[a]; Inv[a] = mod(-p / a * inv(p % a, p), p); return Inv[a]; }参考资料OIwiki：乘法逆元算法学习笔记(9)：逆元【朝夕的ACM笔记】数论-逆元数论篇——逆元
前言数组是一种常见的数据结构，在我们知道数组中某个元素的下标值时，我们可以通过下标值的方式以 O(1) 复杂度获取到数组中对应的元素。但如果我们不知道某个元素的下标值，而只是知道该元素在数组中，这时我们想要获取该元素就只能对数组进行线性查找，如果一个长度为10000的数组，我们需要的元素正好在第10000个，那么我们就要对数组遍历10000次，复杂度退化为 O(n) 。 为了解决上述数组的不足之处，我们引入了哈希表的概念。一、什么是哈希表我们回想一下，若要在字典查找一个单词，肯定不会从头翻到尾，而是会通过单词首字母，找到对应的那一页，然后快速的跳转到那个单词所在的页，这里面用到了哈希表的思维。哈希表，又称散列表，是一种以 key-value 形式存储数据的数据结构。所谓以 key-value 形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以通过某种映射函数快速地找到其对应的 value（如下图）。通常，我们会把给定的键值叫做 key ，把对应的记录称为 value ，可以快速求出该关键字对应的的数据的哈希地址函数则称之为 哈希函数 。 在OI中， 最常见的情况应该是 key 为整数的情况，另一种比较常见的情况是 key 为字符串的情况，但我们一般不直接把字符串作为键值，而是先算出字符串的哈希值，再把其哈希值作为 key 插入到哈希表里 。二、哈希函数的构造在构建哈希表时，最重要的就是哈希函数的设计。哈希函数的构造有三个基本要求：通过 key 可以计算出一个确切的 hash 值如果 key1 == key2 ，则hash(key1) == hash(key2)如果 key1 != key2 ，则hash(key1) != hash(key2)常用的哈希函数的构造方法有 6 种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。①直接寻址法直接寻址法是一种比较常用的哈希函数构造方法，它构造出来的哈希函数为一个线性函数，其形式一般如下：H（key）= key 或者 H（key）=a * key + b其中 H（key）表示关键字为 key 对应的哈希地址，a 和 b 都为常数 。该方法通过取关键字本身或者某个线性函数的值作为哈希地址。例如有一个从 1 岁到 100 岁的人口数字统计表，若直接使用年龄做哈希地址，则有如下表格 ： 使用该方法构造哈希函数的优点是计算方式简单，计算出来的哈希地址比较平均，但同时我们必须实现知道关键字的分布情况（即可能的值域），因此这种方法适合于数据范围较小且连续的情况。②除留余数法如果我们已经知道了整个哈希表的最大长度 m，则可以取一个不大于 m 的数 p，然后让关键字 key 与数 p 做取余运算，用所得到的结果作为哈希地址，其形式一般如下：H（key）= key % p （ p<=m，m为表长 ）举个例子，假设有以下数据{2, 4, 6, 8, 9}，已知表长为10，也就是数组容量为10，则我们可取模数 p 为 10 ，根据除留余数法进行构造后，我们可以得到下图的存储方式。除留余数法是最常用的一种哈希函数构造方法，在此方法中，模数 p 的取值非常重要，一般来说 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数，或者直接就是长度 m 本身。③数字分析法如果关键字本身是由多位字符或者数字组成，就可以考虑抽取其中的变化较多的 2 位或者多位作为该关键字对应的哈希地址。比如下表是若干个由8位十进制数组成的关键字： 通过分析关键字的构成，很明显可以看到关键字的第 1 位和第 2 位都是固定不变的，而第 3 位不是数字 3 就是 4，最后一位只可能取 2、7 和 5，只有中间的 4 位其取值近似随机，所以为了避免冲突，可以从 4 位中任意选取 2 位作为其哈希地址。④平方取中法当关键字的每一位都有某些数字重复出现频率很高，无法确定关键字里哪几位的分布相对比较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址，该方法叫做平方取中法。举个例子： 例如关键字序列为{421，423，436}，对各个关键字进行平方后的结果为{177241，178929，190096}，则可以取中间的两位{72，89，00}作为其哈希地址。 平方取中法的原理是：在平方时，运算结果的中间几位和关键字中的每一位都相关，平方运算扩大了关键字之间的差异 ，所以不同的关键字会以较高的概率产生不同的哈希地址 。这也是一种较常见的哈希函数构造方法，它适用于事先不知道数据并且数据长度较小的情况 。⑤折叠法折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。例如某书的编号为：0-442-20586-4，则可以选择下图的分割方式，在对其进行折叠时有两种方式：一种是移位折叠，另一种是间界折叠。移位折叠是将分割后的每一小部分，按照其最低位进行对齐，然后相加，如图（a）；间界折叠是从一端向另一端沿分割线来回折叠，如图 （b）⑥取随机数法随机数法是取关键字的一个随机函数值作为它的哈希地址，即：H（key）=random（key），此方法适用于关键字长度不等的情况。这里的随机函数其实是伪随机函数，随机函数是即使每次给定的 key 相同，但是 H（key）都是不同；而伪随机函数正好相反，每个 key 都对应的是固定的 H（key）如何选择合适的构造方案如此多的构建哈希函数的方法，在选择的时候，需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面：关键字的长度。如果长度不等，就选用随机数法。如果关键字位数较多，就选用折叠法或者数字分析法；反之如果位数较短，可以考虑平方取中法；哈希表的大小。如果大小已知，可以选用除留余数法；关键字的分布情况；查找表的查找频率；计算哈希函数所需的时间（包括硬件指令的因素）一个好的哈希函数，一般取决于以下几个方面：函数设计不会太复杂，尽量少的影响性能哈希函数的定义域必须包括需要存储的全部 key哈希函数计算出来的地址尽量均匀分布，避免过多的冲突三、哈希冲突根据上一节内容可知，哈希函数需要满足：如果 key1 != key2 ，则hash(key1) != hash(key2)。但有些时候，不同的 key 会算出同样的哈希地址。例如对于表长为 25 的哈希表，假设用除留余数法，取模数为19，我们会发现 hash(2) == hash(21)，这种现象称之为哈希冲突。注意：对于哈希表而言，哈希冲突只能尽可能少，不可能完全避免对于无法避免的冲突，则需要采取适当的措施去处理。 一般来说主要的解决哈希冲突方式分为：开散列法（又称为链地址法）和闭散列法（又称为开放地址法）①闭散列法闭散列法也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么我们可以尝试探测寻找剩余的空位，把 key 存放到冲突位置中的“下一个” 空位置中去。H（key）=（H（key）+ d）MOD m（其中 m 为哈希表的表长，d 为一个增量，所谓的下一个指的就是一个增量）根据不同的增量选取方式，闭散列法的实现一般分为线性探测，二次探测，再哈希法三种(1)线性探测顾名思义，线性探测的意思就是，当某两个元素发生冲突时，将当前索引+1，查看该位置是否为空，是的话就插入数据，否则就继续将索引+1，以此类推……直到插入数据位置 。 比如下图，如果模数为 11 ，此时需要插入38，我们发现 5 号位置已经有60了，则我们不断地把地址+1，最后38被放在了 8 号位置。但这种方法有一个缺点，那就是当数组中连续很长的一个片段都已经插入了数据，此时用线性探测就显得效率没那么高了，因为每次探测的步长都为1，所以这段都已经插入了数据的片段都得进行探测一次，这种现象叫做聚集。我们可以选用 二次探测 来缓解 聚集 这种现象。(2)二次探测二次探测在线性探测的基础上，将每次探测的步长改为了当前下标值 index + 1² 、index + 2² 、 index + 3² …… 直到找到空白位置插入元素为止。二次探测 在一定程度上解决了 线性探测 造成的 聚集 问题，但是它却容易在另一种程度造成了一种聚集，就比如 1² 、2² 、3² …… n² 上的聚集代码实现const int N = 360007; // N 是最大可以存储的元素数量 class Hash { private: int keys[N]; int values[N]; public: Hash() { memset(values, 0, sizeof(values)); } int& operator[](int n) { // 返回一个指向对应 Hash[Key] 的引用 // 修改成不为 0 的值 0 时候视为空 int idx = (n % N + N) % N, cnt = 1; while (keys[idx] != n && values[idx] != 0) { idx = (idx + cnt * cnt) % N; cnt += 1; } keys[idx] = n; return values[idx]; } };(3)再哈希法再哈希法就是将我们传入的 key 用另一个哈希函数再进行一次哈希化，然后使用新的哈希值作为探测步数 step ，按照这个步数找到第一个空着的位置插入数据，这种方法在很大的程度上解决了聚集的问题。再哈希的哈希函数可以写成如下形式：step = constant - (key % constant)，其中，constant 是一个自己定的质数常量，且小于数组的容量； key 就是第一次哈希化得到得值。我们通过这个哈希函数算得的步长来进行查找搜索空位置进行插入即可。②开散列法开散列法也称链地址法，就是在每个hash槽都开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。如果索引的范围是 $1...m$ ，哈希表的大小为 $n$ ，那么进行一次插入/查询需要进行期望 $O( \frac {n} {m} )$ 次比较。代码实现// C++ Version const int SIZE = 1000000; const int M = 999997; struct HashTable { struct Node { int next, value, key; } data[SIZE]; int head[M], size; int f(int key) { return key % M; } int get(int key) { for (int p = head[f(key)]; p; p = data[p].next) if (data[p].key == key) return data[p].value; return -1; } int modify(int key, int value) { for (int p = head[f(key)]; p; p = data[p].next) if (data[p].key == key) return data[p].value = value; } int add(int key, int value) { if (get(key) != -1) return -1; data[++size] = (Node){head[f(key)], value, key}; head[f(key)] = size; return value; } };这里再提供一个封装过的模板，可以像 map 一样用，并且较短struct hash_map { // 哈希表模板 struct data { long long u; int v, nex; }; // 前向星结构 data e[SZ << 1]; // SZ 是 const int 表示大小 int h[SZ], cnt; int hash(long long u) { return u % SZ; } int& operator[](long long u) { int hu = hash(u); // 获取头指针 for (int i = h[hu]; i; i = e[i].nex) if (e[i].u == u) return e[i].v; return e[++cnt] = (data){u, -1, h[hu]}, h[hu] = cnt, e[cnt].v; } hash_map() { cnt = 0; memset(h, 0, sizeof(h)); } };在这里，hash 函数是针对键值的类型设计的，并且返回一个链表头指针用于查询。在这个模板中我们写了一个键值对类型为 (long long, int) 的 hash 表，并且在查询不存在的键值时返回 -1。函数 hash_map() 用于在定义时初始化。四、哈希表的特点根据哈希表的存储结构，我们可以得出哈希表的以下特点。1)访问速度快由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。2)需要额外的空间首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。3)无序散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。4)可能会产生碰撞没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样参考资料哈希表详解什么是哈希表5分钟搞定哈希表哈希表及其存储结构详解数据结构与算法——哈希表OIWiki
一、各种OJ题库 - codeforces：https://codeforces.com/problemset题库 - 洛谷：https://www.luogu.com.cn/problem/list题库 - HydroOJ：https://hydro.ac/d/bzoj/p题库 - vjudge：https://vjudge.net/problem二、数据下载数据下载 - BZOJ：http://tools.attack204.com/bzojdownload/name/三、题面爬取洛谷题面爬取import re import urllib.request,urllib.error import bs4 import ssl ssl._create_default_https_context = ssl._create_unverified_context baseUrl = "https://www.luogu.com.cn/problem/P" savePath ="D:\\信息学竞赛\\LuoguProblem\\" def main(): pNum = input("请输入题目编号:") html = getHTML(baseUrl+pNum) if html == "noFind": print("没有该题目") else: problemMD = getMD(html) print("爬取转换完成！\nmd为：\n") print(problemMD) saveData(problemMD,"P"+pNum+".md") def getHTML(url): headers = { "user-agent": "Mozilla / 5.0(Windows NT 10.0;Win64;x64) AppleWebKit / 537.36(KHTML, likeGecko) Chrome / 85.0.4183.121 Safari / 537.36" } request = urllib.request.Request(url = url,headers = headers) response = urllib.request.urlopen(request) html = response.read().decode('utf-8') #添加没找到提示 if str(html).find("NotFoundHttpException") == -1: #洛谷中没找到该题目的提示网页中会有该字样 return html else: return "noFind" def getMD(html): bs = bs4.BeautifulSoup(html,"html.parser") core = bs.select("article")[0] md = str(core) md = re.sub(" ","# ",md) md = re.sub(" ","## ",md) md = re.sub(" ","#### ",md) md = re.sub(" ","``` \n",md) md = re.sub(" ","\n``` ",md) md = re.sub("</?[a-zA-Z]+[^<>]*>","",md) return md def saveData(data,filename): cfilename = savePath + filename file = open(cfilename,"w",encoding="utf-8") for d in data: file.writelines(d) file.close() if __name__ == '__main__': main()
前缀和概念：前缀和是指是一个数组的某项下标 i 之前(包括此项元素)的所有数组元素的和，前缀和问题一般分为一维前缀和与二维前缀和一维前缀和：是指求解序列的前 i 项和，可以把它理解为数学上的数列的前 i 项和二维前缀和：是指求解矩阵中以(x1, x2)为左上角，以(x2, y2)为右下角的子矩阵元素和，可以形象的理解为求子矩阵的面积前缀和优点：合理使用前缀和可以将一些复杂的操作简单化，从而提高算法的效率一维前缀和首先考虑一个基础例子：给定一个长度为 n 的序列，我们有 m 个询问，对于每一个询问，我们需要求给定的区间 [l, r] 的元素和。基础思路：对于一个区间，我们很容易想到可以通过暴力解法，遍历区间累加求和，代码如下：int n, m, l, r, sum; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } while(m--) { sum = 0; scanf("%d%d", &l, &r); for(int i = l; i <= r; i++) { sum += a[i]; } printf("%d\n", sum); }存在的问题：暴力解法的时间复杂度为 O(nm) ，显然对于 n 和 m 较大一点的数据点，暴力解法很容易超时，而如果我们使用前缀和的方法求解，则可以把时间复杂度降至 O(n+m)，大大提高了算法的效率。一维前缀和做法：首先我们需要对原数组 a 做一个预处理，定义数组 s[ ] ，s[i] 表述数组 a 的前 i 项和，根据数学推算可以得到如下规律：s[ 1 ] = a[ 1 ]s[ 2 ] = a[ 1 ] + a[ 2 ] = s[ 1 ] + a[ 2 ]s[ 3 ] = a[ 1 ] + a[ 2 ] + a[ 3 ] = s[ 2 ] + a[ 3 ]……s[ n ] = a[ 1 ] + a[ 2 ] + a[ 3 ] + …… + a[ n ] = s[ n-1 ] + a[ n ]对于数组 s ，我们可以得到递推公式 s[i] = s[i-1] + a[i] ，因此可以得到如下预处理代码：const int maxn = 1e5+10; int a[maxn], s[maxn]; //s[i]=a[1]+a[2]+a[3].....a[i]; for(int i = 1; i <= n; i++) { s[i] = s[i-1] + a[i]; }回到我们的例子，根据数学推算可发现，对于每次查询，我们只需执行s[r]-s[l-1] 由此我们可以写出以下查询代码：scanf("%d%d", &l, &r); printf("%d\n", s[r]-s[l-1]);对于每次查询，时间复杂度为O(1)，m 次查询的时间复杂度为O(m)，预处理的时间复杂度为O(n)，所以总时间复杂度为O(n+m)。二维前缀和如果数组变成了二维该怎么办？一维前缀和可以拓展到二维，先看一个例子：对于一个 n 行 m 列的矩阵，我们有 q 个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标，对于每个询问，我们需要输出子矩阵中所有数的和。 基础思路：同样我们也可以快速思考出暴力解法，直接遍历矩阵中的所有元素进行求和，代码如下：int n, m, q, x1, y1, x2, y2, sum, a[maxn][maxm]; scanf("%d%d%d", &n, &m, &q); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } while(q--) { sum = 0; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); for(int i = x1; i <= x2; i++) { for(int j = y1; j <= y2; j++) { sum += a[i][j]; } } printf("%d\n", sum); }存在的问题：暴力解法的时间复杂度为 O(nmq) ，显然对于 n 、 m 、q 较大一点的数据点，暴力解法很容易超时，而如果我们使用前缀和的方法求解，则可以把时间复杂度降至 O(nm + q)，提高了算法的效率。二维前缀和做法： 同一维前缀和一样，我们需要对原数组 a 做一个预处理，定义数组 s[ ][ ] ，s[i][j] 表述二维数组 a 中， 左上角(1,1)到右下角( i,j )所包围的矩阵元素的和，接下来推导二维前缀和的预处理递推公式：根据图例可知， 紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积，绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积，红色面积是指(1,1)左上角到(i-1, j-1 )右下角的矩形面积，每一个颜色的矩形面积都代表了它所包围元素的和 。 从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j]。因此我们得到二维前缀和的预处理递推公式为s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]，实现代码如下：const int maxn = 1e5+10; const int maxm = 1e5+10; int a[maxn][maxm], s[maxn][maxm]; //s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]; } }回到我们的问题： 求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和 。紫色面积是指 ( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 ，黄色面积是指(1,1)左上角到(x2,y1-1)右下角的矩形面积，红色面积是指(1,1)左上角到(x1-1,y1-1)右下角的矩形面积。不难推出， 绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1] 。根据图例我们可以写出二维前缀和的查询公式， 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] 。由此我们可以写出以下查询代码：scanf("%d%d%d%d", &x1, &y1, &x2, &y2); printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);对于每次查询，时间复杂度为O(1)，q 次查询的时间复杂度为O(q)，预处理的时间复杂度为O(nm)，所以总时间复杂度为O(nm + q)。差分概念：差分可以看成前缀和的逆运算，差分问题一般分为一维差分和二维差分差分优点：可在O(1)时间实现区间增减，提高算法效率一维差分差分数组推导：差分可以看成前缀和的逆运算。首先给定一个原数组a ：a[1], a[2], a[3],……,a[n];，我们构造一个数组b ： b[1] ,b[2] , b[3],……, b[i];，使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]，也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。我们可发现，每一个a[i]都是b数组中从头开始的一段区间和。那么如何构造差分数组b？最直接的方法如下：a[0 ]= 0b[1] = a[1] - a[0]b[2] = a[2] - a[1]……b[n] = a[n] - a[n-1]我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组。差分数组运用：考虑一个例子，在给定的数组a中，我们有 m 次修改，每次都给一个区间[l,r]的所有数字都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c。暴力做法是for循环l到r区间，时间复杂度O(n)，如果执行m次这样的操作，时间复杂度就会变成O(n*m)，当 n 、m 都比较大的时候，很容易超时。如果需要更高效的算法，差分数组就可以派上用场了。始终要记得，a数组是b数组的前缀和数组，如果对b数组的b[i]做出更新(比如加上c)，在前缀和反推a数组时会把该更新应用从a[i]开始的往后的每一个数。如果 b[i] 变为 b[i] + c a[i] = a[i-1] + b[i] + c = b[1] + b[2] + …… + b[i] + ca[i+1] = a[i] + b[i+1] = b[1] + b[2] + …… + b[i] + b[i+1] + ca[i+2] = a[i+1] + b[i+2] = b[1] + b[2] + …… + b[i] + b[i+1] + b[i+2] + c……对于区间[l,r]的修改，我们只需要打上一个补丁：首先让差分b数组中的 b[l] + c，接着让b[r+1] - c。我们可以发现，第一步把a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c，第二步把a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c。即做出类似如下图例的操作：b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求[l,r]区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。因此我们可以得出一维差分结论：给a数组中的[l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c（减去一个数的操作类似）。时间复杂度为O(1), 大大提高了算法的效率。二维差分拓展到二维的情况：如果扩展到二维，问题就会变成让二维数组被选中的子矩阵中的每个元素的值加上c，该问题同样也可以使用二维差分达到O(1)的时间复杂度。对于给定的数组 a[][] ，我们同样也去构建一个数组b[][]，使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和，此时b[][]则是a[][]的差分数组。如何构造二维差分数组？其实无论是一维差分还是二维差分，我们并不用考虑其构造方法，因为我们在使用差分操作在对原数组进行修改的过程中（a[i]可理解为给区间[i,i]加上a[i]），实际上就可以构造出差分数组。二维差分推导：同一维差分，我们构造二维差分数组目的是为了让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，始终要记得，a数组是b数组的前缀和数组，对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域，假定我们已经构造好了b数组，类比一维差分，我们可以执行以下操作来使被选中的子矩阵中的每个元素的值加上cb[x1][y1] += cb[x1][y2+1] -= cb[x2+1][y1] -= cb[x2+1][y2+1] += c每次对b数组执行以上操作，等价于以下代码，上述操作时间复杂度为O(1)：for(int i = x1; i <= x2; i++) { for(int j = y1; j <= y2; j++) { a[i][j]+=c; } }我们画一个图去理解这个过程：b[x1][y1] +=c；对应下图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。b[x1][y2+1]-=c；对应下图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。b[x2+1][y1]-=c； 对应下图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。b[x2+1][y2+1]+=c；对应下图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，所以要再加上一次我们将上述过程封装成代码：void insert(int x1,int y1,int x2,int y2,int c) { //对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c b[x1][y1]+=c; b[x2+1][y1]-=c; b[x1][y2+1]-=c; b[x2+1][y2+1]+=c; }我们可以先假想 a 数组为空，那么 b 数组一开始也为空，但是实际上 a 数组并不为空，因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 a 数组的初始值a[i][j]，等价于原数组 a 中 (i,j) 到 (i,j) 范围内加上了 a[i][j] ，因此执行n*m次插入操作，就成功构建了差分b数组，时间复杂度为O(nm)。for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d", &a[i][j]); insert(i,j,i,j,a[i][j]); //构建差分数组 } } 当然关于二维差分操作也有直接的构造方法，公式如下：b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]参考资料前缀和与差分OIwiki——前缀和与差分
前言用了一段时间 handsome 主题，发现它自带的标签云是银白样式，如果浏览器是白色背景，标签云就很容易因为颜色相近而被忽略，哪怕换成暗黑模式，标签的颜色也是跟背景相近的，容易看的眼瞎，因此决定找找更改标签云颜色的方法，在此记录一下。预览下面是五种颜色的标签云更改方式打开后台-更改外观-设置外观-开发者设置-自定义JavaScript选择下面一种颜色的 Javascript 代码黏贴上去即可颜色也可以自行设定，修改代码中的十六进制颜色值即可说明：如果主题中启用了pjax，还需要将上面代码添加到pjax-pjax回调函数中 let tags = document.querySelectorAll("#tag_cloud-2 a"); let colorArr = ["#000000", "#000000", "#000000", "#000000", "#000000", "#000000"]; tags.forEach(tag => { tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)]; tag.style.backgroundColor = tagsColor; }); let tags = document.querySelectorAll("#tag_cloud-2 a"); let colorArr = ["#C0C0C0", "#C0C0C0", "#C0C0C0", "#C0C0C0", "#C0C0C0", "#C0C0C0"]; tags.forEach(tag => { tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)]; tag.style.backgroundColor = tagsColor; }); let tags = document.querySelectorAll("#tag_cloud-2 a"); let colorArr = ["#ADD8E6", "#ADD8E6", "#ADD8E6", "#ADD8E6", "#ADD8E6", "#ADD8E6"]; tags.forEach(tag => { tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)]; tag.style.backgroundColor = tagsColor; }); let tags = document.querySelectorAll("#tag_cloud-2 a"); let colorArr = ["#428BCA", "#AEDCAE", "#ECA9A7", "#DA99FF", "#FFB380", "#D9B999"]; tags.forEach(tag => { tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)]; tag.style.backgroundColor = tagsColor; }); let tags = document.querySelectorAll("#tag_cloud-2 a"); let colorArr = ["#00BFFF", "#00BFFF", "#00BFFF", "#00BFFF", "#00BFFF", "#00BFFF"]; tags.forEach(tag => { tagsColor = colorArr[Math.floor(Math.random() * colorArr.length)]; tag.style.backgroundColor = tagsColor; });
A. 乳草入侵题目大意有一片 n*m 大小的草地，" . " 表示草，" * " 表示石头，其中点（mx,my）处有一颗乳草，乳草每个星期能往他周围八个方向生长，石头上无法长草，问至少需要多少个星期乳草就能覆盖整个草地（数据保证一定能长满整个草地）。1 <= n, m <= 100时限 1s解题思路因为问的是至少多少个星期，所以我们考虑用 bfs ，此题为模板题，直接从起点开始 bfs ，因为数据保证了一定能覆盖完是草地的格子，所以 bfs 中最后出队的格子用的时间是最长的，直接记录最后一个出队的点的星期数就是答案，注意起点为第 0 周。测试样例[tabs][tab name="样例1" active="true"]输入3 4 1 1.**...*.....输出4[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; struct node { int x,y,step; }; char ch; int n, m, mx, my, ans = 0; int mp[105][105], vis[105][105]; int dx[10]={-1,-1,-1,0,0,1,1,1}; int dy[10]={-1,0,1,-1,1,-1,0,1}; queue<node> Q; void bfs(int x, int y) { Q.push({x,y,0}); vis[x][y] = 1; while(!Q.empty()) { node f = Q.front(); Q.pop(); ans = f.step; for(int i = 0; i < 8; i++) { int nx = f.x + dx[i]; int ny = f.y + dy[i]; if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == 0 && vis[nx][ny] == 0) { vis[nx][ny] = 1; Q.push({nx, ny, f.step+1}); } } } } int main() { cin >> n >> m >> mx >> my; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> ch; if(ch == '.') mp[i][j] = 0; else if(ch == '*') mp[i][j] = 1; } } bfs(mx, my); cout << ans << endl; return 0; }B. 分糖果题目大意有 n 个小朋友，p 个朋友关系，现在需要发糖果，每个拿到糖果的小朋友会把多出来的部分分给还没得到糖果的朋友，但在分发的过程中，拿到糖果的小朋友会忍不住吃掉糖果，已知两个人之间需要 1 秒传递糖果，吃掉糖果需要 m 秒，问第几秒钟所有的小朋友都吃完了糖果。n <= 1000p <= 50000时限 1s解题思路朋友关系可以组成一条边，此题本质上就是从 c 号小朋友开始，按照朋友关系进行 bfs ，因为最后一个小朋友拿到糖的时间最晚，所以总时间为最后一个小朋友拿到糖果的时间 t 加上吃糖的时间 m 。此题没有直接给出图，而是给出了两点间的关系，所以可以考虑使用邻接表建无向图。测试样例[tabs][tab name="样例1" active="true"]输入4 3 121 22 31 4输出5[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 1005; struct node { int num; int step; }; int n, p, c, m, ans = 0; vector<int> E[maxn]; bool vis[maxn]; queue<node> qe; void bfs(int id) { qe.push({c,1}); vis[c] = 1; while(!qe.empty()) { node f = qe.front(); qe.pop(); ans = max(ans, f.step); for(int i = 0; i < E[f.num].size(); i++) { int nxt = E[f.num][i]; if(!vis[nxt]) { vis[nxt] = 1; qe.push({nxt, f.step+1}); } } } } int main() { scanf("%d%d%d", &n, &p, &c); scanf("%d", &m); for(int i = 1; i <= p; i++) { int a, b; scanf("%d%d", &a, &b); E[a].push_back(b); E[b].push_back(a); } bfs(c); printf("%d", ans+m); return 0; }C. 武士风度的牛题目大意有一头牛，走日字（与象棋的马的走法一样），从一个 n*m 地图的 K 出发，问最少需要多少步就能走到 H ，地图中 " . " 表示路， " * " 表示障碍。n , m <= 150时限 1s解题思路bfs 模板题，注意输入的行和列是反过来的，如果没注意的话建图会出错。测试样例[tabs][tab name="样例1" active="true"]输入10 11..............*..................*.*...........*....*..*...H*............*...*...K...........*.....*..*....*..输出5[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 200; struct node { int x, y, step; }; int m, n, sx, sy, mx, my, ans = 0; int mp[maxn][maxn], vis[maxn][maxn]; int dis[8][4] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}}; queue<node> Q; void bfs(int x, int y) { Q.push({x, y, 0}); vis[x][y] = 1; while(!Q.empty()) { node f = Q.front(); Q.pop(); if(f.x == mx && f.y == my) { ans = f.step; break; } for(int i = 0; i < 8; i++) { int nx = f.x + dis[i][0]; int ny = f.y + dis[i][5]; if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && mp[nx][ny] == 0 && !vis[nx][ny]) { vis[nx][ny] = 1; Q.push({nx, ny, f.step+1}); } } } } int main() { cin >> m >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char ch; cin >> ch; if(ch == '*') mp[i][j] = 1; else mp[i][j] = 0; if(ch == 'K') sx = i, sy = j; if(ch == 'H') mx = i, my = j; } } bfs(sx, sy); cout << ans; return 0; }D. 拯救王妃题目大意有一个 m*n 的矩阵，王妃被关在（a, b），王子要从（1, 1）出发，在 t 秒时限内救出王妃，王子可以往上下左右四个方向移动，矩阵每一个格子都有绑匪，消灭绑匪需要的时间都记录在矩阵中。如果王子能救出王妃，则输出 YES 和最大剩余时间，如果不能就输出 NO 。1 <= m, n <= 70题目保证答案和其他数据都在 long int 范围内时限 1s解题思路题目问的是最大剩余时间，所以考虑 bfs ，因为消灭绑匪的时间各有不同，所以不一定最快搜到终点就一定剩余最少时间。本题的要点在于同一个点可以重复入队（即如果能靠另一条路缩小到这个点的时间，则更新该点的最短时间），我们可以用一个 tim 数组来记录到达点 (i, j) 的时间，如果新的时间 t < tim[ i ][ j ] 则说明该点可以继续入队。因为本题只有尝试过所有的方案才能的到最优解，所以直接 bfs 整幅图就可以，不用设置终点。（本来按题目要求应该开 long long，但可能数据太水，用 int 直接莽过去了）测试样例[tabs][tab name="样例1" active="true"]输入4 3 2 3 22 5 15 3 13 1 14 2 15输出YES4[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 75; struct node { int x,y,t; }; int m, n, a, b, t; int mp[maxn][maxn], tim[maxn][maxn]; int dx[5] = {-1, 1, 0, 0}; int dy[5] = {0, 0, -1, 1}; queue<node> Q; void bfs(int x, int y) { Q.push({x, y, mp[x][y]}); tim[x][y] = mp[x][y]; while(!Q.empty()) { node f = Q.front(); Q.pop(); for(int i = 0; i < 4; i++) { int nx = f.x + dx[i]; int ny = f.y + dy[i]; int t = f.t + mp[nx][ny]; if(nx >= 1 && nx <= m && ny >= 1 && ny <= n && t < tim[nx][ny]) { tim[nx][ny] = t; Q.push({nx, ny, t}); } } } } int main() { memset(tim, 0x3f, sizeof(tim)); cin >> m >> n; for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { cin >> mp[i][j]; } } cin >> a >> b >> t; bfs(1,1); if(t-tim[a][b] < 0) cout << "NO"; else cout << "YES\n" << t-tim[a][b]; return 0; }E. 八数码题目大意有一个 3 x 3 的矩阵，有 0~8 ，其中 0 可以跟他上下左右 4 个数字进行交换，现在给你一个状态和最终状态，问最少需要多少步就可以完成转换。时限 3s解题思路问的是最少需要多少步，考虑用 bfs ，我们可以发现，把这个矩阵拉成 1 维后，它的每一种变化都对应着一种排列，而 9 个数一共有 9! = 362880 种排列，所以 bfs 不会超时。因为需要标记排列是否出现过，所以可以考虑使用康托展开把排列转换成一个整数表示它的状态。测试样例[tabs][tab name="样例1" active="true"]输入2 8 3 1 6 4 7 0 51 2 3 8 0 4 7 6 5输出5[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 11; struct node { int a[5][9]; int x, y, step; }; ll fact[maxn] = {1,1,2,6,24,120,720,5040,40320,362880,3628800}; // 存储1-10阶乘 int P[maxn]; // 二维转一维 int ans = 0, vis[1000005]; int dx[5] = {-1, 1, 0, 0}; int dy[5] = {0, 0, -1, 1}; ll fin; node start, aim; queue<node> Q; ll cantor(node x, int n = 9) { for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { P[(i-1)*3+j] = x.a[i][j]; } } ll ans = 1; for(int i = 1; i <= n; i++) { for(int j = i+1; j <= n; j++) { if(P[i] > P[j]) ans += fact[n-i]; // 统计第i位后面有多少比它小的 } } return ans; } // void print(node x) // { // for(int i = 1; i <= 3; i++) { // for(int j = 1; j <= 3; j++) { // cout << x.a[i][j]<<" "; // } // cout << endl; // } // cout<<endl; // } void bfs() { Q.push(start); vis[cantor(start)] = 1; while(!Q.empty()) { node f = Q.front(), nxt; Q.pop(); if(cantor(f) == fin) { ans = f.step; break; } for(int i = 0; i < 4; i++) { int nx = f.x + dx[i]; int ny = f.y + dy[i]; if(nx >= 1 && nx <= 3 && ny >= 1 && ny <= 3) { nxt = f; swap(nxt.a[f.x][f.y], nxt.a[nx][ny]); nxt.x = nx, nxt.y = ny, nxt.step = f.step + 1; if(!vis[cantor(nxt)]) { vis[cantor(nxt)] = 1; Q.push(nxt); } } } } } int main() { for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { cin >> start.a[i][j]; if(start.a[i][j] == 0) start.x = i, start.y = j; } } start.step = 0; for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { cin >> aim.a[i][j]; } } fin = cantor(aim); // 结束状态 bfs(); cout << ans; return 0; }
A. steve挖矿题目大意一个人在一个 n×m 大小的地图的 p 点开始挖矿，单位时间只能往左、或往右、或往下挖一格，其中有一些格子有矿石，矿石被挖过就没有了，有一些格子是墙壁不能走，挖矿时走过的路能重复走，请问在 t 时间后最多能获得多少价值。1 <= n,m <= 101 <= t <= 10时限 1s解题思路这是一个只有三个方向的 dfs ，因为没有明确的终点，所以递归中止的条件设为当前使用的时间 tn 是否大于规定时间 t 。题目规定走过的路可以重复走，所以 vis 数组并不是单纯用来记录走没走过，而是用来记录走过多少次，打标记的操作则应该是 vis[x][y]++ ，在 dfs 的过程中，如果当前点 vis[x][y] 值大于 1 时，说明一定是重复走了，则不需要再把当前点的矿物价值加入总和。测试样例[tabs][tab name="样例1" active="true"]输入3 4 30 P 0 0*663*7**输出15[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 20; int n, m, t, sx, sy, ans = 0; int vis[maxn][maxn]; char mp[maxn][maxn]; int dx[3] = {0, 1, 0}; int dy[3] = {-1, 0, 1}; bool in(int x, int y) { if(x >= 1 && x <= n && y >= 1 && y <= m) return true; else return false; } bool isNum(int x, int y) { if(mp[x][y] >= '0' && mp[x][y] <= '9') return true; else return false; } void dfs(int tn, int x, int y, int sum) { if(tn > t) { ans = max(ans, sum); return; } for(int i = 0; i < 3; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(in(nx,ny) && isNum(nx,ny)) { vis[nx][ny]++; if(vis[nx][ny] > 1) dfs(tn+1, nx, ny, sum); else dfs(tn+1, nx, ny, sum + mp[nx][ny] - '0'); vis[nx][ny]--; } } } int main() { cin >> n >> m >> t; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> mp[i][j]; if(mp[i][j] == 'P') sx = i, sy = j; } } vis[sx][sy]++; dfs(1, sx, sy, 0); cout << ans << endl; return 0; }B. 捕捉精灵题目大意小明想抓精灵，精灵的血量剩下越低，越容易被捕捉，现在小明有 n 个技能，第 i 个技能的伤害为 $d_i$ ，问怎样安排出招能让精灵剩下最低血量，请输出最佳方案中精灵剩余的最低血量和小明的出招次数，如果有两种方案让精灵剩余的最低血量相同，则输出出招次数较少的方案。1 <= n <= 51 <= hp <= 100001 <= di <= 10000时限 1s解题思路使用 dfs 寻找方案，dfs 函数要把攻击次数 tot 和精灵剩余血量 hpp 当参数往下传，因为题目要求不能打死精灵，假设最小伤害是 $d_x$ ，则 dfs 的终止条件是 $d_x$ > hpp。每找到一种方案，我们都要更新一次精灵最低血量和最少攻击次数。对于这道题，我们可以先把所有的伤害值从小到大排个序，在 dfs 枚举的过程中，如果枚举到的第 i 招的伤害 $d_i$ 已经超过了剩余血量 hpp，则 i 和它之后的招数都不用再枚举（简单的剪枝）。测试样例[tabs][tab name="样例1" active="true"]样例输入100 23350样例输出13[/tab][tab name="样例2"]样例输入101 29950样例输出12[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int maxn = 25; int hp, n, d[maxn]; int ans = INF, cnt = INF; void dfs(int tot, int hpp) { // 如果连攻击力最小的招数都不能用，则说明已经是当前方案最少血量 if(d[1] >= hpp) { if(hpp < ans) { ans = hpp; cnt = tot; } else if(hpp == ans) { cnt = min(cnt, tot); } return; } for(int i = 1; i <= n; i++) { if(d[i] >= hpp) break; // d数组排过序，如果当前的伤害di比剩余血量大，则剩下的技能都不用尝试 dfs(tot+1, hpp-d[i]); } } int main() { scanf("%d%d", &hp, &n); for(int i = 1; i <= n; i++) { scanf("%d", &d[i]); } sort(d+1, d+1+n); dfs(0, hp); printf("%d\n%d", ans, cnt); return 0; }C. 迷宫题目大意有一个由 0 和 1 组成的 n×n 迷宫，入口在左上角，出口在右上角，1 表示障碍，0 表示路，迷宫中可以往八个方向走，问从起点走到终点的方案有多少。n <= 5时限 1s解题思路地图 dfs 寻找方案总数的模板题，直接做就可以了，注意找准入口和出口。测试样例[tabs][tab name="样例1" active="true"]样例输入30 0 00 1 11 0 0样例输出2[/tab][tab name="样例2"]样例输入30 1 01 1 00 0 0样例输出0[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; int n,sum=0,mp[7][4],vis[7][5]; int dx[8]={-1,-1,-1,0,0,1,1,1}; int dy[8]={-1,0,1,-1,1,-1,0,1}; void dfs(int x, int y) { if(x==1&&y==n) { sum++; return; } for(int i = 0; i < 8; ++i) { int nx = x+dx[i]; int ny = y+dy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&mp[nx][ny]==0&&vis[nx][ny]==0) { vis[nx][ny]=1; dfs(nx,ny); vis[nx][ny]=0; } } } int main() { cin>>n; for(int i=1; i <= n; ++i) { for(int j = 1;j<=n;++j) { cin>>mp[i][j]; } } vis[1][6]=1; dfs(1,1); cout<<sum; return 0; }D. 素数环题目大意有 1 到 n 的 n 个数字，如果 n 个数字的排列能满足任意两个相邻的数字（包括头尾）之和都为素数，则这种排列称之为素数环，请输出 n 个数组成的素数环的方案，如果没有则输出 no answer。n <= 20时限 1s解题思路直接 dfs 寻找方案，使用一个数组记录答案，每一层选择数字的时候，除了判断有没有选过之外，还要同时判断当前选的数跟上一层选的数字之和是否为素数，当搜索到递归终点的时候，再对比一头一尾，保证满足素数环的要求。注：此题用 cin 和 cout 可能会超时。测试样例[tabs][tab name="样例1" active="true"]样例输入6样例输出1 4 3 2 5 61 6 5 2 3 4[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 25; int n,flag = 0; int vis[maxn] = {0},ans[maxn] = {0}; int isprime(int n) { if(n == 1) return 0; for(int i = 2; i <= sqrt(n); i++) if(n%i == 0) return 0; return 1; } void dfs(int dep) { if(dep == n) { if(isprime(ans[0]+ans[dep-1])) // 判断一头一尾 { for(int i = 0; i < dep; i++) { if(i) printf(" %d", ans[i]); else printf("%d", ans[i]); } printf("\n"); flag = 1; return; } } for(int i = 2; i <= n; i++) { if(!vis[i] && isprime(i+ans[dep-1])) // 判断当前选的数和前一个选的数的和是不是素数 { vis[i] = 1; ans[dep] = i; // 深度dep可以间接表示答案数组的下标 dfs(dep+1); vis[i] = 0; } } } int main() { scanf("%d", &n); ans[0] = 1; vis[1] = 1; dfs(1); if(!flag) printf("no answer"); return 0; }E. 拆分k题目大意把一个数 n 拆成 k 份，问能有多少种拆分方法，其中如果两种拆分方法拆出来的数字都一样，只是顺序不同，则都算同一种。6 < n <= 2002 < k < 6时限 1s解题思路因为 1、1、5 和 1、5、1 这些都看作是一种，所以我们可以考虑只枚举拆分序列为单调非递减的序列去代表一整类拆分，比如使用 1、1、5 代表 1、1、5；1、5、1；5、1、1 这三个拆分，所以这题的 dfs 函数需要传三个参数：深度、上一层选的数、上一层选完后还剩下的可选择大小。每一层选择的数字，一定要大于或等于上一层选的数字，并且不超过剩余总量的一半，这样才能保证选出来的序列是单调非递减的。测试样例[tabs][tab name="样例1" active="true"]样例输入7 3样例输出4[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; int n,k,ans; void dfs(int dep, int x, int rst) // 深度、上一层的数字，当前还剩的余量 { if(dep >= k) { ans++; return; } for(int i = x; i <= rst/2; i++) { dfs(dep+1, i, rst-i); } } int main() { scanf("%d%d", &n, &k); dfs(1,1,n); printf("%d", ans); return 0; }F. 全排列问题题目大意找出 1 到 n 的所有全排列并输出，要求按字典序输出1 <= n <= 9时限 1s解题思路dfs 模板题，不解释测试样例[tabs][tab name="样例1" active="true"]样例输入3样例输出1 2 31 3 22 1 32 3 13 1 23 2 1[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 15; int n; int vis[maxn]={0}; int ans[maxn];//存储搜索到的排列 void dfs(int dep) { if(dep==n) //dep的作用是搜索到足够的数字就输出排列数 { for(int i=0;i<n;i++) printf("%d ",ans[i]); printf("\n"); return; } for(int i=1;i<=n;i++) { if(!vis[i]) { vis[i]=true; //标记这个数已记录，不应再取 ans[dep]=i; //取数 dfs(dep+1); //搜索下一个可取的数 vis[i]=false; //解除标记，状态变回可取 } } } int main() { scanf("%d", &n); dfs(0); return 0; }G. 组合的输出题目大意从 1 到 n 的 n 个数中抽出 r 个数，问能组成多少种组合（只统计递增的选择）1 < n < 211 <= r <= n时限 1s解题思路dfs 寻找即可，除了深度 dep 之外，函数还需要把上一层选的数当作第二个参数 x 往下传，保证下一层的选择一定大于上一层。测试样例[tabs][tab name="样例1" active="true"]样例输入5 3样例输出1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 25; int n,r; int ans[15]; void dfs(int dep, int x) // 参数x用于传递上一层的选择 { if(dep > r) { for(int i = 1; i <= r; i++) printf("%d ", ans[i]); printf("\n"); return; } for(int i = x; i <= n; i++) { ans[dep] = i; dfs(dep+1, i+1); } } int main() { scanf("%d%d", &n, &r); dfs(1,1); return 0; }H. 自然数拆分题目大意把一个正整数 n 拆分成如上图的若干条加法式子1 <= n <= 30时限 1s解题思路使用 dfs 寻找方案，因为要保证拆出来的数字序列是单调非递减的，所以每次枚举选择的数字不能超过总量的一半，否则后面就没得拆了，因为要按顺序输出，所以每拆出一个数字，就输出一次最新的方案，然后再往下搜索。测试样例[tabs][tab name="样例1" active="true"]样例输入7样例输出1+61+1+51+1+1+41+1+1+1+31+1+1+1+1+21+1+1+1+1+1+11+1+1+2+21+1+2+31+2+41+2+2+21+3+32+52+2+33+4[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 35; int n; int a[maxn]; void dfs(int dep, int n) { for(int i = 1; i <= n/2; i++) // 保证枚举的时候后者一定大于前者 { if(i >= a[dep-1]) // 保证后一个值一定大于等于前一个值 { a[dep] = i; a[dep+1] = n-i; // 每次拆出一个数就输出一次 for(int j=1; j<=dep+1; j++) { if(j!=1) printf("+"); printf("%d",a[j]); } printf("\n"); dfs(dep+1, n-i); } } } int main() { scanf("%d", &n); dfs(1,n); return 0; }I. 工作分配问题题目大意有 n 件工作要分给 n 个人，假设工作 i 分配给员工 j 要花费 $C_{ij}$ ，问怎么分配能让总花费最少1 <= n <= 20时限 1s解题思路使用二维数组存储员工和工作的费用关系，然后直接 dfs 寻找方案即可。我们可以用 dfs 的层数 dep 代表当前考虑到第几个员工，对于员工 i ，只需枚举二维数组第 i 行就可以找出当前员工做每一样工作的花费，每次寻找到一种方案（即 dep > n）就更新一次最优答案，在深搜的过程中，如果这次的安排在还没到底的时候费用就已经超过了之前存储的最优答案，则该种方案不用继续深搜下去（剪枝）。测试样例[tabs][tab name="标签页 1" active="true"]样例输入34 2 52 3 63 4 5样例输出9[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int maxn = 25; int n, c[maxn][maxn], vis[maxn], sum = 0, ans= INF; void dfs(int dep) { if(dep > n) { ans = min(ans, sum); } for(int i = 1; i <= n; i++) { if(!vis[i]) { vis[i] = 1; sum += c[dep][i]; if(sum < ans) dfs(dep+1); // 剪枝，如果当前费用已经大于之前方案的最大费用，则没必要算下去 sum -= c[dep][i]; vis[i] = 0; } } } int main() { cin >> n; for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cin >> c[i][j]; } } dfs(1); cout << ans; return 0; }J. 装载问题题目大意有 n 个集装箱要装入载重量为 c 的轮船，集装箱 i 的重量为 $W_i$ ，在不考虑集装箱体积的情况下，问能装入轮船的最大重量是多少n <= 40c <= 1000时限 1s解题思路用 dfs 去寻找所有的方案，终止条件为层数 dep > n ，对于一件物品来说，它要么放，要么不放，因此分两种方式分别往下 dfs 即可，如果在往下搜的时候，货物总重量已经大于轮船的载重，但还没搜索到底，则该分支不用继续递归下去（剪枝）。测试样例[tabs][tab name="标签页 1" active="true"]样例输入5 107 2 6 5 4样例输出10[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 45; const int maxc = 1005; int n, c, w[maxn], ans = 0; void dfs(int dep, int sum) { if(dep > n) { // 递归到底 if(sum <= c) { ans = max(ans, sum); return; } } if(sum > c) { // 总和超过轮船数（剪枝） return; } // 一个物品要么选择放要么选择不放 dfs(dep+1, sum + w[dep]); dfs(dep+1, sum); } int main() { scanf("%d%d", &n, &c); for(int i = 1; i <= n; i++) { scanf("%d", &w[i]); } dfs(1, 0); printf("%d", ans); return 0; }K. N皇后问题题目大意在一个 n×n 的棋盘上放 n 个皇后，让他们不能互相攻击，要求输出所有的摆放方式，每种方式按次序输出每行皇后所在的列号，如果没有方案，则输出 no solute!n <= 10时限 1s解题思路可以对棋盘按行进行 dfs，函数的参数 dep 表示当前处理的行号，对于每一行，我们按列号进行枚举去尝试放皇后。第 dep 层（即第 i 行）的皇后位置的选择是否合法，我们需要对比前 dep-1 层（即前 i-1 行）的所有已放置的皇后的位置来确定，只要有一个是冲突的，则该行目前枚举到的位置不能放。搜索时找到的合法位置可以用一个一维数组 ans[] 来存储，ans[i] 存储的是第 i 行的皇后所在的列号，在递归时，每一层都记录一下 ans[dep]，到最底层时，把 ans 数组输出即可。注：当 N = 2、3 时，N皇后问题一定无解。测试样例[tabs][tab name="样例1" active="true"]样例输入4样例输出2 4 1 33 1 4 2[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 15; int n,okflag = 0; int ans[maxn]; //数组的下标表示行，对应的值表示列 void dfs(int dep) { int flag; // dfs深度为行数 if(dep > n) { okflag = 1; for(int i = 1; i <= n; i++) { if(i==1) printf("%d", ans[i]); else printf(" %d", ans[i]); } printf("\n"); return; } // 每行按列继续枚举 for(int i = 1; i <= n; i++) { ans[dep] = i; // 代表将第一个皇后放置在第1行第i列（或者说第n个皇后） flag = 1; for(int j = 1; j < dep; j++) // 检测 这个皇后的位置和之前的n个皇后的位置是否冲突 { if(ans[j] == i || (abs(dep-j)==abs(i-ans[j]))) { flag = 0; break; } } // 如果没冲突，才继续向下dfs if(flag) dfs(dep+1); } } int main() { scanf("%d", &n); dfs(1); if(n == 2 || n == 3 || !okflag) printf("no solute!"); return 0; }L. 滑雪题目大意有一个 r×c 大小的二维矩阵，矩阵每个点都有一个数值表示高度，人只能从高往低走，问在这个矩阵中，能走的最长路径是多长1 <= r,c <= 100时限 1s解题思路对于地图上的任意一个点 (i,j) 来说，在 dfs 时走到它路径不止一条，所以最长路径在搜索的过程中是会实时更新的，我们要使用记忆化搜索。开一个 dis 数组用于记忆化， dis[x][y] 表示走到点 (x,y) 的最长距离，因为题目要求只能往低处走，最后总会搜索到一个点是四个方向都比他高的（类似山谷），所以不用担心没有 vis 数组会死递归。在 dfs 的过程中，如果当前点 (x,y) 的 dis[x][y] 已经被计算过，则直接返回数组中存储的结果；如果没有计算过，则对他四个方向进行 dfs ，如果某个方向的点 (nx,ny) 的高度比当前点 (x,y) 矮，则有 dis[x][y] = max(dis[x][y], dfs(nx,ny)+1)。因为地图数据有可能会有多个山峰，并不一定是从最高的那个山峰往下走是最长的（比如样例2，从 23 出发才是最优的结果），所以要对地图的每个点都作为起点进行一次 dfs ，最后输出最大的一个结果。测试样例[tabs][tab name="样例1" active="true"]样例输入5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9样例输出25[/tab][tab name="样例2"]样例输入5 525 1 3 4 52 23 22 24 615 16 21 20 714 17 18 19 813 12 11 10 9样例输出22[/tab][/tabs]AC代码#include <bits/stdc++.h> using namespace std; const int maxn = 105; int mp[maxn][maxn], dis[maxn][maxn]; // dis记录到达点(i,j)的最长路径 int r, c, ans; int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int dfs(int x, int y) { if(dis[x][y]) { return dis[x][y]; // 如果到该点的最长距离已经记录过，则直接返回 } dis[x][y] = 1; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && mp[nx][ny] < mp[x][y]) { dis[x][y] = max(dis[x][y], dfs(nx, ny)+1); // 到达点(x,y)的最远距离，要么原本已经算了，要么可以从四周其中一个比他矮的点过来 } } return dis[x][y]; } int main() { memset(dis, 0, sizeof(dis)); scanf("%d%d", &r, &c); for(int i = 1; i <= r; i++) { for(int j = 1; j <= c; j++) { scanf("%d", &mp[i][j]); } } ans = 0; for(int i = 1; i <= r; i++) { for(int j = 1; j <= c; j++) { ans = max(ans, dfs(i, j)); // 因为有可能有多个山峰和陡坡，所以要每个点都dfs，取最大 } } printf("%d", ans); return 0; }
前言在我刚入门 ICPC 时，听着群里大佬们的聊天，完全听不懂啥意思，随着在圈内混的时间变长，慢慢的也就知道大佬口中的那些不明觉厉的缩写是啥了，这篇文章主要是记录一下入坑以来了解到的一些 ICPC 相关的术语。0. ICPC 与 OIICPC 国际大学生程序设计竞赛：国际大学生程序设计竞赛「International Collegiate Programming Contest，ICPC」是由国际计算机协会「ACM」主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。（不过前些年ACM协会跑路了，现在的赞助是「jetbrain」）。该比赛一般一年一个赛季，分为分为区域赛「Regional Contest」和总决赛「World Final」，竞赛群中说的xx站比赛，一般就是指区域赛，而群里都在膜的 WF 选手，就是总决赛选手。OI 信息学奥赛：青少年信息学奥林匹克竞赛是在广大青少年中普及计算机教育，推广计算机应用的一项学科性竞赛活动。全国从 1984 年开始举办全国性竞赛。区分国际级比赛「International Olympiad in Informatics，IOI」与国家级比赛「National Olympiad in Informatics，NOI」。大学的 ICPC 与高中的 OI 区别：ICPC 要求程序完全正确，且得分与程序的错误提交次数、正确提交时间有关（罚时永远的痛）；OI 设置分级得分，通过部分样例可拿到部分得分（所谓的骗分）ICPC 要求每队只能使用 1 台电脑，在 5 个小时内使用 C/C++、Java 和 Python 中的一种编写程序解决 7 到 13 个问题；OI 一般是 3 到 4 小时上机编程解题的形式，不限编程语言，竞赛题量相对较少ICPC 按队参与，每队 3 人，同时队员之前协作能力；OI 为单人参赛。总的来说，ICPC 除了考验个人能力之外，还要考虑团队的默契和协作能力。1. 常见的术语列举一些常见的术语，不仅在比赛中，常见的 OJ 系统都会采用这些术语：简写全称中文称谓OJOnline Judge在线判题系统AKAll Kill所有题目都过了ACAccepted通过该题WAWrong Answer答案错误RERunting Error程序运行时错误TLETime Limit Error程序运行超时MLEMemory Limit Error程序运行超出内存要求OLEOutput Limit Error程序输出过多PEPresentation Error输出格式错误CECompilation Error程序编译错误RFRestricted Function程序尝试调用禁止的库函数IEInternal Error测评系统内部错误提交之后到出结果前的状态：Pending 程序正在准备；Submitted 或 Received 程序已经被提交；Queuing 程序正在排队等待评测；Compiling 程序正在被编译；Judging 或 Running 程序正在被评测RE可能是浮点数溢出、死递归、除0、下标越界、局部数组过大等情况造成PE 一般是多输出了空行或空格导致，多数 OJ 是不会有PE的，如果格式错误直接就是 WA ，所以要注意输出格式OLE 一般由于无限循环导致输出过多ICPC 题目运行内存一般的限制在 256Kb，512Kb，或 1Mb2. 时间复杂度在一般的线下竞赛中，测评姬在 1s 内能进行 $5 × 10^8$ 次计算，在这个限制下，不同时间复杂度的算法能解决的问题规模如下（此处是较为保险的数据，比赛时具体情况要具体分析）：时间复杂度数量级 nO(N)n < $10^8$O(NlogN)n <= $10^6$O(N$\sqrt{N}$)n < $10^5$O($n^2$)n < 5000O($n^3$)n < 300O($2^n$)n < 25O(N!)n < 11
【博弈论】新世纪の三大基础博弈理论
前言博弈论是 ACM 比赛中的一个考察知识点，不算特别常见，但每次区域赛总会有可能出现个一两题，在我参加的为数不多的几场比赛中，GDCPC，ICPC南昌站，ICPC香港站都有出现过这样的题目。博弈论的题目一般有个特点：一看就知道是要考博弈论，但如果没有思路就得自己玩上个大半天。为了以后遇到这样的题目不再需要和队友玩上几轮游戏，于是决定开始系统学习一下博弈论，本篇文章讲的就是三种最基本的博弈理论：巴什博弈、斐波那契博弈、威佐夫博奕。ICG游戏最基本的博弈论题目一般都是基于ICG游戏来进行的，即公平组合游戏，这类游戏一般具有以下几个特点：竞争性：有两名玩家，且两名玩家是交替进行操作。公平性：每步操作都是在有限的合法操作集合中选取一种进行，且合法操作只取决于局面本身，与操作者无关。唯一性：不能再进行合法操作的玩家判负，不存在平局。因此我们可以发现如果想入门博弈论，往往遇到的入门题目都是取石子或者跳台阶。同样，根据这个定义我们可发现，很多的日常博弈游戏并不是ICG游戏，例如象棋就不满足公平性条件，因为红方只能移动红子，黑方只能移动黑子，操作者会干涉合法操作。巴什博弈巴什博弈（Bash Game）是最基础的一种博弈游戏，它的规则一般如下：有一堆数量为 n 的物品，两个人轮流从物品中取物，每次能取（1~m）个，最后取完的人获胜很显然，如果 n=m+1 ，由于一次只能取（1~m）个物品，那么先手无论取多少个，后手都能一次拿完剩下的物品，后者取胜。因此我们可以发现取胜法则：我们令 n=k(m+1)+r ，很明显对于任意 n ，满足 0 ≤ r ＜ m+1 ，如果 r == 0 ，先手无论怎么取都会输，反之如果 r != 0 ，则先手在第一轮可以先取 r 个，在后面的轮次中，只要保证两人每次都取 m+1 ，就能保证先手赢。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。结论：若 n % (m+1) == 0 ，则先手必败，否则先手必胜巴什博弈例题：HDU-2188题目思路：这题就是巴什博弈模板题，直接套用结论就可以解决。AC代码：#include <iostream> #include <cstdio> using namespace std; int t,n,m; int main() { scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); if(n%(m+1)) printf("Grass\n"); else printf("Rabbit\n"); } return 0; } 斐波那契博弈斐波那契博弈也是一种经典的博弈理论，威佐夫博奕参考资料ICG游戏巴什博弈入门三大博弈理论ACM博弈论基础
前言由于疫情，本来在 2020 后半年会举行的区域赛，想着 2021 年已经大四下学期了，内心处于退役养老阶段，突然在几个月前被通知说被派去了昆明和银川，也只能带着生锈的大脑继续上了。今年的昆明站是线上赛，在牛客网上举行，因为线上赛没有了之前在南昌和香港站的现场氛围，所以感觉比较微妙，而且各种步骤都变得繁琐了起来，原本不需要队员注意的事项也需要队员来做，所以总体来说我还是更喜欢线下赛。比赛日程4月2日时间内容18:15志愿者到位18:30按学校和队伍核对选手信息18:45发热身赛题目19:00-20:30热身赛20:30提交赛事记录4月3日时间内容8:30-9:00志愿者到位9:00-10:00俺们学校和队伍核对选手信息10:00开幕式10:30发正式赛题目11:00-16:00正式赛16:00-16:30提交赛事记录比赛规则因为是第一次打线上赛，所以还是想记录一下这有点繁琐的比赛规则（以下仅为一部分）竞赛试题数：13 题（英文）每个参赛队伍仅允许使用唯一主参赛计算机进行题目查看、程序编写调试、代码提交等操作（即不能双开看题）一支队伍能且仅能独立使用唯一打印设备（要打印啥信息自己备打印机）在比赛期间不得关闭浏览器或关闭牛客笔试平台页面比赛期间参赛选手如果需要上洗手间，必须请示本地监考志愿者，由本地监考志愿者通过腾讯会议联系线上监考人员，获准后才可以离开每个队伍都要配备三个监控机位（电脑），机位电脑均接入腾讯会议，并且要录屏，最后打题的电脑录屏要上交4.2热身赛A.Meditation题目大意：给你 n 个数字，从里面挑出 k 个，要求他们的和是最大的1 ≤ k ≤ n ≤ 100000对于每个数字，0 ≤ g ≤ 10000样例输入5 310227310输出42思路完全的签到题，排序相加就完事了AC代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; int n,k,a[maxn]; ll sum = 0; int main() { scanf("%d%d", &n, &k); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); sort(a+1, a+1+n); for(int i = n; k; --i) { sum += a[i]; k--; } printf("%d\n", sum); return 0; } B.Rounds题目大意有 n 个人，从 1 到 n 编号，每个人有一个整数信用值，现在要玩 k 轮游戏，第 i 轮游戏会从除了第 i 个人之外的其他人身上每人扣 s 信用值，并且都加到第 i 个人身上，每轮游戏后，都能找到一个人有最低信用值 c，问进行 k 轮游戏后，可能会出现的最低信用值 c 的最大值是多少1 ≤ n ≤ 1000001 ≤ k ≤ n1 ≤ s ≤ 100000000对于每个最低信用值 c ，1 ≤ c ≤100000000，而且 s×(n-1) ≤ c，即保证每轮游戏不会减成负数样例输入3 10244238输出28说明After round 1 the amounts of credits held are 44, 32, 28 and the minimum is 28.After round 2 the amounts of credits held are 34, 52, 18 and the minimum is 18.After round 3 the amounts of credits held are 24, 42, 38 and the minimum is 24.The best possible outcome is therefore 28.思路根据 n 的数据范围来看，显然 $O(n^2)$ 暴力模拟不可取，因为题目每一步都涉及到区间加减以及区间查询最值两个操作，所以可联想到用线段树维护整个数组，用 $O(nlogn)$ 的复杂度解决问题。题目并没给出具体操作次数 k ，但告诉我们 k 一定不会大于 n ，所以就当他操作了 n 轮即可。AC代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const ll INF = 0x3f3f3f3f3f3f3f3f; int n, k; ll a[maxn]; struct node { ll mi; ll v; ll lazy; }tree[maxn << 2]; void build(int p, int l, int r) { if (l == r) { tree[p].v = a[l]; tree[p].mi = a[l]; tree[p].lazy = 0; } else { int mid = (l + r) >> 1; build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r); tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi); tree[p].lazy = 0; tree[p].v = tree[p<<1].v + tree[p<<1|1].v; } } void pushdown(int p, int l, int r) { if (tree[p].lazy) { tree[p<<1].lazy += tree[p].lazy; tree[p<<1|1].lazy += tree[p].lazy; tree[p<<1].v += tree[p].lazy * (((l + r) >> 1) - l + 1); tree[p<<1|1].v += tree[p].lazy * (r - ((l + r) >> 1)); tree[p<<1].mi += tree[p].lazy; tree[p<<1|1].mi += tree[p].lazy; tree[p].lazy = 0; } } void add(int p, int l, int r, int x, int y, ll v) { if (x <= l && r <= y) { tree[p].lazy += v; tree[p].v += v * (r - l + 1); tree[p].mi += v; return; } else { int mid = (l + r) >> 1; pushdown(p, l, r); if (x <= mid) add(p << 1, l, mid, x, y, v); if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, v); tree[p].v = tree[p<<1].v += tree[p<<1|1].v; tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi); } } ll query(int p, int l, int r, int x, int y) { if (x <= l && r <= y) { return tree[p].mi; } else { int mid = (l + r) >> 1; ll ans = INF; pushdown(p, l, r); if (x <= mid) ans = min(ans, query(p<<1, l, mid, x, y)); if (y > mid) ans = min(ans, query(p<<1|1, mid + 1, r, x, y)); return ans; } } int main() { // freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); ll ans = 0; for (int i = 1; i <= n; i++) { add(1, 1, n, 1, n, -k); add(1, 1, n, i, i, 1ll * k * n); ans = max(ans, query(1, 1, n, 1, n)); // cout << "------->" << query(1, 1, n, 1, n) << '\n'; } cout << ans << '\n'; return 0; }C.Statues题目大意有 n 个展示灯，按 1-n 编号，有 k 个雕像，每盏灯下只能放一个雕像，每个雕像有一个重量 s 。已知每个雕像摆在对应的第 p 号展示灯下，但此时雕像重量并一定不是按升序排列，每次把雕像从 i 号灯移动到 j 号灯需要耗费 s×|i-j| 的时间，问最少需要耗费多少时间，能让雕像重量按升序排列。样例[tabs][tab name="样例1" active="true"]输入3 31 32 23 1输出8[/tab][tab name="样例2"]输入4 32 23 24 1输出3[/tab][/tabs]思路DP思路AC代码#include <bits/stdc++.h> using namespace std; typedef pair<int, int> P; typedef long long ll; const int maxn = 5e3 + 10; const ll INF = 0x3f3f3f3f3f3f3f3f; int n, k; ll dp[maxn][maxn]; P pos[maxn]; int main() { // freopen("in.txt", "r", stdin); ios::sync_with_stdio(0); cin >> n >> k; for (int i = 1; i <= k; i++) { int a, s; cin >> a >> s; pos[i] = P(s, a); } sort(pos + 1, pos + 1 + k); for (int i = 0; i < maxn; i++) for (int j = 0; j < maxn; j++) dp[i][j] = INF; dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { dp[i][j] = min(dp[i][j], dp[i - 1][j]); if (j) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1ll * pos[j].first * (ll)abs(pos[j].second - i)); } } cout << dp[n][k] << '\n'; return 0; }