2025/7/9 报道
报道，没什么好说的，坐了一上午的动车，下午才到，晚上安排自我介绍，
然后切了点水题。
宿舍6个人，福建2个，绍兴1个，杭州2个，江苏1个。
2025/7/10 上课【贪心】
还在舒适圈范围内）
But
目睹六年级巨佬手撕黑题，恐怖如斯
原来是天津第一小学生，更恐怖了
2025/7/11 上课【计数and容斥】
也还在舒适区。
学习总结写了，找不到了（
2025/7/12 模考【01】
排名20/20
爆了，刚来太紧张，发挥失常。
2025/7/13 上课【字符串】
死去的AC自动机重新攻击我的大脑，
没怎么听懂，所以没有总结（bushi
2025/7/14 模考【02】
排名12/20
又爆了
02模考总结被03模考的模考总结的总结覆盖了（
2025/7/15 模考【03】
连续两天模考（
又一次爆了
排名 6/20
分数150/400
赛中时间记录
8:30 开始模考
8:30-8:57 想T1
8:57-9:06 写T2
9:06-10:09 写T1
10:09-10:38 写T4
10:38-11:14 继续写T1
11:15-11:16 检查代码
11:16-11:24 看T3
11：42-11：58 写T4
11:50 模考结束
| T1 | T2 | T3 | T4 | |
| 期望得分 | 50 | 100 | 0 | 40 |
| 实际得分 | 50 | 100 | 0 | 0 |
T1
题意：
T 组数据，每次询问给定两个数 n,q
初始 n 个格子有砖， q 次询问，每个格子上有 ai 块砖（ i>=0，ai∈{n-1,n,n+1} ）。小G从0号格子开始一格一格往后搬砖，当他在第 i 个格子，设当前所在格子有 x 块砖，他会将这 x 块砖分别拿走放到编号 [max(n,i+1),i+x] 的格子上,每个格子各一块砖，多余的砖丢弃。
对于每次询问给定一个数 y ，当他走到第 y 个格子的时候，第 y 个格子上有多少块砖
（n≤1e5，T≤10，q≤1e5，n≤y≤1e18）
开局看T1，思考满分做法，想不到，先做其他题
写完T2回来继续看T1，思考 subtask2 和 subtask3
建 a序列 的 差分数组，O(1) 更新新的砖 ，一直更新到 1e6 ，每到一个新的位置就把砖数存到 ans 数组里，查询时直接输出 ans[x] ，复杂度O(x)
测样例的时候 数据 4 and 5 WA了，调了好久发现更新区间[L,R]如果L>R时不需要更新
TLE50pts
T2
题意：
定义一个字符串是好的，当且仅当可以重排为回文串。给定字符串 s ，求 s 中最长的好子序列的长度
(|s|≤1e6)
幼儿园题，秒了
(11：15检查代码时发现没写freopen，差点挂了)
T3
题意：
给定 n,k 和 k 颗有 n 个点的树。对于每个点对(i,j)，求出其在每棵树上的路径经过的点(含端点)的交集大小
(1≤n,k≤500)
特殊性质：满足这 k 棵树均为链。注意 1 不一定是链的端点。
思考了下特殊性质，感觉代码不怎么好写，不如去想T4
T4
题意：
给定一个 n*m 的网格图，图上 '$' 表示宝藏，其余都是空地，有两条大河，一条为纵，一条为横，长度都是无穷大，宽度至少为1，
小P知道两条大河经过的宝藏个数和为 k ，注意两条大河相交的地方宝藏个数被计算了两次贡献，
请求出放置两条大河的合法方案数有多少种
(n,k≤1e5，m≤100)
设 hc[i] 和 lc[i] 分别为 行的 和 列 宝藏数的前缀和
hs[i] 和 ls[i] 分别为 横河 和 纵河 宝藏数和为 i 的方案数
可以通过 hc 和 lc 求出 hs 和 ls
1 for(int a=1;a<=n;a++){ 2 for(int b=a;b<=n;b++){ 3 hs[hc[b]-hc[a-1]]++; 4 } 5 }
求 ls 同理
枚举 i 到 k ，所有 hs[ i ]*ls[ k-i ] 的和就是ans
1 for(int i=0;i<=k;i++){ 2 ans+=(hs[i])*(ls[k-i]); 3 }
复杂度O(n²) ，期望40分，but最后写挂了（
2025/7/16 休息日【01】
我报的项目：桌游，电影
早上：先去看《飞屋环游记》然后去棋牌室玩UNO
下午：先去棋牌室玩三国杀，我超，蒸，然后去看《红海行动》
晚上：自习
2025/7/17 上课【数据结构优化】
知识点
1.启发式合并，小的结构合并到大的结构上，几乎适用于所有数据结构合并操作
2.线段树合并，合并两颗线段树重叠的部分
之前只会用普通线段树和求区间最大子段和，今天恶补了其他用法（
B题
(原CF 洛谷CF600E)：
直接用启发式合并暴力从叶子节点合并到根， 每次合并时把小的树合并到大的树上，用迭代器枚举map的每个元素，
如果这个颜色数量比原来的答案更多则直接更新，如果相等则加上，
写这题的时候顺便学了下迭代器。
for(map<int,int>::iterator j=ma[pos[to]].begin();j!=ma[pos[to]].end();j++){ ma[pos[now]][j->first]+=ma[pos[to]][j->first]; if(ma[pos[now]][j->first]>mx[now]){ mx[now]=ma[pos[now]][j->first]; ans[now]=j->first; } else if(ma[pos[now]][j->first]==mx[now])ans[now]+=j->first; }
F题
(洛谷 4556)
树上差分优化发放救济粮的操作，起点终点差分数组增加，两点的LCA的父节点差分数组减少
每个点建一颗动态开点权值线段树，发放的操作完成后从叶子节点向上合并线段树，也可以用和B题相似的做法，计算答案时查找最大值，
求LCA只会用树剖求的蒟蒻（
2025/7/18 上课【计算几何】
emm只听懂了凸包的部分
知识点
1.凸包，凸包的性质，周长最小，面积最小
2.斜率优化dp
3.李超线段树
Andrew算法
每个点按x升序排序，从左到右每加入一个点
则判断此时栈顶的点与次栈顶的点的斜率和新点与次栈顶的点的斜率大小关系
若栈顶的斜率大，则栈顶的点出栈，重复操作直到栈顶的点斜率更小，然后新点入栈，
此时下凸壳就求完了,上凸壳用相同的方法再跑一遍
就能拼成一个完整的凸包了
A题
(凸包模板题 洛谷 2742):
每加入新的一个点就判断这个点与栈顶的点的斜率大小，如果加入的点斜率小，
则出栈，直到遇到斜率更小的点，求完下凸壳后求上壳，两个凸壳拼起来就是完整的凸包
B题
(信友队 1545)
题意：给定 n 个点，求围成的凸包面积
再打一遍凸包模板，设有 n 个点,则一共能分成 n-2 个三角形，用海伦公式求出来每个的面积相加即可，
题目没说答案要两位小数，因为这个浪费我一个小时（
D题
(洛谷 1034)
枚举每个点加入的矩阵，用类似状压的方式暴力搜索
2025/7/19 模考【04】
大爆
排名 12/20
分数74/400
赛中时间记录
8:30 开始模考
8:30-10:02 写T1
10:02-10:14 写T3
10:14-10:32 写T2
10:32-11:02 写T4
11:02-12:00 思考T2和T4
12:00 模考结束
| T1 | T2 | T3 | T4 | |
| 期望得分 | 50 | 30 | 20 | 24 |
| 实际得分 | 50 | 0 | 20 | 4 |
T1
题意：
给定两个01串 a 和 b ，对于 a ，可以拿出一个与 b 长度相同的子串 c ，统计 b 与 c 对于位置字符不同的数量，记作 f(b,c)
求所有的 f(b,c) 中是偶数的数量
(1≤|b|≤|a|≤1e6)
让人想到异或，思考预处理出1的个数为偶数的所有数，异或后查找一下有没有这个数
寻找规律，发现一位的数1的数量为偶数数的数量为1
两位的为2，三位的为4，四位的为8，emm没用,而且2^1e6也存不下
试着求出a的boder，手模一下，发现好像也没用，不死心，试着用kmp能不能做
还是不行，再试试哈希，复杂度也不对，再想着用线段树，不行，
看了下特殊性质，因为 b 为 a 的循环节， 所以答案重复计算了(|a|/|b|-1)次，只要求出第一遍，乘|a|/|b|即可，
于是开始往计数的方向想，没想出来
思考O(n²)暴力的优化，这样check的复杂度必须是O(1)的，根本优化不出来，最后只能交个暴力
(想了一堆方法，早该想到O(1)的check应该是像判断奇偶性这样的简单check，整场比赛完全没有往这个方面想)
T2
题意：
给定 n,m,q, 有 n 个结点，m 种传送门，m 个 n*n 的矩阵 w1~m , q 次询问，第 i 种传送门在结点 u,v 之间的传送时间为 wi,u,v
每次询问给定 s,t,k
求点s到点t换传送门次数不超过k的最小时间
(n,m≤60，wi,u,v≤1e6，q≤1e5，k≤1e3)
第一眼分层图最短路，和P4568很像，复杂度O( (nm+nm)log2nm ),应该可以，但空间复杂度巨大，然后就交了个暴力
T3
题意：
T次询问，每次询问给定一个长度为 n 的排列 p ，你需要将它分成两个不相交的子序列 a,b , 使得 LIS(a)+LDS(b) 最大
(1≤n≤1e5，1≤T≤10)
T1不会写快疯了，直接交暴力
T4
题意：
给定 n,m,k,w 和一个长度为 n 的数列 x ，m 次操作每次操作把第 p 个元素修改为 v，
记 x1，x2，x3...xn 经过排序的序列为 x(1)，x(2)，x(3)...x(n)，定义能量指标为
∑⌊x(i)ik/w⌋
每次操作后求出 x 的能量指标对998244353取模的结果
(1≤n,m≤1e5，1≤k≤5，1≤w≤20，1≤xi,v≤1e9)
先交了暴力，然后开始想，没什么思路
2025/7/20 上课【数列&矩阵】
知识点
1.矩阵
2.拉格朗日插值，群论，扩展欧几里得定理，其他一些数论
A题
(原CF 718C 洛谷CF718C)
因为一些细节，重构了好几次代码，调了一整天
导致一天就只写了一题，直接当题解看就行
题意：
有一个长度为 n 的序列 a ，m 次操作
有两种操作，第一种是区间修改
第二种是求区间里所有的 f(a[i]) 的和
f(x) 是斐波那契数列的第 x 项
f(1)=1，f(2)=2
f(x)=f(x-1)+f(x-2)(x>=3)
(1≤n,m≤1e5，1≤ai≤1e9)
矩阵快速幂板子题
动态开点线段树维护矩阵，再用矩阵快速幂求斐波那契数列
矩阵快速幂可以 log n 求斐波那契数列的第 n 项
设
0 1 1 1
1 1 0 0
矩阵 A 矩阵 B
C = (A*B)n
则 C0,1 为斐波那契数列的第 n 项
事实上，矩阵快速幂可以 log n 求任何线性函数。
查询和修改的操作和普通线段树一样，只是维护对象变成矩阵，可以手写一个数据类型
AC代码
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int maxn=2e5+200; 7 const int mod=1e9+7; 8 #define mid (l+r>>1) 9 #define ls (pos<<1) 10 #define rs (pos<<1|1) 11 #define int long long 12 int n,m,a[maxn]; 13 struct Node{ 14 int m[4][4]; 15 void clear(){ 16 for(int i=0;i<4;i++){ 17 for(int j=0;j<4;j++){ 18 m[i][j]=0; 19 } 20 } 21 } 22 void init(){ 23 for(int i=0;i<4;i++)m[i][i]=1; 24 } 25 void prt(){ 26 for(int i=1;i<=2;i++){ 27 for(int j=1;j<=2;j++)cout<<m[i][j]; 28 } 29 } 30 bool check(){ 31 if(!m[1][1])return 0; 32 if(m[1][2])return 0; 33 if(m[2][1])return 0; 34 if(!m[2][2])return 0; 35 return 1; 36 } 37 Node operator +(const Node &x)const{ 38 Node res; 39 res.clear(); 40 for(int i=1;i<=2;i++){ 41 for(int j=1;j<=2;j++){ 42 res.m[i][j]=(m[i][j]+x.m[i][j])%mod; 43 } 44 } 45 return res; 46 } 47 Node operator *(const Node &x)const{ 48 Node res; 49 res.clear(); 50 for(int i=1;i<=2;i++){ 51 for(int j=1;j<=2;j++){ 52 for(int k=1;k<=2;k++)res.m[i][j]=(res.m[i][j]+m[i][k]*x.m[k][j])%mod; 53 } 54 } 55 return res; 56 } 57 }val[maxn<<2]; 58 Node ad[maxn<<2]; 59 Node d,fir; 60 Node qpow(Node a,int b){ 61 Node res; 62 res.clear(); 63 res.init(); 64 while(b){ 65 if(b&1){ 66 res=res*a; 67 } 68 a=a*a; 69 b>>=1; 70 } 71 return res; 72 } 73 void pushdown(int pos,int l,int r){ 74 if(ad[pos].check())return; 75 val[ls]=val[ls]*ad[pos]; 76 val[rs]=val[rs]*ad[pos]; 77 ad[ls]=ad[ls]*ad[pos]; 78 ad[rs]=ad[rs]*ad[pos]; 79 ad[pos].clear(); 80 ad[pos].init(); 81 } 82 void build(int pos,int l,int r){ 83 ad[pos].clear(); 84 val[pos].clear(); 85 ad[pos].init(); 86 if(l==r){ 87 val[pos]=fir*qpow(d,a[l]-1); 88 return; 89 } 90 build(ls,l,mid); 91 build(rs,mid+1,r); 92 val[pos]=val[ls]+val[rs]; 93 } 94 void add(int pos,int l,int r,int L,int R,Node z){ 95 if(L<=l&&R>=r){ 96 val[pos]=val[pos]*z; 97 ad[pos]=ad[pos]*z; 98 return; 99 } 100 pushdown(pos,l,r); 101 if(L<=mid)add(ls,l,mid,L,R,z); 102 if(R>mid)add(rs,mid+1,r,L,R,z); 103 val[pos]=val[ls]+val[rs]; 104 } 105 Node find(int pos,int l,int r,int L,int R){ 106 if(L<=l&&R>=r)return val[pos]; 107 pushdown(pos,l,r); 108 Node res; 109 res.clear(); 110 if(L<=mid)res=res+find(ls,l,mid,L,R); 111 if(R>mid)res=res+find(rs,mid+1,r,L,R); 112 return res; 113 } 114 inline int read(){ 115 int x=0,f=1; 116 char ch=getchar(); 117 while(ch<'0'||ch>'9'){ 118 if(ch=='-') f=-1; 119 ch=getchar(); 120 } 121 while(ch>='0'&&ch<='9'){ 122 x=(x<<1)+(x<<3)+(ch^48); 123 ch=getchar(); 124 } 125 return x*f; 126 } 127 signed main(){ 128 d.clear(); 129 fir.clear(); 130 d.m[1][1]=d.m[1][2]=d.m[2][1]=1; 131 fir.m[1][1]=fir.m[1][2]=1; 132 n=read(); 133 m=read(); 134 for(int i=1;i<=n;i++)a[i]=read(); 135 build(1,1,n); 136 while(m--){ 137 int tp,l,r,z; 138 tp=read(); 139 l=read(); 140 r=read(); 141 if(tp==1){ 142 z=read(); 143 add(1,1,n,l,r,qpow(d,z)); 144 } 145 else{ 146 cout<<find(1,1,n,l,r).m[1][2]%mod<<'\n'; 147 } 148 } 149 return 0; 150 }
2025/7/21 统考【01】
教练说是S组难度（差点就信了
根本不是S组的难度啊，T1就是绿的
分数140/400
| T1 | T2 | T3 | T4 | |
| 期望得分 | 100 | 60 | 30 | 70 |
| 实际得分 | 40 | 30 | 30 | 40 |
T1
(原题洛谷 P2034)
简单题，直接二分dp，
然后就爆了（怎么没有大样例
早知道拍一下了
T2
题意：
给定一颗 n 个节点的树，这棵树是以编号为键值的二叉树，
可以任意旋转 (既可以转化为任意一颗中序遍历从 1 到 n 的树)
小O喜欢从一个点 s 出发往根节点走，每次他从点 x 走到点 y 时，会发生以下事件
1.如果 x 是 y 的左儿子，并且小O的左手上没有数字，则他的左手会被写上数字 ay
2.如果 x 是 y 的右儿子，并且小O的右手上没有数字，则他的右手会被写上数字 ay
在点 s 出发时，左右手都没有数字。如果到根节点时某只手没有数字，则会被写上 1
定义一个节点的分数是从它开始往根走，结束时左右手的乘积。整棵树的分数是所有节点分数的总和。
请找到一颗分数最大的数，并输出它的分数。
(3≤n≤500，1≤ai≤1e7)
没思路，暴力+特殊性质跑了
特殊性质因为神秘原因写挂了
T3
题意：
给定一个长度为 n 的序列 a ，m 次询问，每次询问给定两个数 l,r ，
求出这个序列区间 [l,r] 里所有数字两两之间的最大公约数的最大值
(1≤n,m,ai≤2e5)
思考区间合并，考虑建权值线段树，然后从下往上合并区间，显然是不可行的，
当时脑抽了一直想怎么合并，最后交了个暴力
T4
题意：
给定一颗起始只有编号为 1 的根节点的树和 n 个操作
操作有两种
1. Add x d 添加一个编号为 节点数+1 的节点，挂在编号为 x 的结点下方，两点距离为 d
2.Query f t 表示求从编号 f 的节点，到编号为 t 的子树中所有节点的路径所有边权异或值的最大值
(n≤2e5，0≤d≤230)
异或的重要性质：异或两遍等于没有异或
每加入一个新点就记录到根节点的异或路径，查询时两个结点的到根节点的异或路线异或一下就是两个结点的异或路径
然后暴力枚举子树
期望70分，写挂了
2025/7/22 模考【05&06】
排名13/20
分数140/400
赛中时间记录
8:00 开始模考
8:00-9:37 写05模考
9:37 换06模考
9:37-10:14 写T1
10:14-12:05 想T4
12:15 模考结束
本来是05模考，结果05模考的T1 T2 T3都有问题，
老师到教室之后开始改题，改完之后还是有问题
一气之下直接把05模考关了
让我们考06模考，难绷
| T1 | T2 | T3 | T4 | |
| 期望得分 | 100 | 0 | 0 | 15 |
| 实际得分 | 45 | 0 | 0 | 15 |
T1
题意：
给定一张 n 个节点 m 条边的有向图，共有 p 个 边集合，
用 u,v,c,w 表示一条边的起点 u ，终点 v ，权值 c ，属于集合 w
Q 次询问，每次询问给定 s,t,k ，求出从 s 到 t 走过的边不超过 k 个不同集合的最短路径长度
(n≤100，p≤6，m≤p*n*(n-1)，c≤1e4，q≤1e5)
一眼 Floyd 啊，zd[i][j][k] 为只走 k 公司 i 到 j 的最短路径，Floyd 处理出来，设 dp[i][j][w] 为从i走到j换公司次数不超过 w 次（埋下伏笔）
直接枚举断点转移即可
1 for(int w=1;w<=n;w++){ 2 for(int k=1;k<=n;k++){ 3 for(int i=1;i<=n;i++){ 4 for(int j=1;j<=n;j++){ 5 zd[i][j][w]=min(zd[i][j][w],zd[i][k][w]+zd[k][j][w]); 6 } 7 } 8 } 9 } 10 for(int i=1;i<=n;i++){ 11 for(int j=1;j<=n;j++){ 12 for(int k=1;k<=n;k++){ 13 dp[i][j][0]=min(dp[i][j][0],zd[i][j][k]); 14 } 15 } 16 } 17 for(int w=1;w<=n;w++){ 18 for(int k=1;k<=n;k++){ 19 for(int i=1;i<=n;i++){ 20 for(int j=1;j<=n;j++){ 21 dp[i][j][w]=min(dp[i][j][w],dp[i][k][w-1]+dp[k][j][0]); 22 } 23 } 24 } 25 }
但是题目是不超过 w 个不同集合，没看到，我写的是转换集合次数不超过 w 次，寄（
T2
题目描述：
有一堆牌共 2n 张，自上而下第 i 张上的数字为 ai。
初始时，最上面 n 张牌已解锁，下面 n 张牌未解锁。
接下来做 2n 轮操作：
首先，小 W 会在牌堆中所有已经解锁的牌中等概率随机选择一张，加入自己的手牌。他的得分会加上现在手牌中所有数字之和。
然后，如果仍有未解锁的卡牌，则解锁最上面那一张。
请你求出游戏结束之后，小W得分的期望对 998244353 取模的结果。
(2≤n≤2e5，1≤ai≤998244353)
看了一眼，感觉不会，去看T3
T3
题目描述：
某一天小 C 所在的公司发生了流感。公司里总共有 n 个人，编号为1,…,n。
在这天开始时，恰好有一个人感染了流感，每个人感染的概率都是 1/n。
在这一整天中，小 C 公司的人按时间顺序发生了
m 次接触，第 i 次接触发生在编号为 xi 和 yi 的人之间。
如果它们其中一个人感染了流感，而另一个人没有，那么没有感染流感的那个人会有恰好 1/2 的概率感染流感。
在这天结束时，小 C 得知编号为 k 的人感染了流感。
现在他想要知道，在已知条件下，每个人感染流感的概率分别是多少？你需要用形如 a/b 的最简分数表示答案。
(2≤n≤15，1≤k≤n，1≤m≤50)
看了一会，感觉T4更有前途，去看T4
T4
题意：
给定一个长度为 n 的序列 a 和一个数 k，
把序列 a 划分成若干区间使得每个区间的长度不超过 k 且所有子区间对应序列的 mex 和最大
即找到 0=p0<p1<p2...<pm = n 且pi<=pi-1+k，使得
的值最大，输出这个值
(1≤k≤n≤2e5，0≤ai≤n)
看完题目后先想1e3的做法，1e3很明显是O（n²）的做法，思考区间dp
枚举左右端点，再枚举断点，做法是O（n³）
复杂度不对，开始转换思路，看了100%的数据，应该带个log或者直接线性，
手摸了半天没真做法，最后交了个暴力
2025/7/23 休息日【02】
整天都在玩三国杀...
2025/7/24 上课【图论建图】
知识点
1.差分约束
2.Boruvka算法
3.同余最短路
4.一些构造
A题
题意：
给定一个图和 s ,t ，求 点s 到 点t 的最短路，并输出路径（按字典序输出最小的一条）
如果存在负权回路输出You show me the wrong map!
为什么会有模板题啊，
把每条边按指向的结点的字典序排序，用一个链表维护路径，跑一遍spfa即可
C题
题意：
给定一张图，可以使一条边边权减半，求 s 到 t 的最短路径
怎么又是板子题，建两层的图跑一遍最短路即可
2025/7/25 模考【07】
爆爆爆
排名 8/20
分数170/400
赛中时间记录
8:00 开始模考
8:00-9:02 写T1
9:02-9:50 写T1
9:50-10:27 写T4
12:00 模考结束
|
|
T1 |
T2 |
T3 |
T4 |
|
期望得分 |
100 |
50 |
0 |
20 |
|
实际得分 |
100 |
50 |
0 |
20 |
T1
题意：
给定两个整数 N,T 和 N 个 Si、Ei，
一天有 T 个时段，共有 N 个人，第 i 个人可以在 [Si,Ei] 打扫卫生，
为至少安排几个人可以覆盖全部的 [1,T] 时段打扫卫生。
无解则输出 -1
(1≤N≤25000，1≤T≤1e6，1≤Si≤Ei≤T)
按S排序，遍历每一个点，做一些判断
1 if(i==1){ 2 if(a[i].s>1){ 3 cout<<-1; 4 return 0; 5 } 6 else{ 7 q[r]=a[i].e; 8 } 9 } 10 else{ 11 if(q[r]>=a[i].e)continue; 12 if(q[r]+1<a[i].s){ 13 cout<<-1; 14 return 0; 15 } 16 while(l<r&&q[r-1]+1>=a[i].s)r--; 17 q[++r]=a[i].e; 18 }
就可以AC
T2
题目描述：
(n≤3e5)
朴素的dp是O(n²)的，写完之后感觉像斜率优化，推了一会式子没推出来，
又想了一下，发现可以用线段树，开始写，一直调不出来，寄，去看T4
T3
题目描述：
(m≤n≤200，T≤10)
好困，懒得看了
T4
题目描述：
保登心爱擅长算数。
某天，心爱拿到了一个长度为 n 的序列 ai ，她很快就求出了这个序列的每个子区间的平均数。
但是，子区间一共有 C2n+1 个。
为了证明你也能求出所有平均数，你需要把所有 C2n+1 个平均数从小到大排序后，
把第 k 个数告诉心爱。
(1≤n,k≤5e5，k≤C2n+1，1≤ai≤1e7)
O(n²)的区间dp，能拿20，又思考了一会没什么思路，
昨天晚上没睡好，后面基本在发呆
2025/7/26 上课【DP专题】
知识点
1.斜率优化
2.单调队列/单调栈优化
3.DDP（带修DP）
课内的作业太难了，只能自己先找点基础的做（
T1(不是xyd的作业)
(洛谷P3195)
朴素dp是O(n²)的，把方程化成y=kx+b的一次函数的形式，观察在图上的性质，
维护一个下凸壳即可，复杂度O(n)
T2(不是xyd的作业)
(洛谷P6563)
O(n³) 的区间DP，转移方程 dp[l][r]=min{max{dp[l][k],dp[k+1][r]}+a[k]}
把 max 分类讨论，随着 k 增大, dp[l][k] 递增，dp[k+1][r] 递减，找到 dp[l][p+1]>dp[p][r]dp[p][r]>=dp[l]][p-1] 的分界点 p
分别考虑 max 的两种情况
2025/7/27 模考【08】
emm,还是爆
排名 5/20
分数125/400
赛中时间记录
8:30 开始模考
8:30-10:37 写T1
10:37-11:24 写T1
11:24-12:00 写T1和T3的暴力
12:00 模考结束
|
|
T1 |
T2 |
T3 |
T4 |
|
期望得分 |
0 |
40 |
15 |
0 |
|
实际得分 |
20 |
90 |
15 |
0 |
T1
题目描述：
(1≤n≤5e4，1≤m≤1e5，pi∈[75,100]，1≤ui,vi≤n)
第一眼感觉像最大生成树之类的问题，可以给每个点赋一个值 g ，表示一号点到这个点不被发现的最大概率，
全图能 联通当前还没联通的点 的边的最大值记为 mx ，g值最大的点的最大边的权值记为 mxe ，则 mx>=mxe，
如果 mx==mxe ，那么加入 mxe 这条边，否则加入 mx 这条边，更新连接后的 g 值
建完图之后跑一遍搜索计算答案
手模了一些数据，没问题，写写写
写了1快个小时，将近两百行，写成一坨了，4个自定义数据结构，7个库,变量数不清了，变量名还乱标的，样例没过，开始调代码，
调了一个多小时放弃了，已经忘记自己在写啥了，比赛快结束的时间几分钟写了个暴力，最后3分钟的时候发现暴力是错的
只会输出-1，时间不够不想调，结果拿了20（不可以，总司令
跟室友说我写 T1 的过程给他们笑成大奋了
T2
题目描述：
(n,m≤200)
暴力 O(n^4) 用二分优化成 O(n³ log n) ，加了一点优化之后感觉能过 n,m<=500,
其实不是 O(n³ log n) 这个复杂度，加了一些奇怪的剪枝，复杂度玄学，应该小了很多，常数也小
直接过了19个点，没开 long long WA了一个，变成90了
T3
题目描述：
(1≤T≤10，0≤S≤1e18，1≤M≤1e18，1≤N≤200，0≤ai≤1e5)
没时间了，暴力
T4
题目描述：
(k≤n,pos≤1e9，q≤2e5)
第一遍题目没看懂，只剩十几分钟了，不如去写 T1 的暴力
2025/7/28 统考【02】
排名9/20
没时间，so没写模考总结
2025/7/29 模考【09】
排名8/20
也没时间，没写模考总结
2025/7/30 休息日【03】
今天普通班结营，不能玩了（
只能呆在班里自习
2025/7/31 上课【分治思想】
知识点
1.分治的基本思想
2.CDQ分治
CDQ分治
解决形如求出xxx性质的点对 (i,j) 的数量
参考oiwiki
可以把点对分成三类
1.i,j<=mid
2.i<=mid,j>mid
3.mid<i,j
可以往下递归区间把一和三类转化成二类，然后用人类智慧求解二类点
B题
(luogu 7115)
先考虑 n=2 的情况，也就是只有0和1，充分发挥人类智慧想出 n=2 的解法后考虑扩大问题规模，
对于值为 [l,r] 内的球，设一个 mid=l+r>>1
值小于等于 mid 的为 0 ，大于 mid 的为 1，然后按 n=2 的方法求出所有值在 [l,r] 的答案，
递归求解 [l,mid] 和 [mid+1,r] 的答案
2025/8/1 上课【树上专题】
知识点
1.树剖求 LCA
2.重链剖分+线段树（树剖完全体）
3.长链剖分 O(n log n) - O(1) 求 k 级祖先
B题
(洛谷 P1967)
kruskal重构树求最大生成树，对于询问的每对点求其LCA即可
F题
(洛谷 P2486)
树剖板子题，重链剖分+线段树，线段树维护区间左端点和右端点的颜色，
如果左子区间的右端点颜色和右子区间的左端点颜色相同，那么颜色段为左右子区间颜色段之和减一
其他的完全是树剖板子
H题
(洛谷 P2680)
二分答案，然后树上差分维护路径和大于mid的路径经过的边，枚举每一条边，
如果大于mid的路径都经过这条边且最大的路径减去这条边的边权小于等于mid，那么返回true
否则如果所有边都没法满足条件，则为flase
二分的左端点 l 要初始化成0（
2025/8/2 统考【03】
排名13/20
没时间写总结
2025/8/3 统考【04】
排名 2/20
分数150/400
|
|
T1 |
T2 |
T3 |
T4 |
|
期望得分 |
100 |
10 |
20 |
10 |
|
实际得分 |
100 |
10 |
30 |
10 |
T1
题目描述：
小信获得了一种魔法积木：
这是一种方格图，要求方格连续，且左边界对齐，下一行不能比上一行长。
现在我们可以往里面填1−n的数字，要求每个格子中的数字要大于等于左边格子，严格大于上方格子。
现在给定每一行的格子数量，求可能满足条件的图形数量。
(k≤7)
开局看完题目直接写，决定记忆化，先写了一个暴搜，测了下样例，发现不对劲
又测了
7 7 6 5 4 3 2 1
7
的最极端数据，发现只有 2e7 的复杂度，怀疑暴力写错了，找了几分钟没发现有什么错的，认定这是水题
T2
题意：
给定 n 和一个数列 a ，每种数字可以变成 “A” 或 “B” 或 “C”，且每个数字都要变。
问有多少种变法使得产生的字符串的所有子序列至少包含一个“ABC”，答案对1e8+7取模。
(n≤3000)
想T2想了挺久，想%40的数据点，一堆假做法DP，最后只交了暴力
T3
题目描述：
(n≤1e6)
测试点编号 1~3 ，n<=5? 打表！
只跑出来 n=4 的，n=5 的跑到考试结束都没跑出来（
赛后 mwl大佬 告诉我直接暴力 n=5 大概是 10^43
T4
题目描述：
(n,q≤2e5，ai≤1e6)
直接暴力了
2025/8/3 统考【05】
排名5/20
2025/8/3 娱乐赛【最后一天！】
题目挺好玩的，随便写了
反正是娱乐赛
第一次拿倒一有一种爽感
2025/8/4 结营
早上大家在班级念结营总结，
下午结营仪式，还有节目，挺有意思的，
结营仪式结束就可以走了
我班里念的结营总结是deepseek写的，
这里重新写一份
结营总结
以前从来没接触过这种训练方式，每天都要写一篇学习总结，
模考都要补完题，写模考总结，
刚开始感觉挺累的，但是坚持下来就没事了，
和自己学校的训练相比，严格了很多，但成长速度也快得多，
我提高组的算法原来学的很不扎实，都是自己乱学的，
感觉自己不应该在这个班，第一次模考考了倒一也没有很意外，
记不清当时怎么想的了，居然坚持下来了。
我觉得大部分是因为同学都很友善，
大家会互相解答问题，互相讨论题目，氛围很好，
他们的观念是别人有疑惑时帮忙解答也会发现自己哪里掌握不扎实，
对自己也有很大帮助，我现在也认为如此，营地期间也有帮别的同学解答上课的知识点，
会发现以为已经完全掌握的算法其实也有一些地方掌握的不是很好，然后再继续针对性地学习。
大家总是称呼别人“巨佬”，说自己是“蒟蒻”，甚至说自己是“傻*”，都很谦虚，
模考考差了，听到最多的话是“没事，你只是失误了，你是个巨佬，我是蒟蒻”之类的。
在这样的环境里面进步神速，这非常可贵，从来没有感受过。
我可以理解为什么到外省训练是福建省的选手水平上升的原因了。
(结营总结到这里结束了)
关于现在我对信奥的看法
它不只是升学的工具，对现在的我来说，学信奥不为升学，为了证明它不比其他竞赛学科差，
它有自己独特的魅力，绝不是某些人口中在机房打游戏。信奥路上能获得很多乐趣、友谊，我一定会改变某些人对信奥的看法。