开发者社区> 技术小哥哥> 正文

POJ1068 Parencodings【用一个int变量作为栈】

简介:
+关注继续查看

 

Problem:1068   User: qq1203456195
Memory: 164K   Time: 0MS
Language: C   Result: Accepted

开始没读明白题的意思【鄙人英文太烂】,百度了题意,刚接触算法时间不长,没啥好想法,就想先根据q序列把()序列还原,然后再推w序列。

用了一个中午的时间把q序列还原成()了,然后就是推w序列。

既然是运算符匹配,肯定是栈了。又不想弄一个栈出来,怎么办呢?突然想到用一个变量就可以了,因为序列中只有(和非(两种情况,只要两类字符的数目抵消就是匹配完了。

复制代码
#include <stdio.h>
#include <string.h>
int main()
{
    int n,i,k,m,d,q,p,r,tk;
    char c[41];
    scanf("%d",&n);//n个case
    while (n--)
    {
        //构造()序列
        scanf("%d",&k);//q序列中k个元素

        memset(c,'(',sizeof(c));
        d=0;//(的数量
        q=0;//栈
        tk=k;//temp_k
        scanf("%d",&m);//q中的元素
        tk--;//读取一个就记录一个        
        for (i=0;i<2*k;i++)
        {
            if(d==m && c[i]=='(')//匹配
            {//确定Wi
                q=r=1;
                p=i-1;
                while(q&&p>=0)
                {
                    if (c[p]=='(')    
                        q--;//出栈
                    else
                    {
                        q++;//入栈
                        r++;//)的数量
                    }
                    p--;                    
                }
                c[i]=r+48;
                if(tk--)//读一个q中的元素
                    scanf("%d",&m);
            }
            if(c[i]=='(')
                d++;//统计(的数量                    
        }
        for (i=0;i<2*k-1;i++)
        {
            if(c[i]!='(')
                printf("%d ",c[i]-48);
        }
        printf("%d\n",c[i]-48);
    }
    return 1;
}
复制代码

 


本文转自ZH奶酪博客园博客,原文链接:http://www.cnblogs.com/CheeseZH/archive/2012/04/13/2446236.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
18251 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
13666 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
23610 0
print_r-打印关于变量的易于理解的信息
print_r - 打印关于变量的易于理解的信息。 bool print_r ( mixed $expression [, bool $return ] ) Note: 参数 return 是在 PHP 4.3.0 的时候加上的 print_r() 显示关于一个变量的易于理解的信息。
759 0
设以下变量均为int类型,则值不等于7的表达式是
设以下变量均为int类型,则值不等于7的表达式是
7 0
IntelliJ IDEA 中看到 classes, sources, javadocs 三种jar的区别和各自的作用
在 intelliJ idea 里面看到 ,Project Structure——》 Libraries ——》 Sources 的路径是红色的 看图会比较好。以guava包为例来说明。 可以看到在这看整个maven项目的依赖时,发现如图的情况,这红色是什么情况,是报错吗?需要处理吗?这3个不同jar都是什么东西,各自有啥作用。
3944 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
13831 0
浅谈C# 匿名变量
每次写博客,第一句话都是这样的:程序员很苦逼,除了会写程序,还得会写博客!当然,希望将来的一天,某位老板看到此博客,给你的程序员职工加点薪资吧!因为程序员的世界除了苦逼就是沉默。我眼中的程序员大多都不爱说话,默默承受着编程的巨大压力,除了技术上的交流外,他们不愿意也不擅长和别人交流,更不乐意任何人走...
852 0
Linux Ubuntu jdk(环境变量)配置
一、下载JDK - jdk版本建议是gz形式的,rpm是RedHat里面的命令,所以下载rpm格式的时候回遇到问题 二、 打开虚拟机,创建目录 1 创建目录 #mkdir home 2 转到该目录下 cd home 3 输入rz,选择下载好的.
855 0
2010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载