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

前言

这四个题属于中等,有的需要一定的代码量,有的需要奇妙的思考。

正文

1. Sonya and Queries 题目链接 ** 题目大意:** 给出一个集合T,n个操作; 每个操作有3种情况: 1、往集合T里面添加一个数字x; 2、往集合T里面删除一个数字x; 3、询问集合T里面,里面与s能匹配的数量。 匹配的方式:对于两个数字x、y,如果两个数字每一位的奇偶性都相同,则认为匹配(不足的位数补0)。 357和135: 357 135 匹配;

13和257: 013 257 匹配;

13和247: 013 247 不匹配;

Exmample input 4 + 200 + 200 - 200 ? 0 output 1

n<=10w, x的范围10^18,添加的数字可以相同,删除时如果有多个数字x只删除一个;

题目解析: 从匹配方式入手。 奇偶性相同,意思就是对于每一个数字,可以转换成01010111的字符串。 那么数字x是否和数字y匹配,就相当于他们的010101字符串是否相同,那么我们可以定义一个trans操作。 数字x和数字y匹配,当且仅当trans(x) = trans(y)。

再来看操作1和操作2,对于询问来说245、45和5是等价的(001,01,1)。 那么操作1可以简化成加入一个trans(x)的数字,操作2简化成删除一个trans(x)的数字。 题目可解。

2. Sonya and Problem Wihtout a Legend 题目链接 题目大意: 给出n个数字,每次可以把一个数字+1或者-1,代价为1; 问把n个数字改为严格递增序列的最小代价。 n (1 ≤ n ≤ 3000) ai (1 ≤ ai ≤ 1e9).

Example ** input** 5 5 4 3 2 1 ** output** 12 样例解释: 1 2 3 4 5 |5 - 1| + |4 - 2| + |3 - 3| + |2 - 4| + |1 - 5| = 12

题目解析: 如果是非严格递增(即是a[i]=a[i+1]是可行的),可以用dp来解决。 令b[i]=第i大的数字, dp[i][j] 表示第前i个数字转移到第j大的数字的代价; 那么有dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(a[i] - b[i])); 1<= k <= j; 在求dp[i][j] 的过程中,维护一个dp[i-1][1~j]的最小值即可。 代码非常简短,如下:

    int n;
    cin >> n; 
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] = b[i] = a[i] - i;
    }
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        lld maxInf = llinf;
        for (int j = 1; j <= n; ++j) {
            maxInf = min(maxInf, dp[i - 1][j]);
            dp[i][j] = maxInf + abs(a[i] - b[j]);
        }
    }
    lld ans = llinf;
    for (int i = 1; i <= n; ++i) {
        ans = min(dp[n][i], ans);
    }
    cout << ans << endl;

3. Plus and Square Root 题目链接 ** 题目大意:** 有一个特殊的计算器,只能执行加号和求平方根的操作,计算器有一个等级,用数字k表示;初始值为x。 执行完加号操作后,x=x+k; 执行完求根操作后,x=sqrt(x);(这个操作只有当x是perfect square的时候才能执行,且要求执行完的x必须是等级的倍数) 执行完求根操作后,等级会上升,k=k+1;(注意,执行完求根操作后,等级+1后再进行倍数的判断) 初始等级是1,初始值是2,问要到达等级n+1,在每次求根操作前需要执行几次加号操作? 如果有多个解,输出任意解都可以。

** Examples** ** input** 3 ** output** 14 16 46 样例解释:表示在等级1、2、3的时候分别按14、16、46次加号;

** 题目解析:** 思路是从根号入手,题目要求x进行sqrt操作后的数字是等级的倍数,列出等级和初始值

 LEVEL  Init
 1      2, 2+1, 2+1+1
 2      2, 2+2, 2+2+2, ..., 2*(3*3*2)
 3      3*2, 3*2+3, 3*2+3+3, ..., 3*(4*4*3)
 ...
 i      i*j, i*j+i, i*j+i+i, ..., i*((k+1)*(k+1)*i)

