[CF286C] Main Sequence
2024-09-27 04:01:05
问题描述
定义幸运数列:
空数列是幸运数列
如果 S 是幸运数列,那么 {r, S, -r} 也是幸运数列 (r > 0)
如果 S 和 T 都是幸运数列,那么 {S, T} 也是幸运数列
给定一个幸运数列中每个数的绝对值,并且要求其中的一些数是负数,其他的可正可负。
问是否有合法方案,如果有,给出任意一种方案。 N ≤ 10^6
幸运数列例子:{1, 2, -2, -1, 1, -1, 1, -1}
输入:1 1 1 1 要求第三个数是负数 输出: 1 1 -1 -1
样例输入
2
1 1
0
样例输出
YES
1 -1
解析
可以比较容易的看出来这是一个括号序列的形式。如果将正数视为左括号,负数视为右括号,那么给定一些数为负数就说明钦定了一些右括号,需要判断是否有满足要求的左括号。为了限定右括号,我们从右往左扫一遍,如果栈顶元素不等于当前元素或当前元素被指定为负数,就将元素入栈并标记为负数;否则弹出栈顶元素。最后如果栈不为空,说明无解;否则输出答案。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
int n,m,i,a[N],q[N],s[N],top;
bool f[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
signed main()
{
n=read();
for(i=1;i<=n;i++) a[i]=read();
m=read();
for(i=1;i<=m;i++){
q[i]=read();
f[q[i]]=1;
}
for(i=n;i>=1;i--){
if(s[top]!=a[i]||f[i]) s[++top]=a[i],f[i]=1;
else top--;
}
if(top){
puts("NO");
return 0;
}
puts("YES");
for(i=1;i<=n;i++){
if(f[i]) printf("%lld ",-a[i]);
else printf("%lld ",a[i]);
}
puts("");
return 0;
}
反思
若将原序列视为括号序列,则给定哪些数是负数就相当于钦定了一些右括号的位置。所以从右往左会比从左往右少写很多东西。还是要注意想好之后能否简化代码的写法,否则有可能会带来非常多的麻烦。
最新文章
- Microsoft Visual Studio 2015 下载、注册、安装过程、功能列表、问题解决
- 事件(event),正则
- Shell脚本8种字符串截取方法总结
- Putty 工具 保存配置的 小技巧
- ffmpeg参数解释
- Hibernate逍遥游记-第10章 映射继承关系-002继承关系树中的根类对应一个表(discriminator、subclass)
- 关于MySql中使用IFNULL()函数失效的问题。
- asp.net Global.asax 不运行解决
- ssh 连接不上报Connection closed by remote host
- [Swift]LeetCode54. 螺旋矩阵 | Spiral Matrix
- Mybatis与JDBC批量插入MySQL数据库性能测试及解决方案
- window无法启动mongodb服务:系统找不到指定的文件错误的解决方法
- Delphi操作Ini文件
- JAVA基础编程50题(4-6题)具体解释
- Linux安装ElasticSearch-2.2.0
- logrotate 日志轮询(转存)
- 无法将 lambda 表达式 转换为类型“System.Delegate”,因为它不是委托类型
- show_space查看对象空间使用情况
- HDU 4763 Theme Section(KMP+枚举公共前后缀)
- ROS:消息发布器和订阅器(c++)