首页 > 代码库 > CF#FF(255)-div1-C【水题，枚举】

CF#FF(255)-div1-C【水题，枚举】

2024-07-12 01:47:06   220人阅读

【吐槽】：本来没打算写这题的题解的，但惨不忍睹得WA了13次，想想还是记录一下吧。自己的“分类讨论能力”本来就很差。

刚开始第一眼扫过去以为是LIS，然后忽略了复杂度，果断TLE了，说起来也好惭愧，也说明有时候太懒得动脑了，总是习惯利用惯性思维，这不是一件好事。

【题意】：给你大小为n的整型数组a[n]，求这数组的一个子串，其中最多可以修改子串中的一个数字，使得到的子串是最长的严格递增的子串，输出该子串的长度 L。

【思路】：O（n）复杂度，枚举断点情况。第0个和第n个位置默认为断点。(用ve[i]表示第 i 个断点在a[n]中的下标位置)

1、断点 ve[i] 可更改，即断点两端数的差值大于1时，L 为前一个断点到后一个断点的距离，即 L = ve[i+1]-ve[i-1]。

2、断点 ve[i] 不可更改，则这里又分两种情况：①由于从断点开始左右两侧分别是严格递增的，所以如果 a[ve[i]] - a[ve[i]-2] > 1，则表示 a[ve[i]-1] 可修改，

　　　　　　　　　　　　　　　　　　　　　　使得断点前后两段可以结合，L = ve[i+1]-ve[i-1]。

　　　　　　　　　　　　　　　　　　　　　 ②如果不满足①的情况，则取 ve[i]-ve[i-1] 和 ve[i+1]-ve[i] 中的较大值。

 

下面是AC代码：

代码下是测试数据

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6  7 #define maxn 100006 8 int ant[maxn]; 9 int main()10 {11    int n;12    while(scanf("%d", &n) != EOF){13       vector<int> ve; ve.push_back(0);14       scanf("%d", &ant[0]);15       for(int i = 1; i < n; i++){16          scanf("%d", &ant[i]);17          if(ant[i]-ant[i-1] <= 0) { ve.push_back(i);}18       }19       ant[n] = -1;20       ve.push_back(n);21 22       int l = ve.size();23       int m, res = -1;24 25       if(l > 2)26          for(int i = 1; i < l-1; i++){27             if(ant[ve[i]+1] - ant[ve[i]-1] > 1){28                m = ve[i+1] - ve[i-1];29             }30             else if(ve[i-1] != ve[i]-1){31                if(ve[i] > 1&&ant[ve[i]]-ant[ve[i]-2] > 1) m = ve[i+1]-ve[i-1];32                else if(ve[i]-ve[i-1] > ve[i+1]-ve[i]) m = ve[i]-ve[i-1]+1;33                else m = ve[i+1]-ve[i]+1;34             }35             else { m = ve[i+1]-ve[i-1];}36 37             if(m > res) res = m;38          }39       else res = n;40 41       printf("%d\n", res);42    }43 }44 /*45 input:46 1147 7 2 6 4 3 1 8 10 24 31 2548 649 7 2 3 1 5 650 951 1 3 3 4 4 5 5 6 652 553 1 3 2 5 454 1155 7 2 6 4 3 3 8 10 24 31 2556 1057 1 3 2 2 4 6 9 3 7 258 5059 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764 967513927 365180541 540383427 304089173 303455737 35005212 521595369 294702568 726956430 336465783 861021531 59961394 89018457 101513930 125898168 131176230 145174068 233665124 278722863 315634023 369133070 468703136 628175012 635723059 653377374 656478043 801979803 859484422 914544920 608413785 756898538 734575199 973594325 149798316 3866437160 1061 424238336 649760493 681692778 714636916 719885387 804289384 846930887 957747794 596516650 18964142262 1063 1 2 3 4 5 5 6 7 8 964 565 1 1 1 1 166 567 1 1 2 3 468 669 7 2 3 1 4 570 471 1 4 3 472 573 0 1 4 3 474 75 output:76 677 578 379 480 681 582 1983 984 685 286 587 488 489 590 */
View Code

 


联系
我们