2023算法复习

使用vjudge进行题目评测，减少找题的工作量。

~/.vimrc 中g++使用F5快速执行代码，

autocmd filetype cpp nnoremap <F5> :w <bar> !g++ % -o %:r && ./%:r<CR>

2023.4月

2023.4.24.

《第一章 算法设计基础》

  1. UVA - 11292 - Dragon of Loowater 贪心，双指针
  2. UVA - 11729 - Commando War 贪心
    证明贪心的正确性，基于一个先假设好的条件，分类讨论结果，比较结果的正确性，使用 (Job){a, b} 对结构体赋予初值
  3. UVA - 11300 - Spreading the Wealth 思考题
    将题目中的变量设出来，得到n个变量和n-1个方程的方程组组，通过其中一个变量x1将其他变量表示出来，再将目标最小化结果由单变量表示出来，发现是一个一维绝对值之和最小化问题，取中位数即可（反证法证明）
  4. CF Gym NEERC 2006 - 100287G - Graveyard 贪心
    非常具有技巧性的题目，首先阅读题目有些难度，主要要注意到equidistant和memorial两个含义，首先用到等距缩放的技巧，并对雕像进行编号，这样就能把圆上的问题转化为一维整数点区间上的问题，并用贪心进行求解非常巧妙：将加入新雕像后的坐标作为整数坐标，总距离为(n+m)，就雕像位置在该坐标尺度下表示出来（小数形式），再将每个雕像移动到最近的整点坐标即可(四舍五入)，最后再证明贪心的正确性。
  5. UVA - 10881 - Piotr’s Ants 思路题
    蚂蚁碰头之后会反向移动，容易发现一点是蚂蚁之间的相对位置是不会变换的，最重要解题点是将蚂蚁的碰头视为相互穿过。
    于是只需先假设蚂蚁是相互穿过的，然后再排序得到相对顺序，再通过初始的相对顺序order[i]，最终根据相对序号的一致性，得到每个编号的蚂蚁的最终位置。
    注：数轴长度为L，并从0开始。
  6. UVA - 1030 - Image Is Everything 暴力模拟题
    题目要求最大的正方体方块个数，也就是挖去所有产生矛盾的方块，剩下的非空方块个数就是最大个数，所以只需要找出所有一定有矛盾的方块：
    1. 如果某个视图上为 '.' 则全部深度的方块均为空。
    2. 暴力枚举每个视图上的每个位置的所有深度，对立方体建立坐标系，定义函数视图相对坐标+深度↦立方体方格坐标\text{视图相对坐标+深度}\mapsto \text{立方体方格坐标}，判断当前方格的颜色是否和当前视图中的颜色一致，如果一致则跳过后续深度枚举，否则将其挖去，继续枚举后续深度。
  • 技巧：
    • 利用宏函数 #define rep(i, n) for (int i = 0; i < n; i++) 可以大幅减少 for 循环的冗余，使代码更加简洁易读。
    • 对于多个返回值的函数，无需对其进行返回，而是使用传递实参的方式进行返回。
  1. Codeforces Round 867 (Div. 3)
    比较简单的比赛，但是由于不理解题意没有打好。看复杂题面的题，首先找题目求解的问题关键词：Answer, You need, Formally … ，再通过题目给出的样例进一步分析题意，最后确定有哪些变量需要开 long long
    1. 两道题，没有仔细开 long long 导致错误提交，也就是思路还不够清晰。
    2. F题，树的边数组开小了1个，树上dp找每个节点u第一和第二长的路径 mx[u][0] 和mx[u][1]，只需两次dfs，固定一个节点为根节点，第一次dfs求出每个节点到叶子节点的第一二大的距离，并存储下最大距离是从 frome[u] 节点转移得到的，第二次dfs可得每个节点上方的最大距离（注意如果是递推到 from[u] 节点则其最大距离为 max(rtlen, mx[u][1] + 1)）。
    3. D题，容易想到不是解的必要条件：n>1且为奇数则一定不是解；还是考虑构造从而得出其充分性，首先a的第一个一定是n，构造的技巧是利用每个元素的范围有限[1,n)，保持构造的结果具有某种递增的规律（围绕某个元素进行构造），在模意义下构造出a=[1,-2,3,-4,5,-6,…,-(n-2),n-1]。
2023.4.25.
  1. UVA - 11464 - Even Parity 暴力
    通过每个点四周必定为偶数个黑点，如果确定了前两排的结果，那么第三排的状态就可以唯一确定了，所以我们只需要暴力枚举第一排，于是之后的每一排都唯一确定了（一个十字架，上面三个顶点的值确定，总和为偶数，那么下面的值一定可以确定下来）
  2. UVA - 1352 - Colored Cubes 暴力
    首先对正方体进行编号，枚举正方体的全部旋转方法24种，打表；然后对实际的5个正方体逐个枚举旋转方法，复杂度为O(24^3)，对于每个面，全部染为有最多共同颜色的面，取最小的染色方法。
    注：能不用 #include <bits/stdc++.h> 就不要使用，会大幅度降低编译速度，并且有变量重名的可能。
  3. UVA - 11210 - Chinese Mahjong 暴力
    麻将题，注意枚举顺序：依次枚举听牌，将牌，刻子和顺子。灵活运用 string 数据类型进行牌型判断，用s.c_str() 转为 char* 输出 string 类型；注意输出结果的空格细节。
  4. UVA - 11384 - Help is needed for Dexter 简单题
    非常简单，找到规律就是log2n向下取整+1
  5. UVA - 10795 - A Different Task 数学题
    巧妙的利用了汉诺塔的性质，一定要移动的一定是最大的终止状态和初始状态不同的大小为k的圆盘，所以一定要把1…k-1移动到唯一多余的柱子上这个状态成为中间状态，利用移动圆盘的对称性，只需将初始和终止两个状态的圆盘都移动到该中间状态上，再+1就得到答案了。
    巧妙的构造递归函数f(P, i, final)，这和dp类似，P表示开始状态，i表示最大的圆盘，final是将1…i-1圆盘全部移动到final柱子上，递推方法也是类似的思路，看最大的圆盘位置有没有移动，如果final[i]!=P[i]，说明1…i-1都要先移动到6-final[i]-P[i]上，然后将1…i-1移动回final[i]，这一步就是传统的汉诺塔，直接给出步数2^(i-1)=1+2+...+2^(i-2)。
2023.4.26.

  1. UVA - 12124 - Assemble 二分答案
    最小值最大问题，显然二分答案，利用结构体存储每个类型的物品，注意到结果中没有涉及到部件的名称，所以无需存储名称。

    注意：使用下标枚举vector中的数据，而不是使用速度慢的 for (auto x : v)（慢20倍左右）。

  2. CF Gym NWERC 2006 - 100722C - Pie 二分答案
    非常简单，只需二分枚举派的大小即可。使用 const double PI = acos(-1.0) 定义PI。

  3. UVA - 11520 - Fill the Square 暴力枚举
    非常简单，从小到大枚举字符即可。

    注意：字符串数组必须至少为最大字符串长度+1，因为有终止符 0 存在。

  4. UVA - 1267 - Network 贪心
    贪心地每次从距离根服务器最远的节点开始向上找最远的祖先节点放置服务器镜像，注意使用链表从边的编号从0开始存图每次要初始化所有的 head[u]=0，并初始化 ecnt=0。

  5. UVA - 1335 - Beijing Guards 二分答案，巧妙的贪心判断结果
    求解环形问题第一步一定是确定基准元，然后分析二分的上下界（非常重要，一定要想清楚），下界一定是两个相邻的礼物需求之和的最大值，上界是最大礼物需求的三倍；最巧妙的是，贪心判断是否可行时，顺次贪心选取的礼物数量只不过方向正好相反，第0个从左开始选r[0]个，第1个也从左选r[0]个，第2个从右选r[0]个，最后判断n-1个从右选的r[n-1]个是否和第0个选的r[0]个重复；但是这样检查一次的复杂度是O(n^2)，注意到题目没有要求具体礼物的编号，并且我们只关心第n-1和第0个人是否选取重复，所以可以以第0个选取的礼物将全部礼物划分为左右两部分，后面的每个人只需考虑在两个部分中各选了多少个即可，最后判断最后一个人有没有在左边选取礼物即可。
    注意：

    1. 二分的上下界分析（必要性），对于判断函数 check() 也可以缩小判断范围。
    2. 边界条件n=1的判断。
    3. 二分答案的两种写法：
int L, R;
// 最小化二分
while (L < R) {
    int mid = (L + R) / 2;
    if (check(mid)) R = mid;  // 如果mid可行
    else L = mid + 1;
}
// 最大化二分
while (L < R) {
    int mid = (L + R + 1) / 2;
    if (check(mid)) L = mid;  // 如果mid可行
    else R = mid - 1;
}
// 两种写法二分结果均为L
return L
  1. UVA - 11462 - Age Sort 桶排序
    没什么技巧，只需注意末尾不要有多余空格。
  2. UVA - 11078 - Open Credit System 贪心，简单题
