不要点我！！！！！！！！！！！！！！！！！！！！！！！

《关于我用AC之神的祝福一天开出2个888罐头这件事》

从别人那学的具体是 （在文字填就行）

#include<bits/stdc++.h> using namespace std; #define ar(x) array<int,x> #define pb push_back const int N=2e6+100,MOD=1e9+7; inline int qm(int x,int y=MOD-2){ int res=1; for(;y;y>>=1,x=1llxx%MOD) if(y&1) res=1llresx%MOD; return res; } inline void mod(int &x){ if(x>=MOD) x-=MOD; if(x<0) x+=MOD; } #define gc getchar() #define rd read() inline int read(){ int x=0,f=0; char c=gc; for(;c<'0'||c>'9';c=gc) f|=(c=='-'); for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48); return f?-x:x; } int jc[N],fjc[N]; void init(int n){ jc[0]=1; for(int i=1;i<=n;++i) jc[i]=1lljc[i-1]i%MOD; fjc[n]=qm(jc[n]); for(int i=n-1;~i;--i) fjc[i]=1llfjc[i+1](i+1)%MOD; } inline int CM(int n,int m){ return n<0||m<0||m>n?0:1ll*jc[n]fjc[m]%MODfjc[n-m]%MOD; } inline int calc(int x_1,int y_1,int x_2,int y_2){ return CM(abs(x_2-x_1)+abs(y_2-y_1),abs(x_2-x_1)); } int x[7],y[7],ans=0; vector<ar(3)> A,B,C; void sol(ar(3) a,ar(3) b,ar(3) c){ int res=0; for(int i=a[1];i<=b[1];++i) mod(res+=1llcalc(b[0],i,a[0],a[1])calc(b[0]+1,i,c[0],c[1])%MOD(b[0]-a[0]+i-a[1]+1)%MOD); for(int i=a[0];i<=b[0];++i) mod(res+=1llcalc(i,b[1],a[0],a[1])calc(i,b[1]+1,c[0],c[1])%MOD(i-a[0]+b[1]-a[1]+1)%MOD); mod(ans+=a[2]*b[2]*c[2]*res); } int main(){ }

点击打开链接 邀请码:sHHh

