程序员进阶之算法练习(十四)

前言

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

正文

本文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,求推荐深圳的坑,私信联系。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爬虫与数据挖掘

浅谈网络爬虫中深度优先算法和简单代码实现

学过网站设计的小伙伴们都知道网站通常都是分层进行设计的,最上层的是顶级域名,之后是子域名,子域名下又有子域名等等,同时,每个子域名可能还会拥有多个同级域名,而且...

16440
来自专栏杨熹的专栏

几种简单的文本数据预处理方法

本文将介绍几种简单的文本数据预处理方法,希望与大家共同学习分享。

33540
来自专栏贾志刚-OpenCV学堂

TensorFlow中的feed与fetch

TensorFlow中的feed与fetch 一:占位符(placeholder)与feed 当我们构建一个模型的时候,有时候我们需要在运行时候输入一些初始数...

51470
来自专栏wym

opencv imwrite函数参数详解+例子

cv2.imwrite(1."图片名字.格式",2.Mat类型的图像数据,3.特定格式保存的参数编码,默认值std::vector<int>()  所以一般可以...

98620
来自专栏QQ音乐技术团队的专栏

​关于M4A文件的随机访问

文章介绍了M4A文件的大概结构,详细解读了其中的Sample Table Box,并结合图例,详细讲解了如何使用它来完成M4A文件的随机访问。 本文属原创作品,...

39680
来自专栏深度学习那些事儿

在pytorch中实现与TensorFlow类似的"same"方式padding

文章来自Oldpan博客:https://oldpan.me/archives/pytorch-same-padding-tflike

3.2K70
来自专栏QQ音乐技术团队的专栏

​关于 M4A 文件的随机访问

文章介绍了 M4A 文件的大概结构,详细解读了其中的 Sample Table Box,并结合图例,详细讲解了如何使用它来完成 M4A 文件的随机访问。

45800
来自专栏ChaMd5安全团队

小姐姐教你做CTF逆向题:利用符号执行技术和约束求解器

0x00 前言 在CTF比赛中,逆向类题目常常以考察选手的逆向分析能力、算法分析能力角度出发,通过还原程序中的算法逻辑,从而获取flag。但是如果可以在程序执行...

1K120
来自专栏吉浦迅科技

DAY15:阅读CUDA C runtime之纹理内存

14830
来自专栏Soul Joy Hub

TensorFlow指南(二)——练习思考:上手TensorFlow

http://blog.csdn.net/u011239443/article/details/79075392 创建一个计算图而不是直接执行计算的主要好处是...

31340

扫码关注云+社区

领取腾讯云代金券