当前位置：网站首页>最长子串（长沙理工大学第十一届程序设计竞赛离线做了n天.....崩溃了）

最长子串（长沙理工大学第十一届程序设计竞赛离线做了n天.....崩溃了）

2022-08-08 18:34:00 【51CTO】

最长子串

Time Limit : 4000/2000ms (Java/Other) Memory Limit : 65535/65535K (Java/Other)

Total Submission(s) : 27 Accepted Submission(s) : 4

Times New Roman | Verdana | Georgia

← →

Problem Description

小E最近开始研究数列，于是小J就给他出了一道题目：给你一个长度为n的数列A（下标从1开始），然后在给你m个询问，有两种询问
第一种输入1 x 找到数列的一个最长连续子串，使得这个连续子串的里面的每个数都大于等于x。
第二种输入2 x y 把数列中x的位置的值修改为y。(对于第二种询问次数不会超过10)
对于每个询问1输出最长连续子串的长度。
子串的含义是数列中一段连续的数。
其中 1< n <= 100000 1 < m <= 10000 0 <= Ai <= 100000

Input

多组输入，每组数据第一行为n m,表示数列的长度和询问的次数
接下来m行，表示m次询问，只有2种格式，详细见描述

Output

如果询问的类型为查询，则输出一行，表示最长连续子串的长度
如果询问的类型为修改，则无需输出

Sample Input

Sample Output

Statistic | Submit | Back

这道题我做了n天啊。。

在acm群里面问有人说for循环也有人说线段树也有人动态规划。。。等等

唉前两种早就用过了那么简单的话我也不好意思问啊

在csdn博客里面问结果发现都是机器人回答的回答的是最长公共子序列我都醉了可能是看题目是最长子串吧

在百度上问由于没有积分无人问津

在qq问问上也没有人回答

最后在acm贴吧里面问的

吧主回复了一句

acdream群今天讨论过
当成10个test做
用并查集从大到小合并，离线做。

给了我很大启发，于是终于ac了唉

题解：

从所给的数列从下标i=0开始分别向左向右查找大于或等于a[i]的个数n 记为count[i]=n

如果a[i+1]>a[i] 只向右查找大于等于a[i+1]的个数n,count[i]=n

如果a[i+1]=a[i] ，count[i+1]=count[i]

如果a[i+1]<a[i]，分别向左向右查找大于或等于a[i]的个数n 记为count[i]=n

然后用一个数组存贮当前值得子序列个数 result[a[i]]=getMax(result[a[i]],coun[i]);

最后对result数组进行处理你该问为什么处理了因为当我们这样查找的时候如果count[5]<count[6] 我们要是查找1 5 输出count[5]就打错特错了

因为6>5 啊懂了吧

看代码吧累死了。。

       
       #include <stdio.h>
       
       #include <string.h>
       
       #include <algorithm>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       coun[
       
       100000
       
       +
       
       10];
       
       int 
       
       a[
       
       100000
       
       +
       
       10];
       
       int 
       
       result[
       
       100000
       
       +
       
       10];
       
       int 
       
       n,
       
       m;
       
       int 
       
       allMax;
       
       int 
       
       getMax(
       
       int 
       
       x,
       
       int 
       
       y)
       
{
       
       return 
       
       x
       
       >
       
       y
       
       ?
       
       x:
       
       y;
       
}
       
       //得出i右侧>=a【i】的个数 
       
       int 
       
       getRightCount(
       
       int 
       
       pos,
       
       int 
       
       i)
       
{
       
       int 
       
       right
       
       =
       
       0;
       
       while(
       
       pos
       
       <
       
       n)
       
  {
       
       pos
       
       ++;
       
       if(
       
       a[
       
       pos]
       
       >=
       
       a[
       
       i])
       
       right
       
       ++;
       
       else
       
       break;
       
  }
       
       return 
       
       right;
       
}
       
       //得出i左侧>=a【i】的个数 
       
       int 
       
       getLeftCount(
       
       int 
       
       pos,
       
       int 
       
       i)
       
{
       
       int 
       
       left
       
       =
       
       0;
       
       while(
       
       pos
       
       >=
       
       0)
       
  {
       
       pos
       
       --;
       
       if(
       
       a[
       
       pos]
       
       >=
       
       a[
       
       i])
       
       left
       
       ++;
       
       else
       
       break;
       
  }
       
       return 
       
       left;
       
}
       
       //对count数组进行处理 
       
       void 
       
       manage()
       
{
       
       int 
       
       Max
       
       =
       
       result[
       
       allMax];
       
       for(
       
       int 
       
       i
       
       =
       
       allMax;
       
       i
       
       >=
       
       0;
       
       i
       
       --)
       
  {
       
       result[
       
       i]
       
       =
       
       max(
       
       result[
       
       i],
       
       Max);
       
       Max
       
       =
       
       result[
       
       i];
       
  }
       
}
       
       //求count[i] 
       
       void 
       
       init()
       
{
       
       memset(
       
       coun,
       
       0,
       
       sizeof(
       
       coun));
       
       memset(
       
       result,
       
       0,
       
       sizeof(
       
       result));
       
       result[
       
       0]
       
       =
       
       n;
       
       allMax
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
    {
       
       if(
       
       allMax
       
       <
       
       a[
       
       i])
       
       allMax
       
       =
       
       a[
       
       i];
       
       if(
       
       i
       
       ==
       
       0)
       
      {
       
       coun[
       
       i]
       
       =
       
       getRightCount(
       
       i,
       
       i)
       
       +
       
       1;
       
      }
       
       else 
       
       if(
       
       a[
       
       i]
       
       ==
       
       a[
       
       i
       
       -
       
       1])
       
      {
       
       coun[
       
       i]
       
       =
       
       coun[
       
       i
       
       -
       
       1];
       
      }
       
       else 
       
       if(
       
       a[
       
       i]
       
       >
       
       a[
       
       i
       
       -
       
       1])
       
      {
       
       coun[
       
       i]
       
       =
       
       getRightCount(
       
       i,
       
       i)
       
       +
       
       1;
       
      }
       
       else 
       
       if(
       
       a[
       
       i]
       
       <
       
       a[
       
       i
       
       -
       
       1])
       
      {
       
       coun[
       
       i]
       
       =
       
       getRightCount(
       
       i,
       
       i)
       
       +
       
       getLeftCount(
       
       i,
       
       i)
       
       +
       
       1;
       
      }
       
       result[
       
       a[
       
       i]]
       
       =
       
       getMax(
       
       result[
       
       a[
       
       i]],
       
       coun[
       
       i]);
       
    }
       
       manage();
       
}
       
       int 
       
       main()
       
{
       
       while(
       
       ~scanf(
       
       "%d %d",
       
       &
       
       n,
       
       &
       
       m))
       
  {
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
       scanf(
       
       "%d",
       
       &
       
       a[
       
       i]);
       
       init();
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       m;
       
       i
       
       ++)
       
    {
       
       int 
       
       x;
       
       scanf(
       
       "%d",
       
       &
       
       x);
       
       if(
       
       x
       
       ==
       
       1)
       
      {
       
       int 
       
       y;
       
       scanf(
       
       "%d",
       
       &
       
       y);
       
       printf(
       
       "%d\n",
       
       result[
       
       y]);
       
      }
       
       if(
       
       x
       
       ==
       
       2)
       
      {
       
       int 
       
       pos,
       
       x;
       
       scanf(
       
       "%d %d",
       
       &
       
       pos,
       
       &
       
       x);
       
       a[
       
       pos
       
       -
       
       1]
       
       =
       
       x;
       
       init();
       
      }
       
    }
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.