注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

20090720做的题  

2009-07-20 13:57:15|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

去括号

brackets

 

问题描述

 

     Luna进了中学之后,学到了代数表达式,但是表达式中总是会出现很多让人烦恼的括号,而实际上,有很多括号是可以去除掉的。比如说a+(b+c)-d就可以把括号去除,变为a+b+c-d。而a-(b+a)+d可以去除括号后变为a-b-a+d

Luna对计算机编程很感兴趣,所以她想是不是可以用计算机来解决这个问题。你能帮助她完成这个任务吗? 

 

输入

        输入的第一行有一个整数N。表示总共有N个表达式需要处理。

接下来N行,每一行一个待处理的表达式,长度不超过255, 并且不含空格字符。表达式中的所有变量都是单个小写的英文字母, 运算符只有加+-*/。也就是说,在表达式中可能出现的字符为:a-z+-*/()。数据保证表达式合法。

另外不考虑'+' '-'用作正负号的情况,即输入表达式不会出现(+a)(-a)的情形。

 

输出:

对于每个表达式输出去除括号后的表达式。

 

说明

不需要对表达式进行化简:如果表达式为a-a,答案同表达式。不需要为了消去括号进行展开:如表达式为(a+b)*(c+d),答案同表达式。

更具体的,若表达式原先出现了m次变量,则输出时仍应保持m次变量,且不应改变这些变量的顺序。见样例。

        另外,保证不会出现空串的情形,既不会出现()

        保证表达式均合法。

 

样例输入

 

9

(a-a)

a+(b+c)-d

a-(b+a)+d

(a+b)*(c+d)

(a*b)+c/d
((a+b)*f)-(i/j)
a*(b/c)
a-(b+c+(d*a))
a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*(p-q)+r*(s*t)*(u-(v+(w*x))*y)+z

 

样例输出

 

a-a

a+b+c-d

a-b-a+d

(a+b)*(c+d)

a*b+c/d

(a+b)*f-i/j

a*b/c
a-b-c-d*a 
a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*(p-q)+r*s*t*(u-(v+w*x)*y)+z

 

数据约定

 

N10


计数问题

Count

 

【问题描述】

 

        一个n*m的方格,初始时每个格子有一个整数权值。接下来每次有2种操作:

               改变一个格子的权值;

               求一个子矩阵中某种特定权值出现的个数。

 

【输入文件】

 

        第一行有两个数N,M

        接下来N行,每行M个数,第i+1行第j个数表示格子(i,j)的初始权值。

        接下来输入一个整数Q

        之后Q行,每行描述一个操作。

操作1:“1 x y c”(不含双引号)。表示将格子(x,y)的权值改成c(1xn,1ym,1c100)

操作2:“2 x1 x2 y1 y2 c”(不含双引号,x1x2,y1y2)。表示询问所有满足格子颜色为c,且x1xx2,y1yy2的格子(x,y)的个数。

 

【输出文件】

 

对于每个操作2,按照他在输入中出现的顺序,依次输出一行一个整数表示所求得的个数。

 

【样例输入

 

3 3

1 2 3

3 2 1

2 1 3

3

2 1 2 1 2 1

1 2 3 2

2 2 3 2 3 2

 

【样例输出】

 

1

2

 

【数据约定】

 

30%的数据,满足:n,m30,Q50000

100%的数据,满足:n,m300,Q200000
旅行

travel

 

【问题描述】

 

河蟹国的道路特别有特点,每一条道路上都有许多景点供游客观赏,同时每条路要经过都要付一定的钱。而河蟹国的特点就是任意两个城市之间有切仅有一条简单路径,这样使游客旅行方便了许多。

XL准备在河蟹市进行一次旅行,他可以从任意一个城市出发,经过不重复的一些路径之后结束他的旅程。但是他带的钱有限,所以他希望知道在最好情况下自己最多能够得到多少欢乐值。

当然,这个欢乐值可能为0——没有任何一个他喜欢并且可以去的景点,所以他就世界回家看仙剑3去了。

 

【输入文件】

 

输入第一行三个整数N M K,分别表示河蟹国的城市数,道路数和XL身上所带的钱的数量。

接着有M行,每行4个整数Ai Bi COSTi VALi,分别表示第i-1条路径连接着AiBi两个城市,经过它需要付COSTi元钱并且得到VALi的欢乐值。

 

【输出文件】

 

      输出文件仅一行一个整数,表示XL在最好的情况下能够得到的欢乐值是多少。

 

【样例输入1

 

4 3 2

1 2 1 1

1 3 1 2

1 4 2 3

 

【样例输出1

 

    3

 

【样例输入2

 

4 3 3

1 2 1 1

1 3 1 2

1 4 2 3

 

【样例输出2

 

5

 

【数据约定】

 

对于30%的数据,满足N≤1000

对于100%的数据,满足N≤30000M≤30000*30000K≤10^9

对于100%的数据,满足0≤COSTi≤10000≤VALi≤1000


 


第一题:耐心题,需要耐心与毅力


第二题:数据结构...感谢c<=100,用100个二维树状数组搞定


如果c的范围太大...?

滚动数组!


第三题:听说暴搜加强剪枝可以过,而我懒了......只写了一个朴素

分治法是对的

可以用边/点分治

  评论这张
 
阅读(735)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017