C 思维 每个人都给出除了自己以外，人数最多的颜色有多少人。问能否判断有人说谎 如果只有一组人数最多的颜色，有人，没人撒谎的情况肯定是，这组内人报告，这组外其他人报告 如果有多组人数最多的颜色，都有人，那么所有人都报告。因为至少有两组，所以总人数不少于。 还一种可能是个人颜色都一样，所有人都报告，也是可以的 其它都不合法 void solve(){ int n; cin>>n; vi a(n+1); rep(i,1,n)cin>>a[i]; set<int>s; map<int,int>mp; rep(i,1,n){ s.insert(a[i])...

A 模拟 检查字母按字典序升序，出现次数是否是一个公差为1的数列 void solve(){ int n; cin>>n; string s; cin>>s; map<char,int>mp; for(char c:s){ mp[c]++; } bool ok=1; int pre=-1; for(auto &[k,v]:mp){ if(v!=pre+1&&pre!=-1){ ok=0; } pre=v; } if(ok)cout<<"YES\n"; else cout<<"NO\n"; }  B 枚举 检查是...

A 模拟 问能否删除一些字符后重新排列，能组成给定的字符串。 可以排列，所以只要传力每种字符的出现次数，都比目标串更多即可，这可以统计，然后枚举目标串的 void solve(){ int n; cin>>n; string s="Kato_Shoko"; string t; cin>>t; map<char,int>mp1,mp2; for(char c:s)mp1[c]++; for(char c:t)mp2[c]++; bool ok=1; for(auto &[k,v]:mp1){ if(mp2[k]<v)ok=0; } if(ok){...

B 逆序对 循环移位 给一个排列，问每次循环移位一个区间后，序列逆序对奇偶性 交经典结论，换两个相邻元素，保证元素不同，逆序对奇偶反转。循环移位这个区间，相当于把移动到左边，其他不变，也就是交换次。根据的奇偶，即可知道操作完，整个序列逆序对的奇偶。 F 状压 枚举 二分  不大，保留灯管的所有情况最多也不多。考虑枚举所有保留的灯管集合，对每个集合去检查能否区分种数字。检查时直接保存mask&a_i，看结果是否有种，这可以unordered_map实现。但常数有点大，也可以记录每种结果的出现次数，手动维护结果种类数。每次枚举都要清空，值域显然不能暴力清空，考虑用时间戳思想。 这样复杂度还...

C 贪心 每次可以选一个子序列，全部减一。问最少多少次操作可以变成不减。 只能减不能加，那么贪心的想，最后一个元素一定不能减，否则它变小了，可能需要前面的元素减更多次才能保证序列不减。 所以处理完一个后缀之后,一定比后缀里的所有都要小，也就是比小。如果初始，需要减小到，如果本来就比小则不用操作。 最后我们每次可以操作一个子序列，也就是同时操作多个。所以操作次数上界取决于需要操作次数最多的那个元素。 #include <bits/stdc++.h> #define int long long using namespace std; using ll = long long; usi...

F 双指针 扫描线 线段树 确定两个指针把数组分成三段，求一个方案使得三个集合的交集最大 有两个指针的位置需要确定，显然考虑枚举，然后对每个确定三个集合交集最大的的位置 对于每种元素，想要这个元素出现在交集里，也就是三个集合都有这个元素，如果确定，设这个元素在里最左出现位置是，最右出现是，那么想让三个区间里都有这个元素，可以位于这区间。 也就是对于每个元素都有个可以位于的区间，然后对于一个位置，的话，交集的大小，就是覆盖这个的区间个数。 那么这就是一个区间加，球单点最值，线段树维护即可。 具体就是，用一个数组维护左侧这个集合的元素，枚举，扫描整个原序列，如果的位置是一个左侧集合未出现的元素，我...

A 树形dp 观察 可以删点，加点，问把一个二叉树变成avl的最少操作次数？ avl的要求就是左右子树都是avl树，且左右子树高度差不超过1. 注意到这是个递归定义，可以考虑树形dp，计算出一个点的两个子树变成avl树的最小代价，然后再用这两个一个变成avl的子树，和当前点拼起来，就能计算当前点为根的子树变成avl的最小代价 但是，想让当前点为根的子树是avl，不仅需要两个子树都是avl，还需要知道两个子树的高度，然后看他们满不满足子树高度差不超过1的这个约束。而子树高度可以是任意取值，所以考虑把子树高度也放在dp状态里 也就是表示以为根的子树，变成高度为的avl树，的最小代价。那么我们转移时...

C 计数 dp优化 对一个长度为n的排列跑单调栈，最后栈中剩下的元素个数为， 注意到一个排列增加一个元素，对剩余元素个数的影响时很好分析的，如果给一个长度n的排列增加一个元素n+1，只有在n+1插入到排列的结尾时，单调栈中剩余元素个数才会增加，其余位置元素个数都不变。 增加一个元素，变化可以求，很适合dp。考虑表示，长度为j的排列，跑单调栈的剩余元素个数为i的方案数。这可以递推， 光有这个转移还不够，我们要求的是。而这个转移的状态数是的，肯定超时。要想办法得到一个转移只有个状态的dp，也就是状态定义是，然后可以地转移这个。 但是这里还带个太难转移了，考虑增加一些状态来辅助 也就是可以分别维护，...

B BFS 思维 网格图上从起点到终点，只能往上下右走，人有一个视野，超出范围的看不到。问是否存在一个死胡同，会误导人走进来 等价于是否存在一个路径，人没走进来时无法确定是不是死路，只有等走进来了才能发现是死路（由于不能往左走，此时已经晚了，游戏失败） 首先需要找到所有死路的点，这可以通过找到所有能到终点的路径，剩下的就是所有死路包含的点。从起点出发，到终点，经过的所有可能点，可以分别从起点和终点出发BFS，所有同时被两次访问到的就是。剩下那些能从起点出发到达的，但不能从终点出发到达的，就是死路的点。 接下来就是找是否存在一个死路，他在左右方向上足够深，超出角色的视野，用一个dp维护所有死路点...

J 二分 多源BFS 切比雪夫距离 01矩阵，最多把一个0变成1，然后每个1每一秒会把曼哈顿距离为1的相邻0变成1，问变成全1的最小时间？ 注意到肯定是越早越困难，越晚越容易，答案具有单调性，可以二分变成全1的时间。 从多个源点出发的染色，故check里考虑多源bfs，发现我们从所有1出发bfs，只能走mid秒的话，可能有的0还没变成1。而我们又有一次染色的机会，所以我们就是要检查能否找到一个点，初始时变成1，然后从这个点出发bfs mid步，能覆盖所有这些还未被染色的0 也就是能否找到一个点，到所有未被染色的点的曼哈顿距离不超过mid。 曼哈顿距离，可以坐标变换后变成切比雪夫距离，  所以就...

D 思维 可以把长度a的连续1变成0，可以把长度a+1的连续0变成1，问最多能得到多少1？ 只要有一段长度a的1，我们把他们变成0，然后和两侧的0，肯定可以构成一个长度至少a+1的连续0，然后我们可以把他们再变成1，重复这个操作可以把所有0都变成1 如果开始没有长度a的1，但是有长度a+1的0，可以类似的操作，还是能全变成1. 所以只要存在长度不小于a的连续1，或者长度不小于a+1的连续0，就可以全变成1。找最长连续1/0长度这是典，不谈 #include <bits/stdc++.h> #define int long long using namespace std; usin...

A 计数DP 1表示看到白天，0表示看到晚上，-1表示看到不确定。给个序列，问所有把-1变成0或1的方案中，白天天数的和？ 首先如果只是求方案数是好求的，但是这里每个方案都有贡献，要求的是所有方案的贡献和。这种一般就维护两个dp数组，一个是贡献和，一个是方案数，方案数正常转移，什么时候能产生贡献了，再把方案数加入答案。 这里能产生贡献的地方就是前一个时0，当前是1，这意味着开始了新的一个白天，我们把计算出来的方案数加上 #include<bits/stdc++.h> using namespace std; const int N=5e5+5; const long long mo...

2025暑期第一场 G 模拟 数学 给两个01串，问分别从两个位置开始的子串，有多少个子区间完全相同？ 注意到这是01串/手玩，可以推出，对于每段相等的最长子区间，长度的话，对答案贡献是 #include <bits/stdc++.h> #define rep(i, a, b) for(int i = a; i <= b; i++) #define per(i, b, a) for(int i = b; i >= a; i--) #define endl "\n" using namespace std; using ll = long long; using ull ...

A 模拟不谈 void solve(void){ cin>>n; char c; cin>>c; if(c=='*')cout<<1<<' '<<n; else if(c=='+')cout<<n/2<<' '<<(n+1)/2; else cout<<n+1<<' '<<1; }  B 贪心，n个位置，k个东西把他们分成一些区间，每个长度不小于t的区间个数最大值？ 首先k个东西要用来隔开，那么剩余n-k个东西可以划分区间，t个一组，那么组数最大值就是。 但是交上...