2023.4.27
  1. UVA - 11549 - Calculator Conundrum 暴力
    利用Floyd判圈算法通过两个节点的运动速度不同（一个运动速度为1，另一个为2），从而在O(n)时间下找大小为n的环。
  2. UVA - 1398 - Meteor - E4 代数几何，线段最大交集
    仅考虑对答案产生贡献的时间段，用结构题存储区间的端点，由于每个时间段均为开集，在用扫描线处理到相同位置的边界点时，优先处理右端点（如果是闭集则优先处理左端点）
  3. UVA - 1330 - City Game - E1 代数几何，最大化矩形面积
    考虑点(i,j)向上扩展出的最大距离记为up(i,j)，向左右按照上方最大距离能扩展的最大距离分别记为left(i,j),right(i,j)，于是这个点按照向上最大距离能扩展的最大面积为(right(i,j)-left(i,j)+1)*up(i,j)。
    进一步考虑用迭代方式求解这三个数组，不难发现up(i,j)=up(i-1,j)，顺次从上到下，以横向扫描线扫描没一行，从左到右更新left，如果up(i-1,j)<up(i,j)则left(i,j)=1，否则left(i,j)=left(i-1,j)；right数组从右到左更新，方法类似。
  4. UVA - 1382 - Distant Galaxy - E1 代数几何，最大化矩形边界点
    找矩形上一定存在的条件：每条边上至少有一个点，于是转化为通过点枚举边，枚举四条边有点多了，所以就枚举上下两条边（按照y轴枚举，需要对y轴进行排序，顺便去重，方便枚举），然后找再两条矩形的竖线构造出矩形，现在考虑如何快速求出最大的边界点，首先考虑矩形的边界点可以通过哪些变量求出，left[i],on[i],on2[i]分别表示第i个竖线左侧在上下两边上的点数目（不包括i）、第i个竖线上夹在上下两边中间的点数（不包括两边）、第i个竖线上夹在上下两边中间的点数（包括两边），于是第i,j竖线构成的矩形上的点可以表示为left[j]-left[i]+on2[j]+on[i]，求(i,j)使得递推式最大化，可以从左至右顺次枚举，记录下on[i]-left[i] (i<j)的最大值mx，于是left[j]+on2[j]+mx就是矩形右直线为j能覆盖的最大点数。
  5. UVA - 10755 - Garbage Heap - E1 代数几何，容斥原理
    先从求二维面积最大矩形权重之和考虑，通过维护前缀和，枚举矩形边界y1,y2，再从小到大枚举x，通过前缀和求出{(1,y1),(x,y2)}的权重之和，记录下前面扫描过的最小值，则最大权重是当前的权重之和减去之前的最小值。
    三维方法类似，主要是怎么求出前缀和，考虑二位的容斥原理，每次要求出{(x1,y1),(x2,y2)}的面积，就是通过s(x1,y1)减去s(x1,y2)和s(x2,y1)的并，这个并可以通过容斥原理得到：s(x1,y2)+s(x2,y1)-s(x2,y2)
    类似的三维也是通过s(x1,y1,z1)减去s(x2,y1,z1),s(x1,y2,z1),s(x1,y1,z2)的并，通过容斥原理可得：s(x2,y1,z1)+s(x1,y2,z1)+s(x1,y1,z2)-s(x2,y2,z1)-s(x2,y1,z2)-s(x1,y2,z2)+s(x2,y2,z2)
    最后也是枚举六面体边界x1,x2,y1,y2，再从小到大枚举z，与二位相似的操作即可求出三维权重最大值。
  6. CF Gym - 101388J - Jurassic Remains - E0 位运算，折半枚举
    难度最大的是读懂这个题目，题目说是要骨头配对，其实就是骨头上关节的编号配对，也就是每个编号至少能有一对，也就是每个字母出现的次数一定要是偶数次，所以可以想到用异或运算解决。
    由于编号只有26种，骨头数目也不超过26个，先将骨头的编号转为对应的二进制位，一个集合中所有骨头的编号异或起来如果是0则满足题意，再通过折半枚举，先枚举n/2个骨头的所有编号组合，并用map的key值记录编号组合，value值记录选择的骨头（相同则取骨头集合中元素最多的），然后在枚举另一半的所有骨头编号组合，判断是否在map中有对应的key值即可，复杂度O(2^(n/2)log(2^(n/2)))=O(n/2*2^(n/2))。
2023.4.29. 算法复习计划1
  • [x] DP平行四边形不等式优化、单调队列优化
  • [x] Trie
  • [x] KMP
  • [x] 线段树
  • [x] SA 2023.5.17.
  • [x] SAM
  • [ ] Tarjan
  • [ ] 二分图匹配
2023.4.30. 初步学习四边形不等式DP优化
  1. 洛谷 - P3515 - Lightning Conductor 平行四边形不等式DP优化-1
    要求 p[i] = max{h[j]-h[i]+sqrt(abs(i-j)) : 1<=j<=n}，先转化为 min 问题，然后发现极小化函数为 h[i]-h[j]-sqrt(abs(i-j)) 记极小值为 f[i]，通过分类讨论可以把绝对值去掉 abs(i-j)=i-j, i > j，只要注意到 -h[j]+h[i]，i-j 都满足平行四边形恒等式，且 -sqrt(x) 为凸函数，所以 -sqrt(i-j) 满足平行四边形不等式，故 f[i] 最优决策 k[i] 单调递增，可以使用分治法求解。
    技巧：由于要讨论 i<j 和 j > i 两种情况，所以可以通过将数组 h, f 进行反转后，用同一个DP分治函数即可实现两种情况。
  2. POJ - 2823 - Sliding Window 连续区间最值RMQ查询，单调队列
    经典单调队列例题，滑动窗口区间最值查询写为数学表达式就是 f[r] = max{a[l] : r-k<l<=r}，单调队列可以实现处理极大极小值问题时，当决策空间在状态域上具有单调性，则可以通过从小到大枚举状态值 r，并用单调队列维护当前可行的最优解即可。复杂度O(n)。
  3. 洛谷 - P2698 - Flowerpot S 连续区间最值查询，单调队列
    本题中区间长度未知，要求求出最小的区间长度 len 使得存在 r-l=len 有 max A[j] - min A[j] >= d 成立（分别取区间最大值和最小值），首先可以二分答案，用单调队列check，复杂度O(nlogn)；然而这题有不用二分答案的方法，要发现当固定左端点 l 时，目标函数是关于右端点 r 单增的，所以如果 [l,r] 满足题意，则 [l,r+1] 也能满足题意，也就是最小的满足题意的 r 就是我们要求的最小长度，所以可以枚举 r，每次区间 [l,r] 满足题意，逐步增加 l 直到不再满足题意为止，中间记录下最小值就是答案，复杂度O(n)。
  4. CodeForces - 372C - Watching Fireworks is Fun 单调队列优化DP
    本题是1D1D型DP，f(i,j) = max{f(i-1,k):|k-j|<=d*(t[i]-t[i-1])}+b[i]-|a[i]-j|，注意到更新区间 [j-d*(t[i]-t[i-1]), j+d*(t[i]-t[i-1])] 是随j连续变换的，所以可以直接用单调队列维护 max{f(i-1,k)}。
    注意：循环区间条件的成立性，要将 pop_front 放在 pop_back 循环外，否则有时候不进入循环则无法执行 pop_back，以保证取到的都是在合法区间内的。

2023.5月

