CF1324B
感觉 \(O(tn^2)\) 不是正解,于是弱弱的发了一波 \(O(tn)\) 。
题意描述
你谷还没有人翻译,这里就简单介绍一下。
给你一个长为 \(n\) 的序列,如果它的一个长度至少为 \(3\) 的子集可以构成回文,
回答 \(YES\) ,否则回答 \(NO\) 。(题目有多组数据)
题目 传送门。
算法分析
简化题意
首先本题要求找到一个长度至少为3的回文子串,显然可以将题目转化为:
找到一个长度为 3 的回文子串。
- 如果原回文子串的长度为奇数,显然可以删除两边的数字,使其长度减少为 \(3\) 。
- 如果原回文子串的长度为偶数,可以删除中间两个字符中的一个,使其变为奇数,再重复上述步骤。
举个栗子:
- 奇数:\(1234321 ->343\)。
- 偶数:\(123321->12321->232\)。
所以得出结论:如果一个序列符合要求,它必然有一个长度为3的回文子串。
朴素算法
得到上述结论之后,我们很容易想到一个朴素做法:
枚举其中间节点,向两边延伸,看有没有相同的数字。
但是显然,这个做法的时间是 \(O(tn^2)\) 的,大数据下是跑不过去的。
所以我们需要一点优化。
时间优化
排除冗余操作
假设我们从左往右推导,已经到了第 \(i\) 个(其中第 \(1-(i-1)\) 中没有符合条件的节点)
显然,在朴素算法中,我们需要将 \(1\)~\((i-1)\) 一一与右边 \((i+1)\)~\(n\) 比较,但是这是没有必要的。
首先显然第 \(i-2\) 个节点在进行到第 \(i-1\) 节点是就已经与右边进行了比较。
同理第 \(i-2\)~\(1\) 个节点早已进行过比较了,且比较不成功,所以再比较是重复而无用的。
所以得出结论:
进行到第 \(i\) 个节点时,只需要比较第 \(i-1\) 个节点与右边数值的大小即可。
可惜这并没有优化多少,所以最重要的优化就来了 (尖叫声)。
改变处理顺序
记 \(vis[i]\) 表示 \((i+2)\)~\(n\) 中有没有与 \(i\) 相同的数。(注意这里不是 i+1,因为 i+1 是中间节点)
这个 \(i+2\) 开始如果没有看懂的话也没有关系,记住就可以了,下文会给出详细讲解。
因为 \(vis[i]\) 的值仅与 \((i+2)\)~\(n\) 有关,所以不妨从后往前进行处理。(想一想为什么)
每次处理时,查看 \(vis[i]\) 的值,如果 \(vis[i]==1\) ,说明前面有与之相同的数值,于是果断return true
。
否则将 \(vis[i+2]=true\) ,继续处理下一个数。
至此,本题得到完美解决。
手玩样例说明
这里仅仅准备给那些上面没看懂的同学们,如果说你看懂了上面的全部,你可以去打代码了。
这里沿用样例二和样例五以及一个自编样例来展开说明。
样例二
5
1 2 2 3 2
从后往前枚举(从 \(n-2\) 开始即可,想一想为什么)。
- 第 \(n-2\) 位,\(dis[a[n]]=true\)(即 \(dis[2]=true\)),发现 \(dis[a[n-2]]==true\),果断
return true
。 - 第 \(n-3\) 位,\(dis[a[n-1]]=true\)(即 \(dis[3]=true\)),发现 \(dis[a[n-3]]==true\),果断
return true
。 - 第 \(n-4\) 位,\(dis[a[n-2]]=true\) (即 \(dis[2]=true\)),发现 \(dis[a[n-4]]==false\),结束操作。
所以答案为 \(YES\)。
其实在第一次操作时便可以结束了,但是为了让读者理解,硬是做下去了**。
样例五
10
1 1 2 2 3 3 4 4 5 5
- 第 \(n-2\) 位,\(dis[a[n]]=true\)(即 \(dis[5]=true\)),发现 \(dis[a[n-2]]==false\),去下一位。
- 第 \(n-3\) 位,\(dis[a[n-1]]=true\)(即 \(dis[5]=true\)),发现 \(dis[a[n-3]]==false\),去下一位。
- 第 \(n-4\) 位,\(dis[a[n-2]]=true\) (即 \(dis[4]=true\)),发现 \(dis[a[n-4]]==false\),去下一位。
- ......
- 第 \(1\) 位,\(dis[a[3]]=true\) (即 \(dis[2]=true\)),发现 \(dis[a[1]]==false\),结束操作。
所以答案为 \(NO\)。
这里让我们回忆刚才的疑问:从 \(i+2\) 开始比较。从这里可以看出,如果从 \(i+1\) 开始,答案为 \(YES\)。
因为如果 \(a[i]==a[i+1]\) ,只能得到两个相邻的数相邻,而不能得到一个回文子串。
自编样例
9
1 3 7 5 8 0 2 5 9
- 第 \(n-2\) 位,\(dis[a[n]]=true\)(即 \(dis[9]=true\)),发现 \(dis[a[n-2]]==false\),去下一位。
- 第 \(n-3\) 位,\(dis[a[n-1]]=true\)(即 \(dis[5]=true\)),发现 \(dis[a[n-3]]==false\),去下一位。
- 第 \(n-4\) 位,\(dis[a[n-2]]=true\) (即 \(dis[2]=true\)),发现 \(dis[a[n-4]]==false\),去下一位。
- 第 \(n-5\) 位,\(dis[a[n-3]]=true\)(即 \(dis[0]=true\)),发现 \(dis[a[n-5]]==true\),操作结束。
所以答案为 \(YES\)。
请读者自行理解,这是正常操作。
代码实现
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#define N 5010
using namespace std;
int n,T,a[N];
bool flag,vis[N];
int main(){
scanf("%d",&T);
while(T--){
memset(vis,false,sizeof(vis));
flag=false;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=n-2;i>=1;i--){
vis[a[i+2]]=true;//一定要先赋值
if(vis[a[i]]){
printf("YES\n");
flag=true;
break;
}
}
if(!flag) printf("NO\n");
}
return 0;
}
码量很小,简单易懂吧。
结语
学 \(OI\) 一定要具备将复杂问题简单化的能力,同时也要多做题,积累优化思路。
如果这篇文章对你有帮助,你懂的。
完结撒花。
最新文章
- Codeforces 549G Happy Line[问题转换 sort]
- opencv笔记3:trackbar简单使用
- iOS字体设置
- CSS现代字体栈
- [原创] 对于深度学习(deep learning)在工业界的应用现状和突破 [by matthewbai]
- vb安装过程中 ntvdm.exe[9696]中发生未处理的win32异常
- Android 开发中常用小技巧
- linux中如何修改文件夹的用户权限 chown命令
- IIS7.5应用程序池集成模式和经典模式的区别介绍
- [Oracle] UNIX与Windows 2000上Oracle的差异(III)
- JavaWeb学习笔记三 Servlet
- 为什么char *name=";it";,printf(";%s";,name) 能够输出字符串?
- python模块(4)
- Qt Widgets——菜单和菜单栏
- [2018-12-15] Hello World!
- IEnumerable和IQueryable的区别以及背后的ExpressionTree表达式树
- windows上使用logstash-input-jdbc
- Java实现心跳机制
- 【刷题】BZOJ 2346 [Baltic 2011]Lamp
- Oracle行转列SQL