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 和 lc 分别为 行的 和 列 宝藏数的前缀和
hs 和 ls 分别为 横河 和 纵河 宝藏数和为 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 }
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) 的和
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代码
[code] 1 #include 2 #include 3 #include 4 #include 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 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
