日常见闻录 - PCsky
type: channel
link: http://www.hyouka.club/index.php/author/1/
description: PCsky
items: 【数学】数论：逆元
items: 【数据结构】哈希表
items: 【信竞日常】获取题目的各种工具
items: 【算法基础】前缀和与差分
items: 【博客优化】handsome主题标签云颜色修改
items: 【gdfzoj】递归搜索：bfs基础练习清单题解
items: 【gdfzoj】递归搜索：dfs基础练习清单题解
items: 【ICPC杂项】ICPC竞赛术语及相关知识
items: 【博弈论】新世纪の三大基础博弈理论
items: 【ICPC题解】2020年ICPC区域赛昆明站热身赛题解

【数学】数论：逆元
type: item
date: 2022-06-29T17:58:00+08:00
description: 前言本文讲解的是逆元的基本概念以及模意义下的乘法逆元，并介绍如何使用拓展欧几里得法，费马小定理法，线性递推法求乘法逆元。一、什么是逆元当我们在计算 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 = …

【数据结构】哈希表
type: item
date: 2022-06-15T16:50:00+08:00
description: 前言数组是一种常见的数据结构，在我们知道数组中某个元素的下标值时，我们可以通过下标值的方式以 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}作为其哈希地址。 平方取中法的原理是：在平方时，运算结果的中间几位和关键字中的每一位都相关，平方运算扩大了关键字之间的差异 ，所以不同的关键字会以较高的概率产生不同的哈希地址 。这也是一种较常见的哈希函数构造方法，它适用于事先不知道数据并且数据长度较小的情况 。⑤折叠法折叠法是将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。此方法适合关键字位数较多的情况。例如…

【信竞日常】获取题目的各种工具
type: item
date: 2022-05-19T18:09:00+08:00
description: 一、各种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()

【算法基础】前缀和与差分
type: item
date: 2022-03-30T10:53:00+08:00
description: 前缀和概念：前缀和是指是一个数组的某项下标 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…

【博客优化】handsome主题标签云颜色修改
type: item
date: 2022-02-22T17:55:00+08:00
description: 前言用了一段时间 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; });

【gdfzoj】递归搜索：bfs基础练习清单题解
type: item
date: 2022-01-28T00:34:00+08:00
description: 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", …

【gdfzoj】递归搜索：dfs基础练习清单题解
type: item
date: 2022-01-28T00:19:00+08:00
description: 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…

【ICPC杂项】ICPC竞赛术语及相关知识
type: item
date: 2021-05-18T17:03:00+08:00
description: 前言在我刚入门 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

【博弈论】新世纪の三大基础博弈理论
type: item
date: 2021-04-28T12:49:00+08:00
description: 前言博弈论是 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博弈论基础

【ICPC题解】2020年ICPC区域赛昆明站热身赛题解
type: item
date: 2021-04-02T23:11:00+08:00
description: 前言由于疫情，本来在 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…