专栏首页算法修养CodeForces #549 Div.2 ELynyrd Skynyrd

CodeForces #549 Div.2 ELynyrd Skynyrd

题目

这道题目实际上可以用动态规划来做。

对于每个区间,我们从右边边界,往左边走,如果能走n-1次,那说明以右边边界为起点存在一个题目中说的子链。

利用倍增算法,实际上倍增也是动态规划。f[i][j] 表示以i为结尾,能够往前走 2^j 次所到达的位置。

最后就是寻找以每个点为右边边界,往前走,能走到n-1次的,并且走的距离最近的的那点,那么在这个点的左边都是满足条件的,在这个点的右边都是不满足条件的。

AC代码

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

#define N 200000
int n,m,q;
int f[N+5][20];
int pre[N+5];
int p[N+5];
int a[N+5];
int last[N+5];
int res[N+5];


int find(int x,int i)
{
    if(x==0)
        return i;
    int j=0;
    while(1)
    {
        if((int)pow(2.0,j)>x)
            break;
        else
            j++;
    }
    if(f[i][j-1]!=0) {

        x -= (int) pow(2.0, j - 1);
        return find(x, f[i][j - 1]);
    } else
        return -1;
}

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

    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i]);
        if(i!=0)
            pre[p[i]]=p[i-1];
    }
    pre[p[0]]=p[n-1];
    memset(last,0,sizeof(last));
    memset(f,0,sizeof(f));
    memset(res,-1,sizeof(res));
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        last[a[i]]=i;
        f[i][0] = last[pre[a[i]]];
        for(int j=1;j<20;j++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=m;i++)
    {
        int x=find(n-1,i);
        res[i]=max(res[i-1],x);
    }

    int l,r;
    for(int i=0;i<q;i++)
    {
        scanf("%d%d",&l,&r);
        if(l<=res[r])
            printf("1");
        else
            printf("0");
    }
    printf("\n");


    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 132 Palindrome Partitioning II

    ShenduCC
  • HDU 5157 Harry and magic string(回文树)

    Harry and magic string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: ...

    ShenduCC
  • LeetCode 201. Bitwise AND of Numbers Range(位运算)

    题意:给你两个数n,m 0<= n<=m <=2^31-1 ,让你计算从n到m的每个数依次位与的结果。

    ShenduCC
  • 蓝桥杯 基础练习 杨辉三角形

    输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出,中间使用一个空格分隔。请不要在前面输出多余的空格。

    Debug客栈
  • Codeforces Round #535 (Div. 3) B. Divisors of Two Integers(思维)

    题目链接:http://codeforces.com/contest/1108/problem/B

    Ch_Zaqdt
  • P1036 选数

    用户7727433
  • 最快最简单的排序---桶排序

    是不是很好理解,就是开一个比最大数据大或者等于的一个数组,然后相应的桶遇到数就++,最后输出就行了。

    用户7727433
  • AtCoder Beginner Contest 177 A ~ E

    C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:

    用户7727433
  • 2491 玉蟾宫

    2491 玉蟾宫 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 大师 Master 题目描述 Description   有一天...

    attack
  • BUPT2017 wintertraining(15) #2 题解

    ​ 因为2520%pre_lcm0,所以x%pre_lcm(x%2520)%pre_lcm

    饶文津

扫码关注云+社区

领取腾讯云代金券