sqrt( i*((k+1)*(k+1)*i)) = i * (k+1) 这样就找到一种构造方式,满足题意。

4. Complete The Graph 题目链接 题目大意: 给出n个点,m条边,边的长度为0到10^9;长度为0的边表示可修改边。 可修改边都需要赋值,边长必须是正整数。 要求赋值完成后,点s到点t的最短路刚好为L。 s n, m, L, s, t (2 ≤ n ≤ 1000,  1 ≤ m ≤ 10 000,  1 ≤ L ≤ 1e9,  0 ≤ s, t ≤ n - 1,  s ≠ t)

Examples input 5 5 13 0 4 0 1 5 2 1 2 3 2 3 1 4 0 4 3 4 output YES 0 1 5 2 1 2 3 2 3 1 4 8 4 3 4 样例解释:把边1-4的长度赋值为8。

** 题目解析:** 先不考虑可修改边。 求出s到t的最短路。 枚举每一条可修改边,先按照长度为1的大小加入;如果加入后的最短路小于L,则找到解,剩下的所有可修改边重置为inf。 在最短路中的找到刚刚添加的最后一条可修改边,把变成重置为L-dis+1,得到一个解。

总结

脑海中还积累着一部分知识,仍需一点时间理清思路。

灰蒙蒙的天气,犹如心情一样低沉。 昔日的球友在上海中医药大学打野球,本来阳光明媚的球场照片里应该也有我的身影。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老司机的简书

老司机出品——包教包会之玩转正则表达式

结束了CoreAnimation系列之后,老司机心里仿佛也轻松了许多。今天说说开发中的一个利器吧,正则表达式。

18330
来自专栏编程

程序员C语言C加加新手小白入门基础最容易犯的17种错误,你中了几个?

相信这么努力的你 已经置顶了我 C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考...

26150
来自专栏深度学习自然语言处理

【干货】python正则表达式应用笔记

正则表达式 (Regular Expression) 又称 RegEx, 是用来匹配字符的一种工具. 在一大串字符中寻找你需要的内容. 它常被用在很多方...

33080
来自专栏程序员互动联盟

【编程基础】c语言中获取整数和浮点数的符号位

1. 为什么要获得符号位 很多时候,我们需要判断数值的正负,来做相应的逻辑处理。条件判断语句可以很好的完成这个需求。有时候会有下面的情况, if ...

49380
来自专栏zingpLiu

python基础(一)

  python的创始人为吉多·范罗苏姆(Guido van Rossum)。1989年的圣诞节期间,吉多·范罗苏姆为了在阿姆斯特丹打发时间,决心开发一个新的脚...

34320
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(String专栏)

Python3 与 C# 基础语法对比:https://www.cnblogs.com/dotnetcrazy/p/9102030.html

15020
来自专栏程序员互动联盟

【C语言系列】C语言概念--基本数据类型简介

1.概述   C 语言包含的数据类型如下图所示: ? 2.各种数据类型介绍 2.1整型   整形包括短整型、整形和长整形。 2.1.1短整形   short ...

51580
来自专栏轮子工厂

卧槽,为什么你的程序执行到一半就退出了,原来是因为加了这个

快到月底了,相信有很多人都和呆博一样,不是“快揭不开锅了”,而是已经快要把锅都吃了〒▽〒。没关系我们可以一起吃掉这篇精神食粮啊,营养又健康,如果觉得味道还不错,...

35020
来自专栏前端下午茶

JS 原型模式

原型模式(Prototype pattern),用原型实例指向创建对象的类,使用于创建新的对象的类的共享原型的属性与方法。

43610
来自专栏恰童鞋骚年

你必须知道的指针基础-3.指针的移动及指针的危险

  指针每次加一就是指针向前移动指针类型对应的字节数。下面通过一个int指针来指向一个int数组,看看指针的加法运算到底是个什么鬼?

10820

扫码关注云+社区

领取腾讯云代金券