截至到201809的素有ccf题解

n较小，直接遍历所有的数据

模拟
对每个数据处理后加入并且更新结果

首先想到的是暴力的算法o(n2)，数据范围是1000
另一种做法：单调栈o(n)
每次只需要把每个位置处的数据向两端延伸，找到以当前数据为最小值的最左端的数据和最右端的数据
单调栈维护的每个数据往左第一个小于当前数据的位置，对于每个数据来说只要top>当前数据，直接入栈，否则取出所有不满足单调性的数据更新ans
对于每个不满足单调性的数据来说，栈顶的下一个元素是她往左的第一个小于她的数据，当前i是栈顶往右的时候第一个小于她的数据，因此可以求得以栈顶为最小值的
子序列的最小值
扩展：单调栈的应用的三类题型 https://blog.csdn.net/zuzhiang/article/details/78134247
刷篱笆 http://codeforces.com/contest/448/problem/C

数位dp
和其他的数位dp不同的是，此题不要求数据的上限，只要求数据的位数，因此可以直接采用for循环
共有6中情况：
1:只出现过2
2:只出现过2,0
3:只出现过2,3
4:只出现过2,0,1
5:只出现过2,0,3
6:只出现过0,1,2,3

正向遍历与反向遍历！ 最开始看到题目想到的是用两次bfs，从起点开始进行一次bfs，再从终点开始进行一次bfs，但是后来发现不可以，因为从终点可以到一个点，但是不一定在起点经过这个点时候还是可以到达终点，比如样例中的那个情况
因此，用到了一个able[x1][y1][x2][y2]数组，表示从(x1,y1)->(x2,y2)可达，第一次普通的bfs找到起点可达的点且的到able数组
第二次遍历的时候从终点开始，四周的点根据able数组确定下一个点去哪里

题目中限制了所有出现的数据均不相同，因此直接使用一个标记数组表示一个数或者一个数的绝对值是否出现过，只要同一个绝对值出现了两次，便有一对新的相反数产生
扩展：若是没有限制每个数只能出现一次，需要两个标记数组，分别存放数值绝对值的个数，分别表示这个绝对值所对应的正数和负数的个数，两者中的较小值便是和

模拟
b数组记录从上到下的窗口分别是第几个窗口
对于每次询问，从上到下依次遍历每个窗口，只要点击点在当前窗口内，便更新窗口所在的相对位置，上面的窗口位置往下，点击点变为第一个窗口

最短路的变形，采用万能的spfa算法或者bfs
与一般的最短路问题的区别是：此题中有限制k，只能够选择不超过k个的空位置
带来的不同便是，原先在访问一个点的时候只需要判断此点事都之前访问过便可以决定是否可以访问此点，但是即使之前访问过当前点，现在仍然可以访问当前点，因为访问当前点时的状态，即经过的限制位的个数不同，仍旧可以访问当前位置，因此，只需要在原先的状态上再加上一位便可以接着访问

简单模拟

暴力模拟o(n3)
对于每个给出的矩形， 遍历矩形内的所有的点，只要是没有刷过的，就更新答案

KMP字符串匹配算法 https://blog.csdn.net/ebowtang/article/details/49129363
写作模板 https://paste.ubuntu.com/p/kpsZnk6bkC/
next数组表示到达当前下标位置时的前缀后缀长度，因此当第k个不相同的时候，需要从第k-1个的下标开始找相同

最短路的变形问题
由于不限制每个分店的送餐数量，因此直接将每个分店均作为其bfs的最开始的起点进行bfs即可
不需要使用spfa算法，因为对于起始点始终平行，全部都是一起更新，不存在某一个被前面一个起点更新之后会被后面一个起点更新的情况

简单模拟，遍历直接输出

模拟 思路：首先需要考虑当前趟是往上还是往下，往上时i-1,j+1，往下时i+1,j-1,同时需要考虑边界，边界涉及到转向的问题，且对于上半部分和下半部分来说边界的处理是不一样的，对于上半部分往上是i=0的时候，往下是j=0的时候，对于下半部分，往上是j=n往下是i=n；实现的时候可以将shang'xia 两部分分开处理，也可以全部放在一起当作同一个边界来处理。代码实现时没有区分上半部分和下半部分。
这道题我开始用递归写的，但是没法通过，直接爆栈，改成循环可以通过。

大模拟
首先需要将所有的买卖命令处理一遍，得到当天结束的时候所有的出价及其股数已经进价及其股数，然后再求使得开盘量最大的开盘价
最开始我想使用三分求解，因为买家在高于开盘价的时候买入，卖家在低于开盘价的时候出售，因此当开盘价过低的时候，大部分买家可以买入，但是少部分卖家可以卖出，反之则反之，呈现一个拱形的趋势，但是不知道为什么过不了，后来想想这道题目，ai < 开盘价 < ai+1的时候结果和开盘价==ai是一样的，因此直接枚举所有的出价和进价，得到使得成交量最大的开盘价，此时开盘价是一个精确到2位小数的数值，因此开盘价便是大于当前开盘价的下一个开盘价-0.01的结果。

最小生成树问题，给定结点以及节点之间连接情况,连接所以的结点并且需要使得所有连接节点的边之和最小
采用加点法的最小生成树，每次找到一条连接已选择的点和尚未选择的点的最小的一条边，将此边加入集合中，然后再使用当前点更新其他的所有的结点的最短距离，直到所有的点都被选择。

将矩阵逆时针旋转90度，直接按照列，从后往前从上往下输出即可。

简单的排序问题，考察当具有多个属性时的排序问题。

首先从树的任意一个结点开始，bfs找到最远的一个结点，则此节点必然是直径的一个端点，然后再从此点开始bfs最远的点即是直径的另一个端点，证明如下 https://blog.csdn.net/xiaotan1314/article/details/53033829

最短路变形，在原先最短路的基础上维护一个当前食物的价格的值即可

只要当前数据与前一个数据不同那么答案就需要更新加上1

简单模拟，直接根据用d减去每个月的天数

求强连通分量的个数 https://www.cnblogs.com/nullzx/p/6437926.html
先将所有的路径取反，然后再后序遍历整张图， 将遍历结果入栈，然后再根据栈中数据的顺序遍历整张图