专栏首页owent不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

在某个神奇的下午,收到一个垃圾邮件(至少被邮件系统当成了垃圾邮件)。

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

果然好久没碰算法,脑子是会生锈的。

第一题大水,懒得写。

第二题伤了很久的脑筋,想出了一个算法结果ultramanhu基于此想出了个更容易理解更容易实现的方法。

以我这种懒人的本性,必须是也懒得写得。

于是意思意思就干上了第三题。题目见这里 http://wenda60.com/programs/view/id-550.html

不得不说,现在不如从前,想出这题的解法还是费了一点时间的。不过这个题目太厚道了,能有的trick在sample里都有了。

这个题是问最少改多少个数字能让输入的数字递增,并且第一个数字不小于1。

很显然一个增子序列嘛。但是又有一点点地不同,应为最终是修改数字,而且数字不能重的,所以增子序列里两个相邻的值还和这两个数之间的数字个数有关。

就是这两个值的相差必须大于之间的数字个数。这里很容易就想到给最长增子序列变种,判断因素加上距离权值;

第二个条件是第一个值必须大于等于1。我想到的简单地做法是,在序列前面加一个0。轻松加愉快啊。

但是最长增子序列的算法是会重定向最佳值的,所以在执行检测的时候注意子序列一定要选0就OK了。

上代码:

#include <cstdio>
#include <iostream>

typedef int LISTYPE;

#define LISMAXN 100005

LISTYPE lR[LISMAXN];

int LIScmp(int a, int b, LISTYPE list[])
{
    return list[a] + b - a <= list[b];
}

int LISLength(LISTYPE list[], int n)
{
    int length = 1;
    
    lR[0] = 0;

    for (int i = 1; i < n; i++)
    {
        //二分查找,复杂度 log(n)
        int b, e, m;
        b = 0;
        e = length - 1;
        while (b <= e && e >= 0)
        {
            m = (b + e) / 2;
            if (LIScmp(lR[m], i, list))
                b = m + 1;
            else
                e = m - 1;
        }

        if (0 == b) 
            continue;

        lR[b] = i;
        if (b >= length)
            length++;
    }
    return length;
}

LISTYPE LOri[LISMAXN];

int main() {
    int n;
    scanf("%d", &n);

    while (n-- > 0){
        int size;
        scanf("%d", &size);
        LOri[0] = 0;
        for (int i = 1; i <= size; ++i){
            scanf("%d", &LOri[i]);
        }

        printf("%d\n", size + 1 - LISLength(LOri, size + 1));
    }
    return 0;
}

不知道为什么,这个代码上去以后显示PE,我也不知道PE在哪了。(我试了各种乱加减空格和换行,都木有用,全PE。故意写错一个数,就变WA了,所以应该真的是PE) 不过反正结果对了后面就懒得再研究了,反正现在又不参赛

PS: 最长增子序列用得是以前写得模板:https://www.owent.net/2009/74.html

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数论模板(个人模板)

    若a与n互质(即GCD(a,n) = 1),则a^Ψ(n) = 1 (mod n)a^{\varphi(n)} \equiv 1 \pmod n

    owent
  • 线段树相关问题 (引用 PKU POJ题目) 整理

    如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

    owent
  • 2011 Google Code Jam 小记

    好久没写这种类型的代码,感觉真是退步了很多。 这是我第一次参加Google Code Jam,以前有过报名可是没有做过。 我发现Google Code Ja...

    owent
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • Day5下午解题报告1

    预计分数:100+60+30=190 实际分数:100+60+30=190 终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈...

    attack
  • 1038 统计同成绩学生 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051
  • 1250 Fibonacci数列

    时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 定义:f0=...

    attack
  • 15.瀑布流、测量

    六月的雨

扫码关注云+社区

领取腾讯云代金券