黄题大杂烩(1)
2026-09-25 10:52:25
发布于：上海
娱乐性产物，没有教导意义。本人坑品极差，写掉要做的事情通常只能完成20%，经常连一半看别的题很好玩就去看别的了。
有实质性错误欢迎提出，作者给你磕八百个响头。
——————————————————————————————————————————
想要迅速地写出黄题，那么可以从两个方面做突破口。
1.大量练习，训练算法敏感度
2.格式化流程
需要找出一段最长的区间，使得区间内的0数量=1数量
这道题我否决了这样几个算法：dp，二分
但是这个直觉是有问题的。毕竟正解不是它们两个中的任何一个。
如何判断一道题目能不能使用dp?
一道DP
这道题目给我的第一感觉会是贪心。
但是因为数据范围实在是太小了，甚至都可以是搜索的时间复杂度了。
所以会更换思路选择多维DP。
容易想到的定义是dp[i]表示在完成i篇论文需要的最小时间。
仔细想了一下可以是完全背包？感觉是可以尝试的。
注释：背包选择如果不是滚动要从0开始考虑
我觉得这题没有黄题难度。
两道DP
A和B用不同的方法去搜索牛场
尽可能保持两者位置的距离最小
A从(f[x],f[y])开始，遵循由N步组成的路径。
B从(b[x],b[y])开始，遵循由M步组成的路径
一共有四个方向：N（向上），E（向右），S（向下），W（向左）
两个路径可以经过相同的点。
在每个时间段，FJ可以不移动，也可以沿着他的道路走一步。
B也可以做出同样的选择。
在每个时间点，他们的无线电消耗能量等于它们之间距离的平方。
算出它们双方到达各自的终点时，最少消耗的能量
看到n,m<=1000 所以判断出可能是O(nm)或者带一个log的东西。
看到“消耗的最小能量”，一般会选择往最短路/动态规划/贪心上面去想。
以题目数据范围去判断，大概率是一个用矩阵的东西。
所以说优先去用动态规划。
动态规划就要考虑定义。
dp[i][j]:在FJ走到第i步，奶牛走到第j步的时候的最小答案
然后再来考虑状态转移。
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+它们各自要走的距离。
这道题目有一些容易出错的地方，比如说，这里的坐标很单纯的就是坐标。
i,j 代表x,y
而不是要把它放进矩阵里面去力竭。
三道DP
这道题目需要一个非常简单的思路转变。
不想写了我很懒。反正我通过了。你们handhansilaodelaosi吧。
实在不会就看看题解。-
那么现在我们可以给出一个答案。关于为什么P1114不能是dp。
因为它不是线性dp能够解决的题目。但是它的数据范围从某种程度上而言又不支持别的dp方式。
就这样。
dp是明治的枚举，不是高级的算法。
其他情况详见：动态规划优化。
现在重新开始研究非常男女计划到底是怎么整的。
这里我们需要一个相对差的概念。
在算法竞赛当中，我们通常需要相对差去在序列中找到满足某种平衡的最长序列。
然后使用一个数组两个变量去记录：一个变量记录男生的数量，一个变量记录女生的数量。
数组记录当前男生和女生的差值。
然后我们用map去搞出之前有没有和当前差值一样的位置，最后取长度最大值。
后面要练几道分治和贪心。
发现其实可以不需要数组。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
map<int,int>mp;
int main(){
int n;
cin>>n;
int uu1=0,uu2=0,ans=0;
mp[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1)uu1++;
else uu2++;
int now=uu1-uu2;
if(mp.find(now)!=mp.end()){
ans=max(ans,i-mp[now]);
}else mp[now]=i;
}
cout<<ans;
return 0;
}
这里有一个特别需要注意的点：
mp[0]=0;
P5149
这个题目是一个模板题（类似）。
一个哈希+逆序对的东西。
后面要练几道分治和贪心和并查集和最短路。
其实我一直认为直接使用map算不上哈希。
这道题目的大致思路就是把同学们的分组用并查集实现出来，然后去按照x,y判断不符合要求的。
再练练哈兮吧。
我觉得总体来说我的哈希得到了0%的提升。
初赛加油吧。
到时候再做一点Trie树。
哈希base一般选择131.
求取区间哈希数值：h1[e]-h1[s-1]*pw[e-s+1]
明天来写一下RE数据范围注意要点。
昨天写这个题的时候RE了。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5;
const ull k=131;
int n,m,q;
string a,b;
ull hxa[N],hxb[N],pw[N];
ull f1(int s,int e){
return hxa[e]-hxa[s-1]*pw[e-s+1];
}
ull f2(int s,int e){
return hxb[e]-hxb[s-1]*pw[e-s+1];
}
bool check(int x,int st){
//从st开始，长度为x能否匹配成功
if(f1(st,st+x-1)==f2(1,x))return 1;
return 0;
}
int ans[N];
int main(){
cin>>n>>m>>q;
cin>>a>>b;
a="0"+a;
b="0"+b;
pw[0]=1;
for(int i=1;i<=a.size();i++)pw[i]=pw[i-1]*k;
for(int i=1;i<a.size();i++)hxa[i]=hxa[i-1]*k+a[i];
for(int i=1;i<b.size();i++)hxb[i]=hxb[i-1]*k+b[i];
for(int i=1;i<a.size();i++){
int l=1,r=min(b.size(),a.size()-i),sum=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid,i)){
sum=max(mid,sum);
l=mid+1;
}else r=mid-1;
}
ans[sum]++;
}
for(int i=1;i<=q;i++){
int x;
cin>>x;
cout<<ans[x]<<'\n';
}
return 0;
}
这个check函数里面，实际上的右端点是st+x-1，需要考虑st+x-1>=a.size()的情况。
所以设置了右端点的min值。
需要拐一个弯。
由于109<230
考虑直接遍历1-30
然后遍历每个数组中的数，看它是否能够配对成功。
注意map的使用，如果只是使用find()会省一部分时间的，不要小瞧它。
P16287
这个明天再弄吧，今天先搞一道最短路。
这是一个最短路模板啊。
黄题现在还需要练：贪心，分治，trie树，搜索，哈希
一个异或题目。不知道为什么混到哈希这边来了。成功将我击倒。
以前好像都没有好好研究过异或。今天来弄一弄，顺便研究一下为什么这道题能用哈希做。
异或重要性质：
1.交换律 ab=ba
2.逆运算 abb=a
不对。发现好像读错题目了。
好吧。原来题目已经把k给出来了。我还以为它没有给K！
反正也能做吧。
有k整个事情就简单很多。
周所周知，a^b=c -> a^c=b
这个式子的主要推导来源是：a^b= c -> abb=b^c ->a=b^c
a=b^c -> a ^ c=b ^ c ^ c -> a^c=b
众又所周知，异或有一个很常见的匹配就是前缀和，特别是在解决区间问题。
那么我们现在有一个pre[i]表示a[1]^ ... ^a[i]
既然想要：pre[l]^pre[r]=k
那我们直接看有没有pre[r]^k=pre[l]即可。
哦。那就是这里用到了哈希。
但是除此之外，它有一个隐秘的贪心。
明天再说。睡觉了
P1280
一个最短路。
但是总的来说，这道题的正解应该是动态规划。
用最短路做起来会有些其奇怪。
一些时间上的细节处理如果一开始思路不太清晰的话，后面会弄得很麻烦。
现在来梳理一下思路。
最好想要求最长休息时间。我们可以将思路转换，变成求最短工作时间。
然后弄一个建模。
比如现在又有p 和 t
那我们就建一条从p到p+t-1长度为t的边。
如果一个点没有任何边那我们就弄一条空边（从点p到p+1长度为0）。
现在说要来考虑的细节问题。
我们需要明确在dijktsra中放入队列的点的含义。
此时需要秉持着“与原来大差不差”的信念并且进行修改。
因为如果随便改你原来熟悉的模板上的东西后面可能会错一些你意想不到的小细节。
也就是说，放过入队列的第一个点必须是(1,0)
即，代表现在所在点位1(还没有开始使用)，目前其工作时长是0.
但这样感觉会错那么一点。
因为如果有从时刻一开始的工作，那么实际上，dis[1]就必须是一。
那我们可以做一个判断。
如果dis[1]有边就是1，没有就是0.
然后再说后续的dij最短路如何去塞点。
此时到了当前点，我们有一大堆可以遍历的边。
唔。按照我们当前的设定，放入的点实际上是已经规划好的。
有点麻烦。
如果是没规划好的状态放进来的？
那么一开始放的就是(1,0)
然后直接去遍历边。
但是后面那加入pq的得是now+1啊。
感觉是差不多了
后面打算练习一些黄色DFS，学习一下如何打暴力。
黄题现在还需要练：贪心，分治，trie树，搜索，哈希
后面要练几道分治和贪心和并查集和最短路。
我要练的还真是不少啊。
什么时候才可以真正开始学提高组？
但是这边有一个问题。真空状态。
哇。真的好麻烦。
所以我重新画图去模拟了一下。
我发现有一个很奇怪的东西：8,1
这就说明——从第八分钟开始，到第八分钟结束。
那就干脆做这样一件事：1->3 变成 1->4
这样所有的点都是天然的”未定义状态“。
那么dis[i]的定义好像也要改。
它实际上是[1,i)的空闲时间。
这道题目的最短路算法需要更改的点其实就一个：dis[i]的定义。
它并不是比较普通平常的一个点到点图论。
而是一个区间到一个点到一个区间。
那么这种涉及到区间，那么左闭右闭还是左闭右开就比较值得深思了。
后面还想要研究一下关于n=1e4下匹配的算法。
放假啦。
当n=1e4的时候。
一般使用O(n^2) （稍微带一点点优化去做）
n=1e4的时候，能够考虑的是二维动态规划，朴素dijkstra
总的来说，这个时间复杂度还是非常特殊的。
因为如果是O（n）或者O（nlogn）还是回去考虑n=1e5的数据范围吧。
注意注意注意！！！！
建图一i定要注意是单向边还是双向边。
刚刚突然想起来就去练了一下普通最短路。
结果发现太久没做图论导致什么都忘了。
双向边自己就建上了。
可恶。
之前说过要弄的一道哈希。
现在来写一下。
这里来记录一下关于哈希比较常用的两个公式：
1.取一段区间内的哈希值
比如，有一个字符串string a，要取[l,r]的哈希值
那么就是 return hash[r]-hash[l-1]*pw[r-l+1];
2.求一个字符串中间被挖掉一块之后的哈希值
比如，有一个字符串string a，要挖掉的部分是[l,r]
那么要保留的部分就是[1,l-1]和[r+1,n]
那么就是return hash(1,l-1)*pw[n-r]+hash(r+1,n)
娱乐性产物，没有教导意义。本人坑品极差，写掉要做的事情通常只能完成20%，经常连一半看别的题很好玩就去看别的了。
有实质性错误欢迎提出，作者给你磕八百个响头。
——————————————————————————————————————————
想要迅速地写出黄题，那么可以从两个方面做突破口。
1.大量练习，训练算法敏感度
2.格式化流程
需要找出一段最长的区间，使得区间内的0数量=1数量
这道题我否决了这样几个算法：dp，二分
但是这个直觉是有问题的。毕竟正解不是它们两个中的任何一个。
如何判断一道题目能不能使用dp?
一道DP
这道题目给我的第一感觉会是贪心。
但是因为数据范围实在是太小了，甚至都可以是搜索的时间复杂度了。
所以会更换思路选择多维DP。
容易想到的定义是dp[i]表示在完成i篇论文需要的最小时间。
仔细想了一下可以是完全背包？感觉是可以尝试的。
注释：背包选择如果不是滚动要从0开始考虑
我觉得这题没有黄题难度。
两道DP
A和B用不同的方法去搜索牛场
尽可能保持两者位置的距离最小
A从(f[x],f[y])开始，遵循由N步组成的路径。
B从(b[x],b[y])开始，遵循由M步组成的路径
一共有四个方向：N（向上），E（向右），S（向下），W（向左）
两个路径可以经过相同的点。
在每个时间段，FJ可以不移动，也可以沿着他的道路走一步。
B也可以做出同样的选择。
在每个时间点，他们的无线电消耗能量等于它们之间距离的平方。
算出它们双方到达各自的终点时，最少消耗的能量
看到n,m<=1000 所以判断出可能是O(nm)或者带一个log的东西。
看到“消耗的最小能量”，一般会选择往最短路/动态规划/贪心上面去想。
以题目数据范围去判断，大概率是一个用矩阵的东西。
所以说优先去用动态规划。
动态规划就要考虑定义。
dp[i][j]:在FJ走到第i步，奶牛走到第j步的时候的最小答案
然后再来考虑状态转移。
dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+它们各自要走的距离。
这道题目有一些容易出错的地方，比如说，这里的坐标很单纯的就是坐标。
i,j 代表x,y
而不是要把它放进矩阵里面去力竭。
三道DP
这道题目需要一个非常简单的思路转变。
不想写了我很懒。反正我通过了。你们handhansilaodelaosi吧。
实在不会就看看题解。-
那么现在我们可以给出一个答案。关于为什么P1114不能是dp。
因为它不是线性dp能够解决的题目。但是它的数据范围从某种程度上而言又不支持别的dp方式。
就这样。
dp是明治的枚举，不是高级的算法。
其他情况详见：动态规划优化。
现在重新开始研究非常男女计划到底是怎么整的。
这里我们需要一个相对差的概念。
在算法竞赛当中，我们通常需要相对差去在序列中找到满足某种平衡的最长序列。
然后使用一个数组两个变量去记录：一个变量记录男生的数量，一个变量记录女生的数量。
数组记录当前男生和女生的差值。
然后我们用map去搞出之前有没有和当前差值一样的位置，最后取长度最大值。
后面要练几道分治和贪心。
发现其实可以不需要数组。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
map<int,int>mp;
int main(){
int n;
cin>>n;
int uu1=0,uu2=0,ans=0;
mp[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1)uu1++;
else uu2++;
int now=uu1-uu2;
if(mp.find(now)!=mp.end()){
ans=max(ans,i-mp[now]);
}else mp[now]=i;
}
cout<<ans;
return 0;
}
这里有一个特别需要注意的点：
mp[0]=0;
P5149
这个题目是一个模板题（类似）。
一个哈希+逆序对的东西。
后面要练几道分治和贪心和并查集和最短路。
其实我一直认为直接使用map算不上哈希。
这道题目的大致思路就是把同学们的分组用并查集实现出来，然后去按照x,y判断不符合要求的。
再练练哈兮吧。
我觉得总体来说我的哈希得到了0%的提升。
初赛加油吧。
到时候再做一点Trie树。
哈希base一般选择131.
求取区间哈希数值：h1[e]-h1[s-1]*pw[e-s+1]
明天来写一下RE数据范围注意要点。
昨天写这个题的时候RE了。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5;
const ull k=131;
int n,m,q;
string a,b;
ull hxa[N],hxb[N],pw[N];
ull f1(int s,int e){
return hxa[e]-hxa[s-1]*pw[e-s+1];
}
ull f2(int s,int e){
return hxb[e]-hxb[s-1]*pw[e-s+1];
}
bool check(int x,int st){
//从st开始，长度为x能否匹配成功
if(f1(st,st+x-1)==f2(1,x))return 1;
return 0;
}
int ans[N];
int main(){
cin>>n>>m>>q;
cin>>a>>b;
a="0"+a;
b="0"+b;
pw[0]=1;
for(int i=1;i<=a.size();i++)pw[i]=pw[i-1]*k;
for(int i=1;i<a.size();i++)hxa[i]=hxa[i-1]*k+a[i];
for(int i=1;i<b.size();i++)hxb[i]=hxb[i-1]*k+b[i];
for(int i=1;i<a.size();i++){
int l=1,r=min(b.size(),a.size()-i),sum=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid,i)){
sum=max(mid,sum);
l=mid+1;
}else r=mid-1;
}
ans[sum]++;
}
for(int i=1;i<=q;i++){
int x;
cin>>x;
cout<<ans[x]<<'\n';
}
return 0;
}
这个check函数里面，实际上的右端点是st+x-1，需要考虑st+x-1>=a.size()的情况。
所以设置了右端点的min值。
需要拐一个弯。
由于109<230
考虑直接遍历1-30
然后遍历每个数组中的数，看它是否能够配对成功。
注意map的使用，如果只是使用find()会省一部分时间的，不要小瞧它。
P16287
这个明天再弄吧，今天先搞一道最短路。
这是一个最短路模板啊。
黄题现在还需要练：贪心，分治，trie树，搜索，哈希
一个异或题目。不知道为什么混到哈希这边来了。成功将我击倒。
以前好像都没有好好研究过异或。今天来弄一弄，顺便研究一下为什么这道题能用哈希做。
异或重要性质：
1.交换律 ab=ba
2.逆运算 abb=a
不对。发现好像读错题目了。
好吧。原来题目已经把k给出来了。我还以为它没有给K！
反正也能做吧。
有k整个事情就简单很多。
周所周知，a^b=c -> a^c=b
这个式子的主要推导来源是：a^b= c -> abb=b^c ->a=b^c
a=b^c -> a ^ c=b ^ c ^ c -> a^c=b
众又所周知，异或有一个很常见的匹配就是前缀和，特别是在解决区间问题。
那么我们现在有一个pre[i]表示a[1]^ ... ^a[i]
既然想要：pre[l]^pre[r]=k
那我们直接看有没有pre[r]^k=pre[l]即可。
哦。那就是这里用到了哈希。
但是除此之外，它有一个隐秘的贪心。
明天再说。睡觉了
P1280
一个最短路。
但是总的来说，这道题的正解应该是动态规划。
用最短路做起来会有些其奇怪。
一些时间上的细节处理如果一开始思路不太清晰的话，后面会弄得很麻烦。
现在来梳理一下思路。
最好想要求最长休息时间。我们可以将思路转换，变成求最短工作时间。
然后弄一个建模。
比如现在又有p 和 t
那我们就建一条从p到p+t-1长度为t的边。
如果一个点没有任何边那我们就弄一条空边（从点p到p+1长度为0）。
现在说要来考虑的细节问题。
我们需要明确在dijktsra中放入队列的点的含义。
此时需要秉持着“与原来大差不差”的信念并且进行修改。
因为如果随便改你原来熟悉的模板上的东西后面可能会错一些你意想不到的小细节。
也就是说，放过入队列的第一个点必须是(1,0)
即，代表现在所在点位1(还没有开始使用)，目前其工作时长是0.
但这样感觉会错那么一点。
因为如果有从时刻一开始的工作，那么实际上，dis[1]就必须是一。
那我们可以做一个判断。
如果dis[1]有边就是1，没有就是0.
然后再说后续的dij最短路如何去塞点。
此时到了当前点，我们有一大堆可以遍历的边。
唔。按照我们当前的设定，放入的点实际上是已经规划好的。
有点麻烦。
如果是没规划好的状态放进来的？
那么一开始放的就是(1,0)
然后直接去遍历边。
但是后面那加入pq的得是now+1啊。
感觉是差不多了
后面打算练习一些黄色DFS，学习一下如何打暴力。
黄题现在还需要练：贪心，分治，trie树，搜索，哈希
后面要练几道分治和贪心和并查集和最短路。
我要练的还真是不少啊。
什么时候才可以真正开始学提高组？
但是这边有一个问题。真空状态。
哇。真的好麻烦。
所以我重新画图去模拟了一下。
我发现有一个很奇怪的东西：8,1
这就说明——从第八分钟开始，到第八分钟结束。
那就干脆做这样一件事：1->3 变成 1->4
这样所有的点都是天然的”未定义状态“。
那么dis[i]的定义好像也要改。
它实际上是[1,i)的空闲时间。
这道题目的最短路算法需要更改的点其实就一个：dis[i]的定义。
它并不是比较普通平常的一个点到点图论。
而是一个区间到一个点到一个区间。
那么这种涉及到区间，那么左闭右闭还是左闭右开就比较值得深思了。
后面还想要研究一下关于n=1e4下匹配的算法。
放假啦。
当n=1e4的时候。
一般使用O(n^2) （稍微带一点点优化去做）
n=1e4的时候，能够考虑的是二维动态规划，朴素dijkstra
总的来说，这个时间复杂度还是非常特殊的。
因为如果是O（n）或者O（nlogn）还是回去考虑n=1e5的数据范围吧。
注意注意注意！！！！
建图一i定要注意是单向边还是双向边。
刚刚突然想起来就去练了一下普通最短路。
结果发现太久没做图论导致什么都忘了。
双向边自己就建上了。
可恶。
之前说过要弄的一道哈希。
现在来写一下。
这里来记录一下关于哈希比较常用的两个公式：
1.取一段区间内的哈希值
比如，有一个字符串string a，要取[l,r]的哈希值
那么就是 return hash[r]-hash[l-1]*pw[r-l+1];
2.求一个字符串中间被挖掉一块之后的哈希值
比如，有一个字符串string a，要挖掉的部分是[l,r]
那么要保留的部分就是[1,l-1]和[r+1,n]
那么就是return hash(1,l-1)*pw[n-r]+hash(r+1,n)
全部评论 2
#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> s(n+1); for(int i=1;i<=n;i++){ int x; cin>>x; s[i]=s[i-1]+(x==0?-1:1); } for(int len=n&~1;len>=2;len-=2){ for(int i=1;i<=n-len+1;i++){ if(s[i+len-1]==s[i-1]){ cout<<len; return 0; } } } cout<<0; }2026-09-10 来自 浙江
0你这个做法从某种程度上是O(n2)的（本来是n2/4，但是用大O表示法就是O（n2）,n<=105从理论上是坠机的）。如果n<=10^6就挂了。我写的那种做法实际实现出来是O(nlogn)的，而且代码从某种上是更好理解更易懂的。
总而言之你这种做法是OK的，但是我的也是对的。一个题目一般也不会只有一种做法。
我的那种其实是才算是这个题目的“正解”。我以前的帖子也经常烂尾。虽然没有写完，但是相对差确实是好做法。
另外就是我不常登ACGO。所以回复的很慢。
2026-09-13 来自 上海
0
有帮助，赞一个