也是深夜发帖（改了内容，原帖深夜） 也是突然想起自己不是xmw学员，当时来到ACGO是真心为了学OI 真心不建议学术者来这里，比这里好的平台太多了 退站了，只有偶然回来签到和观摩，然后ZDZL有活动和广告顺便发帖子宣传一下吧 所以严格意义上来说，这是最后一篇个人帖子了 后期我会把精力放在学业和OI上，以及ZDZL和个人团队 我也没有什么在ACGO的个人遗产，可能只有两个号而已 再见了，可以qq联系我，CF和AT是小号名，洛谷同名

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个具体值 1.2 题目背景、允许、禁止与限制 背景： 有一张图，nnn 个设备和 mmm 条物理连接，第 iii 条物理连接有一个权值 wiw_iwi 允许： 对于从设备 AAA 到设备 BBB 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个 我们记设备 AAA 到设备 BBB 之间通信的稳定性为 AAA 至 BBB 的所有可行路径的稳定性中最高的那一条 求任意两点之间的通信稳定性（若不存在道路，则输出 −1-1−1） 1.3 题目数据范围与猜测 O(n log m)O(n~log~m)O(n log m) 1.4 一句话概括题意 有一张无向带权图 求任意两点所有路径经过边中最小值最大是多少 2 题目破题推导 2.1 第一步：正向思维转逆向思维 我们考虑将“最小值最大”转化，变为一张图的最大生成树上两点之间最小的那条边 2.2 第二步：证明 命题：一张图上的节点 AAA 到 BBB 之间所有路径经过边中最小值的所有可能中的最大值 === 一张图的最大生成树中 AAA 设无向图 G=(V,E)G=(V,E)G=(V,E)，每条边 e∈Ee\in Ee∈E 拥有边权 w(e)w(e)w(e)。 对图中任意两点 A,BA,BA,B，定义 f(A,B)=max⁡P 是G中A→B的路径{  min⁡e∈Pw(e)  }f(A,B)=\max_{\substack{P\text{ 是}G\text{中}A\to B\text{的路径}}} \Big\{\;\min_{e\in P} w(e)\;\Big\} f(A,B)=P 是G中A→B的路径 max {e∈Pmin w(e)} f(A,B)f(A,B)f(A,B) 的含义：枚举 AAA 到 BBB 的全部路径，每条路径取路径上边权的最小值，再对这些最小值取最大值。 设 TTT 是图 GGG 的一棵最大生成树，PTP_TPT 代表树 TTT 上 AAA 到 BBB 的唯一路径。记 valT=min⁡e∈PTw(e)val_T=\min_{e\in P_T} w(e) valT =e∈PT min w(e) 求证： f(A,B)=valT\boldsymbol{f(A,B)=val_T} f(A,B)=valT 证明： * 第一步：证明 f(A,B)≥valTf(A,B)\ge val_Tf(A,B)≥valT 最大生成树 TTT 的所有边都来自原图 GGG，因此树上路径 PTP_TPT 也是原图中一条合法的 A→BA\to BA→B 路径。 根据 f(A,B)f(A,B)f(A,B) 的定义：f(A,B)f(A,B)f(A,B) 是所有合法路径的 min⁡{w(e)}\min\{w(e)\}min{w(e)} 的最大值。集合的最大值一定大于等于集合中任意一个元素。把路径 PTP_TPT 纳入考虑，得到 f(A,B)  ≥  min⁡e∈PTw(e)=valTf(A,B)\;\ge\; \min_{e\in P_T}w(e) = val_T f(A,B)≥e∈PT min w(e)=valT * 第二步：证明 f(A,B)≤valTf(A,B)\le val_Tf(A,B)≤valT （反证法） 反设 f(A,B)>valTf(A,B) > val_Tf(A,B)>valT 。 根据 f(A,B)f(A,B)f(A,B) 的定义，则原图中一定存在某条路径 P′P'P′，满足 min⁡e∈P′w(e)=X>valT\min_{e\in P'} w(e) = X > val_T e∈P′min w(e)=X>valT 该式等价于路径 P′P'P′ 的每一条边权都满足 w(e)≥X>valTw(e)\ge X>val_Tw(e)≥X>valT 。 回顾最大生成树的Kruskal算法：边按权值从大到小排序，依次加入，不构成环则保留。 valTval_TvalT 是树上 A,BA,BA,B 路径的最小边权，也就是树上 A,BA,BA,B 正是依靠这条权为 valTval_TvalT 的边才完成连通。 但路径 P′P'P′ 的全部边权都严格大于 valTval_TvalT ，说明在Kruskal处理完所有权大于 valTval_TvalT 的边时，AAA 与 BBB 就已经连通。 此时权值为 valTval_TvalT 的边不再起到连通两个连通块的作用，按照Kruskal规则，这条边不会被选入最大生成树。 这与“权值为 valTval_TvalT 的边属于最大生成树 TTT 的 A−BA-BA−B 路径”矛盾。 故假设不成立，因此 f(A,B)≤valTf(A,B)\le val_T f(A,B)≤valT 合并不等式 联立 {f(A,B)≥valTf(A,B)≤valT\begin{cases} f(A,B)\ge val_T\\ f(A,B)\le val_T \end{cases} {f(A,B)≥valT f(A,B)≤valT 得到 f(A,B)=valT\boldsymbol{f(A,B)=val_T} f(A,B)=valT 3 模型匹配 最大生成树用最小生成树模板改一下（排序改为降序） 树上 AAA 到 BBB 的最小值用LCA。但是我们发现题目中并没有提到“图一定连通”，说明可能会有森林，但是依旧在原数组上做LCA即可 4 最终代码（禁止抄袭，仅用于参考） 易错点： LCA的初始化dfs传入的时候第二个参数（根节点的父亲）应该是 000 而非负数，使用负数会越界

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个具体值 1.2 题目背景、允许、禁止与限制 背景： 有一个 1,2,...,n1,2,...,n1,2,...,n 的排列 aaa 允许： 要求记录排列中有多少长度为奇数的子序列中位数是 bbb 1.3 题目数据范围与猜测 n≤100000               1≤b≤nn \le 100000~~~~~~~~~~~~~~~1\le b \le nn≤100000               1≤b≤n 1.4 一句话概括题意 有一个排列，统计其中长度为奇数的子序列的中位数为 bbb 的个数 2 题目破题推导 2.1 第一步：正向思维转逆向思维 我们记一个数列 ppp： * 若 ai<ba_i < bai <b 则 pi←−1p_i\leftarrow -1pi ←−1 * 若 ai>ba_i > bai >b 则 pi←1p_i\leftarrow 1pi ←1 * 若 ai=ba_i =bai =b 则 pi←0p_i\leftarrow 0pi ←0 那么只有奇数长度的序列和为 000 时才能确保“长度为奇数的子序列中位数为 bbb” 接下来可能有些人会有疑问： * 中位数的定义是中位数是指把所有元素从小到大排列后，位于中间的数。 万一这个子序列和是 000 但是中间没有元素 bbb 呢？ * 不会存在！ 因为如果这个和是 000 且长度为奇数，当且仅当含有一个 000 和若干组 1,−11,-11,−1 其他情况要想让和是 000，只有可能含有若干组 1,−11,-11,−1，而这样 2×任意数2\times 任意数2×任意数 一定是偶数，不满足题目中提到的“奇数长度子序列” 2.2 第二步：数学性质 如果从 pj(p[b]=j)p_j(p[b]=j)pj (p[b]=j) 开始从左往右连续的序列总和为 sumsumsum，则为了让整个子序列总和为 000 的同时满足“中位数”的要求，需要在左边选出一个序列，总和为 −sum-sum−sum 同时，右边可能有多个序列总和都为 sumsumsum，因此需要统计所有个数 3 模型匹配 用 ppp 的时候要注意一下，不能有负数，加一个 nnn 的偏移量 4 最终代码（禁止抄袭，仅用于参考）

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最小值 1.2 题目背景、允许、禁止与限制 背景： 有一个很长的彩带，有 nnn 个彩珠，它们可以被分成 kkk 组，分别坐落在彩带的不同位置上 允许： 剪一段彩带，保证这个彩带中含有所有 kkk 种珠子 求最小彩带的裁剪长度 限制： 可能存在某些坐标并没有珠子 可能存在一个坐标有多颗珠子 1.3 题目数据范围与猜测 n≤106          1≤k≤60          0≤珠子位置<231n \le 10^6~~~~~~~~~~1\le k \le 60~~~~~~~~~~0\le珠子位置<2^{31}n≤106          1≤k≤60          0≤珠子位置<231 1.4 一句话概括题意 有一个数轴，有若干珠子坐落在上，求分割最短距离使得该范围内包含所有种类的珠子 2 题目破题推导 2.1 第一步：以终为始 以终为始思考：要想使得答案最短，这个区间的样子应为？ 先给一个基本猜测：至少存在一个区间，使得该区间左右端点均坐落在彩珠上且 左→右左 \rightarrow 右左→右 这个区间内包含所有种类的彩珠 2.2 第二步：数学推导+证明 假设我们有一个任意合法区间 [l0,r0][l_0,r_0][l0 ,r0 ]，l0l_0l0 和 r0r_0r0 可以是数轴上的任意实数，满足这个范围内含有全部 kkk 种彩珠 * 处理左端点 如果 l0l_0l0 本身就在某个彩珠上，记 l1←l0l_1 \leftarrow l_0l1 ←l0 如果 l0l_0l0 并不在某个彩珠上，找到其右边第一个彩珠的位置，记作 l1l_1l1 * 处理右端点 如果 r0r_0r0 本身就在某个彩珠上，记 r1←r0r_1 \leftarrow r_0r1 ←r0 如果 r0r_0r0 并不在某个彩珠上，找到其左边第一个彩珠的位置，记作 r1r_1r1 原来的彩珠范围内 [l0,r0][l_0,r_0][l0 ,r0 ] 内的所有彩珠，一定都留在 [l1,r1][l_1,r_1][l1 ,r1 ] 的范围内，因为我们只是调整了空白区域的位置 同时 r0−l0≥r1−l1r_0-l_0\ge r_1-l_1r0 −l0 ≥r1 −l1 ，所以一定保证这会比原来结果好 那么一旦存在多个结果均比原来结果好，就说明一定存在一个区间使得左右端点在彩珠上且满足截取要求 2.3 第三步：限制 那么我们就把一个数轴上所有实数区间变成若干个区间，这些区间是任意两个点位置的左右端点 这样有左右端点的限制了 3 模型匹配 每个点按位置从左到右排序 然后大概类似一个双指针：head和tail分别都是珠子编号 tail不断++，直到扩展区间能完全包含 kkk 种珠子，更新答案，然后收缩头部直到区间不能完全包含 kkk 种珠子 4 最终代码（禁止抄袭，仅用于参考）

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最大值 1.2 题目背景、允许、禁止与限制 背景： 有一个 h×wh\times wh×w 的 0/10/10/1 矩阵 楼梯是由若干连续行中填有 1 的格子集合组成的。在每一行中，被选中的格子必须形成一个连续的段。 同时，满足以下条件： * 每下一行的选中格子数量不得少于紧邻其上的上一行 * 每行中最左边的选中格子必须位于同一列 允许： 矩阵中 111 代表可以作为楼梯的一部分 求这个楼梯最多可以由多少 111 组成 1.3 题目数据范围与猜测 h×w≤2×105→O(hw)h\times w \le 2\times10^5\rightarrow O(hw)h×w≤2×105→O(hw) 1.4 一句话概括题意 有一个矩阵，求这个矩阵中构成楼梯的最大值 2 题目破题推导 2.1 第一步：以终为始 要想得到最大楼梯，楼梯一定是这样的 也就是若干个相同高度的+逐渐比自己低的，比自己后面低的，比自己后面的后面低的... 2.2 第二步：分情况讨论 * 当前这一项和自己一样高 那太好了，可以直接加入我们的楼梯队列中 * 当前这一项比自己高 那也没关系，可以把上面那部分消掉 * 当前这一项比自己矮 那很可惜，它只能间接地作为我的后面了（当然有可能不适用） 这里之所以是间接的，因为有可能我的后面，它的前面有和它一样高的或者比它矮的 2.3 第三步：边界思维 注意不存在右边比自己矮的柱子的情况，dp应该直接置 000 3 模型匹配 * 单调栈模板 这里需要维护单调递增栈，为了维护当前点后面第一个比自己低的 * dp的时候循环是从 www 到 111，这样才能依靠之后列的答案推前面的若干列 然后dp就可以是： dp[i]=dp[r[i]]+a[i]∗(r[i]−i)dp[i] = dp[r[i]] + a[i] * (r[i] - i) dp[i]=dp[r[i]]+a[i]∗(r[i]−i) * dp[i]dp[i]dp[i] 表示考虑到第 iii 列，最大楼梯大小 r[i]r[i]r[i] 表示当前这个柱子右边（后面）第一根比自己矮的 dp[r[i]]dp[r[i]]dp[r[i]] 表示右边（后面）第一根比自己矮的柱子最多有多少 a[i]a[i]a[i] 表示当前这根柱子高度 r[i]−ir[i] - ir[i]−i 表示当前这个柱子到右边第一个比它矮的柱子之间的距离，高度 ×\times× 距离 === 整体方块大小，这里不需要考虑消去的那部分，因为那部分根本没算进来 两部分相加就可以得到当前答案 4 最终代码（禁止抄袭，仅用于参考）

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个具体值 1.2 题目背景、允许、禁止与限制 背景： 有一个单词集合 SSS 允许： 一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀 求这个集合中有多少集合使得里面所有单词都互相安全，空集永远是安全的 1.3 题目数据范围与猜测 O(n4)O(n^4)O(n4) 1.4 一句话概括题意 有一个字符串集合，求这个集合中有多少集合使得里面所有字符串都互相安全，空集永远是安全的 2 题目破题推导 2.1 第一步：数学思考与证明（反证法） 思考单调性： 把所有字符串按字典序排序后，如果对于一组字符串 i,j,ki,j,ki,j,k 使得 j<i,k<jj < i,k < jj<i,k<j 且均不为前缀，则 kkk 对于 iii 一定不为前缀 证明： 假设存在一组字符串 i,j,ki,j,ki,j,k 使得 k<j<ik < j < ik<j<i 且均不互为前缀，但 kkk 为 iii 的前缀。 那么就说明 iii 的开头一部分完全等于 kkk 发现 k<jk < jk<j 说明在某一位会出现 ki<jik_i < j_iki <ji 那么由于 iii 的开头一部分完全等于 kkk，会出现 ii<jii_i < j_iii <ji ，因此 i<ji<ji<j 但是这时与求证定义矛盾，因此可以证明把所有字符串按字典序排序后，如果对于一组字符串 i,j,ki,j,ki,j,k 使得 j<i,k<jj < i,k < jj<i,k<j 且均不为前缀，则 kkk 对于 iii 一定不为前缀 2.2 第二步：边界意识 因为这里面说了“空集永远是安全的”，因此记录的时候要始终多加 111 代表空集 还有因为 n≤50n\le 50n≤50，因此选择的可能性（集合的组合）是 2502^{50}250 3 模型匹配 那就是一个很简单的dp，这里由于是所有方案可能性都要考虑到，所以要注意初始化和累加 4 最终代码（禁止抄袭，仅用于参考）

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个具体字符串 1.2 题目背景、允许、禁止与限制 背景： 有一个大字符串 SSS 和小子串 TTT 允许： 需要反复找到 SSS 中包含的第一个 TTT，然后把它删除 限制： 有可能 SSS 删除完毕之后会产生新的 TTT，也可能同时存在多个 TTT 1.3 题目数据范围与猜测 1≤∣S∣≤106→O(∣S∣2×∣T∣)1 \le |S| \le 10^6 \rightarrow O(|S|^2\times |T|)1≤∣S∣≤106→O(∣S∣2×∣T∣) 1.4 一句话概括题意 重复删除大字符串中第一次出现的小子串，直到不存在这样的子串 2 题目破题推导 2.1 大拆小，小组大 一步步来，先考虑暴力： 暴力的缺陷就是在于每次匹配不成功，大串和子串都要从头开始重新匹配。 那么有没有什么方法可以避免这种情况呢？这种情况发生的主要原因就是因为我不知道需要回退到哪里，因此为了避免回退的不够多导致无法匹配，只得从头开始 接下来我们就思考如何设置回退的长度，使得既能不浪费时间，还能正确实现？ 先想如果快速实现的话，逻辑应该是怎样的： 应该是一直匹配匹配...，突然到某一位的时候发现匹配长度 === 目标子串长度，这时候我们将子串匹配状态退回到“把子串删除后主串那个位置匹配了多少位子串”，主串不退回 你发现了吗，这样既能满足时间复杂度 O(∣S∣)O(|S|)O(∣S∣)，又能满足正确匹配 3 模型匹配 kmp计算回退长度 栈，因为需要回退不定长度，因此普通栈时间开销很大，因此需要数组模拟栈 栈是干嘛的呢？因为添加和删除可以看成是后进先出，所以栈记录的是字符串中的下标 4 最终代码（禁止抄袭，仅用于参考）

我的妈呀，也是在第32发抽中小哑了好吧，虽然不是我想要的海瑟，但至少不是画中女郎好吧，我已经知足了，得吃😋

你的存在并没有把我从黑暗中拉出来，可你在的时候我努力改变，可我没能做的。 那晚的灯光太刺眼了，刺眼到看不清你，你的名字也忘了，甚至连那句我爱你都没有说出来。 我淋过雨也吃过苦，但是爱你的话没能说出口，一段伤是走不出来的，不然就忘了她。 曾经你犹如含苞待放的花骨朵，现在你是我的掌中宝。 为何我总是一个人孤单的活着，聊天记录你删除，但记忆能删除吗？

本期主角： 看看他的主页 就是那种很平平无奇，他是怎么得欢乐赛第1名的呢？ 我采访了他 果然他用了AI,官方赶紧制裁他 后续； 大家赶紧点赞，防止官方看不到，这种人赶紧制裁

ac狗难得灵验一回 在−109-10^9−109秒后，贴主决定发帖 不是我怎么老RE啊？ ACGO给我送榨菜来了\color{cyan}{ACGO给我送榨菜来了}ACGO给我送榨菜来了 不是我怎么老RE啊？\color{cyan}{不是我怎么老RE啊？}不是我怎么老RE啊？ 不是我怎么老RE啊？(已红温)\color{red}{不是我怎么老RE啊？(已红温)}不是我怎么老RE啊？(已红温) sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!! sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!! sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!! sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!! sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!! sh∗t!!!!!!!!!!\color{red}{sh*t!!!!!!!!!!}sh∗t!!!!!!!!!!

OK呀家人们有没有兄弟姐妹想要看我写什么的可以多多评论

本人现在是已经过了三级，正在考四级（虽然不是很高）。但是正常我应该是已经获得了GESP三级的勋章，但是我没有（已实名），有没有人知道是为什么，发到评论区谢谢

我个人推断应该是AC君辞了。然后换了新的人，整治了社区，估计以后ACGO会成僵尸GO一个冷清的社区/学术的社区