2023.5.1.
  1. 洛谷 - P3195 - 玩具装箱 单调栈实现1D1D平行四边形不等式优化DP
    需要非常深刻的思考，做了详细的笔记。单调栈实现的方法是一般化方法，比分治法更好，实现上也就是四步，计算新状态值、弹栈、二分、入栈。
  2. 洛谷 - P6932 - WF2017D Money for Nothing 分治法实现平行四边形不等式优化DP
    DP函数不难写出max{(d[r]-d[l])*(p[r]-p[l]}，首先贪心考虑一个商家的(d,p)值，如果di<dj且pi<pj则商家j一定不如商家i好，所以可以直接将j去掉；买家同理，如果di>dj且pi>pj则买家j一定不如买家i好，直接将j去掉。于是我们得到了买家和卖家的p关于d单调递减的离散函数，根据这个就可以证明w(l,r)=(d[r]-d[l])*(p[r]-p[l])是满足交叉大于包含的平行四边形不等式，所以满足决策单调性，于是用分治法即可解决（应该不能用单调栈解决吧，单调栈解决应该要求决策点和状态值是同一个集合中）
2023.5.2.
  1. UVA - 10859 - Placing Lampposts 树形DP
    通过求解技巧在于转换问题，是两个极小化条件，首要条件是灯的数目最少，在灯数目最少前提下，要求每个两段都有灯的边尽可能多（等价于一端有灯的边数最少），可以通过加入大常数M，将这两个问题转化为一个最优化表达式：设灯的数目为a，只有一段有灯的边数为b，且M大于b的上界，则该问题等价于最小化x=Ma+b。这样x/M就是边的数目，x%M就是只有一端有灯的边数。进一步设计状态，f(i,j)表示第i个节点的父节点灯的状态为j的最小x值，通过讨论第i个节点是否放灯进行状态转移，每棵树上进行一次dfs即可（森林中只需每次处理一颗树）
  2. UVA - 1169 - Robotruck - E3 单调队列优化DP
    通过转化状态转移方程（将区间求和用前缀和表出，与当前状态值i相关的变量就是常量可以提到min\max外部），再观察决策值集合是关于i严格递增的并且dp的状态值仅和j相关，所以可以使用单调队列优化。
  3. 蓝桥杯练习题 - 第二届省赛 - 前四道题
2023.5.3.
  1. 蓝桥杯练习题 - 第二届国赛 - 两道题, 第三届省赛 一道题：
    查找循环节：有理数a/b，只需记录每个小数点后第i位的值为A[]，并记录计算每个小数点时分子对应值a，与小数点位置的对应关系pos[a]=i（可以用map实现，因为a的最大值是分母的10倍），求小数点后第i位就是 (a*10^(i-1)%b)*10/b，其实只需保留上次小数点分子的值 a，然后 a*10/b 就是当前小数点的值。
  2. UVA - 1099 - Sharing Chocolate 状压DP
    利用二进制表示是否选择某个元素的集合（状压），首先想到构建f(x,y,S)表示是否可以通过x行y列的巧克力划分出集合S，然后发现三者必然满足xy=sum(S)，于是又可以将状态减少到两个，y=sum(S)/x，表示为f(x,S)，由于f(x,y,S)=f(y,x,S)，于是又可以每次将行与列中较小者作为状态值x，并且状态转移时只需枚举子集合S0，因为当固定x或y不变时，可通过S0计算出另一个变量例y0=S0/x，最后是枚举子集合的方法：for (int S0 = (S-1)&S; S0; S0 = (S0-1)&S0) 结果与dfs暴力枚举（优先枚举1）效果相同。
    注意：记忆化搜索实现dp时，使用 int& ans = f[i][j]; 然后最后返回时记录 return ans = 状态值;，并使用 vis[i][j] 记录下该状态是否访问过，如果访问过则直接返回 f[i][j]。
  3. UVA - 11825 - Hackers’ Crackdown 状压DP
    本题是很巧妙的问题转换，最大化指标集划分个数，且每个指标集划分中集合之并都是全集，以指标集S作为状态值，转移通过枚举子集S0，并且需要S0指标对应的集合并是全集，则可转移 f(S)=max{f(S-S0)}+1。
    注意：本题可以不用记忆化搜索直接for循环完成，因为可以从小到大枚举状态值S，从而保证转移时子状态的dp值一定是存在的。上一题不好使用 for，也正是因为无法保证子状态的dp值在之前是枚举过了的。
  4. UVA - 11995 - I Can Guess the Data Structure! 简单题
    判断是否满足栈、队列、优先队列三种数据结构。
    注意：实现队列时 queue[front++] 是弹出操作（不是 front--）
  5. UVA - 11991 - Easy Problem from Rujia Liu? 简单题
    先用map编号在放入vector数组中，可以直接用 map<int, vector<int> > 代替。
  6. POJ - 2051 - Argus 优先队列简单题
    读入结构体中部分元素值时，可以先构建一个结构体实例，然后输入到该实例中。
  7. UVA - 11997 - K Smallest Sums 优先队列合并多个递增序列（多路合并）
    核心是利用不等号对加法的保号性（如果问题改成乘法，应该只需合并单减和单增的两个序列），将n维问题转化为两两单增序列的合并，从而从O(k^klogk)降到O(k^2logk)，考虑两个单增序列的合并方法：可以先固定一维，然后移动后一个变量
A[1]+B[1] <= A[1]+B[2] <= ... <= A[1]+B[n]
A[2]+B[1] <= A[2]+B[2] <= ... <= A[2]+B[n]
...
A[n]+B[1] <= A[n]+B[1] <= ... <= A[n]+B[n]

于是变成了n路合并问题，只需要每次将每一路开头的放到优先队列中，然后就可以找到当前最小值，然后取出最小值的后继元素，继续放到优先队列里（优先队列的结构体中可以只存储A[i]+B[j]和j的值），那么合并出来的元素个数也是n个（为什么是n个呢，反证法，如果n+1可以对下一个序列产生贡献，那么一定存在之前n个中的某一个没有被选中，那么它一定小于等于n+1，所以仍然可以从前n个中的元素对后续序列产生贡献，无需n+1元素，矛盾），本质其实用到了不等号对加法的保号性，Ai+Bj<=Ak+Bl 则 Ai+Bj+C<=Ak+Bl+C（所以说如果改成乘法，我认为只需维护前n小和前n大的序列也可完成该问题），总复杂度O(n^2logn)。
41. UVA - 1160 - X-Plosives 并查集判环
在没有重边下环存在的另一种说法：如果把每个端点看作不同的字母，那么环就是存在k个边，并且k个边上的端点对应了k个不同的字母，则一定有环；也就是用n条边将n个节点连接起来，不允许重边，则一定有环（证明很容易想到，因为n个节点用n-1条边连接起来必定是一棵树，一棵树上再加一条边必定出环）

2023.5.4.
  1. Gym - 101461B - Corporative Network - E1 并查集路径压缩
    用并查集可以动态维护每个叶子节点到根节点的距离，只需在路径压缩之前更新距离 int rt=updatefa(u); dis[u]+=dis[fa[u]]; fa[u]=rt;
  2. UVA - 1428 - Ping pong 计数问题条件的拆分（用树状数组实现动态前缀和查询）
    问题可以转化为求解 C[i] = #{j:A[j]<A[i],1<=j<i}，左侧集合在i处有两个限制条件，由于A[i]和i是已知的，所以限制条件分别为 A[j]<A[i] 和 1<=j<i，暴力枚举复杂度肯定是O(nr)的（r为A[i]的上界），所以我们希望通过固定一个限制条件然后考虑另一个单独条件，从而完成求解，本题有两种做法：
  • 第一种是固定 1<=j<i，然后求解 #{A[j]<A[i]} 的个数，由于 A[i] 的范围不大只有 1e5 所以这种方法行得通，时间复杂度O(nlogr)
  • 第二种是固定 A[j]<A[i]，然后求解 #{1<=j<i} 的个数，这个方法无需 A[i] 的范围条件，所以时间复杂度O(nlogn)，这种方法更具一般性
struct Bit {  // 树状数组模板
    int t[maxn];
    void init(int n) { for (int i = 1; i <= n; i++) t[i] = 0; }
    void add(int i, int x) { for (; i <= n; i += i&(-i)) t[i] += x; }
    int query(int i) { int sum = 0; for (; i; i -= i&(-i)) sum += t[i]; return sum; }
} bit;
  1. UVA - 11235 - Frequent values - E3 区间众数（单调递增，可用树状数组实现）
    区间众数一般用分块求解，只是本题有数列单增的条件，所以相同的数一定是连在一起的，只需要记录下每段相同数的左端点和右端点，并对每段进行编号，然后将查询的区间分为三部分：[l, min(R[l], r)], [id(l)+1, id(r)-1], [max(L[r], l), r]，分别求出每一段的众数，中间一段可以用rmq倍增求解。
    注意：对区间进行编号时，直接对区间id进行+1或-1的操作，而不是先转移下标然后找id，也就是id(l)+1不一定和id(R(l)+1)一样，因为如果l是最右侧的一段区域，那么R(l)+1就没有对应区间id了。
struct RMQ {  // 2023.5.25.重写了一遍RMQ模板
    int log2[maxn];
    int f[maxn][17];  // 1<<16 <= maxn && 1<<17 > maxn
    RMQ(int a[], int n) {
        for (int i = 2; i <= n; i++) log2[i] = log2[i>>1] + 1;
        for (int i = 0; i < n; i++) f[i][0] = a[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 0; i + (1<<j) - 1 < n; i++)
                f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);
    }
    int query(int l, int r) {
        if (l > r) return 0;
        int k = log2[r-l+1];
        return max(f[l][k], f[r-(1<<k)+1][k]);
    }
};
  1. UVA - 1400 - “Ray, Pass me the dishes!” - E10! 动态区间查询最大连续和
    最大连续和如果是静态的（就是在[1,n]上求），可以直接O(n)的dp完成，用 f[i] 表示以 A[i] 结尾的最大连续和，则 f[i] = max{A[i], A[i]+f[i-1]} 。也可以用 O(nlogn) 的分治法完成，只需记录左右区间的最大前缀和和最大后缀和，线段树上合并的方法就类似分治法，记录每个子区间的最大前缀和和最大后缀和，然后就可以合并得到最大连续和。
    技巧：
    • 将区间的值val和左右端点用一个结构体记录，然后两个区间的比较可以根据题意，首先比较两个区间的值，然后比较左端点，最后比较右端点，注意只需重载小于号。
    • 结构体套结构体的初始化可以用 {} 生成写法，例如 struct Node{Segment a, b; int l, r;}; struct Segment{int l, r;} 于是可以直接生成Node{ {l1,r1}, {l2,r2}, l,r} 一个 Node 元素。
      注意：计算左孩子时候的位运算是 ls=(p<<1)，不要写反了！
  2. 蓝桥杯 - 第三届省赛 - 取球游戏 NIM游戏
    由于数据量只有 1e4，所以直接线性递推输赢就行，f[i] 表示先手拿到 i 个球是否必胜，f[i] = max{f(i-k)^1:k={1,3,7,8}, k<=i}，边界 f[0]=1。
2023.5.5.
  1. UVA - 11992 - Fast Matrix Operations 线段树区间修改区间多目标查询
    由于该题存在多个线段树，所以我使用的是指针实现的线段树，无需考虑每个线段树的具体大小，但速度会满一些（没有特意卡常应该不会超时）；该题主要是需要查询三个目标包含 sum, mx, mn（区间和、最大值、最小值），可以设计结构体 Segment 存储每个节点的这三个信息，由于维护区间和还需要区间长度，所以还需记录 len，再设计修改函数 set(x), add(x)；再对线段树中每个节点设计 Node 结构体，该结构体中存储 Node *ls, *rs; int l, r, addv, setv; Segment seg; 分别表示该节点的左右儿子，左右区间端点，add操作的懒标记和set的懒标记，seg表示该节点的信息。只需注意以下几点：
    • Segment 的初始化问题，如果对答案进行合并，那么mx初始化为最小值，mx初始化为最大值。
    • 线段树中合并，在update函数结束时父节点更新子节点的区段信息 p->seg = ls->seg + rs->seg，在build时候直接传输 Node* 地址。
    • 懒标记下传，在update，query中每次进入子节点时候都要进行懒标记下传。标记下传一般分为两步，首先是树节点的 addv, setv 的更新，然后是区段信息 seg 的更新。
      注：其实 setv 无需存储，因为set之后一定是叶子节点，并回收内存。
  2. 校赛测试4题
2023.5.6.
  1. SPOJ - NKMOU - IOI05 Mountains 动态开点线段树+二分查询
    需要用线段树维护前缀最大和，所以需要区间求和 sum 和区间前缀最大和 mxpre，问题查询就是线段树上二分答案，本题主要是数据范围为1e9所以不能用传统数组线段树，只能用动态开点线段树，时间复杂度只与操作数有关 nlogn。set 操作无需懒标记，因为set之后整个区间段都是一个值，所以回收内存。动态开点需要注意指针的使用，建议在传输节点时使用 & 而不是指针，因为 & 可以用 . 来引用内部变量，而指针需要用 -> 比较麻烦，bug不容易看出来。
