程序员进阶之算法练习（十四）

前言

坚持做算法练习对开发的好处是抽象能力变强，拿到一个需求能很快对其进行抽象，然后再用学过的设计模式相关知识进行整理，最后用代码实现。
最大的好处在于：对功能的抽象以及整理会更容易实现，用设计模式来整理便于维护，写完之后很容易测试。
讲那么多，首先的要求是坚持。

正文

本文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）
假设在a^2+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，求推荐深圳的坑，私信联系。