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

前言

这次只有四个题目,E题是个奇奇怪怪的数学题,就不去啃这个硬骨头了,我们来分析下A/B/C/D:

  • A题是简单的找规律题;
  • B题是博弈的入门题;
  • C题是简单的模拟题,题目较长;
  • D题是贪心,也可以说是构造。

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。

文集: 程序员进阶之算法练习(一) 程序员进阶之算法练习(二) 程序员进阶之算法练习(三) 程序员进阶之算法练习(四) 程序员进阶之算法练习(五) 代码地址

A

题目链接 题目大意:输入n,输出一个字符串。 n = 1:I hate it n = 2:I hate that I love it n = 3:I hate that I love that I hate it

代码实现

    int n;
    cin >> n;
    
    string ret = "I hate ";
    for (int i = 0; i < n - 1; ++i) {
        if (i % 2 == 0) {
            ret += "that I love ";
        }
        else {
            ret += "that I hate ";
        }
    }
    ret += "it";
    cout << ret << endl;

题目解析: 找规律。 把字符串分割成三部分"I hate " + ... + "it",再根据n构建中间的字符串。

B

题目链接 题目大意:一个游戏,每次把一个数字x拆成两个数字i,j并且i + j = x。 输入n个数字,轮流进行操作,不能操作者输,输出结果。 代码实现

    int n, t = 1; // 1表示先手必败 0表示先手必胜
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        if (k != 1) {
            t = 1 -( t ^ (k % 2));
        }
        cout << t + 1 << endl;
    }

题目解析: 假设,先手必胜为0, 先手必败为1. 那么有 0 + 1 = 0 1 + 0 = 0 0 + 0 = 1 1 + 1 = 1 异或操作符嘛。 具体理解思路就是: 1、当你对一个数x进行拆分时,其实就是拆分必胜和必败的状态; 2、必胜一步可以转为必败,必败一步可以转成必胜; 所以实际上根据奇偶数就可以判断必败或者必胜。 比如说:1是必败,那么2就是必胜,3就是必败,4就是必胜。

C

题目链接 题目大意: 题目为模拟手机系统本地推送。 输入n、q。 n为应用数量,q为操作数量。(1 ≤ n, q ≤ 300 000) 每行有两个数字x、y; x=1的时候表示id=y的应用产生一条notify; x=2的时候表示已读所有id=y的应用; x=3的时候表示读取前y个notify; 问每次输入后,剩余的未读数量。

代码实现

int n, m, ls = 1, k = 0, sum = 0;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        lld x, y;
        cin >> x >> y;
        if (x == 1) {
            a[++k] = y;
            ++num[y];
            ++sum;
        } else if (x == 2) {
            sum -= num[y];
            num[y] = 0;
            flag[y] = k;
        }
        else if (x == 3) {
            for (; ls <= y; ++ls) {
                if (ls > flag[a[ls]]) {
                    flag[a[ls]] = ls;
                    --num[a[ls]];
                    --sum;
                }
            }
        }
        cout << sum << endl;
    }

题目解析: 题目的难点在于操作2会更新应用所有的通知 以及 操作3读取前y个notify的去重。 观察题目,发现只关注未读的数量,而未读的数量只有操作1能产生。

把操作1形成的数字看成一串数列,num[i]记录id为i的应用目前的未读数量; 对于操作2,只需把num[y]清空,添加flag[y]=k的标志,表示应用y在第k个以前全部已读; 对于操作3,只需向右遍历数字,直到个数大于等于y。

PS:因为没看清题目的操作3,导致误认为是最新的前y个,实际是最初产生的y个,这样导致的难度相差比较多。

D

题目链接 题目大意:n个点,每个点有权值x[i],a[i], b[i], c[i], d[i]。 每个点都存在一条边到其他点,代价为: |xi - xj| + ci + bj seconds if j < i. |xi - xj| + di + aj seconds otherwise (j > i). 求从点s,到点t,遍历所有点的最短路径。(每个点只走一次)

代码实现

    lld ans = cost(src, dest);
    
    NEXT[src] = dest;
    for (lld i = 1; i <= n; ++i) {
        if (i == src || i == dest) {
            continue;
        }
        lld MAX = inf, key = 0;
        for (lld j = src; j != dest; j = NEXT[j]) {
            if (cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]) < MAX) {
                MAX = cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]);
                key = j;
            }
        }
        ans = ans + MAX;
        NEXT[i] = NEXT[key];
        NEXT[key] = i;
    }
    
    
    cout << ans << endl;

题目解析: 每个点都遍历一遍,那么最终路径是一条s到t的直线。 归纳法: n = 2的时候,直接s到t的路径得到最优解; n = 3的时候,枚举能插入的位置,可以得到最优解; ... n = k的时候,在n=k-1形成的s到t链上,枚举能插入的位置,得到最优解。

假设插入的位置是i,那么n=k-1的链会分解成几段:s到i,NEXT[i]到t,i到k,k到NEXT[i],其中 s到i 、 NEXT[i]到t 的距离不变。 那么当 cost(i, k) + cost(k, NEXT[i]) - cost(i, NEXT[i]) 最小时,i就是插入的最优解。

证明的关键点:当n=k插入的时候,点k不会对s到i、NEXT[i]到t 的路径造成影响。

证明实际存在缺陷,目前还未完善证明,这个做法实则是贪心。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

单表代替密码原理及算法实现

    要了解单表替代密码就得先了解替代密码,在这里我就做一下简单的介绍:       替代是古典密码中用到的最基本的处理技巧之一 。       替代密码是指...

57860
来自专栏云霄雨霁

算法设计策略----分治法

17300
来自专栏数说工作室

统计师的Python日记【第3天:Numpy你好】

本文是【统计师的Python日记】第3天的日记 回顾一下,第1天学习了Python的基本页面、操作,以及几种主要的容器类型;第2天学习了python的函数、循环...

487120
来自专栏企鹅号快讯

拒绝加班!工作中必会的15个excel函数

有人会说,现在网上excel技巧太多,一眼看过去感觉各个都好牛逼,恨不得全部收藏起来。可是,能真正能用到的时候并不多,因为学习的知识都太散了,也不能及时进行总结...

59650
来自专栏绿巨人专栏

Modern Algebra 读书笔记

37250
来自专栏前端儿

九九乘法表

小时候学过的九九乘法表也许将会扎根于我们一生的记忆,现在让我们重温那些温暖的记忆,请编程输出九九乘法表.

24110
来自专栏清墨_iOS分享

OpenGLES绘制立体多边形加纹理

前面写了OpenGLES的入门篇,一些朋友觉得还不错,找到我问了一些知识,这次我有针对性的写下这篇文章,也为我OpenGLES进阶篇做个开始。 我已认证微信,感...

488120
来自专栏WOLFRAM

九宫格数独游戏

26080
来自专栏数据科学与人工智能

【Python环境】Python自然语言处理系列(1)

一:python基础,自然语言概念 from nltk.book import* 1,text1.concordance("monstrous") 用语...

336100
来自专栏数说工作室

【SAS Says】基础篇:复制、堆叠、合并数据

特别说明:本节【SAS Says】基础篇:复制、堆叠、合并数据,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好...

1.3K50

扫码关注云+社区

领取腾讯云代金券