struct Segment {  // 记录区间信息，要维护的值例如区间长度len，区间和sum，区间最大最小值mx,mn，区间最大前缀和mxpre
    LL len, sum, mxpre;
    void set(int x) { sum = len * x; mxpre = max(0LL, sum); }  // 与题目给出的区间操作对应，例如区间赋值set，区间增加某个值add
    Segment operator + (const Segment &rhs) const {  // 区间合并，用于合并两个子区间的信息
        return (Segment){len + rhs.len, sum + rhs.sum, max(mxpre, sum + rhs.mxpre)};
    }
};
struct Node {
    Node *ls, *rs;  // 1. 左右儿子指针
    int l, r, val;  // 区间的左右端点[l,r]，2. 区间的值val（全部为统一值（叶子节点）时才有作用）
    Segment seg;  // 区间段信息
    Node(int l, int r, int val):l(l),r(r),val(val) { ls = rs = nullptr; seg.len = r-l+1; seg.set(val); }  // 3. 初始化树节点，初始化只需区间的左右端点和初值，因为初始化的一定是叶子节点，所以是统一初值的
    bool isleaf() { return !ls && !rs; }  // 4. 判断是否是叶子节点，其实只需判断ls和rs其中一个
    void set(int x) { val = x; seg.set(x); del(); }  // 与题目给出的区间操作对应，如果有懒标记记得更新懒标记(addv)，5. 如果是重置set，则可以回收内存
    void create() {  // 6. 创建左右儿子节点
        if (!isleaf()) return;
        int mid = (l+r) >> 1;
        ls = new Node(l, mid, val);
        rs = new Node(mid+1, r, val);
    }
    void del() { if (ls) delete ls; if (rs) delete rs; ls = rs = nullptr; }  // 内存回收
    ~Node() { del(); }  // 7, 析构函数，在delete rt时会递归调用del，所以可以递归删除整棵树
};
Node *rt = nullptr;  // 树根节点
void build(int n) { if (rt) delete rt; rt = new Node(1, n, 0); }  // 8. 如果旧树存在则先删除，然后只需构建出新的树根节点
void pushdown(Node &p) { p.create(); }  // 下传懒标记，首先要创建左右儿子节点（如果没有），因为这只在update和query中使用到，并且只会在update处进行新节点创建，query只会下传懒标记
void update(int l, int r, int x, Node &p = *rt) {  // 这里的更新操作就是区间重置
    if (l <= p.l && p.r <= r) { p.set(x); return; }
    pushdown(p);
    int mid = (p.l + p.r) >> 1;  // 一定要根据mid进行递归方向判断，直接进入然后遇错返回会慢很多
    if (l <= mid) update(l, r, x, *p.ls);
    if (r > mid) update(l, r, x, *p.ls);
    p.seg = p.ls->seg + p.rs->seg;
}
int query(int h, Node &p = *rt) {  // 这是单点查找满足最大前缀和不超过h的节点的例子
    if (p.seg.mxpre <= h) return p.r;
    if (p.isleaf()) return p.l + h / p.val - 1;  // 10. 这里一定要判断是否是叶子节点，因为叶子节点已经是全部相同的val，可以得到要求的区间信息
    // pushdown();  // 如果有懒标记则这里也需要pushdown
    if (h >= p.ls->seg.mxpre) return query(h-p.ls->seg.sum, *p.rs);
    return query(h, *p.ls);
}
int query(int l, int r, Node &p = *rt) {  // 这是求区间和的例子
    if (p.l == l && p.r == r) return p.seg.sum;
    if (p.isleaf()) return p.val * (r-l+1);  // 10. 一定要判断是否叶子节点，并返回
    // pushdown();
    int mid = (p.l+p.r) >> 1;
    if (r <= mid) return query(l, mid, p.ls);
    else if (l > mid) return query(mid+1, r, p.rs);
    else return query(l, mid, p.ls) + query(mid+1, r, p.rs);
}

总的来说就是上述的10点和传统线段树不同的位置。

  1. UVA - 12419 - Heap Manager 线段树动态开点+二分查询
    如果用1表示区间被占用，0表示区间空闲，则每个区间 [l,r] 只需维护 pre, sub, suf 前缀最大连续0、字串最大连续0、后缀最大连续0的长度。还是和上面的方法一致：
  • 结构体 Info 维护区间信息，包含 len, pre, sub, suf 参数和重载 + 用于区间信息合并，本题有重置操作，所以还要 set(x) 函数。
  • 结构体 TNode 维护树上节点信息，包含 TNode *ls, *rs; int l, r, val; Info info; 含义与上题一致。需要 Node(l,r,val), isleaf(), set(x), create(), del(), ~Node() 六个函数。
  • 结构体 SEG 线段树，包含 Node *rt 为当前的树根节点。其他函数为 build(n), pushdown(p), pushup(p), update(p,l,r,val), query(p,l,r,len)，最后还可以加一个 check(len) 函数用于检查当前内存能否放入 len 长度的进程，即判断 len <= rt->info.sub。
    注意：线段树中 update,query 区间操作时，一定要根据当前节点的 mid 位置来指定下一个子节点的移动方向，而不是先进入再遇错返回，这样会浪费很多时间。（本题慢了一倍）
2023.5.7.

2023年XJTU校赛
场上和wyz一起做出了11道题，拿了校一不错的成绩，下面对剩余4题进行补充：题面

  1. XJTUOJ - #1384 - 2023XJTUPC G.和而不同 - 构造题
    条件非常构造的一道题，构造图的题往往可以从最简单的开始想，本题只要构造出链就完成了，并且链的权重就是从最大的权重向下取整开始(n+1)^2/4，然后后续每个权重依次减一就好了。证明上首先注意到如果长度m相同的两个最短路，它们的长度一定不同，所以只需考虑两个长度相邻的最短路m和m+1，如果这两个长度上不交，则说明任意两个长度的最短路长度都没有交。（只是这个确实太特殊了，用的其实就是归纳法证明）
    长度为m+1的最小边权和为s1=(k−n+2)+...+(k−n+2+m)=(2k−2n+4+m)(m+1)/2s1=(k-n+2)+...+(k-n+2+m)=(2k-2n+4+m)(m+1)/2，长度为m的最小边权和为s2=k+...+k−m+1=(2k−m+1)m/2s2=k+...+k-m+1=(2k-m+1)m/2，将二者做差s1−s2=m2+2m−nm−n+2+ks1-s2=m^2+2m-nm-n+2+k，再将k=(n+1)2/4k=(n+1)^2/4带入，该函数视为mm为变量，就会发现f(m)f(m)最小值大于0，所以两最短路一定两两无交。
  2. XJTUOJ - #1392 - 2023XJTUPC O.打则 - 数学题
    更离谱的一道题，答案就是n!n!，只是要同构证明推导。（还在想）
  • J. 大秦酒店欢迎您 - 线段树或莫队（卡常）
  • I. 喵喵喵 - 数学题
2023.5.8.
  1. XJTUOJ - #1388 2023XJTUPC K.莉可丽丝 - DAG最短路
    该题是全场最后一个提交通过的，体现出太菜了，当时太紧张做的很丑陋，于是重写了一遍。主要思路就是：由于要求两条路径边的并的权重最小值，通过思考最终状态（逆向思考），我们一定可以发现，两条最短路的并结果一定是，从1节点开始前面一段一样的路径（可能长度为0），中间分开走两条不同的路径，最后合并回一条路径上（可能长度为0），所以我们只要枚举中间分开的节点u和v，只需要预处理出每个节点开始的单源最+次短路即可（次短路只需要记录每个节点的前两短的路径，然后就可以更新了），由于是DAG图，所以可以O(n)求出单源最短路。最后枚举所有的u,v答案就是ans=min{dis[1][u].d1+dis[u][v].d1+dis[u][v].d2+dis[v][n].d1}其中d1表示最短路，d2表示次短路。
    技巧：
    • 可以用结构体存储路径长度信息（最短路和次短路），这样更新路径的函数就可以写进结构体中，代码更容易书写。
    • 拓朴排序只需要记录下每个节点的拓扑序，其实就是进队的次序，然后每次距离初始化为0的点不同，使用进队次序再次求最短路，就可以得到不同点开始的最短路径了。
int in[maxn], n, m, q[maxn], rear;
void toposort(int st) {
    q[++rear] = st;
    for (int front = 1; front <= rear; front++) {  // 每次都是取出队首元素可以这样写
        int u = q[front];
        for (int e = head[u]; e; e = E[e].nt) {
            int v = E[e].b;
            if (--in[v] == 0) q[++rear] = v;
        }
    }
}

注意：如果结构体中变量有初值，则不能用`(Dis){}`（列表初始化了），这里建议使用构造函数`Dis(int d1=INF, int d2=INF):d1(d1),d2(d2) {}`。
2023.5.9.
  1. 洛谷 - P6242 【模板】线段树 3 - 区间历史最值&区间上界限制
    在线段树中进行了详细的总结，主要是区间上界限制的复杂度证明。
  2. 洛谷 - U216697 线段树区间历史版本和 - 区间历史和
    每个节点需要将当前和 sum 和历史和 sum_ 区分开，并且同时维护这两个信息，其实可以容易想到 sum 的所有相关标记 sum_ 一定至少要有，并且还要知道在标记下传前一共历史操作作用了多少次 tv。
    详细地说：使用区间懒标记 tv 来记录懒标记下传前有多少个区间和没有更新到历史和中，由于本题还有对区间加法操作，所以需要区间加法的懒标记 addv，对于历史区间同样需要对应的懒标记 addv_，因为要记录该懒标记有多少次没有更新到下面的区间中，这种多标记更新的方法写一个更新函数更加方便 update(k, k_, t) 表示区间加法修改量和历史加法修改量，最后的 t 表示区间懒标记，也就是有多少个当前节点的 sum 和 addv 还没更新到历史中去，最关键的就历史更新是要优先在当前更新之前的：
