所以我这个题解尽量从“解题思路”的角度出发而非题解的角度。“解题思路”的角度是指选手视角，从读题和分析出发，提出问题并解决。
希望我这个题解看完了，不管手会不会，至少嘴巴先会了。
首先AB题的定位是给学过一定算法竞赛，有一定的基础的选手做的。
就真的刚学完C语言，会写for循环就过来玩了的这种建议从HGDC开始看，然后J因为是纯思维，没有代码量其实也可以想一下。
std会集中放在本帖的最后面。
A、牛牛与牛妹的RMQ
如果是真·萌新的话就这个题先过，先按照顺序学一下这几个算法。
1、前缀和
2、单调栈
3、RMQ（或者线段树）
4、树状数组（最好把线段树也一块学了）
这个题的本意是出个考察数据结构的小综合。这种套路常见于XCPC比赛的铜牌里，或者各省的省赛中等题。这种题的话老手看了以后一般都会说这是个”板子拼接题“，这种题的做题思路其实就是按照题目描述，分析需求，然后按需取用数据结构。
OI比赛一般不会有用这种思路来出的题，原因嘛...第一是因为这其实是一种“垃圾题”的出题思路，第二是因为这种题其实只考察算法竞赛的基本功扎不扎实，OI选手基本功过于扎实了，出了也直接白给。
当然，本题作为日常练习题的话还是蛮好的。说它是“垃圾题”不是因为它简单或者好写，是说这种题的出题思路是一种快餐思路。
解题思路
首先读完题，题目需求是首先从数组中选出一些位置，然后从中随机出两个位置（这两次随机可能相同）。
问你随机这两个位置框出区间的极大值有多少种情况，每种情况出现的概率是多少。
我们先解决第一个问题：极大值有多少种情况？
part 1 极大值有多少种可能的情况
换句话说就是当我选中一些下标后，哪些数字会出现在RMQ中？
“区间信息的可并性”是指当我们已知区间)，
)的信息且当
)，如果区间信息满足可并性，则能够O(1)的知道区间[
]的区间信息。（当然不是所有区间信息都满足可并性，例如区间众数，区间元素种类数等）
然后我们随便选，假设选到了一个。
根据刚才上面提到的“区间信息可并性”)的极大值一定来自于
这三段区间中的某一个极大值。
想到这里就会发现，看来并不需要两重for循环枚举选中的下标就可以枚举到所有的极大值情况。你只需要将下标sort后按照顺序枚举)到
)然后依次计算
这四个区间，其实就涵盖了极大值所有可能的情况。
当然，根据题意，两次所选下标可能是相同的。这种情况极大值就是这个下标上的数字本身，也就是上的数。
至此，我们得到结论。当所选特殊下标为k时，将会产生2k-1种极大值情况，它们分别是k-1个排序后顺序相邻下标的区间RMQ和k个特殊单点。（RMQ算法是什么东西在题目的体面描述中已有介绍，这个要是不会的话自己看吧）
part 1.5 极大值的作用域
当然，我们并不喜欢开区间，所以我们把两个端点往里面收一收，变成如图所示的闭区间。
如果你从[l,p]中随便选一个下标l'，再从[p,r]中随便选一个下标r'，你会发现好神奇，震惊，RMQ(l',r')一定等于a[p]。
显然，这是废话，因为l到p之间，p到r之间都不存在比a[p]更大的数。
关键在于这个“极大值作用域”怎么求呢，很简单，单调栈。（如果不知道什么是堆栈或者什么是单调栈的同学建议花个5到10分钟百度一下）
考虑一个自栈顶向下单调递减的堆栈自左向右扫描，然后对于每一个数字遵循如下的规则
那肯定就是现在这种情况，好，就是这个瞬间。考虑一下18为什么会把p这个位置上的数字10给弹出去。
为什么非得是18弹出去的10，而不是什么7啊5啊或者3之类的。
根据单调栈的规则，大的数字才能弹小的数。那为什么非得等到18来弹？
显然是因为18到10之间不存在比10更大的数字。
诶呀，r求出来了。
l呢？不妨再思考一个问题，为什么在堆栈当中10没有把100弹出去但是它把100到10之间的数字全弹走了？
因为100到10之间的数字都比10小啊，这不就是100到10之间不存在比10更大的数字。
好了，这下都求出来了。
pairstk[MAXN];//
a[0]=INF;
a[n+1]=INF-1;
for(int i=0;i<=n+1;++i)
{
while(top&&stk[top].first<=a[i])
{
L[stk[top].second]=stk[top-1].second+1;
R[stk[top].second]=i-1;
top--;
}
stk[++top]=make_pair(a[i],i);
} part 2 计算每种极大值可能性出现的概率
假设这个M34就是[]的区间极大值。根据part 1.5 中的方法，很好求出极大值M34的作用域。
就比如说是如图所示的的覆盖范围。
现在不管手会不会算这个例子，嘴巴肯定会算了。答案是：
也就是第一次选下标选中p2或者p3的概率并且第二次选中p4的概率，加上第一次选中p4并且第二次选中p2或者p3的概率。
所以现在需要一种算法可以计算l到p之间，p到r之间的所选下标数目。那么ok，树状数组。
如果你不知道树状数组的话
B、牛牛抓牛妹
如果是真·萌新的话就这个题先过，先按照顺序学一下这几个算法。
1、图论最短路
2、二进制状态压缩（学一下状压DP，或者状压搜索）
3、生成树（最好学一下prim）
这个题是我觉得这场出的最有意思的一个题。首先这个题是想要出成一个交互类问题，但是牛客oj目前不支持交互功能嘛。（真的做交互题的话，像这个问题一般就会设计成输入continue的时候裁判程序回复你一个牛妹的当前位置）因为牛妹的策略固定的情况下选手可以模拟出牛妹的位置，所以就做成这种伪交互的形式。
解题思路
首先看到范围n=100,k=7。这个时候意识到，不是常见的数据范围，有猫腻。
有些题确实是可以看数据范围猜算法。
11(n!)
20(2^n)
40(2^{n/2}*n/2)
500(n立方级别)
1e3,1e4(n平方级别)
1e5,1e6(log级别)
1e7(On级别)
1e8,1e9,1e10(根号级别)
1e12以上(O1级别) 大概是这个意思，实际上看个乐呵就行。但实际上确实是数据范围越大，复杂度就限制的越死，大概能找到点方向。
再看这个范围n=100,k=7，就特别明显是让你搞n*2^k的分层图。
part 1 分层图
什么是分层图呢，就是说对于一个图中有一些“开关”或者其他因素导致图出现变化的“动态图”问题。如果说一张图有n个点，k种不同的变种。如果n*k是可以接受的，就能够暴力的把每一种变种图都强行的建出来存起来。
显然本题可以强行把每一张变种图都建出来的，所以先搞出来再看有什么猫腻。
当然一共也就8张图，手画起来其实还蛮快的。
part 2 最短路生成树
按照题目里的说法“总是按照最短路线向终点前进，当最短路出现多个后继时总是选择下标最小的”，这个描述。
如果说图是连通的，那么除了终点以外，其他的每个点都有一个后继。n个点，n-1个后继。作为一个算法竞赛选手，当你听到“n个点，n-1条边”这句话的时候DNA就该有反应了。
如何实现呢？其实这个过程很类似prim算法求解最小生成树，你只需要以终点为起点做bfs，然后记录过程中每个节点的后继，当出现多个备选项时取min即可。
你看上面是不是有8颗树？
诶？有人不是树？这就是关键了。
观察到当state=101和state=111的时候，49号节点和67号节点没有后继。如果说图是连通的，那么除了终点以外，其他的每个点都必一个后继。
49和67没后继，那太好了，说明它们和终点压根就不连通。
part 3 重建图再搜索
其实根据题意，牛妹就是个机器人，我们想让她干啥她就得干啥。我们可以使用continue指令让牛妹在当前位置沿着紫色的边往前走1步，也可以使用lock和unlock指令让牛妹在不同状态的图对应节点之间“移动”。
重新建图，这次只用连接紫色的“生成树边”和不同状态对应节点之间的“状态转移边”。
part 4 搜索回溯
用dfs做回溯的话就，特别简单...基操不教。（基本操作，不会有人dfs不会输出答案吧，不会吧不会吧）
bfs的话萌一点的萌新讲真还真不知道。这个其实也很简单，多开一个pre数组记录前驱。bfs的过程肯定是某一个节点引出下一个节点，pre表示第x的节点是pre[x]引出的，所以一路寻找pre[x]，直到没有前驱为止。然后将这个序列整个翻转就是答案序列。
然后搜索出的答案序列为1->19->21->30->31->13->49。
然后根据答案序列翻译成指令，走紫色边就是continue，跳图就是lock和unlock
lock 6 //1->19 continue //19->21 lock 3 //21->30 continue //30->31 unlock 6 //31->13 lock 2 //13->49 checkmate!
C、牛牛与字符串border
出这个C和D的题面其实是为了面向刚入算法竞赛门的选手做一些科普。稍微有个印象，日后学字符串好相见。
当然这个C题面设计的不光是为了科普，也有点故意不说人话，把选手往样例上面赶。然后样例做一些简单的“诱导”去骗一些WA。
这个题的坑如果想当然的话肯定要踩一下的。不过老手如果不是自己打而是在比赛里的话一般不会踩...原因嘛，看解题思路的part 2.5咯。
解题思路
上来读题，然后看了半天不知道在说啥。知道大概是字符串构造，但是具体要求不清楚。
part 1 看样例
看样例就会盲猜一个构造gcd(n,k)为循环节的循环串，要求和原串长度相同并且修改的次数最小。这时候写不写呢？
如果你觉得有猫腻，但是能过样例。根据代码量判断，如果代码量很小，那直接撸，撸完再说。不然的话还是建议稳一手仔细想想。
part 2 桶装法
假设循环节为g的话，那么字符串下标为g,2g,3g...kg的字符都必须是相同的字符。
然后g+1,2g+1,3g+1....kg+1这一组也必须是相同的字符。
这个的话有个技巧，就是按照下标i%k分组。
题目要求修改次数最小，那么这里有个小贪心。就是把每一组都改成众数字母，这个应该不难想。
part 2.5 看眼榜
写完测过样例之后一定先别着急交，这种找规律的题尽量让赛场上其他队给你当工具队去探路。自己要冷静别头铁。
这个技巧是在比赛当中才会用到，就是说如果这是一个结论题，然后样例又能看出明显的诱导性，这时候重点关注一下前几发提交，总有头铁的人去试出题人有没有在样例里下套或者骗人。然后这个题你一看就有问题嘛，然后就得小心一点了。
part 3 上暴力
#include
using namespace std;
const int MAXN=100005;
int fa[MAXN],n,k;
int findf(int x)
{
return fa[x]==x?x:fa[x]=findf(fa[x]);
}
void unions(int x,int y)
{
if(findf(x)!=findf(y))
{
fa[findf(x)]=findf(y);
}
return;
}
int main()
{
while(scanf("%d %d",&n,&k)!=EOF)
{
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
for(int i=k;i<=n;i+=k)
{
for(int j=1;j<=i;++j)
{
unions(j,n-i+j);
}
}
mapmp;
int cnt=0;
for(int i=1;i<=n;++i)
{
if(!mp[findf(i)])mp[findf(i)]=++cnt;
cout<<mp[findf(i)]<<" ";
}
cout<<endl;
}
return 0;
} 看过榜之后发现规律不是白给的就要冷静一下，然后如果说按照题意模拟起来不麻烦。那务必选择打暴力，暴力程序的收益其实很高，我们来算笔账。
1、节约了徒手找规律的时间和精力。
2、节约了手算数据的人力。
3、可以对拍拍到爽，至少节约1到2次罚时。
如果是多人比赛的话只要电脑空下来就可以用来搓暴力。（人歇机千万别歇）
part 4 找规律
这个规律只要写了暴力其实很好找嘛，除了题目样例给的gcd的情况，特殊的情况就是当k>=n/2的时候，循环节变成了n-k，这个时候只要稍微改改之前写好的代码很快就AC了。
简单证明
假设k<n/2
那很显然，根据题意一定会产生k和2k两个限制条件。根据border定义，此时圆圈部分等于圆圈部分，五角星部分等于五角星部分。但是问题来了，这是一个串，不是两个串，而这个后缀中五角星和圆圈是同一个位置，说明五角星和圆圈应该是同一个字符。
所以循环节一定是k的因数。
此时这个循环节变成了n-n/k*k，这个表达式其实就是模除取余数。所以循环节不但是k的因子也同时是n%k的因子。
so，公因子里面选个最大的就好。
问题来了gcd(n,n%k)它是啥呢，它不就是gcd(n,k)。
假设k>=n/2
如果k比n的一半还大，那显然只有一个限制条件。然后如图所示吧，我觉得一看就懂。
D、牛牛与整除分块
整除分块是数论里面一个挺重要的东西，数论入门的时候，积性函数枚举因子，枚举除数，都会用到它。
借题面向新手科普一下这个东西，当然这道题本身的规律并不难。
解题思路
part 1 看范围
当你看到1e6组n<=1e9以内的范围时。就应该立刻意识到算法是O(1)的，卡的太死了。
part 2 打暴力
这个东西我觉得你不会的话那就是没办法的啊，真的只能打暴力看看。
#include
using namespace std;
int n;
setse;
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;++i)se.insert(n/i);
for(set::reverse_iterator i=se.rbegin();i!=se.rend();++i)
{
printf("%d ",*i);
}
printf("\n");
}
return 0;
} part 3 找规律
首先可以发现，当k小的时候答案是k。然后顺着思路去想，k“小”如何界定。然后应该是不难发现这个界限大概是根号n附近，有时候会多一两个。
不难发现如果将他们两两配对（最大的数和最小的数），它们的乘积总是最接近39的。
这个性质有点类似实数除法中除数和商的互逆性质。在实数中的话
。这里配好对以后对于配对的数字，也满足
时
。
然后算法就有了，当输入的k小于时输入什么，输出什么。反之的话看n/k是几，然后利用对称轴x=
给他对称过来就知道答案了。
E、牛牛与跷跷板
这个题就是想给到搜索题，但是觉得直接走格子迷宫搜索的话太白给了。（而且有太多原题了，挺无聊的）然后就加了个two pointer的算法，实际上你二分也能过。two pointer这个算法可以翻译成双指针，尺取法。去学的话搜这两个关键词就行了。
解题思路
part 1 bfs
如果你学过bfs，然后看到这个题脑子里没有半点搜索的意思。那bfs就白学了，一般情况下只要学过bfs，做过题应该就能看出来这是道搜索。
part 2 建图
①左右相邻
对于左右相邻的情况，因为按照y分好了组，在排序后可以O(n)处理。只有顺序相邻的板子才有可能物理上是相邻的。
②上下相邻
其实还是这样红绿红绿交替建边（边都是双向边，这个箭头只表示建图的顺序），只不过这次得处理一下一次性多连几个。然后建完图直接搜就行了。
F、牛牛与交换排序
这个题思维上不是很大，估计会平衡树的人不多，应该不会有人想不开上个平衡树吧？
这个题的spj其实是烟雾弹，除非一开始就排好序了，不然k是唯一的。不会有多解啦。
解题思路
part 1 首先确定k
根据题意，你在做翻转操作之前要给定一个k，并且k一旦确定就不能再改了。
5 5 2 1 4 3
看样例分析一下，想要确定k其实不难。你要想吧5 2 1 4 3排序排成1 2 3 4 5，k就必须等于3，不然你1都换不过去。（题目的限制条件是每次选翻转的区间只能更靠右，所以不能用长度为2的区间翻转两次达到这个效果）
所以说只要数组不是已经排好序的，k上来就定了。确定k的方法是从左到右找到第一个顺序不对的数字，然后看它的位置和现在位置的距离。
part 1.5 双端队列和翻转标记
队列和堆栈都是只能在一端插入数据，然后在某一端取出。但是双端队列呢它就厉害一点，它两端都能操作。这个数据结构还是挺常用的。有一点切记，千万不要用stl的双端队列容器deque，这个容器用不得，常数在天上飞了。
现在有个需求，给你这么一个双端队列，然后让你在支持双端队列的基本操作的前提下加一个将队列中的元素全部翻转的需求。
这个实现起来也不难，引入一个翻转的懒惰标记。当不存在懒标记时正常做队列操作，反之如果存在懒标记，那么此时本应操作队头时改为操作队尾，本应操作队尾时改为操作队头就可以了。（为什么可以这样搞呢，因为双端队列这种线性表结构本来就是左右对称的，所以可以用对称操作来实现“翻转”的效果）
const int MAXN=1e5+5;
struct deQue
{
int buffer[MAXN*2];
int head=MAXN,tail=MAXN-1;
bool rev;
bool empty()
{
return tail<head;
}
int size()
{
return tail-head+1;
}
int front()
{
return rev?buffer[tail]:buffer[head];
}
int back()
{
return rev?buffer[head]:buffer[tail];
}
void push_front(int x)
{
rev?buffer[++tail]=x:buffer[--head]=x;
}
void push_back(int x)
{
rev?buffer[--head]=x:buffer[++tail]=x;
}
void pop_back()
{
rev?head++:tail--;
}
void pop_front()
{
rev?tail--:head++;
}
void reverse()
{
rev^=1;
}
}q; part 2 check
根据part 1，其实已经找到了k，接下来只要确定这个k到底ok不ok就行了。有了带翻转标记的双端队列，这个check函数不难想。只要依次遍历过去，把数字插入到队列当中，然后如果队尾元素不是你要的，就翻转过来看看。如果都不行，那肯定凉了。
最后再遍历一遍整个数组，看是不是真的排好序了。
G、牛牛与比赛颁奖
这个题本来是想出一个比较水的模拟，然后它怎么变成现在这样了呢。就...还是不想白给。然后就想
“那我们模拟的时候加个差分前缀和吧”
然后意识到一个问题，听说自己家新生赛的时候裸的差分前缀和玩烂了。那不行，那不白给自家新生了。
“那我们扩一下范围再加个离散化扫描线吧”
然后回过神来这个题就不是纯小白题了，但是这个题也没有脱离新生题的范畴，用到的小trick小结构也算比较简单的那种。
解题思路
part 1 差分
利用差分操作，可以很轻松的把一个区间操作拆分成两个后缀操作的叠加效果。如果n的范围是1e5,1e6,1e7的话是可以用数组直接储存。但是也就是“存不下”而已，差分拆区间照拆不误。
part 2 扫描线
part 3 桶装法统计
看一眼题目的范围，m的数据范围在1e5，最极端的情况不过是一个队加了1e5次。如果按照和为X装桶，每个桶里面储存AC题数恰好为X的队伍，是能存的下的。所以一边扫描，一边桶装。
part 4 按题意模拟
用桶装法统计完数据只要按照题目要求做就行了，注意题目中所说的那两个特殊点，奖牌线为0题和同时满足多个奖牌要求时要能够判出来。这是一个易错点。
H、牛牛与棋盘
签到题，本场白给的题
解题思路
part 1 双重for
就两重for循环打印矩阵就好了，这个黑白格子的划分可以用位运算&1，或者模2这样比较取巧的方式实现。
I、牛牛的“质因数”
出这个题是因为，发现有的人学筛法学的真的死。就，他的埃式筛就真的就只能用来筛质数。线性筛存了无数个板子，什么《线性筛质数》，《线性筛因子数》，《线性筛因子和》，《线性筛欧拉函数》，《线性筛莫比乌斯函数》....
确实很多算法没必要搞懂底层原理，比如说一些卷积类，图论算法。搞懂其实也玩不出花来。但是显然筛法不一样，与其存一坨不如好好学一下。
顺便也提一句，线性筛不是埃式筛的上位替代。该会的都得会，又不是玩手游，怎么还搞五星六星上下位替代。
埃式筛有个花活，就是它可以配合莫比乌斯函数做一些简单的数论容斥。在某些数论问题当中可以略微代替莫反。（莫反也是容斥，但是比较重，而且推式子比较苦手，能筛的话肯定是选筛啊）
解题思路
part 1 线性筛建树（或者埃式筛也是一样的，不过要取最小）
昨天听雨巨讲课的时候讲了线性筛，那太好了，大家听了课肯定都会了啊。（误）
没听懂其实也没关系。这个筛法树的建立只用到了线性筛的一点性质。
想一个问题，为什么埃式筛是O(nlog)的，但是线性筛是O(n)的。
因为埃式筛的每一个合数被重复筛过了，而线性筛每个合数仅被筛到一次。
对于一个质数，其实可以看成是1去乘上这个质数得到。
而对于一个合数，显然线性筛找到了一个最小的质数乘上一个数得到这个合数。
好，那么除了1以外，剩下所有的数字都有一个质数跟他产生了关系。
这个就是“n个节点，n-1个关系”，看到这句话，DNA要起反应。
对于每个节点，如果它是质数的话，父节点就是1，如果它是合数的话，父节点就是线性筛的时候用那个数筛到了它。
从筛法树上的节点往根节点爬，取出沿途的边权质数，就得到了对于某节点质因数分解的全部质数。
part 1.5 线性预处理的质因数分解
有“筛法树”这个思想以后，线性的质因数分解就变成了基操。（当然，分解确实是线性的，如果要打印出来就还是log的）
#include
using namespace std;
const int MAXN=10000005;
int prim[MAXN],tot,fa[MAXN],fa_edge_prim[MAXN];
bool is_prim[MAXN];
void prim_table(int n)
{
tot=0;
is_prim[0]=is_prim[1]=false;
for(int i=2;i<=n;++i)
{
is_prim[i]=true;
}
for(int i=2;i<=n;++i)
{
if(is_prim[i])
{
prim[++tot]=i;
fa[i]=1;
fa_edge_prim[i]=i;
}
for(int j=1;j<=tot;++j)
{
if(i*prim[j]>n)break;
is_prim[i*prim[j]]=false;
fa[i*prim[j]]=i;
fa_edge_prim[i*prim[j]]=prim[j];
if(i%prim[j]==0)//f(p*m),p为质数，p整除m，即m=p^k*q的情况。
{
break;
}
}
}
}
int n,x;
int main()
{
prim_table(10000000);
scanf("%d",&n);
while(n--)
{
scanf("%d",&x);
if(x==1)
{
printf("1\n");
continue;
}
while(x!=1)
{
printf("%d",fa_edge_prim[x]);
if(fa[x]!=1)printf(" ");
x=fa[x];
}
printf("\n");
}
} part 2 筛法树上DP
其实有了筛法树，这道题已经可以O(nlogn)的复杂度做了，就沿着筛法树爬就行了。按照题意模拟全都取出来然后模拟拼接。
但是DP的话是可以做到整个题都是O(n)的。然后这个DP方程不难推，举个特例
比如用2筛到24时，F(12)=223,F(24)=2223，就可以写作F(24)=F(24/2)+2*10^3
坑点在于，出了2,3,5,7以外，其他质数可不止一位。所以实际上还要记录当前F(x)的数字是几位数。
J、牛牛想要成为hacker
本场第二有意思的题（自认为），这个题怎么来的呢。就之前在牛客出练习赛，然后签到题是那个给你若干个数，然后输出一个三角形。然后当时数据范围放了n=1e5，然后我说大概能暴力，因为n^3拉不满。然后转念一想，不对啊，真的拉不满么？最后改成了n=100，然后就有了本题。
然后说一下啊，这个题的数据范围是1e5，但是没放满。为什么呢，因为再大的话服务器跑spj就受不了了。而且就算跑完了判题也贼慢，比赛交的人多怕炸服务器所以最后实际上只放了大概8e4左右。
解题思路
part 1 任取3个数不能构成三角形
这个点相对来说比较简单，样例里面给了一种幂函数的数列是绝对组不成三角形的。
但是这个显然不够优嘛。手玩一下肯定是能发现，斐波那契数列正是不能组成三角形并且增长速度最慢的数列。
part 2 拖，就鞥拖
如果说不限制构造数字的值域，那显然可以非常简单的达成part 1 里面的任取三个数都不能组成三角形。
很显然，根据暴力算法，for三重循环i,j,k，当j和k循环转满一圈后，i才++。
那么假设红色箭头代表i，蓝色箭头代表j，绿色箭头代表k。硬拖时间最多拖到三个循环变量全部离开斐波那契段为止。
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin >> n;
int a[50];
a[0]= 1;
a[1]= 2;
for (int i = 1; i <= min(40, n); i++)
{
cout << a[i] <<' ';
a[i+1] = a[i]+a[i-1];
}
for (int i = 41; i <= n; i++)
cout << 1 <<' ';
return 0;
}
全部评论
(13) 回帖