程序员进阶之算法练习（十四）
前言
坚持做算法练习对开发的好处是抽象能力变强，拿到一个需求能很快对其进行抽象，然后再用学过的设计模式相关知识进行整理，最后用代码实现。 最大的好处在于：对功能的抽象以及整理会更容易实现，用设计模式来整理便于维护，写完之后很容易测试。 讲那么多，首先的要求是坚持。
正文
本文5个题来自CF707，所有的题解代码在这里。 题目难度从低到高，最后一题光题解就写了一页。
- A 简单题；
- B 简单题；
- C 数学题；
- D 实现题；
- E 优化题；
A
题目链接
题目大意
输入n * m个字符，字符中存在C M Y为混色，否则为黑白，输出对应的描述。
Examples input 2 2 C M Y Y output #Color
input 3 2 W W W W B B output #Black&White
题目解析
难度在读题，黑白不仅仅是W B，还有G。
B
题目链接
题目大意
n个城市，其中k个城市提供面粉，城市中有m条路。 在n个城市中的选择一个不提供面粉的城市，要求这个城市能到达提供面粉的城市，如果有多个输出边长最小的一个。（没有输出-1） n, m and k (1 ≤ n, m ≤ 10^5, 0 ≤ k ≤ n)
Examples input 5 4 2 1 2 5 1 2 3 2 3 4 1 4 10 1 5 output 3 input 3 1 1 1 2 3 3 output -1
题目解析
n个点，m条边，k个关键点。在关键点外的集合n-k，中找到一点T，使得T与关键点中任意点连接，并且边长最小。 难度都在读题，容易知道，关键点只要存在一条边与非关键点相连，那就有解。 存下边，把点标记为关键点(f[i]=1)和非关键点(f[i]=0) 遍历查找边由f[i]=1到f[i]=0的最小边即可，无解输出-1。
C
题目链接
题目大意
给出一个数字n，求一组勾股数中的另外两个，使得三个构成勾股数。 n (1 ≤ n ≤ 10^9)
Examples input 3 output 4 5 input 6 output 8 10 input 1 output -1
题目解析
容易知道，n=1,2无解。（最小的勾股数3、4、5） 假设在a2+b2=c^2 中 令a=n 那么有n*n=c*c-b*b=(c+b)*(c-b) 当n为奇数时，令c-b=1, 有n*n=(b+1+b) => b=(n*n-1)/2 当n为偶数时，令c-b=2, n*n=(b+2+b)*2 => b=(n*n/2-2)/2
令mod=2-n%2，那么有b= (n*n/mod - mod)/2
D
题目链接
题目大意
n*m的格子，q个操作 (1 ≤ n, m ≤ 10e3, 1 ≤ q ≤ 1e5) 每次有4种操作： 1 i j, a[i][j] = 1 2 i j, a[i][j] = 0 3 i, for j in a[i], a[i][j] = !a[i][j] 4 k, 返回操作到第k次的状态，k=0表示起始状态。 每次操作后输出当前格子为1的数量。
Examples input 4 2 6 3 2 2 2 2 3 3 3 2 2 2 2 3 2 output 2 1
3 3 2 4
样例的解释
题目解析
操作1、2比较简单，操作3是组操作，设置flag[i]表示第i行在最终结算时是否翻转，那么有 操作1为a[i][j] = !flag[i]. 操作2为a[i][j] = flag[i]. 操作3为flag[i] = !flag[i].
操作4较为复杂，回到操作k，k为之前的操作。 考虑到题目对k没有限制，那么k可以为之前的某个回退操作，从而产生递归回退的效果； 同时回退到操作i之后，下一步可以再回退到操作j，这样线性的操作不可取。 但是单个操作只会是一个线性的分支，整个操作序列可以形成多个线性的分支，汇总在一起就是一颗树的表现。 对于第i个操作，操作完毕后的状态为j，连一条边从i到j，表示从第i个操作完之后会进入操作j的状态。 那么对操作1、2、3，i会连上一条边到i+1；操作4，i会连上一条边到k。 对于某一个操作，先执行，然后dfs，最后撤销执行即可。
E
题目链接
题目大意
输入k条链，链上的节点在n*m的矩阵上； 每条链有len[i]个点，每个点的输入包括x、y、w表示在n*m矩阵上的坐标和权值。 q次操作， 操作1，把链上的点翻转（权值由w变成0，或者从0变成w）； 操作2，询问子矩阵内点的权值; 操作2最多2000次； （n,m,k = 2000, q=10^6）
Examples input 4 4 3 5 1 1 2 1 2 3 2 2 1 2 1 4 3 1 7 4 1 3 1 2 3 3 2 4 3 1 4 1 7 4 1 1 4 2 9 3 2 8 3 3 3 4 3 4 4 4 1 3 4 1 2 ASK 2 2 3 3 ASK 1 1 4 4 output 15 52
样例
题目解析
先看最暴力的做法，对于每个switch，把点的值Switch；对于每个ask，遍历所有的链得出结果。 优化部分，添加flag，标志每次switch，询问时再进行计算。 每条链复杂度为O（Len），k条链的修改为O（n)O(m)，询问的时间为O(n)O(m)。 总的复杂度为O(nm2000)2=1610e9。（*2是因为每次询问都要修改一次、求和一次）
接着使用数据结构来优化。 易知，子矩阵求和使用树状数组即可。求和操作可以优化为O(logN)*O(logM)。 同样在询问的时候再来修改权值，那么有修改复杂度为O(logN)*O(logM)*O(N)*O(M)。 求和复杂度可以忽略，总得复杂度为2000 * log2000 * log2000 * 2000 * 2000 = 8 * 10e10。 （虽然理论上q=10e6限制了当矩阵数为2000时，每次询问前的switch操作有限，但是一条链可以很长，对很长的链进行操作即可，所以最后的修改次数我们还是按N*M来计算） ** 为什么变大了？**
因为每次询问前的修改操作变成耗时操作，如果题目每次在询问前都修改所有的值，复杂度会很高。 继续优化。 每次修改的都是同一个值（整条链为0，整条链恢复），那么可以预处理出这个值d[i][j]，表示第i条链对第j个子矩阵的贡献。 这样就可以避免每次询问前修改值，使用之前预处理的计算值即可。 复杂度为5*2000*2000*log2000*log2000 = 2billion； 全部为加法，并且题目给出的时限为3s，可行。
用空间换时间是典型的优化。
总结
现在的工作不是很忙，每天早上提前到公司可以写写文章，空间的空闲可以做做题目，不知道明年是否还有这样的环境。
PS，求推荐深圳的坑，私信联系。