void update(LL k, LL k_, int t) {  // Info区间信息更新
    sum_ += k_ * len + sum * t;  // 历史更新优先于当前区间更新
    sum += k * len;
}
void update(LL k, LL k_, int t) {  // TNode树上节点更新
    info.update(k, k_, t);
    tv += t;
    addv_ += addv * t + k_;  // 历史懒标记更新优先于当前懒标记更新
    addv += k;
}
最后一个重点就是标记下传，分别对历史区间和当前区间的懒标记分别进行下传并更新就好了 `t[ls].update(addv, addv_, t)`。
2023.5.10.

  1. XJTUOJ - #1387 2023XJTUPC J.大秦酒店欢迎您 - 线段树历史区间和
    非常巧妙的转换，首先由 [SDOI2009] HH的项链 可知，区间颜色数可以对询问进行离线，然后对右端点进行排序，假设当前数组中的第i个位置的元素a[i]表示从i到当前枚举到的右端点r即[i...R]中的颜色种类数，考虑每次右端点的颜色对哪些区间的颜色数有贡献，不难发现，如果最右侧加入新的颜色为color[R]，那么如果1...R-1中最右侧出现的color[R]位置在p，那么这种颜色就会对p...R的所有位置的颜色数+1的贡献。又可以发现，a[i]在[l,r]的区间和就是[i,R]:l<=i<=r中每个区间的颜色种类数之和，对于右端点在R的时刻，我们统计[l,R]上的a[i]相当于得到了所有右端点为R的颜色种类数，所以如果把历史中每次更新R的区间和全部加起来，那就是区间[l,R]上所有子区间的颜色种类数。

    • aiRa_i^R 为[i,R]的所有颜色种类数。
    • ∑i=lRaiR\sum_{i=l}^Ra_i^R 为[l,R]的所有右端点为R每个区间的颜色种类数之和（a[i]的区间和）
    • ∑j=lR∑i=ljaij\sum_{j=l}^R\sum_{i=l}^ja_i^j 为[l,R]中所有子区间的颜色种类数之和（a[i]的历史区间和，因为右端点R是从左到右逐个枚举过去的，历史和就是第一个求和符号）
      所以本题就变成了带有区间加法的区间历史和，与洛谷 - U216697完全一致。

  2. UVA - 11136 - Hoax or what - 集合最大值与最小值
    使用multiset即可动态维护集合的最大值与最小值。

  3. UVA - 12232 - Exclusive-OR - E18!!! - 异或操作转边权和
    18次错误提交，心态差点蹦了，结果发现是pdf上的I don’t know.中的引号字体不对，竟然是中文引号，在手机上pdf也是这个，pdf上应该没有字体问题，而正确的应该是英文引号I don't know.（离谱）
    本题主要就是利用异或的可加性，把每个值看作一个节点，每个二元异或操作p q v就是用边权为w的边连接p q节点，不难发现一个性质，如果两个节点u v连接在同一个根节点rt下，那么a[u]^a[v]也就是dis[u]^dis[v]，因为可以看作a[u]^a[rt]^a[rt]^a[v]，由于异或的性质中间的a[rt]消去，所以两个点的异或询问就是树上两点路径的异或和。总的来说每种操作具体实现如下：

    1. 操作1，给出p的值v，如果一个集合中的某一个点已知，那么所有点的值均已知；（所有已知的点可以连接到超级根节点上，这样他们到超级根节点的距离的异或和就是对应的值）
    2. 操作2，给出两个点p q的异或值v，可以分别找到对应的根节点rt1 rt2，用边权为v^a[p]^a[q]的边连接起来就好了；（使用这个边权还是用的异或相消的性质，注意根节点的连接处的细节，如果一个根节点的值已知，也就是他是超级根节点，那么另一个根节点就连接到其子节点上）
    3. 操作3，询问a[p1]^a[p2]^...^a[pk]，首先把所有已知值的点全部异或起来，然后剩下的可以发现，由于只能通过两两之间的异或值得到，所以只需考虑所有节点所在集合的根节点的数目，如果是偶数个，则一定可以两两配对；否则一定无法消去根节点的值，输出I don't know.。
      技巧：本题能大幅度减少代码量的技巧就是设计超级根节点（节点编号为0,...,n-1那么超级根节点可以设计为n），将所有已知值的节点全部连接到超级根节点上，这样如果getfa()得到的根节点是n，则说明该点的值已知。并且可以将操作1和操作2合并，操作1相当于合并了p n v三个点。
      其余要注意的细节也很多：
    • ^ 异或符号的优先级是低于 != 和 == 的（多数位运算操作都是），所以判断条件时候要把位运算括起来。
    • 并查集使用的时候，一定要注意在带有路径信息的集合合并时，注意是哪个根节点与另一个根节点进行合并。（例如本题中两个根节点，如果有一个根节点值已知，那么另一个根节点就作为他的子节点）
    • 读入一行的方法有很多，首先是自定义读入函数 read()，其次是在假定一行的总长度的前提下可以用 fgets 读入到字符串，然后用 sscanf 读取：
    char opt[31];
fgets(opt, 31, stdin);  // 假定一行的最大输入字符数为31（注意包括了终止符0，所以读入30个字符）
if (sscanf(opt, "%d%d%d", &p, &q, &v) == 2) v = q, q = n;  // 判断读入是2个还是3个

    这个方法是蛮好用的，只需计算出读入的字符数量上界，如果是int整数最多11个字符，加上空格分隔就是12个字符，读入n个也就是最多12n+1个字符大小就够了。

    最后一种是最慢的 getline(cin, str)，使用stringstream重载输入流：

    #include <sstream>  // 两个头文件
#include <iostream>
string str; getline(cin, str);  // 读入一行
stringstream ss(str);  // 重载输入流
ss >> a >> b; if (!(ss >> c)) c = b, b = n;  // 判断读入是2个还是3个
2023.5.11.
  1. UVA - 11987 - Almost Union-Find - E1 - 并查集合并和单点转移
    主要就是如何将集合中的单点进行转移到另一个集合中，想到每次单点转移不要转移真实的本体，而是创建一个新的节点代替原来的，将原来的节点永远抛弃掉。所以总共可能产生的节点数就是n+m个，并每次将整个集合的信息保存在根节点上就好了。
  2. UVA - 12299 - RMQ with Shifts - 线段树单点修改模板题
    只需注意读入上的问题就好了，由于每个询问长度不超过30个字符，所以交换的个数也不超过30个，直接暴力单点修改，区间最小值查询即可。
2023.5.13.
  1. UVA - 1232 - SKYLINE - 动态开点线段树，暴力修改
    注意到本题的结果不超过2e6，所以对于每次查询，暴力找该区间上以当前值为最大值的子区间，然后对其进行修改并统计答案，这样修改的最坏时间复杂度是每个点都是单点修改，那么也不会超过O(2e6*logn)，所以可以直接求解。区间信息只需记录最小值和最大值，由于默认初始全部为0，所以可以使用动态开点线段树。
  2. UVA - 11525 - Permutation - 线段树二分查询
    注意题目的问法，该问题就是从序列1,...,n中每次选出第si+1大的元素，然后从中删去。这就可以用线段树十分简单的实现，每个区间记录可用点的数目，然后二分结果删去即可。
2023.5.14.
  1. UVA - 1455 - Kingdom - 线段树区间修改+单点查询+并查集
    关键就是要把一整个州看作一个整体加入到线段树中，而不是把边的信息加入到线段树中，这样就变成线段树的区间修改+单点查询了。
2023.5.15.
  1. UVA - 1401 - Remember the Word - E3 - Trie+DP组合
    一类分解方案书的问题都可以考虑用DP组合求解诶：考虑与目标相关的方案数，设计状态转移方程并优化复杂度。对于本题有两个DP方程：

    f(i)=∑{f(i+len(x):x is s[i,⋯ ,N] prefix]}g(i)=∑{g(i−len(x):x is s[1,⋯ ,i] suffix]}f(i)=\sum\{f(i+len(x):x\ is\ s[i,\cdots,N]\ prefix]\}\\ g(i)=\sum\{g(i-len(x):x\ is\ s[1,\cdots,i]\ suffix]\}

    ff表示s[i,⋯ ,N]s[i,\cdots,N]的分解个数，gg表示s[1,⋯ ,N]s[1,\cdots,N]的分解个数，由于Trie树可以在O(M)\mathcal{O}(M)查找前缀串，其中MM为Trie的最大深度，所以转移方程最好与前缀枚举有关，不难发现f(i)f(i)是最优选择。总时间为O(NM)\mathcal{O}(NM).
    注意：数组的数据类型，有字符串和int要区别开！！
  2. UVA - 11732 - “strcmp()” Anyone? - E2 - Trie
    Trie往往和树上组合相关，一定要从一个局部结构入手，定义清楚每次计算的目标，该问题中s(i)表示s串的第i位，假设s(i-1)对应Trie树p节点，s(i)对应Trie树q节点，那么我们考虑所有之前加入过Trie树的p节点对应前缀出现次数为val[p]，则当前q节点对答案产生的贡献为val[q]*2+val[p]-val[q]=val[p]+val[q]，这部分贡献包含两个，第一个是和s(1…q)相同的前缀数并乘二val[q]*2，第二个是在第s(i)位与其不同的前缀数val[p]-val[q]，不同的字符只会被比较一次。
  3. UVA - 1328 - Period - KMP求解字符串的最小周期长度
    KMP具有求解字符串最小周期长度的作用，首先给出结论：**当(i-fail[i])|i时（a|b表示a整除b），i-fail[i]为它的最小周期长度。**通过证明下面两个引理即可证明：
    1. 在s[0,...,i-1]具有周期性（可以将其划分为几个相同的串的拼接）的前提下，i-fail[i]就是这些周期长度中最小的一个。
    2. 反之，由fail数组的性质，如果(i-fail[i])|i，则i-fail[i]一定是一个周期长度。
      两个引理都可以用画图理解+归纳法来证明，主要要看到以i结尾长度为i-fail[i]后缀对应的子串会和之前fail[i]-1结尾的字串对应相同长度的后缀相同，利用已有的周期串相同，将该子串位置进行交换，从而得到子串拼接，进一步得到周期串。
  4. UVA - 1449 - Dominating Patterns - E5 - AC自动机模板题
    模板题，主要可以学习一种向失配节点传递信息可以用逆向拓扑序完成（和SAM桶排序有点类似）。
    注意：字符串的题数组会开非常多，每个数组的数组大小一定要注意是否书写正确。还有一定要对每个数组都检查一遍初始化。
2023.5.16.
  1. UVA - 11468 - Substring - E1 - AC自动机+概率DP
    给出生成串中每个字符的概率大小，在AC自动机上不包含任何串的生成串的概率。设计状态f[i][j]表示在节点i再走j步不包含任何模式串的概率，于是可以由全概率公式（每个条件概率对每个条件发生的概率加权平均）得到转移方程

    f(i,j)=∑k=1nf(i+ck,j−1)⋅pck⋅[i+ck不包含任何模式串]f(i,j) = \sum_{k=1}^nf(i+c_k,j-1)\cdot p_{c_k}\cdot [i+c_k\text{不包含任何模式串}]_{}

    其中 i+cki+c_k 表示节点 ii 后面添加上字符 ckc_k 走到的节点。
    并且由于我们只需要判断一个节点是否包含模式串，所以可以将val[],last[]合并为一个数组match[]，表示当前节点为后缀中是否包含模式串，只需要在insert函数中将模式串终止节点设置为match[p]=1，match[v] |= match[fail[v]]即可判断后缀中所有可能的模式串。
    注意：这种运用结构体中函数较多的问题，一定要先把主程序写好，否则主程序写一半去写结构体，主程序就容易漏东西，例如这体就开始忘了ac.getfail()样例太小看不出来错误。
  2. UVA - 11019 - Matrix Matcher - E1 - AC自动机二维匹配（或者Hash也可做，还没尝试）
    将二维的模式串按行加入到AC自动机中，然后再对文本串也按行进行匹配，用cnt[r][c]表示(r,c)作为模式串左上角已匹配到的行数，假设当前文本串为第r行，如果r在c处完全匹配到模式串中的第v行，则cnt[r-v][c-y+1]++，其中y为模式串的列数，需要注意判断r-v>=0这个条件，不然可能数组溢出。
  3. LibreOJ - 111 - 后缀排序 - 后缀数组模板题
    学习了后缀数组SA的基数排序构造方法，非常巧妙，基于倍增的排序原理，加上基数排序可以在O(nlogn)求出后缀数组，只需要4倍空间大小，比SAM小很多。
2023.5.17.

进一步学习了后缀数组的高度数组height并对sa做了详细笔记，要注意理解的是sa是rk->i，rk是i->rk，height是rk->h，求解实际问题中往往枚举的是后缀的排名rk，其实可以用不同的变量来提醒自己，而不要全部都用i，容易弄错。

  1. UVA - 11107 - Life Forms - E2 - 多文本串查找最大公共(>n/2)模式串
    由于sa只能处理一个字符串，所以我们可以考虑将字符串用不同的特殊字符(直接用256+id,id为文本串的编号,这样一定不会重复)连接起来得到大文本串T(长度为N)，加入特殊字符就是为了避免两个属于不同的文本串误当做一个模式串与其他文本串进行匹配了(因为有唯一的特殊字符,所以包含特殊字符的模式串一定无法和其他文本串进行匹配)。再结合height数组，我们可以很容易地得到多个文本串之间的公共子串长度(因为公共子串一定会出现在两个文本串后缀的LCP当中)；我们同样会得到同一个文本串内的公共子串，所以我们需要记录T的每个位置i对应的文本串id用bel[i]保存，和对应该文本串的后缀长度len[i]，用flag[i]记录文本串i是否包含当前LCP，如果flag[i]的个数>n/2时，说明当前的LCP长度就是满足要求的。
    所以判断长度为L的前缀，可以通过贪心的方法，找一段连续的height>=L的文本串个数(配合flag[i]，并且还需要用bcnt表示当前连续短的编号)，如果遇到height<L说明当前连续块终止，bcnt++然后重置文本串计数器tot，于是check(M)函数的时间复杂度为O(N)。
    故可以用二分答案的方法求解最小的符合题意的前缀长度L，总时间复杂度O(NlogM)，其中M为单个文本串的最大长度。
    注意：本题查找的是至少大于一般的文本串中出现的子串，也就是tot>=n/2+1，tot为当前串在全部文本串中出现的次数。
2023.5.20.

划水了两天，弄大创浪费了好多时间～如果不能打难题，那打点水题其实也不错🐶

  1. UVA - 12206 - Stammering Aliens - E3 - 求文本串中出现次数超过m次的最长子串
    后缀数组：类似前一题的方法，二分答案长度为L的公共长度，然后用height[]进行判断出现次数是否超过m，本题要求最右侧出现的位置，所以记得多次记录max值。
    注意：使用这种方法查找长度为L的公共子串的出现次数，一定要注意当height[rk]<L时，是否有n-sa[rk]>=L（也就是后缀长度大于等于L），这种情况就是m=1的时候会出现问题。
    本题的后缀数组做法还有另一种方法：需要发现一个有趣的性质，如果排名为rk的后缀有一个出现次数>=m的前缀t，则t一定是rk-m+1,...,rk的前缀，所以问题就变成求数组height[]的窗口大小为m-1的区间最小值（滑动窗口，单调队列求解，一定要注意是长度为m-1，因为height是相邻后缀的前缀长度，所以m=1的时候必须特判，和二分方法要注意的问题相同），所有窗口的最小值中的最大值就是出现次数至少为m的最长的子串ans1，再用RMQ求sa[rk-m+1,...,rk]中的最大值就是ans2。
    注意：RMQ的log数组如果要使用则只需初始化一次log[0]=log[1] = 0; for (int i = 0; i < maxn; i++) log[i] = log[i>>1]+1;，不然速度不如while(1<<(k+1) <= r-l+1) k++;。
    Hash做法：和后缀数组第一种做法类似，二分答案L，然后将所有的长度为L的子串的Hash值全部提出来放到数组hash[]中，然后得到下标排序（将相同的Hash值放在一起），最后判断连续相同串的个数是否是大于等于m就行了。注意Hash基数的选取最好是素数。
    注意：由于hash,rank变量名和std中的重名了，所以可以选择删去using namespace std;，只需注意在使用sort, max, min, queue, set...的时候加上std::即可。
typedef unsigned long long ULL;

struct StrHash {
    ULL n, H[maxn], xp[maxn], x = 2027;
    StrHash() { xp[0] = 1; for (int i = 1; i < maxn; i++) xp[i] = xp[i-1] * x; }
    void init(char *s) {
        n = strlen(s); H[n] = 0;
        for (int i = n-1; i >= 0; i--) H[i] = H[i+1] * x + s[i];
    }
    ULL hash(int l, int r) { return H[l] - H[r+1] * xp[r-l+1]; }
}shash;
2023.5.21.
  1. UVA - 11475 - Extend to Palindrome - Manacher模板题
    要将原串通过最短的填补得到回文串可以贪心的方法，最大化利用后缀的回文性质，也就是找到最大的后缀的回文串，然后将前面一段倒序输出在原串末尾即可。

重新学习了一边SAM，用等价类的思想很容易搞清楚原理，但是构造的时间复杂度第二个while还是不会证明其线性性。

2023.5.22.
  1. SPOJ - BEADS - Glass Beads - SAM模板题，长度为L字典序最小的子串
    一个串将自身开头放到结尾，那么就是将原串插入到SAM中两遍T=S+S，这样在DAG上得到的长度为L的字符串都是原串通过交换操作得到的结果，我们只用找到其中字典序最小的一个串记为ans，通过贪心每次找最小的字典序方向，最终停止的节点p对应的len[p]就是以该字符串为后缀的最右侧的终止位置，然后于是len[p]-n+1就是原串中交换操作停止的位置。
    5.23.发现问题：上文中加粗部分其实并不显然，需要利用到T=S+S和ans多次出现时相差部分的周期性。
    要证明上述加粗部分，只需证T[1,...,len(p)]的后缀包含ans，只需证T[1,...,len(p)]的endpos集合与ans的endpos集合相同。
    如果ans只在T中出现一次，显然成立，因为endpos中就一个元素，必然是ans结束的位置；假设ans在T中出现过多次（不妨令为2次），设其出现位置从左到右分别为ans1,ans2，那么ans1和ans2必然有交集（除非S=ans，这种情况结论同样成立），因为串长度为L，而T的长度就2L，而ans2-ans1的部分一定就是ans串的周期串b（证明和KMP找最小周期串相同），再发现T=S+S，所以ans1一定会和T中第二个S存在交集a，并且我们断言这个a就是b的后缀，如果不是，那么由于周期串的性质，ans1左侧一定还存在ans串，与ans1是最左侧的ans串矛盾；并且我们发现，第二个S的交集a正好就是第一个S与ans1的差，所以a+ans1的出现次数一定和ans的出现次数相同，我们又发现这个串是T的前缀，所以a+ans1就是T[1,...,len(p)]。
    QED
    72. SPOJ - BEADS - Glass Beads
    本题还有后缀数组的做法，类似的，将T=S+S加入到后缀数组中，然后从小到大查询后缀大小，如果该后缀长度>=L，则说明找到答案，再利用height数组找到重复出现的最小的开头位置即为答案。
  2. SPOJ - SUBST1 - New Distinct Substrings - 求不同的子串个数
    本题有两种方法：第一种是SAM的DAG图上的DP，另f(u)表示从u节点出发，能走出的路径数目，于是f(u)=1+∑(u,v)f(v)f(u) = 1+\sum_{(u,v)}f(v)_{}（(u,v)(u,v)表示节点u,vu,v之间有一条有向边），那么f(0)−1f(0)-1就是本题的解，也就是从根节点出发走出的所有的路径数。
    第二种是利用排除法，使用SA中的height数组，由于每个后缀的左端点两两不同，如果存在两个子串相同，那么相同的子串长度一定是某个height中记录过，这里每个height表示所有固定左端点，右端点一次递增的height个子串，我们只需要从L*(L+1)/2中删去所有的height值就可以得到两两不同的子串个数了。
2023.5.23.

总结了下SAM的算法模板，重新思考了时间复杂度问题，但仍然无法完美证明。大创总算结束了！

2023.5.24.

重写72题的后缀数组做法。

  1. 第14届蓝桥杯国赛模拟赛A - 火柴棒数字 - 贪心
    每个数字消耗一定的火柴棍，火柴棍总数一定，求能拼出的最大数字。只需注意到相同数字肯定是位数越大越好，再是越大的数字往前排，贪心就行了。
2023.5.25.
  1. 第14届蓝桥杯国赛模拟赛B - 火柴棒数字 - 模拟
    要求模拟12小时的钟表的两个指针的夹角大小，简单的做法应该就是枚举所有可行的时刻，计算出每个时刻h:m:s下的时针旋转角度x=30h+m/2+s/120，分针旋转角度y=6m+s/10，秒针z=6s，然后做差得到A=min(|x-y|,360-|x-y|),B=min(|y-z|,360-|y-z|)，一定要注意，两个时针的夹角要小于180，也就是说需要两个方向上夹角都算一遍取最小值，结果是4 48 0
  2. 第14届蓝桥杯国赛模拟赛C - 最大公约数 - E4 - RMQ求区间gcd
    每次操作将相邻的两个元素其中一个换成两者的gcd，求将数组A全部变为1所需的最少次数。只需注意到：如果A中存在1，则直接贪心，就是最优解；如果A中没有1，则找到最短的区间其gcd为1，若该区间长度为L，则答案就是n+L-2。
    注意：RMQ细节还是很多的，以下为RMQ模板，给出了三处细节。
template <const int maxn>
struct RMQ {
    int f[maxn][17], n, *A, log[maxn];  // (1<<16) <= n && (1<<17) > n
    void init(int n, int *A) {
        this->n = n, this->A = A;
        log[0] = log[1] = 0;
        for (int i = 2; i <= n; i++) log[i] = log[i>>1] + 1;  // 初始化数组枚举的长度是<=n
    }
    void build() {
        for (int i = 0; i < n; i++) f[i][0] = A[i];
        for (int j = 1; (1<<j) <= n; j++)
            for (int i = 0; i + (1<<j) - 1 < n; i++)
                f[i][j] = gcd(f[i][j-1], f[i+(1<<(j-1))][j-1]);  // 构建f数组第三项i加长度后不用减1
    }
    int query(int l, int r) {
        int k = log[r-l+1];
        return gcd(f[l][k], f[r-(1<<k)+1][k]);
    }
};
  1. 第14届蓝桥杯国赛模拟赛
    • D - 出差 - E1 - Dijkstra
      最短路模板题，注意：记得双向边要*2边的个数，建议在maxm处就乘以2为好。
    • E - 卡牌 - E1 - 二分答案
      二分答案模板题，有个坑点，m的数据范围是long long。
    • F - 迷宫 - E6 - BFS
      很简单的题，但是就没注意到同一个点可能存在多个传送门，要用vector，而且不需要用map，就用数组即可，不然会超时。
2023.5.26.
  1. 第14届蓝桥杯国赛模拟赛 - H - E5 - 双指针
    看似简单但讨论不仔细很容易出错的题，令l[r]表示以r作为右端点向左的连续区间[r-l[r]+1,r]中每个a[i]都包含因子g的最大区间长度，如果a[r]不包含因子g，则l[r]=0。这样设的原因是我们想要考虑每次固定右端点r，讨论每次区间修改的元素，由于可以将修改的元素直接定为g，所以只需要连续区间都包含因子g即可。固定右端点r，讨论修改的元素：
    1. 修改a[r]：则ans += l[r-1]（无论a[i]是否包含因子g，都可以使得左侧以a[r]为右端点的连续区间a[r-l[r],...,r]都满足条件，总共有l[r-1]个）
    2. 若a[i]包含因子g，则我们可以修改a[r-l[r-1]-1]为g（左边第一个没有因子g的元素），并且如果它左侧还有连续区间，我们还能将其继续加上，于是当r-l[r-1]-1>=1时（左侧存在一个没有因子g的元素），ans += 1 + L[r-l[r-1]-2]。
2023.5.27.
  1. 第14届蓝桥杯国赛模拟赛 - G - E? - 修路
    没有通过全部样例60分，DP方程想的有点怪：f(i,j,k)表示走完A[1,...i]和B[1...j]最后停在k处的最短路程（k=0停在A，k=1停在B），由于最开始要从0开始，所以我们将A,B从大到小排序，最后答案为min{f(n,m,0)+A[n], f(n,m,1)+B[m]}，转移方程是

    f(i,j,0)= min⁡1⩽k<if(k,j,1)+dis(k+1,j)+Ak+1−Ai= −A[i]+min⁡1⩽k<if(k,j,1)+dis(k+1,j)+Ak+1= −A[i]+amn(i,j)\begin{aligned} f(i,j,0) =&\ \min_{1\leqslant k < i} f(k, j, 1) + dis(k+1,j) + A_{k+1}-A_i\\ =&\ -A[i] + \min_{1\leqslant k < i} f(k,j,1) + dis(k+1,j) + A_{k+1}\\ =&\ -A[i] + amn(i,j) \end{aligned}

    其中使用amn表示min中的最小值，因为min中的式子与i无关，所以可以通过前面的计算结果给出amn，假如我们求出了f(i,j,k)，则amn(i+1,j) = min{amn(i+1,j), f(i,j,1) + dis(i+1,j) + A[i+1]}，对于B和bmn的讨论同理。
    这样DP的关键还有一个就是枚举顺序的问题，通过思考只需要从小到大枚举i+j即可，从数组上看就是每次斜着往后延拓一个长度。
    还有一个问题就是初始化，只需要初始化边界内容f[1][j],f[i][1],amn[1][j],bmn[i][1]即可。但是不清楚部分大数据过不了。
  2. 第14届蓝桥杯国赛模拟赛 - I - E1 - 背包与魔法
    在01背包的基础上加入一个可以将物品重量增加K，价值翻倍的魔法，只需对原来的01背包状态转移方程在增加一个维度用于记录是否使用过魔法，f[i][j][k]表示用前i个物品装j大小的背包并使用过k=0,1次魔法，转移上和01背包类似

    f(i,j,0)= {f(i−1,j,0),j<wi,max⁡{f(i−1,j,0),f(i−1,j−wi,0)+vi},j⩾wi.f(i,j,1)= {f(i,j,0),j<wi,max⁡{f(i,j,0),f(i−1,j−wi,1)+vi},wi⩽j<wi+K,max⁡{f(i,j,0),f(i−1,j−wi,1)+vi,f(i−1,j−wi−K,0)+2vi},wi+k⩽j.\begin{aligned} f(i,j,0) =&\ \begin{cases} f(i-1,j,0),\quad j < w_i, \max\{f(i-1,j,0),f(i-1,j-w_i,0)+v_i\},\quad j \geqslant w_i. \end{cases}\\ f(i,j,1) =&\ \begin{cases} f(i,j,0),\quad j < w_i,\\ \max\{f(i,j,0), f(i-1,j-w_i,1)+v_i\},\quad w_i\leqslant j < w_i + K,\\ \max\{f(i,j,0), f(i-1,j-w_i,1)+v_i, f(i-1,j-w_i-K,0) + 2v_i\},\quad w_i+k\leqslant j. \end{cases} \end{aligned}

  3. SPOJ - LCS - Longest Common Substring - E2 - 最长公共子串
    本题还是可以使用SA的做法，与69题一样，时间复杂度O(LlogL)。
    使用SAM，将第一个串插入到SAM中，对于第二个串的每个字符c，在其中查找next[p][c]是否存在，存在则跳转p=next[p][c]，并且当前长度l++，如果找不到则跳转link[p]边，并将l=len[p]因为当前后缀一定包含len[p]的长度的后缀，所以len[p]一定是在当前搜索串中的后缀（类似AC自动机的操作，只不过这里不是完全匹配，而是最大后缀匹配，l就是当前的最大后缀匹配长度），我们可以证明跳转p的次数一定不超过第二个串的长度O(|B|)：
    这是因为当前SAM中的节点p对应的字符串集合中一定包含长度为l的后缀，由于l增加的次数最多为|B|次，而每次跳转p=link[p]会使得l的大小至少减少1，所以总跳转次数一定<=|B|。（类似SAM中第一个while循环的次数不超过n次）
  4. HDU - 4622 - Reincarnation - E2 - 判断不同的子串数目
    用SAM的最后插入节点的len[cur]-len[link[cur]]可以得到s[1,...,r-1]变化到s[1,...,r]的不同子串数目，所以只要求前缀和就可以得到s[1,...,r]中的所有不同子串数目，进一步如果每次修改起始节点l=1,2,...，然后重启SAM，用类似的方法，从而可以得到s[l,...,r]中的所有不同子串数目。
2023.5.28.

总算考完微分几何了，休息了一下下。

2023.5.29.
  1. SPOJ - NSUBSTR - Substrings - E2 - 求长度一定的子串的出现次数（SAM求后缀链接树DFS）
    在SAM一个endpos节点p存储的字符串长度就是len[p]-len[link[p]]，节点p的endpos集合大小就是每次其中存储的每个子串的出现次数（以endpos相同定义的等价类），所以首先可以通过DFS后缀链接树、或者根据len数组排序，从大到小枚举节点，计算出endpos大小（在子串插入节点处初始化endpos[cur] = 1），然后假设f[l]表示长度为l的子串对应的endpos集合大小，则f[len[link[p]]+1,...,len[p]] <-max- endpos[p]将endpos[p]与左侧给出的那些f取max，我们注意到大的串长度一定包含短串，所以我们只需要对f[len[p]]更新，然后从大到小更新f[i] = max(f[i], f[i+1])就可以得到上述效果。
    下面使用基数排序对len进行排序，其中la[i]表示len[]数组中的第i大元素对应的编号。
int c[maxn], la[maxn];  // 与SA基数排序相同，c[]为桶，la为len array，从rk值对应到id
void toposort() {
    resetn(c, 0, sz);
    for (int i = 0; i < sz; i++) c[len[i]]++;
    for (int i = 1; i < sz; i++) c[i] += c[i-1];  // 由于len[i]的值域范围一定小于sz，所以可以将sz作为桶大小
    for (int i = sz-1; i >= 0; i--) la[--c[len[i]]] = i;  // sz为桶大小
2023.5.30.
  1. HDU - 4436 - str2int - E3 - 广义SAM模板题（只用到DAG图）
    本题就是要同时处理多个文本串，SAM处理多个字符串有两种做法，第一个和后缀数组类似，就是在每个文本串末尾加入分隔符；第二种是广义SAM，就是一个SAM中同时插入多个字符串，其实方法很简单，只需在每次插入新串前重置last = 0，插入串的字符c时，判断是否当前插入的节点已经在SAM中有对应节点，如果已有则将last直接转移过去，否则类似创建nq节点，从q节点中分裂出后缀长度小于等于len[p]+1部分的子串，除了不用将link[cur]设置为nq其他与之前完全一致，这里引入split函数，只需要对insert(char c)函数进行修改：
int split(int c, int p, int q, int cur = -1) {
    int nq = new_node();
    copy(next[nq], next[q]);
    link[nq] = link[q]; len[nq] = len[p] + 1; link[q] = nq;
    if (cur != -1) link[cur] = nq;
    while (p != -1 && next[p][c] == q) next[p][c] = nq, p = link[p];
    return nq;
}
void insert(char c) {
    c = id(c); int p = last, np = next[p][c];
    if (np) {
        if (len[p]+1 == len[np]) last = np;
        else last = split(c, p, np);
        return;
    }
    int cur = new_node();
    len[last = cur] = len[p] + 1;
    while (p != -1 && !next[p][c]) next[p][c] = cur, p = link[p];
    if (p == -1) { link[cur] = 0; return; }
    int q = next[p][c];
    if (len[p] + 1 == len[q]) { link[cur] = q; return; }
    split(c, p, q, cur);
}
2023.5.31.
  1. HDU - 6704 - K-th occurrence - 后缀链接树倍增+线段树合并处理endpos集合
    本题是要求文本串T的子串T[l,...,r]在T中的第K次出现次数，首先很容易想到在后缀链接树上倍增求出T[l,...,r]所处的endpos节点（方法就是记录下每个字符串结束位置T[0,...,r]对应的SAM节点pos[r]，然后从pos[r]出发，在后缀链接树上倍增找祖先节点u中满足len[u]>=r-l+1最浅的节点），本题还要求SAM中节点的endpos集合中的第K大元素，那么如何处理endpos集合呢？考虑利用线段树进行维护，我们不用每次重建整棵树，而是对线段树进行合并（类似动态开点，但这里不能使用new节点，因为一个父节点可能存在多个儿子节点，儿子节点之间可能有重合边，而更新父节点时候如果重复更新一条边会将多余的点进行抛弃，这就会导致内存泄漏的问题，因为不清楚那些节点要删去），这里用一个数组记录下来，然后新节点就是在数组上继续向后取值。那么又有最后一个问题：时间复杂度计算已经在字符串相关算法中 - SAM - 维护endpos集合中给出。复杂度为O(nlog⁡n\mathcal{O}(n\log n常数较大，且空间要开到2nlog⁡2n2n\log 2n，本题还有后缀数组做法，见明天的笔记。
  2. 洛谷 - P3834 - 可持久化线段树 2 - E5
    可持久化线段树模板题，就是一种每个位置上用动态开点构建权值线段树，已在线段树笔记中描述细节。
2023.6.1.
  1. HDU - 6704 - K-th occurrence - 后缀数组RMQ+二分+可持久化线段树
    这是查询子串T[l,...,r]第K次出现次数的另一种做法，我们有了所有后缀的排序，于是当前T[l,...,r]的子串一定出现在第l个后缀当中，所以我们从rank[l]开始，在排好序的后缀中向上找最小的L<=rank[l]使得(L,rank[l]]中的height数组大小均>=len（二分+在height数组上构建RMQ做check函数）；同理，还要找到R>=rank[l]最大的R使得[rank[l],R)的height数组大小均>=len。于是我们就得到了子串出现的后缀对应的排名：[L,...,R]，最后要求出第K大位置，那么我们就构建根据sa[]数组构建可持久化权值线段树（已记录可持久化线段树笔记），在root[R],root[L-1]两颗线段树之差上进行查找第K大元素就OK了。
    SA的常数(1.8s,33.2Mb)一般都比SAM(2.3s,104.1Mb)要小的多，而且代码量上近似，只要有好的基本功，分别实现完每个算法最后拼接起来即可。
2023.6.3.

复习计划2：

  • [x] 基础计数
  • [ ] 递推关系
  • [x] 二维几何基础
  • [ ] 二维几何常用算法
  • [x] 凸包
  1. UVA - 11538 - Chess Queen
    在n*m的棋盘上放2个不同颜色的皇后，有多少种冲突的方法。基础题，只需要分别讨论三种冲突方法，分别为水平方向，竖直方向，两种斜线方向，然后将三者进行求和即可。
2023.6.4.
  1. UVA - 11401 - Triangle Counting
    统计用长度为1,...,n的边，不重复地选出三条边拼成不同的三角形的个数。
    1. 首先固定其中最长的一条边长x，则由三角形公式y+z>x，可得x-y<z<x，则y=1,2,...,x-1时，z的选择个数有0,1,...,x-2。
    2. 注意还要求y!=z，且不要重复记录三角形（上述计数方法每个三角形重复记录了两遍，所以最后还要/2），要求y!=z也就是去除y=z的情况，不难发现y=z时，x/2<z<x，等价于，[x+12][\frac{x+1}{2}]
2023.6.5.
  1. UVA - 11806 - Cheerleaders
    在m*n的网格图中放k个石子，并要求最外的一层上至少有一个石子的方案数。这种问题解决方法就是将**“至少一个”转化为“全集 - 任意一个都没有”**，没有任何限制条件的全集记为SS，设AA表示第1行没有一个石子，BB表示第m行没有一个石子，CC表示第1列没有一个石子，DD表示第n列没有一个石子，于是总方案数就是∣S∣−∣A∩B∩C∩D∣|S| - |A\cap B \cap C\cap D|，而求解第二项就用容斥原理即可。
    这里给出一个较为容易的方式实现容斥原理，因为容斥原理就是对于每个性质是否进行选择，并根据选择性质的个数确定正负号，而且枚举的总个数正好就是2n−12^n-1，其中nn表示性质的类别个数，于是可以使用二进制枚举，范围为0∼2k−10\sim 2^k-1，二进制中第ii为1表示选择第ii个性质，于是二进制中1的个数表示选择性质的总个数，通过其判断符号的正负。
2023.6.6.
  1. UVA - 11178 - Morley’s Theorem
    几何计算题，只需分别实现向量夹角angle(u, v)，向量逆时针旋转rotate(u, rad)和计算直线交点line_intersection(A, u, B, v)。
  2. UVA - 1342 - That Nice Euler Circuit - E2 - 平面图中的Euler定理
    二维平面图的顶点数V、边数E和面数F满足欧拉定理：V+F=2+EV+F=2+E，这个定理的证明很有意思，要用到对偶图，以及分别在对偶图上建立对偶生成树（已做笔记）。根据欧拉定理就很容易给出结果，F=2+E−VF = 2+E-V，现在就要求出图中所有的顶点（包括两边的交点，并且要去重），再通过顶点求边数（如果一个顶点在一条边的内部，则这个点能划分出新的一条边），所以我们只需要分别实现segment_proper_intersection(A1,A2,B1,B2)判断两个线段A1A2和B1B2是否正规相交（即线段的内部有交点），以及on_segment(P,A,B)判断P是否在线段AB的内部。
2023.6.8.
  1. UVA - 11796 - Dog Distance - 相对运动距离计算
    要求两个折线段的最近距离和最远距离，从每个单独的线段上看，两个在线段上运动的质点之间的相对位移一定是直线段，所以我们考虑固定A点，然后移动B点然后将问题转化为A点到B的移动线段的最短距离，这样就得到了最短距离，而最远距离一定在端点处取到。每次以两个点首先运动到拐点的一个点作为终止，所以总共时间复杂度就是P(∣A∣+∣B∣)\mathcal{P}(|A|+|B|).
    只需实现distance2line(P,A,B)点P到直线AB距离，和distance2segment(P,A,B)点P到线段AB距离。
  2. UVA - 10652 - Board Wrapping - 凸包模板题
    计算出每个矩形的四个点，然后求出凸包，最后求凸包围成的面积即可。需要实现convex_hull(P,n,hull)计算大小为n的点集P构成的凸包hull和利用三角划分求出多边形的有向面积（以逆时针方向为正向）。
2023.6.10.

今天打完了2023年蓝桥杯决赛，感觉还行，总共10题，完整做出了6题，其中一个是树形dp（需要维护每个节点的深度为1，2的前三大权重和（利用一个Max结构体，内部套一个Node结构体，记录id和权重w），分4种情况对答案进行更新），还有一个是SAM模板题（分别统计出现次数为1,...,L的不同子串的个数，L为文本串长度，只需要求出每个节点的endpos大小，然后利用len[p]-len[link[p]]为节点p对应的子串集合大小这个性质对答案进行累加求和即可ans[endpos[p]] += len[p]-len[link[p]]），前两道填空题自认为蛮难，但都有思路（一个dp，一个要用bitset模拟的快速幂），倒数第二题暴力骗了点分，应该是点分治的题，应该要复习下了。
比较可惜的是一个简单题还没想出来，给两个数组A,B长度分别为n,m，设数组C={A[i]+B[j]:i,j}，求C中第K大值，范围是n,m<=1e5。

2023.6.12.
  1. UVA - 11168 - Airport - 凸包+点到直线距离
    也是凸包模板题，题目要求的直线一定是凸包上的某一条边，若直线方程为Ax+By+C=0，则点(x,y)(x,y)到直线距离为\frac{|Ax+By+C|}{\sqrt{A^2+B^2}，然后由于所有点均在直线的一边，所以绝对值要么全部为正要么为负，所以直接记录∑x,∑y\sum x,\sum y，然后直接求出所有点到直线的平均距离，逐一枚举，取最小者即可。
    注意：判断凸包时点集合大小至少为2，所以需要特判只有1个点的情况，输出保留3位小数，所以要输出0.000。
coding > algorithm
2023算法复习
https://wty-yy.github.io/posts/35639/
作者
wty
发布于
2023年5月7日
许可协议